acceptodds
Under review as a conference paper at ICLR 2027

Pollen: Single-server Sparse Secure Aggregation with Minimal Leakage

Abstract

Secure aggregation protects the values of client updates in federated learning but assumes dense model updates. This assumption misaligned with modern language models and recommendation system models, whose index embedding and parameter-efficient fine-tuning layers produce highly sparse updates. While recent works such as Meridian (S&P 2026) and Clover (CCS 2025) have proposed sparse secure aggregation protocols, they focus on non-colluding multiple-server setting only, and the privacy effects of sparse updates comparing to dense are still not well understood. In this paper, we identify a new leakage channel, termed client index structure leakage, arising from the co-occurrence structure of sparse updates. We show that under a positive distributional-gap assumption, any sparse aggregation protocol whose server view preserves per-client index co-occurrence information admits cross-round client re-identification attacks. Conversely, we show that revealing only the union of active input indices is sufficient, as this information is already derivable from the ideal functionality of dense secure aggregation. Together, these results characterize a minimal leakage profile for sparse secure aggregation. Guided by this characterization, we introduce a new primitive, labeled multiparty private set union (LMPSU) and present a lightweight single-server construction, Pollen, based on arithmetic invertible Bloom lookup tables and secure aggregation. Building on this primitive, we design a sparse secure aggregation protocol for sparse embedding updates. Experiments show that our approach eliminates re-identification attacks while achieving a communication savings compared to dense secure aggregation.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
federated learning, secure aggregation, sparse secure aggregation

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_83dZOpenReview ↗
Rating
2
Confidence
4
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

Pollen studies privacy leakage from the structure of sparse federated updates: even when update values are protected, per-client active-index sets can enable cross-round re-identification. This paper argues that revealing only the union of active indices and their summed updates is sufficient for sparse aggregation, then implements this output through a single-server, IBLT-based labeled private set union built on secure aggregation. Experiments test the linkage attack, communication and runtime, and learning loss on selected tasks.

Critical strengths
  1. The connection between a concrete index-based attack and a protocol designed to remove that attack surface, and the practical benefit of supporting sparse aggregation with one server and no large offline phase.
  2. It avoids the large offline communication required by the compared single-server sparse aggregation schemes.
  3. It identifies and measures a privacy risk that remains when gradient values are hidden but individual index sets are visible. Its randomized IBLT construction combines duplicate indices and their labels while concealing how many clients contributed each index.
Critical weaknesses
  1. A dense aggregate reveals the union only if active updates do not cancel to zero. The privacy comparison depends on this condition. The cancellation analysis assumes a distribution that is not established for the actual sum of clients’ quantized updates, and the 45 union-recovery trials provide limited evidence for rare failures at scale. This matters because union disclosure could otherwise reveal information unavailable from ideal dense aggregation.
  2. The paper does not clearly identify which sparsification setting produced Figure 4’s loss curves. Thus, the strongest saving is not yet paired with evidence of its learning-quality cost.
Questions for authors
  1. For the actual quantized client updates, how often does an active index cancel to zero in the aggregate, and what additional information does Pollen reveal if that happens?
  2. Which K/LK/L setting produced Figure 4? Are learning-quality results available for the 0.010.01 and 0.0010.001 settings responsible for Table 5’s largest savings?
  3. What concrete multi-round decoding-failure bound is supported by the chosen IBLT parameters, given the confidence bound on the zero-failure trials?
  4. Do the communication totals include secure-aggregation setup traffic and the model broadcast to clients, or do the reported savings concern client upload only?
1 comment
AuthorsOpenReview ↗

Rebuttal for Reviewer 83dZ

Cancellation measurements:

The 45 union-recovery trials establish recovery in the tested executions, rather than a negligible cancellation bound. Appendix F.1’s Gaussian assumptions and quantization order have not been established for the actual sum of quantized client updates. We present that calculation as conditional and retain an explicit honest-residual cancellation term in the end-to-end comparison. Measurements of total-aggregate recovery alone do not validate the condition under collusion.

Utility and communication scope:

In the updated version (Figure 4, p. 9; Section 5, p. 10; Appendix D.3, pp. 19–21, including Figure S1 on p. 21), we are identifying Figure 4’s exact sparsification configuration and restrict its utility conclusion to that setting. Figure 4 concerns only LMPSU applied on the embedding level without gradient sparsification effect, so K/L for the experiment stays at 1. We explicitly mention this in the updated manuscript. To evaluate the utility implications of additional sparsification, we add loss comparisons at (K/L=0.01) and (0.001) between Pollen and plaintext aggregation using identical sparsification and training settings. We also include the plaintext (K/L=1) reference. Comparing Pollen with plaintext under the same sparsification isolates any additional loss introduced by the aggregation protocol, while comparison with the (K/L=1) reference shows the effect of sparsification itself.

We agree that the largest communication savings should be interpreted alongside their learning-quality cost. We therefore distinguish communication-only benchmarks from configurations with measured utility results and restrict our utility claims accordingly. The reported per-client cost estimates exclude model broadcast and server downloads, while setup and recovery traffic are not fully counted by the fixed amortized control term. Table 5’s caption (p. 9) and Appendix D.4 (pp. 21–23) now state these accounting boundaries explicitly. The Pollen/Flamingo ratios compare payload-plus-control estimates; they are not measurements of end-to-end communication savings under a common SA backend.

Concrete decoding-failure bound:

The 45 union-recovery trials are separate from Table 6’s peeling experiments, which report 1,048,576 trials and zero observed peeling failures for each selected configuration.

For a configuration fixed before independent validation, this outcome would yield a one-sided 95% upper confidence bound of approximately 2.857 × 10⁻⁶ on the peeling-failure probability. Over 100 rounds, the union-bound contribution would be approximately 2.857 × 10⁻⁴, with Theorem 6’s algebraic failure terms added for each round.

The available records do not establish independent post-selection validation, so this calculation does not certify 95% coverage for the selected configurations. We now explicitly distinguish Table 6’s empirical point estimates from confidence upper bounds in Appendix C.1 (“Interpreting zero failures,” p. 17).

Reviewer_4MMxOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper is on secure aggregation with sparsification constraints. Conventional (dense) secure aggregation mechanisms aim to aggregate entire gradients by the clients, which are not very efficient in communication-constrained environments. Sparse secure aggregation protocols aim to incorporate gradient sparsification techniques to during secure aggregation to reduce the communication overhead of secure aggregation. The paper first proposes a new attack to show gradients can be recovered from the indices sent by the clients only (previous works demonstrated attacks that use both the indices and the corresponding gradient parameters, this work aims to improve upon that by using the indices only). Then a new sparse secure aggregation protocol have been proposed which claims to be more efficient than previous methods.

Critical strengths

The paper demonstrates performance evaluations across various models, and demonstrates improvements against multiple benchmarks.

Critical weaknesses
  • I think the paper needs a major rework to make the presentation publication ready. A lot of the technical notions are stated without actually describing what they mean or what they represent. The main body of the paper also relies extensively on the supplementary material to introduce the key notions, proofs, and overall technical arguments. In one place (Section 4.2, second paragraph) the paper even starts a sentence with "Recall that .." to refer to some entities (keysum, hashsum, count, valuesum) that are only defined at the Appendix. The paper should be self-contained, and the important technical notions should be explicitly defined in the main body. The reviewers are not required to read the appendix, and as importantly this severely breaks the flow.

  • In Section 2, it is not clearly defined what the embedding universe represents, and similarly what p_i and q_i represents. We are only told that each client produces an update by sampling s items independently from pi. It is not clear if these entities represent the data samples, or the values of the local gradient parameters or their sampled indices (e.g., for rand-k or top-k sparsification), or any other entity? If they correspond to the gradient parameters observed at different indicates, then the sampled items would be correlated, hence different samples would not be independent? If they correspond to the indices, why are the sampling probabilities pi and pj are different? And then several Lemma and Theorems are listed one after the other regarding these "embedding items" but without much intuition. And at the end we are told "As long as the server can observe each client’s active embedding item set, it can compare overlap patterns across rounds and re-identify clients with high probability.", but I am still not clear what is meant by an "active embedding set" of a client?

  • Section 3.1 starts with "The intuition behind the recoverability is clear: once the server aggregate all sparse weight update, it can deduce the union of active embedding by looking at the support indices with non-zero aggregated gradient." This is not clear to me.

  • Security and threat model: I am a little confused about the security claims in the paper. The paper consider a malicious server who can deviate from the protocol arbitrarily (page 3 threat model). But then why would the server follow the LMPSU protocol truthfully? In fact, the security guarantees (Section 4.1) seem to depend on the condition "Assuming the underlying LMPSU and the broadcast channel from server to client are secure against malicious server with corrupted clients, our sparse SA presented in Figure 6 realizes the sparse SA that provides input privacy against malicious server." What do we mean by LMPSU and broadcast channel being secure against a malicious server? How is this condition ensured? There seems to be a contradictory argument here, this looks more like an honest-but-curious server instead of malicious.

  • Experiments: Experiments leaves comparison against TinySA for foundation models, with the reasoning of their higher offline cost. On the other hand, I think there should be a comparison at least in the LoRA-setting (Table 4).

Questions for authors

Please see my comments above.

3 comments
AuthorsOpenReview ↗

Rebuttal for Reviewer 4MMx

Presentation Issue:

We are defining the IBLT fields before using them in Section 4.2: (K) sums randomized keys, (H) sums randomized fingerprints, (C) sums random masks, and (V) sums labels. A pure bucket contains one distinct item, possibly contributed by several clients; division by nonzero (C) is a finite-field operation. We also explain Section 3.1 directly: an aggregate’s nonzero blocks identify the union whenever the relevant active updates do not cancel. We refer to the attached revised manuscript (Section 4.2, pp. 7–8, for the IBLT definitions; Section 3.1, pp. 5–6, for union recoverability) as well as the latexdiff for the revised presentation.

Embedding Universe Definition:

The embedding universe (V) is the set of row identifiers, such as token IDs or recommendation-item IDs. Client (i)’s distribution (p_i) describes its local item-sampling profile, and (q_i) is the probability that two independent draws from that profile match. Profiles may differ because clients hold different local data. An active set contains the indices represented in the submitted sparse update. The independent-draw assumption concerns sampled indices; it does not assert independence of gradient coordinates or characterize arbitrary top-(k) selection. Our attack re-identifies updates across rounds using index information; it does not reconstruct numerical gradients from indices alone.

Threat Model clarification:

Our privacy claim is conditional on an actively secure SA instantiation; the server need not decode honestly. Honest-client interaction occurs through SA, and decoding is local post-processing of the authorized aggregate. This reduction is combined with the leakage characterization above. We do not assume the server to follow the protocol correctly.

Across rounds, consistent broadcast is a separate assumption, stated in Section 4.1 (p. 7). Appendix E (p. 23) describes a model commitment checked against an authenticated, globally consistent log or equivalent service; a model hash alone does not establish consistency. This infrastructure is assumed, and its cost is excluded from our performance evaluation. The guarantee permits abort and does not establish correctness against arbitrary corrupted contributions.

TinySA in the LoRA setting:

We agree that offline cost alone does not justify omitting this comparison. We added a representative analytical comparison for DistilBERT embedding-LoRA rank 16 (Appendix D.4, pp. 21–23; Table S1, p. 22). We specify participation, recovery, and collusion parameters and use a common field width. We report TinySA’s offline and online communication separately, alongside Pollen’s payload/control estimate. These are formula-derived communication estimates; no TinySA runtime was measured. We explicitly identify the differences in adversary assumptions and sparsification semantics, so this comparison does not establish an end-to-end benchmark under matched assumptions.

I thank the authors for the rebuttal. I am still confused by the threat model. So does the framework rely on an honest third party? Why were these costs excluded from the performance evaluation, especially since one of the core motivations of the work is that alternatives have high cost?

Thank you for giving us chance to clarify this in advance.

We would like to clarify that the threat model is inherit from Secure Aggregation, which does not rely on any honest third party and can guarantee input privacy against active malicious server. This is because the framework is built on a dense Secure Aggregation as a building block, and the dense Secure Aggregation is operating on the IBLT as input rather than the full model. This is important as the IBLT has size much smaller than the model size. The cost of this underlying dense Secure Aggregation is already included in our experiment result.

Hopefully this answers your concern.

Best, Authors

Reviewer_82VBOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper proposes Pollen, a single-server sparse secure aggregation protocol for federated learning. It analyzes cross-round client linkage from sparse update supports and characterizes union disclosure relative to ideal dense secure aggregation under a no-cancellation assumption. Its construction combines labeled multiparty private set union, randomized arithmetic IBLTs, and existing secure aggregation to recover active indices and summed gradients while aiming to hide individual support sets and item frequencies. Validation includes linkage attacks on four datasets, communication and runtime comparisons for embedding and LoRA updates, and training-loss comparisons on language and recommendation models. With additional top-k sparsification, the paper reports communication reductions of up to 2803× over dense secure aggregation.

Critical strengths
  1. An important privacy problem with empirical motivation. The paper examines information exposed by sparse update indices even when individual gradient values are protected. Its linkage experiments across four datasets illustrate why support privacy deserves attention alongside value privacy. This is consequential because sparse communication is increasingly relevant to large embedding models.

  2. A compact construction suited to single-server aggregation. Pollen combines randomized arithmetic IBLTs with existing secure aggregation, allowing communication to scale with the provisioned union capacity rather than the full embedding universe. This offers a promising way to exploit sparse updates within conventional federated learning architectures and gives the work potential practical value, provided its security guarantees are established.

Critical weaknesses
  1. The main linkage theorem does not match the stated observation model. Definition 1 uses collision counts that preserve sample multiplicities, whereas Definition 3 only guarantees access to deduplicated support sets. For two clients with distributions (0.9, 0.1) and (0.1, 0.9), the positive-gap assumption holds, but after 100 draws their supports are almost always identical. With uniformly anonymized supports, the two-round linkage error is at least approximately 0.499947, compared with Appendix F’s claimed bound of 0.000143. This invalidates Theorem 3 as stated and undermines the general necessity claim supporting the paper’s leakage characterization.

  2. The collusion-security proof requires information unavailable from the stated ideal output. A colluding server can subtract corrupted clients’ known IBLTs and recover the honest survivors’ union. That union is not generally determined by the total labeled union and corrupted states when honest contributions cancel. For example, fix the corrupted input as {(a,1),(b,1)} and honest inputs as {(a,1),(c,1)} and {(a,−1),(d,1)}. Replacing both honest occurrences of a with b leaves the ideal output unchanged, but changes the recoverable honest union. Thus, security of the underlying encoded-vector aggregation does not establish the claimed LMPSU realization. Theorem 9 explicitly assumes honest-residual non-cancellation, but this restriction is not established throughout the end-to-end guarantees. This leaves a central privacy claim unsupported.

Questions for authors
  1. Clarification of the observation model: Does the server observe sample multiplicities, or only deduplicated active-index sets as specified in Definition 3? If only sets are observable, how does Theorem 3 address the two-client example with distributions (0.9, 0.1) and (0.1, 0.9), where the positive-gap assumption holds but the supports become indistinguishable as the sample size increases?

  2. Clarification of the security guarantee: Is the claimed LMPSU realization restricted to inputs satisfying honest-residual non-cancellation? If so, where is this restriction imposed in the functionality and end-to-end theorems? Otherwise, how can the simulator reproduce the honest-survivor union when two executions have identical total labeled unions and corrupted states, but different honest unions exposed by subtracting the corrupted clients’ IBLTs?

1 comment
AuthorsOpenReview ↗

Rebuttal for Reviewer 82VB

Clarification of Observation Model:

Section 2 explicitly analyzes independent sampling with replacement. The collision analysis applies when sampled multiplicities are observable. We agree that Definition 3 currently guarantees set recovery without explicitly requiring multiplicity recovery. We therefore added a multiplicity-preserving observation definition and state Theorem 3 and its associated necessity claim under this stronger assumption (Section 2+3, page 4-6). Under that observation model, the two distributions in the reviewer’s example remain distinguishable through their multiplicities. The example identifies a limitation of extending the bound to deduplicated supports; it does not contradict the collision analysis under the revised observation assumption. Separately, Table 2 demonstrates empirically that linkage is effective using deduplicated support sets on the evaluated training workloads.

Clarification on Security Guarantee:

We agree with the reviewer about the assumption. In fact, as the reviewer observed, our paper explicitly admits that the analysis is being done solely under no cancellation assumption. We include this assumption in the end-to-end LMPSU guarantee as well (Section 3.2, p. 6; Section 4.1, p. 7; Theorems 9–10, pp. 18–19). We refer to the attached updated version for the updated assumption.

Comments on the paper

2 comments
AuthorsOpenReview ↗

General Comment

We thank the reviewers for their valuable comments. Along with the comments, we also submit a revision of the paper regarding the comments that we made and will refer to the changes in the revision in our comments.

First, there is a common concern regarding the non-cancellation assumption of Pollen. Theorem 9 already states the honest-residual non-cancellation condition. We agree that this condition must also appear explicitly in the end-to-end claims that rely on it. In the revision, we propagate this condition to Corollary 1, Theorem 5, and the stated domain of the LMPSU realization (Definition 6 and Corollary 1, p. 6; Theorem 5, p. 7; Theorem 9, p. 18). Reviewer 82VB’s cancellation example is excluded by this honest-residual condition, even though the total labeled union alone is unchanged.

For well-formed corrupted contributions, the simulator subtracts the known corrupted updates from the dense aggregate, obtains the honest aggregate labels, and recovers (U_H) under this condition. It samples one independent uniform aggregate mask per honest-union item, constructs the honest aggregate IBLT, and adds the known corrupted IBLTs. This reproduces the aggregate-view distribution. If honest contributions cancel, the protocol may additionally reveal honest-union membership; we state that leakage explicitly rather than claim unconditional dense-SA equivalence in the attached revision.

We also distinguish this result from Theorem 10’s reduction for arbitrary corrupted encoded vectors. Active security of the underlying SA protects encoded inputs subject to its authorized aggregate leakage; it does not by itself establish valid sparse-input extraction. Simulation from the honest labeled union and accepted corrupted vectors remains possible, while an ordinary LMPSU realization requires the stated input domain and appropriate well-formedness conditions.

Finally, we now address the reviewers individual concern as below on individual comment section.

AuthorsOpenReview ↗

Rebuttal Round Ends Tomorrow

As the discussion phase concludes tomorrow, we have not yet received input on the several new experiments the reviewers requested, which we finalized and detailed in our comments and our revised manuscript. The additional experiments further reinforce the strong advantage of our proposed technique over all state-of-the-art privacy-preserving methods across a broad range of settings. We would greatly appreciate any feedback and remain happy to address any outstanding concerns before the discussion period ends.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.