PREAMBLE: Private and Efficient Aggregation via Block Sparse Vectors
Authors: Hilal Asi
Vitaly Feldman
Hannah Keller
Guy N. Rothblum
Kunal Talwar
Venue: NeurIPS 2025 poster ()
Keywords: Differential Privacy
Vector Aggregation
Two-server model
Primary area: theory
TL;DR: We show that private vector aggregation can be done with sublinear communication in the two-server setting, with efficient protocols and zero-knowledge proofs.

Abstract: We revisit the problem of secure aggregation of high-dimensional vectors in a two-server system such as Prio. These systems are typically used to aggregate vectors such as gradients in private federated learning, where the aggregate itself is protected via noise addition to ensure differential privacy. Existing approaches require communication scaling with the dimensionality, and thus limit the dimensionality of vectors one can efficiently process in this setup. 

We propose PREAMBLE: {\bf Pr}ivate {\bf E}fficient {\bf A}ggregation {\bf M}echanism via  {\bf BL}ock-sparse {\bf E}uclidean Vectors. PREAMBLE builds on an extension of distributed point functions that enables communication- and computation-efficient aggregation of {\em block-sparse vectors}, which are sparse vectors where the non-zero entries occur in a small number of clusters of consecutive coordinates. We show that these block-sparse DPFs can be combined with random sampling and privacy amplification by sampling results, to allow asymptotically optimal privacy-utility trade-offs for vector aggregation, at a fraction of the communication cost. When coupled with recent advances in numerical privacy accounting, our approach incurs a negligible overhead in noise variance, compared to the Gaussian mechanism used with Prio.

PREAMBLE: Private and Efficient A Aggregation via Block Sparse Vectors
Hilal Asi Apple
Vitaly Feldman Apple
Hannah Keller* Aarhus University
Guy N. Rothblum Apple
Kunal Talwar Apple
Abstract
We revisit the problem of secure aggregation of high- nigh-dimensional vectors in a two-server system such as Prio. These systems are typically used to aggregate vectors such as gradients in private federated learning, where the aggregate itself is protected via noise addition to ensure differential privacy. Existing approaches require communication scaling with the dimensionality. and thus limit the dimen- sionality of vectors one can efficiently process in this setup.
We propose PREAMBLE: Private Efficient Aggregation Mechanism via BLock- sparse Euclidean Vectors. PREAMBLE builds functions that enables communication- and computation-effice block-sparse vectors, which sparse vectors where the non-zero entries occur in a small number of clusters of consecutive coordinates. We show that these block- sparse DPFs be combined with random sampling and privacy amplification by sampling results, to allow asymptotically optimal privacy-utility trade-offs for fraction of the communication cost. When coupled with recent advances in numerical privacy accounting, our approach incurs negligible overhead in noise variance, compared the Gaussian mechanism used with Prio.
extension of distributed point aggregation
vector aggregation,
1 Introduction
Secure Aggregation a fundamental primitive in multiparty communication, and underlies sev- eral large-scale deployments of federated learning and statistics. Motivated by applications to pri- vate federated learning, we study the problem aggregation of high-dimensional vectors, each of bounded Euclidean norm. We will study this problem in the same trust model Prio (CB17). where at least one two servers assumed to be honest. This setup has been deployed at large scale in practice and our goal in this work is to design algorithms for estimating the sum of large number of high-dimensional vectors, while keeping the device-to-servee communication, as well as the client and server computation small.
This problem was studied in the original Prio paper, as well as several subsequent works [BCC+ 19 Tal22 AGJ=22] RSWP22 RU23 ROCT24. In Prio, the client creates addi- tive secret-shares of its vector and sends those to the two servers. One of the shares can be replaced by short seed, and thus the communication out of the client for sending D-dimensional vector is D + O(1) field elements. Additionally, such deployments typically require resistance to malicious clients, which can be ensured by sending zero-knowledge proofs showing that the secret-shared vector has bounded norm. Existing protocols [ROCT24] allow for very efficient proofs that incur negligible communication overhead.
In recent years, the size of models that are used on device has significantly increased. Recent work has shown that in some contexts, larger models are easier to train in the private federated learning setup (3P+ CCT+24). While approaches have been developed to fine-tuning models while
Reseaach done while Apple.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

(a) 1-sparse
(b) k-sparse
(c) 1-block-sparse
(d) k-block-sparse
Figure Possible non-zero patterns (gray) of 1-sparse, s-sparse, 1-block- sparse and k-block-sparse vectors.
training fraction of the model parameters (e.g. 22)) increasing model sizes often imply that the number of trained parameters in the range millions to hundreds of millions. The communication cost is further exacerbated in the secret-shared setting, as must communicate D field clements, which are typically 64 or at least 32 bits, even when the gradients themselves may be low-precision. As example, with 64-bit field, an eight calllonn-dimensionn gradient will require at least 64MB of communication from each client to the servers.
In applications to private federated learning, noise is typically added to the sum of gradients from hundreds of thousands of devices, to provide provable differential privacy guarantee. Even absent added noise, the aggregate is often inherently noisy in statistical settings. In such setups, computing exact aggregate may overkill, and indeed, previous work the trngleetrusted-server setting has proposed reducing the communication cost by techniques such as random projections (SYKM17 VBBP+ VBBP*21
22 AFN* CIK+ However, random projections increase the sensitivity of the gradient estimate, and hence naively, would require more noise to be added to protect privacy.
This additional overhead can be reduced if each client picks different random subset of coordi- nates, and this subset remain hidden from the adversary. Thus while each client could send sparse vector, the sparsity pattern must remain hidden. This constraint prevents any reduction in commu- nication costs when using Prio. A beautiful line of work GII BGIT5] BGHT6 21] on Function Secrel Sharing addresses questions of this kind. particular, Distributed Point Functions (DPFs) allow for low-communication secret-sharing of sparse vectors in high-dimensional space. However, this approach primarily designed allow the servers to efficiently compute any one co- ordinate of the aggregate. The natural extension of their approach to aggregating dineesiinnsi vectors incurs a non-trivial overhcads for the parameter settings of interest, where the sparse vectors have tens of thousands of non-zero entries.
In this work, we address this problem of high-dimensionee vector aggregation two-server setting. We give the first protocol for this problem that has sub-linear communication cost, reasonable client and server computation costs, and gives optrmal trade-offs between utility and (differential) privacy. Our approach builds on the ability to efficiently handle the class of k-block sparse vectors (see Fs. 1. For parameter B, we group the D coordinates into = D/ B blocks of B coordinates each. A k-blocck-pparee vector is one where at most & of these blocks take non-zero values. We make the following contributions:
We identify block-sparseness the "right" abstraction, that effectively balances the pressiveness needed for accuracy with the structure needed for efficient cryptographic ag- gregation protocols.
We propose an extension of the distributed point function construction of [GH16] that can secret-share k- d-block-sparre vectors while communicating =u kB field elements. For typical parameter settings, our approach that uses blocks is significantly more communication- and
computation-efficienn. compared to schemes for sparse vectors.
We show how an aggregation scheme for k-block-sparse inputs combines with sampling analyses for utility, and ing. Combined with recent advances in numerical privacy accounting, we show that for reasonable settings of parameters, our approach leads to privacy-utility trade-offs compa- rable to the Gaussian mechanism, while providing significantly smaller communication costs. For instance, in the case of an eight million-dimensional vector with 64 bit field size, our approach reduces the communication from 64M about 1M B, while increasing the noise standard deviation by about 10% for (1, -D- when aggregating 100K vectors.
analyses for privacy account-

---

Overview of Techniques
Compressing high-dimensional vectors for noisy aggregation a standard consequence of the beau- tiful advances in randomized sketching algorithms. For example, one standard random pro- jection techniques, including efficient versions of the Johnson-Lindenstraus lemma [L844] AC06), to construct sparse unbiased estimator for each vector. A random rotation of the vector, followed by subsampling an appropriate number (say m z 50, 000) of coordinates is sufficient to get a good approximation the aggregate. Indeed this approach has been proposed for vector aggregation in prior works.
This approach has two significant challenges. Firstly, get good approximation for practical pa- rameters, the number of non-zero coordinates m is in the tens of thousands. While sparse vectors can be communicated efficiently using distributed point functions (DPF) constructions in the literature, the overheads in terms of client computation, communication, and server computation are fairly sig- nificant. Secondly, this reduction to sparse vectors significantly increases the sensitivity of the final estimate and results in larger privacy noise. Indeed for aggregating vectors of norm 1 in ID,, using DDssaass vector increases the sensitivity, and thus the required privacy noise, by multiplicative 1/7. This leads to an unappealing trade-off between communication and privacy noise.
We show that constraining the sparsity structure to have k non-zero blocks (each of size B = m/k) instead of m non zero coordinates overall can allow for sigmificant performance gains for aggrega- tion protocols in the two-server setting. We further show that this constraint comes at little cost: analyses privacy amplification by sampling allow us to handle the increased sensitivity with little impact to the privacy-utility tradeoff. We give some details of each of these pieces next.
Our work is in the two-server trust model pioneered in Prio CB17.. Each client has a secure com- munication channel with each of the servers, and the servers can communicate with each other. Differential privacy is guaranteed so long as one of the servers is honest (even the other server is malicious and can observe the final aggregate). We show how to efficiently secret-share k-block- sparse vectors in this model. Note that any such vector has at most mn non-zero coordinates, and thus is sum of 1-sparse vectors. Each of these can be shared using the Distributed Point Function (DPF) construction of [BG116]. This approach however leads to a communication cost of m log D, where À is the security parameter. Thus e.g. when D is more than a million and X 128, the com- munication cost is at least 300 bytes per non-zero coordinate of the vector. For m = 50, 000, this amounts to 15MB of communication. (This basic scheme also incurs very significant compute overhead, with the server cost being at least OmmD), though that can be reduced by using opti- mizations based on probabilistic batch codes [BCGII8] overhead in communication cost.) Thus for m being in the tens of thousands, approaches that only exploit sparsity (rather than block-sparsity) far from feasible.
O(D m log D) at small additional
We first observe that a simple modification of the DPF construction can exploit the block structure, reducing the communication cost to O(m + kλ log D). For the concrete setting above, where D is over one million and = 128, holding choosing B N 1000, our communication would be 400KB, if the field size is 64 bits. This also allows a bulk of the evaluations of a pseu- dorandom generator (PRG) to be in counter mode which can be more computationally ef- ficient. This approach still requires O(kD) server-side PRG evaluations. The use of prob- abilistic batch codes can reduce this computa- tional overhead. We propose a different ap- proach that uses cuckoo hashing within the DPF construction, that reduces the server's s computa- tion to O()) and reduces by 3x the number of PRG evaluations the server has to do. See Sec- tion A for a comparison with prior work and
Partttonss Shosamoling a -1024)
Partiiind sussamo ing -2011
Partttoned Suasanaiing -0028)
kB 50000 constant and
Figure 2: The trade-off between expected squared er- ror and per-client communication, when computing the sum of n 10" vectors in D = 2 dimensions with (1.0, 10 10-9)-DP. The curves show our algorithm using different block sizes E [10*, and the blue shows the baseline approach of sending the whole vec- tor. We limit ourselves to algorithms for which the server run time is linear or near- linear in D.
with a concurrent and independent work.
3

---

Aggregate (Informal)
Client Algorithm. Input: vector v E R.. Parameters: dimension D. blocksize B, sparsity
1. Randomly select I , with [ k.
2. Define k-block sparse vector which equal to ( (ee - v blocks indexed by (i.e. coordinates (j 1) + jBB for j E 1) and 0 everywhere else. This rescaling ensures that the expected value of w is
3. Use sspaock-sparse DPF construction to communicate w to the server. This needs communica- tion O + kλ log D/B).
Servers will decrypt recover (secret-shares of) each vector w. They collaboratively compute sum and add noise (Ox)..
Figure 3: Informal Description of our approach Approximate Aggregation via k-block sparse vectors
To prevent a malicious client from corrupting the aggregate, we also provide efficient zero- knowledge proofs of validity for our construction of secret-shared k-block-sparse vectors. This allows the client to prove that all but & of the blocks are zero vectors. The proofs maintain pri- vacy for honest clients, while preventing malicious clients from sending malformed contributions. The proofs do not change the asymptotic communication or the client (prover) or server (verifiers) runtimes. particular, the client runtime and communication depend only on the sparsity and on A, and not on D. Our protocol has two rounds of communication between the client and servers, but can be made non-interactive using the Fiat-Shamir heuristic, see (Appendix The proof system combines techniques from prior works [BCG 21 JCC22al with novel interactive proof showing that secret shares of PRG seeds in a DPF tree only differ in a small number tree nodes (when the seeds are identical the PRG outputs "cancel out", corresponding to zero block). Finally, we can use an efficient zero-kmon prro-knoweedge proof system from prior work [ROCT24] to also prove that that the Euclidean norm of the vector of non-zero values is small.
As discussed above, naively applying random projection techniques to reduce communication results in unappealing trade-off between communication and privacy noise. We avoid this overhead by exploiting the fact that the sparsity pattern of vectors hidden from each server our construction, as in some recent work [CSOK23 CIK 24). This allows us to use privacy amplification by sampling techniques, at a block-by-block by-block level, coupled with composition. For a large range of parameters, it allows to reduce the overhead in the privacy noise, and asymptotically recover the bounds one would get if we communicated the full vector. Fig. 3 presents an informal outline our approach. We defer to Section 3 discussion of different approaches to sampling, and their trade-offs. Coupled with numerical privacy analyses, we get the reduction in communication cost essentially for free (Fig. 2).
While our approach of subsampling blocks rather than coordinates is motivated here for the two- server setting, some of the benefits extend easily to the single trusted server setting where the cost of sending the index would now get amortized over a large block. The privacy analysis of the subsampling approaches requires some control of the norm of each coordinate, which gets relaxed in our approach to a bound on the l2 norm of each block. The latter is a significantly weaker requirement. Our privacy analysis shows that block-based sampling nearly matches the privacy- utility trade-off of the Gaussian mechanism for large range block sizes.
Organization: We start with preliminaries in Section 2 and describe sampling approach and privacy analysis in Secttion 3) Our k-block-sparse DPF construction is sketched in (Section 4 (with full details in Appendix H). We report empirical evaluations in [Section Additional related work, additional preliminaries, and all proofs are deferred to the Supplement.
2
Preliminaries
We will be working with vectors v E R,,, and in the linear algebraic parts of the paper, we view them ....... UD. As is standard, the cryptographic parts of the paper will view the vectors as coming from a finite field G = F,; for a suitably large q, the quantized versions of n real vectors be added without rollover so that we get estimate of the
of quantized vectors.
We will use to represent the block size and A = D/ will be the number of blocks. We will assume A is power of 2 and d will denote log, A. X will denote our security parameter. In the

---

cryptographic part of the paper we will view vector as a function from {0, 13 x [B] + G where [B] = {0, ..........-... 1}.
We recall the definition of (s, oj-indiisinguishabiiity and differential privacy.
Definition 2.1. Lete 0, [0. 1), and let Y and Y' be two random variables. We say that and Y' are (e, 8) iniistinguuisabbee for any measurable set S, it is the case that
Pr(Y" E ES) S Pr[Y ES] +
and Pr(Y S Pr|Y' E S
Definition 2.2 (Differential Privacy (DMNS66). Let A D - R be randomized algorithm that maps dataset X E "D" to a range R. We say two datasets X. X are neighboring if X can be obtained from X' by adding or deleting one element. We say that A is (e, -ddffferrent private if for any pair of neighboring datasets X and X', the distributions A(X) and A(X") are (e, 8) indistinguuishable
Definition 2.3 Pssuudorandom Generator (PRG)). Let X E N be a security parameter, A Pssedd- random generator (PRG) is an efficiently computable function G2 =00,1] - 10,1] 13 where B(A) is a fixed polynomial in X and {(A) > X. A PRG is secure if its output is indistinguisabble from a truly random bitstring. More formally, for all efficient adversaries A, there is a negligible f function negl()) (X) such that
[Pr[s + (0,1) A(Ga(s)) = 1] 10, A(z) - 1]I negl(A)
3 Private aggregation via k-block-sparse vectors
In this section we propose two instantiations of our sampling-based sparsification, and describe the formal privacy and utility guarantees of the resulting aggregation algorithms. In both schemes each user is given a vector E IR which consists of A D/B blocks, each of size B. We refer to the value of on block E [A] by u, R Our subsampling schemes are parametrized by an upper bound on the Eg norm of each block L and the number of blocks k to be sent by each user. We will also assume, for simplicity, that & divides A. The bound L is somewhat stronger than a total bound on the &g norm of the input that is typically assumed in mean estimation. A number of standard techniques are known for converting an & norm bounded vector to an -boundd vector such as Kashin representation LV10). We show that techniques from [AFN+2] 23] can be used to convert a vector of l norm 1 to a vector in which each block has norm / /B/D while incurring expected squared error on the order I/B, Note that this result relies crucially on the fact that ensuring that block norms are upper-bounded is easier than ensuring that each coordinate norm is upper- bounded. We formally prove that the expected error due to truncation falls as Ö ( O in Appendix F
and evaluate this impact empirically in Section 5)
Our subsampling schemes differ in how the k blocks are subsampled. In Partitioned Subsampling, partition the blocks into A groups of A/k consecutive blocks, and pick one block out of each group, randomly and independently. In Truncated Poisson Subsampling. we select each block with probability g. to get in expectation ك blocks. If the number of blocks that end up getting sub- sampled is larger than k, we keep at random is of them. This gives at most & non-zero blocks, which can communicated using our k-bllock-sparse DPF. Both schemes give about the same expected utility, and privacy bounds that match asymptotically. The partitioned subsampling results in more structured k-bllock-pparse vector, which a concatenation of 1-block-sparse vectors, which are simpler to communicate. The truncated Poisson subsampling has more randomness, and can be analyzed numerically using larger set of tools, though it may have slightly higher communication cost. As we discuss in Section 5) each of these may be preferable over the other for some range of parameters. formal description of these schemes is given Fig, 6a and Fig. 6blin the Appendix.
Theorem 3.1 (Utility of the subsampling schemes). Let v! 2t . be collection of vectors such
that each v² oi...., v'S E TR. and ||o/|12 L for all E [n] and i E [A]. Let w denote the (randomized) report of either of our subsampling algorithms for each j E [n] and let W = Eje(n W + NO, d²Ip)) be their noisy aggregate. Then
E|[
Σ jE[n]
< nI?
+ ..2
K
5

---

Theorem (rroved in Appendix D provides guidance on how to set the smallest communication cost so that the sub-sampling error negligible compared to the privacy error. Indeed, assume for
simplicity that our vectors lie in the -all v E
[ JT This implies that the norm of each block is upper bounded by L BBDD Noting that Dí the (upper bound above on the) error of the algorithm is nd/k: + o²D. This implies that we should set kB c n//o² 2 for some constant c >> 0. In other words, the number of coordinates that are non-zero must be set to cn/o². which is independent on D, well as of the blocksize. Thus block-based subsampling does not impact the sampling noise, and any setting of k and B with the product kB 2 en/o² would suffice.
We also note that the proof is oblivious to the subsampling method and only uses the fact that marginally, each coordinate has the right expectation, and is non-zero with probability k/A. Thus applies range of subsampling methods.
We now analyze the privacy of our subsampling methods using the standard notion of differential privacy [DMS066 with respect to deletion of user data. In the context of aggregation, we can also think of this adjacency notion as replacing the user's data with the all-O vector. We state the asymptotic privacy guarantees for our partitioned subsampling method below (the proof can be found in Appendix E). Similar guarantees hold for the Truncated Poisson subsampling with an appropriate choice of parameters and can be derived from the known analyses LACG+ 16 Ste22 together with the fact that the truncation operation does not degrade the privacy guarantees [FS25b].
Theorem 3.2 (Privacy of partitioned subsampling). Let v² ,"..,,"" Th be a collection of vectors such ll2 S for all j E [n] and E [A]. Let w denote the
that each v = vi...., V (randomized) report using Partitioned Subsampling, for each j E [m]] and let A be an algorithm that outputs W
E RD and ||e:
> JE(n) w + NO, o2 ID)) Then there exists a constant such that for every 5 > O, if
then A is (c, (e.8))differentiall private V A log(4/6), A.A///.///ll(//// \olog(1/8) }
8. 2 c- max
for E O LV LoA
Note that this implies that when T. Oly ((/Tog(1/8//a) which asymptotically matches the bound for the Gaussian mechanism. In other words, the privacy cost of our algorithm close to that of the Gaussian mechanism, when kB 2 n/o" and 2 v Alg //o For a fixed kB, this constraint translates to an upper bound on the block size.
V1/A and we set kB to be n//o,, the resulting e is
This asymptotic analysis demonstrates the importance of hiding the sparsity pattern. Specifically, without hiding the pattern we cannot appeal to privacy amplification by subsampling and need to rely on the sensitivity of the aggregated value. The sensitivity is equal to vk- LA k
= LA vi"
By the properties of the Gaussian noise addition (Thm. B.2). we obtain that the algorithm is LA (lg((1/))
(0
,6 -DP. This bound is worse by a factor of / than the bound we get in ovk
Theorem 3.2, A similar gain was obtained for private aggregation of Poisson subsampled vectors in CSSO23]
Communicating 1-sparse vectors: A common application of secure aggregation systems is to aggregate vectors that are 1-sparse (often known as 1-hot vectors) or k-sparse for a small l for applications such as histogram estimation. Directly using DPFs for these vectors requires (D) PRG re-seedings and thus can be expensive. Noting that k-sparse vector is also k-block sparse, one can directly use PREAMBLE to reduce the server computation cost at a modest increase in communication cost. Alternately, in settings where we want to add noise in distributed setting, RAPPOR [PK14]] and its communicmmnni variants such as PI-RAPPOR [FT2]] and Pro- SeriveGeomeetyyResposee [FNNT22] can be used along with Prio. Since 1-hot vectors become
vectors { 1 } after Hadamard transform, one can view these vectors as Euclidean vec- tors D and use PREAMBLE to efficiently communicate them. ProjertiveGoomettyyeessnnss is particularly well-suited for this setup even without sampling, the resulting message space is
VD

---

dimeeniins,,,n,,, and a linear transformation of the input space. Thus one can aggregate in "mes- sage space": each message 1-hot vector in message space, and we can add up these vectors using PREAMBLE. The linear transform to go back to data space is simple post-processing and the privacy guarantee here can use privacy amplification by shuffling. Since we avoid sampling in this approach, it can scale to larger n. without incurring any additional utility overhead.
Numerical Privacy Analysis In practice, numerical privacy analysis give much tighter privacy bounds. We can analyze the two approaches described above. For partitioned subsampling, we use the recent work on privacy amplification by random allocation [FS25b] to analyze the privacy cost. The authors show that the privacy parameters of the k-out-of-m version of the Gaussian mechanism can be bounded using numerical methods. These privacy bounds were improved further in recent work FS25a and we defer an updated evaluation to the full version.
For the approach based on truncated Poisson subsampling, it is shown in FS25b] that the privacy cost is no larger than that of the Poisson subsampling version without the truncation. The Pois- son subsampling can then be analyzed using the PRV accountant of [GLW2I]. While the PRV accountant usually gives better bounds than one can get from RDP-based accounting, we suffer a multiplicative overhead as the scaling factor K in Truncated Poisson is smaller than k. For the nu- merical analysis, we optimize over q to control the overall variance one gets from this process. Note that when lo is large and q k-O(vk) one would expect truncation to be rare, and thus K to be close to & and thus to k:
One can also study different subsampling process where / is a uniformly random subset of size k. We may expect better privacy bounds to hold for this version, intuitively as there is more randomness compared to partitioned subsampling. Feldman and Shenfeld [FS25b] show that the privacy bound of this variant is no larger than that of partitioned subsampling. We conjecture that the privacy cost of this version is closer to (untruncated) Poisson with sampling rate q = k/A. Since the latter can be more precisely accounted for using the PRV accountant, we expect careful numerical accounting of this version to do better than the RDP-based bounds for partitioned subsampling.
d-block-sparse-DPF Construction: Main Ideas
We sketch here the main ideas of our DPF construction, deferring full details to Appendix H Our construction builds on the tree-based DPF construction from [BGI16) for sharing a I-sparse function f (0. 1)dd - f0. 1}. f outputs' on all but most one input a E f0. 1)d. At very high level, in their construction the client shares with each server seed to a pseudo-random random generator. Each server uses their seed to expand out an entire tree with 2d leaves, where each node in the tree contains the seed to a PRG and some additional "control bits". The client also sends a (public) "correction word" for each layer of the tree. The control bits and the correction word are used to ensure that in each layer, the strings in each node secret shares of the zero string, except for the single node in that layer that is on the path from the root to the leaf a corresponding to the non-zero output of f- The servers evaluate the DPF by first expanding the PRG seed for node and then, depending the value of their control bit, adding the correction word for this level.
In our construction of s-spare DPFs, there are k non-zero nodes in each layer: the nodes that are on the paths from the root to the k non-zero leaves. A naive suggestion could be to also use i correction words for each layer, but this increases the server's computation by a k-fold multiplicative overhead (in a nutshell, each server would need to apply a correction procedure for each node and for each correction word). Instead, we use cuckoo hashing and a collection of slightly more than & correction words per layer, where each node in the layer only needs to apply a correction procedure to two correction words that are relevant to it (the relevant correction words are determined by two hash functions that are public). This reduces the server's computation to 2 corrections per node (the correction procedure is just an XOR: it is quite lightweight). We can also use 3 or 4 hash functions to reduce the number of correction words per layer to be very close to k, see Remark H.
To handle block-sparse functions we modify the tree: each leaf now corresponds to an entire block (and all but & of them will be zero). The servers expand the seed corresponding to each leaf into an entire block, and the correction words for the last layer ensure that these expansions are secret shares of the correct output (thus the correction words for the last layer are of length B). This avoids the high cost of repeating the bit-output construction B times. Rather than paying B-multiplicative
7

---

to a OdD)-dimensoon space; the hidden constants in the two O(-) notations are related, where making one smaller makes the other larger. In practice, simple approach often used is to apply a random rotation to the vector, followed by truncating any entry that is larger than e vD for an overhead in the key size, we pay the cost of a single bit-output construction, plus O(k B) for the correction bits in the last layer. We also only have only single PRG evaluation per block/leaf (with a large output). This approach reduces the number of large PRG evaluations by factor of 2-3 compared to techniques from prior work that used cuckoo hashing to construct sparse DPFs (see Section A and Remark [H.4). As noted above, if we use 3 or 4 hash functions for cuckoo hashing, then the number of correction words for the last layer is very close to and the communication complexity approaches k B.
Zero-knowledge proofs of validity. We construct an efficient proof-system that allows client to prove that it shared valid block-sparse DPF. The proof is divided into two components:
1. & correction- bit sparse. The client proves that at most it of the (secret shared) correction bits corresponding to leaves in the tree non-zero.
These are just bits so here we can use an efficient proof systems of [BG[16 for sharing standard DPFs (the client also needs to send 1-sparse DPFs whose sum is the vector of control bits).
2. k block-sparse. Given that most k of the correction bits for the leaves are non-zero, the client proves that there are at most k non-zero blocks in the output.
Consider the final layer of the DPF tree: in zero block, the two PRG seeds held by the servers are identical (shares of the zero string), whereas in non-zero block, they are dif- ferent. Rather than expanding the seeds to B group elements (as in the vanilla construction above), we add another À bits to the output, and we also add corresponding bits to each correction word. We refer to these as the check-bits of the PRG outputs / correction words, and we refer to the original outputs as the payload bits. In the zero blocks the check-bits of the outputs should be identical: subtracting them should results in zero vector. In each non-zero zero block, the check-bits of the (appropriate) correction word are chosen so that the correction procedure will result in all-zero check-bit string. Thus, in our proof system, the servers verify that, in each block, the secret-shared check-bits are indeed all zero. This can be done quite efficiently. We remark that de Castro and Polychroniadou (dCP22a also used check-bits to verify sparsity (albeit in a different construction).
The additional cost for the proof (on top of the construction above) O(k d A) communication, (k poly (d, A)) client work, (A- 2d poly (d, server work for each server. The proof system is sound against a malicious client, but we assume semi-honest behavior by the servers.
5 Experimental Evaluation
In this section, we give empirical evidence demonstrating that PREAMBLE is accurate, private, and communication efficient.
Blocking improves communication cost: Figure 4a shows the required communication, or DPF key size, for À = 128, a group of size 204 in the final tree layer. Communication depends on the sparsity block size B, and data dimension D. We vary B and hold kB 2 constant. We also include baseline communication comparison, which is the minimum communication required to communicate kB group elements size log |G| and the D/B indices of the non-zero blocks to single trusted server. Our plots are for 4-way cuckoo hashing, where the muckoo-hashing overhead about 1.03. Using fewer hashes would increase the key size, but lead to more efficient server computations.
Blocking reduces Truncation Error We analyze empirically the ease of ensuring block-wise norm bound. Theoretically, a norm bound of O
each entry can be ensured if one transforms
appropriate constant c. For moderate values of c, the truncation error (i.c. the norm of the induced error) small for random rotation. Imposing the weaker condition that each block has &, norm at most /DBB
results in lower truncation error. In Fig. 4b) we plot the truncation error as a function
8

---

of c, when we apply a random rotation, for different values of the block size B. It is easy to see that c will result in non-trivial truncation error for any block size. Our plots show that even moderately large B allow us to take very close to for negligible truncation error.
Communinan istionatioon (bylec)
De1
0.4
B-4
Subamp fattiieeee Sppome 4006) Sillorre Subsemo iyg =5122)
D-1D0M
Tuncatton Ennor
93
B-32
baseline, D=
224
02-
2
0.2
0.0
1.0
12
1.4
1.6
1.8
2,0
Commrn Cast
(h)
(c)
Figure 4: (Left) Communication vs. Block size for our s-spase DPF construction, compared to a single- rusted-server baseline. (Middle) The trade-off between the truncation error [[Trunc.(Go) Gullz and con- stant c, where e E R²D is arbitrary, and G is a random rotation matrix. The plots show the error for various block sizes, for D = 2 (Right) The trade-off between the standard deviation of the error and per-client communication C' kB, when computing the sum of 10 vectors with dimension D 2 with (1.0, 10 ".-D. The blue shows the baseline approach of sending the whole vector.
Blocking is compatible with Privacy: We next evaluate the privacy-utility trade-off of our ap- proach, compared to not using any sampling. For our baseline Gaussian mechanism, we use the Analytic Gaussian mechanism analysis from [WBK2I] For these numerical results, we assume that L is fixed to / /B/D. For each of the approaches, we compute the total variance of the error in the sum, which includes the privacy error that results from the numerical privacy analysis, and the sampling error as bounded by Theorem 3.1] For the communication cost, we simply plot &B as it a good proxy for the actual communication cost for large range of parameters. Based on the evaluation above, we consider values of B that are in the range (210) 221).
Fig. 4c shows the trade-off between communication cost and the standard deviation of the error for our algorithm, using partitioned subsampling, as well as the Gaussian baseline. As is clear from the plots, our approach allows us significantly reduce the communication costs, at the price of a minor increase in the error. This holds for range of D from 1M to 8M, and for range of e values. (additional plots in the Appendix).
As we decrease the communication kB, the error in Fig. 4c essentially stays constant until a point, and then rapidly increases. This is largely due the fact that for large block sizes, the norm of each block is larger so that the required lower bound on a to ensure privacy amplification by subsampling larger. While the plots are derived from the numerical analysis which is tighter, intuition for this can be derived from the condition & > / log 1/0/a, or equivalently a > / 1/8/k /k in Theorem 3.2) Thus for the case of small BB, one would prefer smaller block sizes. Our plots show that block sizes in the range [210 213 provide low error across range of parameters. Recall that in Fig. 4a we saw that block sizes above 2 are sufficient to get most of the communication benefits.
Next we turn to experiments simulating the use of PREAMBLE in private model training. In Fig. 5a we plot the overhead in the per-batch noise standard deviation vs. the block size, if we were to analyse DPSGD 16 with the Gaussian mechanism for each batch replaced by partitioned subsampling. Due to the more complex accounting that uses general Renyi subsampling, the in- crease here is larger. Finally, we show some end-to-end experiments for private learning (Fig. 5b and Fig. 5c). We report results for using DP-SGD (with momentum) on MNIST (LCB10) and CIFAR- 1O Kri09] with privacy parameters E 1.0 and ó = 10- 6 For MNIST, we use the model from [FFN+23) which has 69050 trainable parameters. For CIFAR, we train a simple two-layer neu- ral network with 66954 parameters on CLIP (RKH*21 embeddings. We give additional details of the setup, including all hyperparameters in Appendix J) Our results show that PREAMBLE allows for significant reduction in communication while incurring a small increase accuracy. Indeed, for both datasets, PREAMBLE with the chosen parameters allows to communicate around 2 1 parameters, compared to roughly 6 10 parameters using the Gaussian mechanism. Additional experiments are deferred to the supplement.

---

0.01
22
0.70
12 0:00
12
(a)
(b)
(c)
Figure 5: Comparison between PREAMBLE. and the Gaussian mechanism for private model training. (I.eft)
Ratio of the per-hatch noise standard deviation PREAMBLE ,E: over the noise of the Gaussian mechanism. (Middle) Accuracy for PREAMBLE and Gaussian mechanism on MNIST with 90% confidence intervals.
(Right) Accuracy for PREAMBLE and Gaussian mechanism on CIFARIO with 90% confidence intervals.
Conclusions
In this work, have described PREAMBLE, efficient algorithm for communicating high- dimensional Euclidean vectors in the Prio model. Our construction reduces this problem to ag- gregating k-block-sparse vectors, using random sampling, and privacy amplification-y--samplll type analyses to allow private aggregation with a small overhead in accuracy. We showed how to ficiently communicate such vectors, and construct zero-know knowllnoeeddge proofs to validate bound on the Euclidean norm and k-block-sparritty of these vectors. Our algorithms require client communication proportional the sparsity kB of these vectors, and client computation also scales only with kB for parameters of interest. Our construction allows the servers to reconstruct each contribution using (D) field operations and PRG evaluations in counter mode.
We leave open some natural research directions. Our numerical privacy analyses are close to tight but still have gaps. We conjecture that the k-out-of-A sampling approach should admit better privacy analyses than the partitioning--ue based approach, and should be no worse than Poisson sampling. Our approach based Cuckoo hashing with hash functions incurs constant factor communication overhead, and has a O(}) failure probability. While the overhead can be reduced using more hash functions, the failure probability remains k for a small constant e [MW088] While for our application approximate aggregation, this has little impact, it would be natural design version of our scheme that has a negligible failure probability without increasing the server compute cost.
Acknowledgments
Hannah Keller has received funding from the Danish Independent Research Council under Grant-ID DFF-2064-00016B (YOSO).
References
[AC06] Nir Ailon and Bernard Chazelle. Approximate nearest neighbors and the fast johnson- lindenstrauss transform. Proceedings of the hhirty-Eightte Anmual ACM Symposium Theory of Computing, STOC '06, page 557-563, New York, NY, USA. 2006. As- sociation for Computing Machinery.
[ACG 16] Martín Abadi, Andy Chu, Ian Goodfellow, Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi, editors, ACM CCS 2016, pages 308-318. ACM Press, October 2016.
[ACLS18] Sebastian Angel, Hao Chen, Kim Laine, and Srinath T. V. Setty. PIR with compressed queries and amortized query processing. In 2018 IEEE Symposium on Security and Privacy, pages 962-979, IEEE Computer Society Press, May 2018.
[AFN+23] Hilal Asi, Vitaly Feldman, Jelani Nelson, Huy Nguyen, and Kunal Talwar. Fast opti- mal locally private mean estimation via random projections. In A. Oh, T. Naumann,
10

---

A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Infor- mation Processing Systems, volume 36, pages 16271-16282. Curran Associates, Inc., 2023.
[AFN+24] Hilal Asi, Vitaly Feldman, Jelani Nelson, Huy L. Nguyen, Kunal Talwar, and Samson Zhou. Private vector mean estimation in the shuffle model: Optimal rates require many messages. 2024.
[AFT22] Hilal Asi, Vitaly Feldman, and Kunal Talwar. Optimal algorithms for mean estimation under local differential privacy. In International Conference Machine Learning, ICML, USA, pages 1046-1056, 2022.
[AG21] Apple and Google. Exposure notification prevaccyn analytics (ENPA) white paper. https::/cco..d1e-staaiii.. con apple com http:/aeeaaaaappemooooooaaaaaaaa hitree///aaa..ccccccatttttacca/t /ENPA Bttpa//AAAAAWtittA.eee White White_ .af.aprppfff....... 2021.
covid19/
[AG] + 22] Surya Addanki, Kevin Garbe, Eli Jaffe, Rafail Ostrovsky, and Antigoni Polychroni- adou. Priot: Privacy preserving aggregate statisties via boolean shares. In Clemente Galdi and Stanislaw Jarecki, editors, Security and Cryptography for Networks 13th International Conference, SCN 2022, Amalfi, Italy, September 12-14, 2022, Proceed- ings, volume 13409 of Lecture Notes in Computer Science, pages 516-539. Springer, 2022.
23] Sheikh Shams Azam, Martin Pelikan, Vitaly Feldman, Kunal Talwar, Jan Silovsky, and Tatiana Likhomanenko. Federated learning for speech recognition: Revisiting current trends towards large-scale ASR. In International Workshop on Federated Learning in the Age of Foundation Models in Conjunction with NeurIPS 2023, 2023.
[AS19] Jayadev Acharya and Ziteng Sun. Communication complexity in locally private dis- tribution estimation and heavy hitters. In Proceedings of the 36th International Con- ference on Machine Learning, ICML, pages 51-60, 2019.
[BBC+19] 19] Dan Boneh, Elette Boyle, Henry Corrigan- Gibbs, Niv Gilboa, and Yuval Ishai. Zero- knowledge proofs on secret shared data via fully linear peps. In Alexandra Boldyreva and Daniele Micciancio, editors, Advances in Cryptology CRYPTO 2019 39th An- nual International Cryptology Conference, Santa Barbura, CA, USA, August 18-22, 2019, Proceedings, Purt III, volume 11694 of Lecture Notes in Computer Science, pages 67-97. Springer, 2019.
[BBC+23] 23] Dan Boneh, Elette Boyle, Henry Corrigan-Gii Gibbs, Niv Gilboa, and Yuval Ishai. Arithmetic sketching. In Helena Handschuh and Anna Lysyanskaya, editors, CRYPTO 2023, Part I, volume 14081 of LNCS, pages 171-202. Springer, Cham, Au- gust 2023.
[BCC 21] Dan Bonch, Elette Boyle, Henry Corrigan-Gibee Niv Gilboa, and Yuval Ishai. Lightweight techniques for private heavy hitters. In 2021 IEEE Symposium on Se- curity and Privacy (S & P), pages 762-776, 2021.
[BBG20] Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy profiles and amplification by subsampling. Journal of Privacy and Confidentiality, 10(1), 2020.
[BBGN19] Borja Balle, James Bell, Adrià Gascón, and Kobbi Nissim. The privacy blanket of the shuffle model. Advances in Cryptology- CRYPTO 2019 39th Annual International Cryptology Conference, Proceedings, Part I1, pages 638-667) 2019.
[BBGN20] Borja Balle, James Bell, Adrià Gascón, and Kobbi Nissim. Private summation in the multi-message shuffle model. In CCS '20: 2020 ACM SIGSAC Conference Computer and Communications Security, pages 657-676, 2020.
[BCGI18] Elette Boyle, Geoffroy Couteau, Niv Gilboa, and Yuval Ishai. Compressing vector OLE In David Lie, Mohammad Mannan, Michael Backes, and XiaoFeng Wang, editors, ACM CCS 20/8, pages 896-912. ACM Press, October 2018.

---

[BDF* 18] Abhishek Bhowmick, John C. Duchi, Julien Freudiger, Gaurav Kapoor, and Ryan Rogers. Protection against reconstruction and its applications in private federated learning. CoRR, abs/1812.00984, 2018.
[BGH*23] Elette Boyle, Niv Gilboa, Matan Hamilis, Yuval Ishai, and Yaxin Tu. Improved Constructions for Distributed Multi-PPint Functions. 2025 IEEE Symposium on Security and Privacy (SP), pages 2414-2414 2432, Los Alamitos, CA, USA, May 2025. IEEE Computer Society.
[BGI15] Elette Boyle, Niv Gilboa, and Yuval Ishai. Function secret sharing. In Elisabeth Os- wald and Mare Fischlin, editors, EUROCRYPT 2015, Part II, volume 9057 of LNCS, pages 337-367. Springer, Berlin, Heidelberg, April 2015.
[BGI16] Elette Boyle, Niv Gilboa, and Yuval Ishai. Function secret sharing: Improvements and extensions. In Edgar R. Weippl. Stefan Katzenbeisser, Christopher Kruegel, An- drew C. Myers, and Shai Halevi, editors, ACM CCS 2016, pages 1292-1303, ACM Press, October 2016.
[BNO08] Amos Beimel, Kobbi Nissim, and Eran Omri. Distributed private data analysis: Simul- tancously solving how and what. In David Wagner, editor, Advances Cryptology CRYPTÓ 2008, pages 451-468, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg.
[BS15] Raef Bassily and Adam D. Smith. Local, private, efficient protocols for succinct his- tograms. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC, pages 127-135, 2015.
[BS16] Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Martin Hirt and Adam Smith, editors, Theory of Cryptography, pages 635-658, Berlin, Heidelberg, 2016. Springer Berlin Heidelberg.
[BW18] Borja Balle and Yu-Xiang Wang. Improving the gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. In International Conference on Machine Learning, 2018
[CB17] Henry Corrigan-Gibe and Dan Bonch. Prio: Private, robust, and scalable computa- tion of aggregate statisties. In Aditya Akella and Jon Howell, editors, 14th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2017, Boston, MA, USA, March 27-29, 2017, pages 259-282. USENIX Association, 2017
[CCT 24] Geeticka Chauhan, Steve Chien, Om Thakkar, Abhradeep Thakurta, and Arun Narayanan. Training large asr encoders with differential privacy. In 2024 IEEE Spoken Language Technology Workshop (SI.T), pages 102-109. IEEE, 2024.
[5] Lynn Chua, Badih Ghazi, Charlie Harrison, Pritish Kamath, Ravi Kumar, Ethan Jacob Leeman, Pasin Manurangsi, Amer Sinha, and Chiyuan Zhang. Balls-and and bins sam- pling for DP-SGD. In The 28th International Conference on Artificial Intelligence and Statistics, 2025.
[CIK+24] Wei-Ning Chen, Berivan Isik, Peter Kairouz, Albert No, Sewoong Oh, and Zheng Xu. Improved Communication-privann trade-offs in 12 mean estimation under streaming differential privacy. In Proceedings of the 41st International Conference on Machine Learning, (CML'24. JMLR.org, 2024.
[CJMP22] Albert Cheu, Matthew Joseph, Jieming Mao, and Binghui Peng. Shuffle private stochastic convex optimization. In The Tenth International Conference on Learning Representations, ICLR, 2022.
[CK020] Wei-Ning Chen, Peter Kairouz, and Ayfer Özgür. Breaking the communication- privacy-accuracy trilemma. arXiv preprint arXiv:2007.1170) 2020.
[CLR17] Hao Chen, Kim Laine, and Peter Rindal. Fast private set intersection from ho- momorphic encryption. In Bhavani M. Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu, editors, ACM CCS 2017, pages 1243-1255. ACM Press, Octo- ber / November 2017.
12

---

[CMS11] Kamalika Chaudhuri, Claire Monteleoni, and Anand D. Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12(29):1069- 1 1109, 2011.
[CSOK23] Wei-Ning Chen, Dan Song, Ayfer Ozgur, and Peter Kairouz. Privacy amplification via compression: Achieving the optimal aaraac-accuracy-commme in distributed mean estimation. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
trade-off
[CSS12] T. H. Hubert Chan, Elaine Shi, and Dawn Song. Privacy-preseen preserving stream aggrega- tion with fault tolerance. In Angelos D. Keromytis, editor, Financial Cryptogruphy and Data Security, pages 200-214, Berlin, Heidelberg, 2012. Springer Berlin Heidel- berg.
[DCO25] Andy Dong, Wei-Ning Chen, and Ayfer Ozgur. Leveraging randommess in model and data partitioning for privacy amplification. arXiv preprint arXiv:2503.03045 2025.
[dCP22a] Leo de Castro and Anitgoni Polychroniadou. Lightweight, maliciously secure veri- fiable function secret sharing. In Orr Dunkelman and Stefan Dziembowski, editors, Advances Cryptology- EUROCRYPT 2022, pages 150-179, Cham, 2022, Springer International Publishing.
[dCP22b] Leo de Castro and Antigoni Polychroniadou. Lightweight, maliciously secure veri- fiable function secret sharing. In Orr Dunkelman and Stefan Dziembowski, editors, EUROCRYPT 2022, Part volume 13275 of LNCS, pages 150-179. Springer, Cham, May/ June 2022.
[DJW18] John C. Duchi, Michael I. Jordan, and Martin J. Wainwright. Minimax optimal proce- dures for locally private estimation. Journal of the Americun Statistical Association, 113(521):182-2011 2018.
[DK12] Michael Drmota and Reinhard Kutzelnigg. A precise analysis of cuckoo hashing. ACM Trans. Algorithms, 8(2), April 2012.
[DKM+06] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Advances in Cryptology (EUROCRYPT volume 4004 of Lecture Notes in Computer Science, pages 486-503. Springer Verlag, 2006.
[DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise sensitivity in private data analysis. In Shai Halevi and Tal Rabin, editors, Theory of Cryptogruphy, pages 265-284, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg.
[DR14] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found. Trends Theor Comput. Sci., 93344):211440 2014.
[DR16] Cynthia Dwork and Guy N. Rothblum. Concentrated differential privacy. CORR, abs/1603.01883 000.00187,4000 2016.
[DR19] John C. Duchi and Ryan Rogers. Lower bounds for locally private estimation via communication complexity. In Conference Learning Theory, COLT, pages 1 1161- 1191, 2019.
[DRR188] Daniel Demmler, Peter Rindal, Mike Rosulck, and Ni Trieu. PIR-PSI: Scaling private contact discovery. PoPETs, 201 159- October 2018.
[DRS22] Jinshuo Dong, Aaron Roth, and Weijie Su. Gaussian differential privacy. Journal of the Royal Statistical Society Series B: Statistical Methodology, 84(1):3-37, 02 2022.
[BPK14] Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. Rappor: Randomized aggre- gatable privacy-preserving ordinal response. In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, CCS '14, page 1054-1067, New York, NY, USA, 2014. Association for Computing Machinery.
13

---

[FHNP16] Michael J. Freedman, Carmit Hazay, Kobbi Nissim, and Benny Pinkas. Efficient set intersection with simulation-be based security. Journal of Cryptology, 29(1):115-155, January 2016.
[FM12] Alan Frieze and Páll Melsted. Maximum matchings in random bipartite graphs and the space utilization of cuckoo hash tables. Random Structures & Algorithms, Algorithmm,41(3) 4133)3334 364, 2012.
[FNNT22] Vitaly Feldman, Jelani Nelson, Huy Nguyen, and Kunal Talwar. Private frequency es- timation via projective geometry. In Kamalika Chaudhuri. Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th In- termtiional Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 6418-6433. PMLR, 2022.
[FP12] Nikolaos Fountoulakis and Konstantinos Panagiotou. Sharp load thresholds for cuckoo hashing. Random Struciures & Algorithms, 41 (1333306-333, 2012.
[FE166] Giulia Fanti, Vasyl Pihur, and Úlfar Erlingsson. Building a RAPPOR with the un- known: Privcc-preserving learning of associations and data dictionaries. Proc. Priv. Enhancing Technol., 2016(3):41-6) 2016.
[FS25a] Vitaly Feldman and Moshe Shenfeld. Efficient computation of the privacy loss distri- bution for random allocation, 2025.
[FS25b] Vitaly Feldman and Moshe Shenfeld. Privacy amplification by random allocation, 2025.
[FT21] Vitaly Feldman and Kunal Talwar. Lossless compression of efficient private local randomizers. In Marina Meila and Tong Zhang, editors, JCML, volume 139 of Pro- ceedings of Machine Learning Research, pages 3208-3219. PMLR, 2021.
[GI14] Niv Gilboa and Yuval Ishai. Distributed point functions and their applications. In Phong Q Nguyen and Elisabeth Oswald, editors, Advances in Cryptology - EURO- CRYPT 2014, pages 640-658, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg.
[GKKM22] Badih Ghazi, Pritish Kamath, Ravi Kumar, and Pasin Manurangsi. Faster privacy accounting via evolving discretization. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song. Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 7470-7483. PMLR, 17-23 Jul 2022.
[GKM+21] Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Rasmus Pagh, and Amer Sinha. Differ- entially private aggregation in the shuffle model: Almost central accuracy in almost a single message. In Proceedings of the 38th International Conference on Machine Learning, ICML. pages 3692-3701, 2021.
[GLW21] Sivakanth Gopi, Yin Tat Lee, and Lukas Wutschitz. Numerical composition of differ- ential privacy. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 11631-11642. Curran Associates, Inc., 2021.
[GMPV20] Badih Ghazi, Pasin Manurangsi, Rasmus Pagh, and Ameya Velingker. Private aggre- gation from fewer anonymous messages. In Advances in Cryptology EUROCRYPT 2020 39th Annual International Conference the Theory and Applications of Cryp- tographic Techniques, Proceedings, Part 11, pages 798-827, 2020.
[MRR88] Robert Helmer, Anthony Miyaguchi, and Eric Rescorla. Testing privacy- preserving telemetry with prio. https://hacke: http://haccss..milllaaaaaa mozilla. org///08///1000 testing--rriii pprivacy-preeervig--ee teteerii--geeeeettttttttttt---ae
2018.
[2SW+22] Edward J Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. LoRA: Low-rank adaptation of large language models. In International Conference on Learning Representations, 2022.
14

---

[JL84] William B. Johnson and Joram Lindenstrauss. Extensions of lipschitz mappings into hilbert space. Contemporary mathematics. 26:189-206, 1984.
[KH21] Antti Koskela and Antti Honkela. Computing differential privacy guarantees for het- erogeneous compositions using fft, 2021.
[KKPPR24] Erki Küllots, Toomas Krips, Hendrik Ferikson, and Pille Dullonen-Raudverr Slamp- fss: Two-party multi-point function secret sharing from simple linear algebra. Cryptol- ogy ePrint Archive, Report 2024/1390 1394, 2024. luttps://eprint. iacr. org/2024/ 1394. pdd
08L S. P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova, and A. Smith. What we learn privately? In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 531-540 2008.
[KMW08] Adam Kirsch, Michael Mitzenmacher, and Udi Wieder. More robust hashing: Cuckoo hashing with stash. In Dan Halperin and Kurt Mehlhorn, editors, Algorithms ESA 2008, pages 61 1-2,, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg.
[KOV15] Peter Kairouz, Sewoong Oh, and Pramod Viswanath. Secure multi-party differential privacy. In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems 28, pages 2008-2016. Curran Associates, Inc., 2015.
[Kri09] Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
[LCB10] Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online]. Available: http://yannn http://yan.lecun..co http://www..cu...o/eee//////aeee wwt..///////bniiisttttoo 2, 2010.
[LV10] Y. Lyubarskii and R. Vershynin. Uncertainty principles and vector quantization. In- formation Theory, IEEE Transactions on, 56(7):3491-3501 2010.
[MM18] Sebastian Meiser and Esfandiar Mohammadi. Tight on budget? tight bounds for r-fold approximate differential privacy. In Proceedings of the 2018 ACM SIGSAC Confer- ence on Computer and Communications Security, CCS 18, page 247-264, New York, NY, USA, 2018. Association for Computing Machinery.
[MMR 17] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera y Arcas. Communication efficient learning of deep networks from decentralized data. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, AISTATS, pages 1273-1282) 2017.
[MTZ19] Ilya Mironov, Kunal Talwar, and Li Zhang. Rényi differential privacy of the sampled gaussian mechanism. ArXiv, abs/1 908/ 10530, 2019.
[6XY+16] Thông T. Nguyên, Xiaokui Xiao, Yin Yang. Siu Cheung Hui, Hyejin Shin, and Junbum Shin. Collecting and analyzing data from smart device users with local differential privacy. CORR, abs/1 05053. 2016
[PRO1] Rasmus Pagh and Flemming Friche Rodler. Cuckoo hashing. In Proceedings of the 9th Annual European Symposium on Algorithms, ESA '01, page 121-133, Berlin, Heidelberg, 2001. Verila.r-Verlag.
[PSZ14] Benny Pinkas, Thomas Schneider, and Michael Zohner. Faster private set intersection based on OT extension. In Kevin Fu and Jaeyeon Jung, editors, USENIX Security 2014, pages 797-812. USENIX Association, August 2014.
[RKH*21] 21] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sand- hini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever. Learning transferable visual models from natural lan- guage supervision. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 8748-8763. PMLR, 18-24 Jul 2021. Model at https: // githhb.. com com/oppnai/CLIPP
15

---

[ROCT24] Guy N. Rothblum, Eran Omri, Junye Chen, and Kunal Talwar. PINE: Efficient verifi- cation of a euclidean norm bound of a Secret- vector. In 33rd USENIX Security Symposium (USENIX Security 24), pages USENIX Association.
Philadelphia, PA, August 2024.
[RSWP22] Mayank Rathee, Conghao Shen, Sameer Wagh, and Raluca Ada Popa. ELSA: secure aggregation for federated learning with malicious actors. IACR Cryptol. ePrint Arch., page 1695, 2022.
[RU23] Olivia Röhrig and Maxim Urschumzew. dpsa4fl: Differential privacy for federated machine learning with PRIO, 2023.
[SFZ*14] 14] Chongjing Sun, Yan Fu, Junlin Zhou, Hui Gao, et al. Personalized crivacy-preservve frequent itemset mining using randomized response. The Scientific World Journal, 2014, 2014.
[SGRR19] Phillipp Schoppmann, Adrià Gascón, Leonie Reichert, and Mariana Raykova. Dis- tributed vector-OLE: Improved constructions and implementation. In Lorenzo Caval- laro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz, editors, ACM CCS 2019, pages 1055-1072. ACM Press, November 2019.
[SMM19] David Sommer, Sebastian Meiser, and Esfandiar Mohammadi. Privacy loss classes: The central limit theorem in differential privacy. Proceedings on Privacy Enhancing Technologies, 2019:245-269, 04 2019.
[Ste22] Thomas Steinke. Composition of differential privacy & privacy amplification by sub- sampling, 2022.
[SYKM17] Ananda Theertha Suresh, Felix X. Yu, Sanjiv Kumar, and H. Brendan McMahan. Distributed mean estimation with limited communication. In Proceedings of the 34th International Conference on Machine Learning. 2017.
[Tal22] Kunal Talwar. Differential secrecy for distributed data and applications to robust dif- ferentially secure vector summation. In L. Elisa Celis, editor, 3rd Symposium on Foun- dations of Responsible Computing, FORC 2022, June 6-8, 2022, Cambridge, MA, USA, volume 218 of LIPIcs, pages 7:1-7:16. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2022.
[TWM 24] Kunal Talwar, Shan Wang, Audra McMillan, Vitaly Feldman, Pansy Bansal, Bailey Basile, Aine Cahill, Yi Sheng Chan, Mike Chatzidakis, Junye Chen, Oliver R. A. Chick, Mona Chitnis, Suman Ganta, Yusuf Goren, Filip Granqvist, Kristine Guo, Frederic Jacobs, Omid Javidbakht, Albert Liu, Richard Low, Dan Mascenik, Steve Myers, David Park, Wonhee Park, Gianni Parsa, Tommy Pauly, Christian Priebe, Re- han Rishi, Guy N. Rothblum, Congzheng Song, Linmao Song, Karl Tarbe, Sebastian Vogt, Shundong Zhou, Vojta Jina, Michael Scaria, and Luke Winstrom. Samplable anonymous aggregation for private federated data analysis. In Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security, CCS '24 page 2859-2873, New York, NY, USA, 2024. Association for Computing Machinery.
[VBBP+21] Shay Vargaftik, Ran Ben-Basat, Amit Portnoy, Gal Mendelson, Yaniv Ben-Itzhak, and Michael Mitzenmacher. Drive: One-bit distributed mean estimation. In M. Ranzato, A. Beygelzimer Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 362-377. Curran Asso- ciates, Inc., 2021.
[VBBP+22] Shay Vargaftik, Ran Ben-Basat, Amit Portnoy, Gal Mendelson, Yaniv Ben Itzhak, and Michael Mitzenmacher. Eden: Communication-effie and robust distributed mean estimation for federated learning. In Proceedings of the 39th International Conference on Machine Learning, 2022.
[WBK21] Yu-Xian Ju-Xiang Wang, Borja Balle, and Shiva Kasiviswanathan. Subsampled rényi differ- ential privacy and analytical moments accountant. Journal of Privacy and Confiden- tiality, 10(2), 2021.
16

---

[YB18] Min Ye and Alexander Barg. Optimal schemes for discrete distribution estimation under locally differential privacy. IEEE Trans. Inf. Theory, 64(8):5662-5676, 2018.
[ZDW22] Yuqing Zhu, Jinshuo Dong, and Yu-Xiang Wang. Optimal accounting of differential privacy via characteristic function. In Gustau Camps- Valls, Francisco J. R. Ruiz, and Isabel Valera, editors. Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 4782-48 122-4817 PMLR, 28-30 Mar 2022.
[ZW19] Yuqing Zhu and Yu-Xiang Wang. Poission subsampled rényi differential privacy. In International Conference on Machine Learning, pages 7634-7642. PMLR, 2019.
[ZWC+22] 22] Mingxun Zhou, Tianhao Wang, T.-H. Hubert Chan, Giulia Fanti, and Elaine Shi. Lo- cally differentially private sparse vector aggregation. In 43rd IEEE Symposium on Security and Privacy, SP, pages 4224439,4 2022.
17

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction summarize our contributions, that are detailed in the rest of the paper and the Supplementary material.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss limitations in the conclusions section, where they fit better with the open questions.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech- speech-to-text system might not be used reliably provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
18

---

Answer:
[Yes]
Justification:
All theorems state their assumptions, and are proven in the main paper or the supplement.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data provided not)?
Answer: [Yes]
Justification: Our algorithms are described in full detail. All experiments are detailed in the text, or in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature the contribution. For example
(a) the contribution primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results way produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case au- thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
19

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [No]
Justification: Our main contribution is algorithmic, and the algorithm is described with very detailed pscudocode. The experiments in the paper are fully described. We evaluate standard ML benchmarks.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co
for more details.
While we encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //nips. cttps//cccpbbbbc/ccccccccc wwwpce/gguueeeeeee Shtps//CooSSSeeeeeeeeee onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer:
[Yes]
Justification:
All details described in the paper or the supplement.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should presented in the core the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification:
We provide error bars for our experiments on real data.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
20

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (c.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative еπτог rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
we describe the computational setup of our algorithms in the supplement.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't t make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer:
[Yes]
Justification:
The paper conforms to the NeurlPs code of ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: This paper presents work whose goal is advance the field of private and secure data analysis. There are many potential societal consequences of our work, none which we feel must be specifically highlighted.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
21

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: the paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines restrictions to access the model or implementing safery filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: the paper only uses standard benchmarks and acknowledges/cites them.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
22

---

If assets are released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, wwtppppppppehooooo cow com/datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and the documenta- tion provided alongside the assets?
Answer: [NA]
Justification: the paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text instructions given to participants and sereenshots, applicable, well as details about compensation (if any)?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper deseribe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
23

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: the core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy haatpe///berrissccc/oooeereeeeee for what should or should not be described.
24

---

A Additional Related Work
As discussed above, Prio was introduced in [C177. and triggered a long line of research on ef- ficient validity proofs for various predicates of interest. Perhaps most related to our work is POPLAR [BBCG+2I], which uses Distributed Point Functions (DPFs) to allow clients to com- municate 1-sparse vectors in a high-dimensional space. They are used in that work to solve heavy hitters over large alphabet, where the servers together run a protocol to compute the heavy hitters. In their work, the aggregate vectors is never constructed, and hence the DPFs there are optimized for query access: at any step, the servers want compute a specific entry of the aggregate vector. In contrast, we are interested in the setting when the whole aggregate vector is needed, and this leads to different trade-offs in our use of DPFs.
We consider not just single-point DPFs, as used in POPLAR, but rather generalization for larger number of non-zero evaluations. [BCGIT8] also consider such multi-point functions and improve upon the naive implementation of a k-sparse DPF using l single-point DPF instantiations. Multi- point function secret sharing has also been optimized using cuckoo hashing [ACLS18] [SGRR19 dCP22b). They use cuckoo hashing to break one vector with k non-zero entries into k' > k smaller vectors with one non-zero entry each, after which standard DPF keys are constructed for those k' vectors. Applying cuckoo hashing in this way incurs roughly 2x-3x overhead in the total number of vector entries, dependent on the number of hash functions chosen and the cuckoo hashing memory overhead. While these prior work didn't focus to block-sparse functions would result in a similar 2x-3x overhead in terms of the total number of blocks and thus also the total number of large PRG evaluations (with output length B). Our construction applies cuckoo hashing differently and avoids this computational overhead. Finally, we remark that similar cuckoo hashing-based approaches [CLR17 DRRT18 FHNP16 PSZ14 have also been used in the context of private set intersection.
block-sparse DPFs, applying their methodlogy
Another recent work in this line of research [BBC+23] uses projections, which may at first seem related to our work. Unlike our work, these arithmetic sketches are designed for the servers to be able to verify certain properties efficiently, without any help from the client. In contrast, our use of sketching is extraneous to the cryptographic protocol, and helps us reduce the client to server communication.
The fact that differential privacy guarantees get amplified when the mechanism is run on ran- dom subsample (that stays hidden) was first shown by Kasiviswanathan et al. [KLN+08) and has come to be known as privacy amplification by sampling. Abadi al. (ACG* 16) first showed that careful privacy accounting tracking the moments of the privacy loss random variable, and numer- ical privacy accounting techniques can provide significantly better privacy bounds. In effect, this approach tracks the Renyi DP parameters [MTZ19 or Concentrated DP DRI6 [S166 parame- ters. Subsequent works have further improved numerical accounting techniques for the Gaussian mechanism (BI18) and for various subsampling methods [WBK2] [BG20 Tighter bounds on composition of mechanisms can be computed by more carcfully tracking the distribution of the pri- vacy loss random variable, and a beautiful line of work 15 DRS22 MMI8, SMM19 KH21 GLW21 GKKM22 ZDW22]. Numerical accounting for privacy amplification for a specific sam- pling technique we use has been studied recently in [CGH 25 FS25b).
The Prio architecture has been deployed at scale for several applications, including by Mozilla for private telemetry measurement [HMRIS I8] and by several parties to enable private measurements of pandemic data in Exposure Notification Private Analytics (ENPA) [AG21]. Talwar et al. [TWM+24) show how Prio can be combined with other primitives to build an aggregation system for differen- tially private computations.
We remark that the problem of vector aggregation has attracted a lot of attention in different models of differential privacy. Vector aggregation crucial primitive for several applications, such as deep learning in the federated setting [ACG 16, 1MR+17), frequent itemset mining [SFZ+ 144, linear regression INXY+ 16), and stochastic optimization [CMSIT CJMP22. The privacy- accuracy trade-off's for vector aggregation are well-understood for central DP [DKM (KMM+66, for lo- cal DP [BNO08 CSS12 DR19 DJWI8 1DF+18 AFT22], as well as for shuffle DP [BBGNI9 BBGN20 GMPV20 GKM+21 J. Several works have addressed the question of reducing the com- munication cost of private aggregation, the local model (CKO20) FT21 + and under
sparsity assumptions [B15 FPE16 YB18 AS19 22). While the shuffle model can allow
25

---

for accurate vector aggregation [GKM 211, recent work [AFN'2 24] has shown that for large D, the number of messages per client must be very large, thus motivating an aggregation functionality.
Our use of subsampling to reduce communication in private vector aggregation is closely related to work aggregation in the single trusted server, secure multi-party aggregation and multi-message shuffling models [CSOK23 CIK 24]. Aside from different trust model, our work crucially relies on blocking to reduce the sparsity. Sparsity constraints also make regular Poisson subsampling less suitable for our application and necessitate the use of sampling schemes that require more involved privacy analysis.
Very recent works. After a preliminary version of our work was made public, we were made aware of an independent and concurrent work [BGH that studies the problem of communicating m-sparse vectors in the two-server setting. They compare three different schemes for this task and empirically compare them. Their "big-state" DMPF is equivalent to naive scheme and their probabilistic batch codes (PBC) construction uses cuckoo hashing in a black-box way, similarly to the prior works discussed above. They also propose new scheme based on Oblivious Key-value stores (OKVS), which obtains constant-factor improvements in the server runtime compared to the other two schemes for some range of sparsity. To keep the server-side computation low, the OK- based schemes (which allow a range of tradeoff) incur at least 2 communication overhead.
Beyond these differences in various performance measures, of our main contributions is identi- fying -porriipy as a property that lends itself both to significant savings in DPF constructions and to efficient -prraccyrreeevingggg aggregation. IBGH+22 don't focus block-sparse DPFs, but their approaches can be applied towards block-sparse constructions. The cuckoo haaioon based con- structions would incur 3 overhead in the number of large PRG evaluations (as discussed above). The OK V-bssed schemes incur the above 2x communication overhead.
Another recent work [KKEPR24] also provides efficient multi-point DPF construction (they also don't focus on block-sparsity. Their scheme requires the client to solve linear systems with equations and at least (k + A) unknowns over a field of size 2 So even if the blocks are small, for large the client work is larger than in our scheme.
B Additional Preliminaries
Definition B.1. Function Secret Sharing (BGI15) Let =e be a class of functions with imput domain and output group G, and ler X N be security parameter. 2-party function secret sharing (FSS) scheme is pair of algorithms with the following syntax:
. Gen[1>, f) is probabilistic, polynomial-time key generation algorithm, which on input 1x and description of function f outputs tuple of keys (Ko, k1).
Eval(i, ki, x)) is a polynomial-time evaluation algorithm,, which on input server index E {0, 1}, key k. and imput x I, outputs a group element y G.
Given some allowable leakage function Leak: 10, - {0, 13* and parameter 7 [0, 1), we require the following two properties:
Correctness: For any f E F and any I, we have that
Prl
Σ
Eval(b, kb, x) = f(x)] 2 1 1-7,
bE(0,1}
Security: For any b E {0, 1}. there exists a ppt simulator such that for any polynomial-size function f E F::
(kol(ko, k1) - Gen(1> ~ (ks, +- Simm,1> Leaks(
Note that we have defined relaxed notion of correctness here, where allow small probability y of incorrect evaluation. While y will be 0 for some of our constructions, the most efficient version of our protocol will have a 7 that is polynomially small in the sparsity k.
We define 1-sparse and d-block-sparse distributed point functions, which are instantiations of FSS for specific families of sparse functions:
26

---

Definition B.2 (Distributed Point Function (DPF)), A point fa. for E {0, 1) and B E G is defined to be the function f {0, 1 + G such that f(a) = 3 and f(x) = 0 for æ # a. A DPF an FSS for the family of all point functions.
Definition B.3 (k-block-sparse DPF), A k-block-sparse function fa.3 with block size B for fa?...., o-..,, where a' {0, 1]d and 3 {,00 ,...., ..0.......-11 and 3 {%).... ..... -B GB defined to be the function f {0, 1] B - G such that f(a'llj) 33 and f(x) for x + a'lli with j E [B] and i E [k]. A k-block-sparse DPF an FSS for the family of all k-block-
sparse functions.
Cuckoo Hashing. Cuckoo Hashing [PRO]] is an algorithm for building hash tables with worst case constant lookup time. The hash table depends two (or more) hash functions, and each item is placed in location specified by one of the hash values. When inserting items from a universe U into a cuckoo hash table of size k, the hash functions map U to [b.. When the hash functions are truly random, as long as k is a constant fraction of k, there a way to assign each item to one of its hash locations while avoiding any collision:
Theorem B.1. Cuckoo Hashing (DK22) Suppose that E {0,1) is fixed. The probability that cuckoo hash of ls [(1 c)k} data points into two tables of size i succeeds is equal to:
(2c²- 5c + 5)(1 - c)a 1
+
c)
122
Note that if 0.32, this simplifies to about 1 - 1/k- O(1/k2). Therefore, this choice of leads to failure probability of Ō(1/k) Variants of cuckoo hashing where more than hash functions are used can improve the space efficiency of the data structure. E.g. using 4 hash functions allows for an efficiency close to 0.97 with probability approaching FP12 FM12).
We will use the following standard result in differential privacy.
Theorem B.2 (Gaussian Mechanism [KM* DRI4)). Let e, 8 E (0, Let A: (RD)+ RD be the mechanism that for sequence of vectors U1,-.., Un RDD outputs Σ, 4 + oo If for all i E [n), the input v, is restricted to ||v:lla S and (a/s)² 2 2 (lo5(1.2//0)) is (E, 8) differrrennylll private. We refer to a as the scale of the mechanism. In this context s is the sensitivity of the sum adding/deleting an element.
then A
C Pseudocode for sampling schemes
D Missing Proofs from
Section
Proof of Theorem 3.1
First, note that E(w"] vd for all [n]. Therefore we have
E W|[
E
w v + N(O 02 I
je(n
12
Σ [llw] - -11 + +0²D
nE
[|| - 2 113] +
< n1 1) K
22
In L'
Here we have used the fact that the variance of the w decomposes across A blocks, where each block contributed p(1 - p) times the square of its value when non-zero (which is L(A/k)) and p = d. is the probability of a block being non-zero.
3
27

---

SampledVector (Partitioned Subsampling)
Input: vector E RDD Parameters: dimension D. blocksize B, sparsity &, sampling probability A
D/B, blockwise &g bound L.
Split the block indices into & consecutive subsets = (
for j e [k].
Select an index i; randomly and uniformly from Sj and define = {ii)se
3. Define the subsampled (and clipped) v' as
clip (v)
if otherwise
where clip, ) is defined as if || and |
2, otherwise.
Output w v'.
(a) w-wise 1-sparse sampling scheme
Secpled (Truncated Poisson Subsampling)
Input:
vector RDD Parameters: dimension D, blocksize B, sparsity k, sampling probability 2.
A D/B, blockwise & bound L.
1. Select subset To by picking each coordinate in fl,..., A} independently with probability g.
If [o > k, let be random subset of Io of size k. Else set = Jo-
Let x: = E|[ = F.jmin(Bin(A, q); k)] under this sampling process.
Define the subsampled (and clipped) vf as
clip (vv)
if otherwise
o
Output of.
(b) k-sparse sampling scheme
Figure 6: Pseudocode for Subsampling algorithms.
E Proof of Theorem 3,2
We will need the following asymptotic bound on the privacy of Poisson subsampling of the Gaussian noise addition.
Lemma E.1 ((ACG+16). Let Ai,..., BR - RR. be a sequence of Gaussian noise ad- dition algorithms with sensitivity s and noise scale a. Let P Pa(AI...., Ar) be the Poisson sub- sampling scheme in which each user's data is used in each step with probability n randomly and independently (of other users and steps). Then, there exist a constant e such that for every 8 >> 0, if a/s 2 an / log((1/) then Py Pr Ar) satisfies (e, 8)-P for O(n (olog(1/)),
Proof of Theorem 3.2 We first observe that we can analyze algorithm as an independent com- position A ....... Ag. with the instance A, outputting the coordinates of W in the set S, {( 1) +1 .j.. for j E [k). For convenience of notation we will analyze A₁ (with the rest being identical). Observe that the output of A₁ is Wi...., ... W WArk- Now, by the definition of the sampling scheme any user's data is summed in exactly one (uniformly chosen) of Wi...., W Wayk- Each of these algorithms is Gaussian noise addition with sensitivity LÁ k and scale a. This implies that we can apply results for privacy amplification by allocation for Gaussian noise from [FS25b) to analyze this algorithm. For the analytic results we use an upper bound on the privacy parameters of random allocation in terms of Poisson subsampling for Gaussian noise. Specifically, for every k-wwise composition of 1 out of A/k random allocation for Gaussian noise addition algorithms satisfies (c, 5p Ad, + DDP, where (c, 6r) are the privacy parameters of A A-step Poisson subsam-
- =0) 24 In ($)) Here (Eu, 66) are the privacy pling scheme with rate 7 = -l))) for ? = (e + e parameters of each Gaussian noise addition. Note that the sensitivity of the aggregate in each block
28

---

LA _A/22l((55/(16)) (Thm. B.2 We
LA/k. Therefore, by setting do 63(3 we get
set 8' = =6/3 and note that by the first part of our assumption on o O/L, - and therefore
e 50 - 3Eg. Now the second part of our assumption of a L implies that
k
3k
7 S 35u
In
2A
3/A In (154/ (46))
h:
3h:
In
ko
2A
8
31. (155A/nn111////11 (48)) 1/2.
vko
This implies that 17 AA Now, by Lemma E.1 the A-step Poisson subsampling scheme with subsampling rate 77 is (c, (e,8/3)-DD for
== L 1o/(1/))
Here we note that the conditions of the lemma translate to
ak k
2
A logg((1/))
LA
or equivalently, - 2 cv A (loog(//0) (which is ensured by the third part of our assumption). Finally, noting that Aog + 8' < 25/3, we get the claimed bound.
F Ensuring bisek-wise norm bound
We now formally show that one can reduce the problem of computing means of lg bounded vectors to our setting of block-wise bounded norm. Without loss of generality, we can assume that each input vector has & norm 1. Our main reduction is based on the techniques developed by Asi er al. [AFN+23] in the context of communication--fficie. algorithms for mean estimation with local differential privacy. Their randomizer for mean estimation relies on randomized dimensionality reduction followed by optimal differentially private randomizer in lower dimension referred to as PrivUnit. PrivUnit requires vector of unit length as an input, whereas the randomized dimensionality reductions they use result in vectors of varying lengths. Asi et al. apply scaling to ensure that the norm condition satisfied and develop several techniques for the analysis of the error resulting from this step. We observe that their dimensionality reductions can be used just as (randomized) linear maps (in the same dimension) with each block B coordinates in the image corresponding to the projection of the original input into B dimensions. Thus can apply clipping/scaling to ensure that block norms are upper bounded and then analyze the resulting error in essentially the same way as in [AFN+23] 23). Our first application of this approach shows that random rotation with simple block norm clipping / /B/D achieves expected squared error of 1/B I/B.
Theorem F.1. For a vector U1,..., VA E RD, where ii B let blkclip denote the vector u1. UAS such that for every [A], u; = clip (V)) Let DxD be randomly and uniformly chosen rotation matrix. Then for every v E TRD such that ||0||2 11
E | (ITT t
21 = 0
B
Our proof of this result relies on the following lemma from (AFN 23
Lemma F2. Let x be a random unit vector on the unit ball of R and z be the projection of x onto the last B coordinates. We have
E - -
=
BBD
29

---

Proof of Theorem F.7 We first note that the squared enror scales quadratically with the norm of and therefore it is sufficient to prove the theorem for unit norm v. For given U, Let and wi..... Wi be the blocks of size B in Observe that when U is randomly chosen rotation matrix, w random and uniform unit vector. Naturally, the uniform distribution over random unit vectors is not affected by permuting coordinates and therefore for every i E [A] we can apply Lemma F22 to get
Uv
Blllallaa B/D O
BD
In addition, by the same symmetry, we have that
B D
Blll Blllul =
Combining these two results, we have
- =112] = E
(UK - U0112 -
E
t
[bbkkcipp - m
E
Σ
clip ( wi
iE/A
Σ KE[A]
(11uzll2 v BB/D) 2
[
B
= Σ KETA]
E
2 B/ 1| l22)
Σ y [( [VBID- - -11202 112)
= 22/B/D.
iE|Ai
=0 2 VB/D VBD/
= O(1BB)
While this method is simple describe and analyze, it is relatively inefficient as it requires D multiplications. We also show that a significantly more efficient scheme from [AFN*23] based on Subsampled Randomized Hadamard Transform (SHRT) can also be easily adapted to our setting the expense of somewhat worse Ö(1 ((1/BB) /B) expected squared error. Specifically, let W SHT denote the following distribution over random matrices: H E DDD is the Hadamard matrix, S E DxD is a random permutation matrix, and T Dx is diagonal matrix where Tú, are independent samples from the Rademacher distribution (that is, uniform over +l). An important (and well-known) property of this family of matrices is that multiplication by W and WT can be performed in time O(D log D) [AC06].
Theorem F.3. Let W E DxD be a randomly and uniformly chosen SHT matrix as described above. Then for every v E IR. such that ||ll|2 S 1,
(Wblkclipp v [1]]]= =0 (log² D
[[
E
B
Further, multiplication by W and W can be performed in time Oog D).
To prove this result, we first establish some relevant properties of SHRT.
Lemma F.4 ((AFN-2) 23D. Suppose WB SpHT is obtained with Sg being 13 x D uniform sam- pling matrix without replacement, Ht being Hadamard matrix and T being Rademacher diagonal matrix as above. Then for some constant C > 0, for any fixed BRD of unit Euclidean norm and 5 E (0, 1),
B log (B/6)/D <8.
Pr Wn
W - VD
> C Cy
30

---

In particular, choosing = 1/D implies that for some constant C₁ > 0.
B
I8 WB
[[WBul]]
S Ciy log (D)/D.
we restrict our attention to the case ||||| and let Wi..... Wa We. We note that matrix being a random uniform permutation implies that every B-block of coordinates in We corresponds to picking B coordinates of HT randomly and uniformly without replacement. Therefore, we can apply Lemma i [A]:
Proof of Theorem F.3 As in the proof of Theorem F.I
F.4 obtain that for every
log D) VD In addition, by the permutation symmetry of the distribution of S, we have that
(
E Elllwllell [ =
Flllwi D
Now, following the same steps as in the proof of Theorem F.1 we have
E || bikclips(We) =1|3] s 2/BBID
Σ ( BBBD |100112))
W
= -0(B
log D)
) =0
(log(D)
v B/D
B
vD
/B
G
Communicating 1-sparse vectors
common application of secure aggregation systems is to aggregate vectors that are 1-sparse (often known 1-hot vectors) k-sparse for a small k. Directly using DPFs for these vectors requires O(D) PRG re-seedings and thus can expensive. Noting that k-sparse vector is also k-block sparse, one can directly use PREAMBLE to reduce the server computation cost at modest increase communication cost. Alternately, in settings where we want to add noise in a distributed set- ting. RAPPOR [EPK14] and its cower-communicatiin variants such PI-RAPPOR [FT21] and SojietiveGGoomettRReepnsss [FNNT22) can be used along with Prio. Since 1-hot vectors become
after Hadamard transform, can view these vectors as Euclidean vec- vectors in { VVD b
tors in RDD and PREAMBLE efficiently communicate them. ProjetriveGeomettyResppsss particularly well-suited for this setup even without sampling, as the resulting message space is O(D)-dimensoonal and linear transformation of the input space. Thus one can aggregate in "mes- sage space": each message is 1-hot vector in message space, and we can add up these vectors using PREAMBLE. The linear transform go back to data space is simple post-processing and the privacy guarantee here can use privacy amplification by shuffling. Since we avoid sampling in this approach, it can scale larger n without incurring any additional utility overhead.
H k-block-sparse-DPF Construction Details
H.1 Secret-Sharing b-bllockspprrse Vectors
We first review the tree-based DPF construction from [BGI16), both for single bit outputs and for group element outputs (using notation). We then describe how we build on their techniques to construct efficient t-block-sparse DPFs.
Tree-based DPF of [BG116] The original tree-based DPF construction is formulated for one- sparse vectors without blocks. Let us suppose that the client wants to send a 1-sparse function f {0.1) 1)dd + {0, with an input domain size of D 2d, where the output is zero only on input {0, 1]d. Let define fi 10, + {0, 1} as the function that computes the sum
31

---

f((z) = Eve(o f(ally) where || denotes concatenation. Note that fa = f and each fi is 1-sparse. Let be the input that produces a non-zero output for ft.
In the tree-based construction an invariant holds every layer i in the tree. Servers and 2 hold functions 8;, 8 {0, 1 + {0, _ whose vectors of outputs are secret shares of TÚ Ea,, where rs is a (pseudo) random X-bit string and ea; is the basis vector with value at position a, and elsewhere. In other words, sx(x) - (x) is zero for & a; and is pseudorandom value r; for = ag. The servers also hold functions u4, U, {0. + {0, 1]. whose vectors of outputs are secret shares of e;. The client knows all secret-shared values.
When 0, defining these functions is simple: client with input x so: lg return constant X-bit string chosen at random, and sets vo = so(x) to()). It also sets up to return a random bit and vo (a)) ug (2:).
For the inductive step, we do the following:
Each server provisionally expands out their seeds using a PRG G: {0, - {0, 1)) We can think of the first half of the PRG's s output as the left and the second half as the right child in the tree. They parse for x E {0.1)'
s 1/ (x) [0) o/44 (+D G(t(())
G((()))))
Let by be such that a # a: l7, so that this is the term that needs to be corrected to zero The client computes the correction according to:
Cj-1 = 564= ( (asl 14 (aullb.)
and sends it to both servers. The servers then set, for each x E (0, and b E {0, 1J:
1 (x116) u.(x)1+11 (xrl(b] = (z|lbb - u;(x)
It is then easy to check that for x + oi. the equality uz(x) vz(x)) implies that 884 1 (x|lb) = 4--1 (x]lb)). Moreover for y = aillbr we have
(1) (2+ = 51/41 (v) u,(a))c+1 - (2) + v1(a))c+1
1//1(1) (441(1) - (u,(a,)) v ((as))cc+1
(14)(1) (((1(1)) -1.44
O.
Here the last step follows by definition of c++11-
Finally, we need correct the bit components. For this purpose, we compute two bit corrections. Recall that u:+1 (v) 1/+1 (3) for each & a.llb for b E {0,1]. We com- pute m4+1(0) (0) = (ax|(0)))
u (ag [0) + b, and similarly m1+1(1) u4+1 (agll1)- Us+1 (aall) [1] - (1 - 6;), and send both of these to the two servers. Similarly to above, the servers now do, for each x E {0, 1}. and each E (0. 1):
Us+1 (a: (b) (x|lB) - uc(x)m++1 (b) U (=|lb) (x|lb vz(x)
The correctness proof is identical to the one for the case.
Note that the multiplications above all have one of the arguments being bits this is point-wise multiplication. We have now verified that the invariant holds for (2 + 1).
We refer to the tuple (c,, (0) (1)) as a correction word, where is the seed correction and (0), (1) are the correction bits. Intuitively, since uz(y) = vz(y) for each & a,, each corree- tion word is only applied to one expanded seed in each level. For all other expanded seeds, the cor- rection word is either never applied (if u, (n) = ve(y) = 0) or applied twice (if u, u;(y) ns () = 1), in which case these two applications cancel out.
32

---

Non-zero output from group G. [GG16]] define variant of their construction where the output of the DPF on imput a outputs not 1, but rather a group element / E G. Given a convert(-) function, which converts X-bit string to group element in G, the changes to the construction are minimal. for all y & a. Since the DPF according to Definition B.2 should output 3 on input a, an additional correction word cd+1. which consists only of a seed correction, is constructed such that either convert(sa(a)) (asaaa))ccoeelle (ta +
Since the invariant holds, 8n (a) - in (a) * and (y) - i, (y)
cd+1 = B or conver((sa(a)) conver((ta(a)) Cd+1 = B, depending on whether ua(a) or va(a) is one.
The block-sparse case with block size B 2. We adapt the DPF construction of [BGII6) from point functions to block-sparse functions, where the output on any number of input values from a single block will be a non-zero group element. More formally, a block-sparse function fa.p with block size B for E {0, 13d and 3 ,
G is defined to be the function f {0. 1) + G such that l(all))) = 83 and f(x) = 0 for x # alli with j E [B].
To formulate block-sparse DPF based on tree-based DPF construction, for the final tree layer compared to the previous tree layers, such that the output is B Blog |G] bits rather than 2(x + 1) bits in the original construction. We call this G'.
a different PRG
1 11 (x|) B 1) G'(sa(x)) (441 (z [=]]0))] [ 1) G'(((z))
The correction word can be constructed analogously to the original construction, and we make use of convert(-) function, which maps log |G|-length bit string to an element in G. For any input x = alli for any j E [B], we set Cd41.; such that convert(s's) ( convertr))) ((amvee(((aax)))) (x)) +c411. = 3 or convert(s' (4 (x)) converl (1)++(())) - Ca+1. = Bj. depending on whether ua(a) or va(a))
is one.
This construction avoids the high cost of using the original DPF construction B times, both in terms of computation and communication. In particular, the original construction would involve B DPF keys of size (o B)) each, while this construction yields single DPF key of size O(d++B) B). DPF key generation with the original construction will involve O(d + log B) PRG evaluations for each of the keys, while our optimization involves (dd PRG evaluations, as well as one larger PRG evaluation, where the size of this PRG output scales with B. In the evaluation step, when the entire tree is evaluated, naively using the original DPF construction B times would result in B 2d+log B PRG evaluations, while our optimization involves only O(24) smaller and O(24) larger PRG evaluations.
The k-block-sparse case We now describe the idea of a construction for k-block-sparse DPFs, as specified in Definition B.3 Instead of a single index a; at each level, we have a set {af...., "), where k corresponds to the number of distinct i-bit prefixes in o, at most k. We will begin by formulating change to the construction that allows to share k-block-sparse vectors, which is naive extension to the block-sparse version of the DPF construction of [BG[16]. Later, we introduce an optimization reduce the number of correction words applied to each node.
The invariant on all tree layers except the lowest one is essentially the same as before, except that there are now i separate u and functions per correction word at each layer, and the client will send l correction words per layer. The PRG at the upper level now outputs 2(k - 1) additional bits, and the bit components of the expanded and corrected seeds secret shares of an indicator, which specifies which correction word, if any, will be applied next. As in the original construction, we maintain the goal that each correction word is applied only at most one expanded seed in that layer. In particular, the correction word with index expanded seed at position af E [2']. In the lowest layer, we can formulate a correction word, which is interpreted as a group element, by applying an idea analogous to that of the block-sparse case.
[X] level
[d] will be applied to the
For the goal of generating DPF keys for a b-block-sparse vector, this construction avoids the over- head of generating kB DPF keys from the original construction. We inherit all advantages of using blocks of size B from the block-sparse construction and obtain further savings by allowing k non- zero blocks. We can compare the the costs of naively using instantiations of a block-sparse DPF to those of a single k-block-sparse DPF instantiation. Asymptotically, the two approaches require
33

---

the same amount of communication, with identical DPF key sizes, and the DPF key generation re- quires the same number of PRG evaluations. The savings for the construction come in the form of computation savings for server evaluation, where the number of PRG evaluations decreases by factor of k; since servers must now evaluate a single tree, rather than l trees when instantiating a 1-block-sparse DPF & times. However, since each server applies up to k correction words at each level, the total server computation still depends linearly on k. This yields the following result
Theorem H.I. Let G {0, 1) + 1 (2,(+)))))) and G' {0,1]A + {0, 1) B flog [Gll be pseudo- random generators. Then there is a scheme (Gen, Eval) that defines a b-block-sparre DPF for the family of Rt-block-sparee functions faa,3 {0, 1] B - G with correctness error The key size kd(A+ + 4) + kB [og [G[]. I. In Gen the number of invocations of G is at most kd, and the number of invocations of G' is at most k. In Eval the number of invocations of G is at most d, and G' is invoked once. Evaluating the full vector requires 2d invocations of G and 2 invocations of G', and
OkDD) additional operations.
O B) PRG calls for each of the DPF keys, while using our k-block-sparse DPF key gener- ation requires O(24) small and 00 larger PRG calls.
Cuckoo Hashing. We next show how we can reduce the k-fold multiplicative overhead in the servers' computation using cuckoo hashing. The idea is to only have w control bits (rather than) k for each node in the tree as follows. In practice, we can set the constant w to be between 2 and 5.
At every layer i in the tree, there are k non-zero nodes, which have indices {af) We use k correction words per layer. Each tree node in the i-th layer is assigned w correction words. These correction words are selected using we hash functions (per layer i), where each hash function maps the 2 tree nodes to the set of correction words. The hash functions are public and known to both servers (they are chosen independently of the values of the DPF). The client assigns each non-zero node to one of the w correction words specified (for that node) by the hash functions. This assignment does depend on the non-zero indices of the DPF and must not be known to the servers. Cuckoo hashing [PROI] shows that for any set of k non-zere nodes (specified by the values () except with probability Ō(t) over the choice of the hash functions, the client can choose the assignment that there are no "collisions": no two non-zero nodes are mapped to the same correction word. In the case of failure. which occurs with probability at most O ).. the client will generate a outputs keys corresponding to the zero vector, which can trivially be realized by picking arbitrary assignment. This does not affect the security of the construction as the failure of cuckoo hashing is not revealed. It does however mean that the correct vector is sent with probability 1 - O ( ), rather than 1. For statistical applications, this small failure probability has little impact.
The correction words are now constructed and applied as usual, except for the fact that each correc- tion word now has only correction bits instead of k on each side and that one of only correction words is applied per expanded seed/node. The bit components of an expanded and corrected seed still correspond to an indicator specifying which single correction word is applied at the next layer, as before; however, it is no longer up to one of all & possible correction words that will be applied, but rather one of the possible correction words specified by the hash functions.
For simplicity, we present the formal construction by setting w = 2. The details can be found in Figures 7 [nd using helper function for DPF key generation in Figure to specify the construc- tions at each of the upper tree layers. Note that we formulate evaluation in Figure for a single path in the tree for simplicity; to reconstruct the entire vector instead of just one entry, all nodes in the tree can be evaluated using the same approach. In that case, the number of invocations of G is at most 24, and the number of invocations of G" is at most 2d.
Theorem H.2. Let G : (0, 1) - 10,1) 2]((+2) and G' 10, + 10, Dog [G]] be pseudo-
random generators. Also suppose (hr [hx)eeu+1] -12-1]
[ck] describes a set of random hash
functions. Then the scheme (Gen, Eval) from Figures 7 and is a k-block-sparse DPF for the
9
family of b-block-sparse functions fa,o {0, 1]d+log B + G with correctness error Ö(t). The key size is 3kd(A + 4) + 3KB log [G]] In Gen the number of invocations of G is at most kd, and the number of invocations of G' is at most k. In Eval the number of invocations of G is at most d, and G' is invoked once. Evaluating the full vector requires 2 invocations of G and 2 invocations of G', and (D) additional operations.
34

---

Remark H.3. Note that cuckoo hashing can yield different trade-offs from those in Theorem H.2 if more than 2 hash functions are used. For to achieve low faiture probability is approximately 3k. w = 4, the total number of required correction words to achieve a low failure probability can be reduced to be only about 1.03k [FP12 FMI2Y, leading to a key size of 1.03kd + 4) + 1.03k:B| [log [G] Increasing decreases the total number of correction words, and therefore the total key size and required communication, by a constant factor, the cost of increasing the total number of field operations per node by constant factor. The number of PRG evaluations does not depend on w.
the total number of required correction words
Remark H.4. Recall from related work the application of cuckoo hashing to multi- function secret sharing (ACLSI8 DRRTI8 SGRRT9 @CC22b)), where cuckoo hashing is applied directly to the k-spurse 2 -i-diennsional secret vector, constructing smaller vectors with a single entry each before generating DPF keys. In this approuch, the total number of vector entries, and therefore also the number of PRG evaluations, is 2 2 or 3 2 when 2 or 3 hash functions are used for cuckoo hashing, suggested by (DRRTI8). Because our application of cuckoo hashing is at the level of correction words within the DPF construction, it avoids this overhead and requires only 2d vector entries.
Proof of Theorem H.2 We prove both correctness and security of the scheme.
Correctness. We describe and argue correctness of our optimized k-block-sparse DPF construc- tion in a way that is analogous our arguments for the original construction of [BGL16]. The invariant for the k-sparse case that in layer of the tree construction, the k nodes corresponding to a; are non-zero, and all others are zero. In addition, we maintain the invariant that exactly one of the two bit components on the non-zere path is and the other is O. More formally, we would like that if x & ax (z)) = fz(z), (z) (x), and (x) = rx(x). Furthermore, we would like that for x E (ks, exactly one of u, = vx(x), and yi (xx = (x) should hold.
The function h; [2--1] + [3A]² maps one af in tree layer i to two correction words. We use cuckoo hashing to determine which of these two correction words will be applied for af defining function gi : [2i + {0, Due to cuckoo hashing, we know that this mapping exists for any k-block-sparse function given all h; with probability 1 O In the upper levels, the PRG
G: (0. 1)^ {0, 1) 2ax+1 output is parsed as follows:
4..11000004...00000//00000/00040 G(s((z))
= G(4(x))
In the original construction, the seed portion of the correction word was set in such a way as to set zero the node corresponding to a; bg]lo; where by is defined such that 0++1 A 0s 0gllbr Let us now analogously define by, defined such that af41 + af It is possible that there exist indices L + l' E [k]] such that 1/ = af_1 in which case we do not want to set the seed portion of the node corresponding to a | to O. For such an l, we set the seed portion of the corresponding correction word to random bit-string instead. For other l, we set the corresponding seed correction, specified by the gi ( output of h, h,(a,), as expected:
Ch44saaMaaaaa11 5/4 +
The corrected seed components are then for each x E 10, 13' and b E {0, 1}:
8:41 (I (b)) (x|(6)] - (144)) - [+]
(x|166]))) = (x((6) - (2(x) - (x(xx))))))))) (+)]]
35

---

It is then easy to check that for & af for all & E [k), the equalities (z(2) = (x(2) and q: (2) r((a))
imply that (1+1(1]16) = (x)66))))) Moreover for = 1|6; as long as & a++1, we have
(1+( - (4+1(y) = (1) un -n, (a
g ( (m
(1)+(() us vz(a
(44)( ((+1(y) (ur(a.) v,(a (h11a(a)))1
- (9:(a²) - r:(a (clc)) (af)11)
(1) (v+ 1c 1015
Here the last step follows by definition of Chep (ax)s=+
Finally, we need to correct the new bit components. For this purpose, we compute two bit cor- rections. Note that ui+1 (v) v++1(y) and g++((y) = ry) for each y 0i+1- On the other hand, when y E 03+1, we would like either (y) = (1) and (:+1 (y) # rv) (141(y) 1441 (v) and %++ (v) (v), depending (y) We set the bit corrections to: mhes (a (10)) (af) (0) (a (4/1((
+ (0+22(())))))++ + () a441)
Mhosi (a (af) (at1) (1) = (a/l1 - ( + 1) e a441)
(9+2(0))
Phots (a)4)a))9041 (a (0) = d't1(a/110) - (d)) 942(((00))+ = a41)
Phosi (ausaaaaaaa (of)) (1)
a441)
To apply the bit correction, the following is computed:
(++1(=]]b (=|lb)
(b) 9:(x) m (b)
(x1(b] (=+1 v, u, 1c]]0| (b) r((2) (())m... (
Z e (x]lb) (x(l))) - (,(x)) (x) (b) q: (x(x) (x)))))))))))))))))))
ret1 (x||b) = (x|1))) (x (=) (b) (x))))
The correctness proof is identical the one for the case when w/|b & 0141. Otherwise, when zi|b a4+1, we show that
(2) (b) (()) (x) (b) Ui+1 (x|lb) - est (x|lb) = (x41(x]ll) u, (s)
(v/41(x1()) (0))) - ri (z)
(/(( -
us (at
- (((()))((=))))>>.ttt))))))
(x)) -
- (o)
942(({{16)+ +1
Using analogous arguments, (+1 - (z]b) = gi+z (a Therefore, exactly one of either u4+1 (b]lbb) u (x)llb) or gy+i(y) (y) can hold, and the required invariant is maintained.
In the lowest layer, the PRG evaluated for each E [kt]
s (
... I| |
(a || =)==("))((aa))
t (a [10) ... (a' - - =('(((()(a))))
In a next step. we call the convert(-) function on each component of these outputs. The goal is to formulate one correction word for each of the k non-zero blocks.
More formally, we would like to choose correction words (ha (()))) for j E [B] such that 8841 (afIl)) let1 (a$1l5) 18:
(a-1 s' (afIl)) + ua(a' "aaa")nnrnta (j) + (hans1911))))))111
(a = (a (b)) + vala (alla")nnan(ae)mm + ra(a" ra(aa)) (cnen
36

---

Note that for & a, (zااع) = (xll)), ua(z) va(x), and qa(x) = rr(x), so s4+1(=115) t++1(2115) for all j E [B], regardless of the correction words.
ra(af) and ua(af) o, then ua(a²) # va(a²) and qa(a²) ra(af). Otherwise, qa(a²) * va(af). Exactly one of (d+1(x))) lj) and ( is independent of
For a', ga+1(a")
a (sy- By subtracting over G, we can find the target value of the other one and choose the correction word accordingly.
In a bit more detail: the client computes the sequence
(#4+1 (a'll)) - a' (a)1 G. It computes the seed correction for each both servers.. If Id+1 (a+)
[B] and send it
(aa (j) (ua,ela')- -aaalaa)) (d'441(a
Otherwise:
(eraaa""eoanaaa)) (1s(a²) ra(aa)) (6441 (2+1(a
Since (ua(a²) va(a')), (aa(a ra(af) E (-1,0, the inverse over G is well defined.
Now for x = a², we can write
sa+ (a'1l5)) (a+1(a"115))
= (a'ila'11))) - (a'1la))))) + (ua(a²) (hoo))
+ (aala") -a((=)))n
=dr1(a1115) ('4110 (0) 6' (a'l))) + 1 B3.
Security. We argue that each server's DPF key is pseudorandom. The security proof is analogous to the proof Theorem 3.3 in [BGI16]. We begin by describing the high-level argument. Each server begins with a random seed, which is unknown to the other server. In each tree layer, up to k random seeds are expanded using a PRG, generating 2 new seeds and 4 bits, all of which appear similarly random due to the security of the PRG and the fact that the original seed appeared random. The application of a correction word will cancel the randomness bit components. Specifically, one seed component and all bit components are canceled; however, given only the correction word and the tree node values held by single server, the resulting secret shares still appear random.
of these 6 resulting seed and
possible to define a series hybrids Hybw,e where the correction words in all levels < w replaced by random bit strings for i [d + 1), replacing Step 2 in Figure & the first l correction word components in layer w are replaced by a random bit string, and if w = + the first components of the final level correction word replaced with random group elements, replacing St Figure 7 We also consider the view of the first of the two servers, without loss of generality. Specifically:
1. Choose so))), (0), no (0), (o)) 2o (0), r0 honestly.
2. Choose CW ..... CW"-1 (0, 1) ()sk 3k++4)) uniformly at random.
3. Choose CW such that the first components are uniform samples and the remaining ones are computed honestly.
4. Update s;(a{), ui(af), (aa) honestly for all < and E [
5. For i = w, set (a(a)) .v; (a))) (a.), .....,,,,, (a))))) to random samples. Addi-
tionally set (a (a ),u (a ( (a f)................ ..... (t
(o: 6. For i w, compute CW" and update all 8; (a 4(af), ui(af), va(af) (l(a)) m((af) honestly for all & E [k).
random samples. Compute t, ( (af-t).e; (e.(((t)))m((at)))) honestly.
7. The output is s0)) un (0), go (o) [,..)c)
37

---

Note that when w = f = O. this experiment corresponds to the honest key distribution, whereas this yields completely random key. We claim that each pair of adjacent hybrids will be indistinguishable based on the security of the pseudorandom generator.
when w d + I.
We first consider we - d and a H yblddsstiguuihing adversary A who distinguishes Hybw. from either Hybw.t+1 if <
or Hybo+1.0 otherwise. Given an adversary A with advantage p. we can construct a corresponding PRG adversary B. This PRG advensary is given a value r E {0, 1)2((+2)) and distinguishes between the cases where r is truly random and r = G(s), where E {0, is random seed. Given a, 8, w, l, the adversary B constructs DPF key according to Hyb however, instead of sampling tu (a Ue (a Tw(a randomly, we set:
1100)/1000]aaaaa__ (a (a (ioo=ll(][[/ea (w (
to Iff r is computed pseudorandomly. then it is clear that the resulting DPF key is generated as in Hybw,e(1* a 3). We must also argue that if is random, the resulting key is distributed as in either Hyb if l < k - 1 or Hyb otherwise. If tw (wr(a Der (o F'n (a is random, then the corresponding correction word is also uniformly random, since it is computed as the xor of fixed bit-string with these randomly selected bit-strings, forming a perfect one-time pad. After applying this correction word, the resulting seed and bit components are also uniformly distributed, given only the previous seed and bit components for that server, as well as the correction words.
Combining these pieces, an adversary A that distinguishes between the hybrids with advantage p yields a corresponding adversary B for the PRG experiment with the same advantage and only polynomial additional runtime.
Finally, we consider w d We can make an argument similar to the previous one that an ad- versary that distinguishes between the distributions H Hyba+1. and Hyba+1.8+) with advantage di- rectly yields a corresponding adversary for the pseudo-randomnes of the PRG output, interpreted as group element, with the same advantage and only polynomial additional runtime. B can embed +))
the challenge by setting the corresponding correction word -1)" (8) ( If r is generated pscudo-randomly, this is exactly the distribution of H Hyb++1.. r is truly random, then it similarly acts as a one-time pad on the remaining terms and the corresponding correction word is uniformly distributed, as in Hyba+1.441
I Proofs of Validity
We construct an efficient proof-system that allows client to prove that it shared a valid block-sparse DPF. The proof is divided into two components:
1. & correction-bii sparse. The client proves that most &s of the (secret shared) correction bits are non-zero.
2. & block-sparse. Given that at most & of the correction bits are non-zero, the client proves that there are at most k non-zero blocks in the output.
We detail these components below. The proof system sound against a malicious client, but we assume semi-honest behavior by the servers.
Theorem 1.1. The scheme of Theorem H.2 can be augmented to be a verifiable DPF for the same function family (k-block-sparse functions). The construction incurs an additional round of interac- tion between the client and the servers (this can be eliminated using the Fiat-Shamir heuristic). The soundness error is (poly (2)
The additional cost for the proof (on top of the construction above) is O d X) communication, (k poly (d, X)) client work, (k 2d poly (d, X)) server work for each server.
Proving k-sparsity of the correction bits. (the correction bit is "on" if these bit values are not identical). The client proves that the vector of 2 - 2d correction bits (2d pairs) is k-sparse, i.e. at most & of the bits are non-zero. We use the efficient construction of 1-sparse DPFs from [BG[16), which comes with an efficient proof system (the construction in [BBCG+21 also handles malicious servers, but we do not treat this case here).
The secret shares for the correction bits are in {0, 1}
The client sends k 1-sparse DPFs (unit vectors over {0, 1 whose sum equals the vector of
38

---

Gen
Gen(1", a. B, G. B,K):
1. Let (a Jeer E [[0,1]
Sample random so(0) + {0, 1} and (0) {0, 1}^
For from to d 1, use cuckoo hashing to define mapping functions h2 (2 [ck) and : {(i bit prefixes in a} + {0,1} 1
If gi (0) = 0, let (0) = O, (0) = 1, (0) = O, and ro = 0. Else let up (0) = 0. (0) = 0, (0) = 0, and r0())
For from d:
Compute GenNeat(a, i, S,-1, f4-1, us-1; 2 P--1; hes Des 9641) and parse the oulput CW' 8i, 4is us vi; 4:
6. group by entries with the same d-bit prefix
7. For each distinct (d-bit prefixes in a, denoted a²:
(a [101| /10)/|_..1ls//4 (a || 1) G' (s(((()))
(a+1(a 11 (a C
For j [B], convert (a=l((l = conver(((( and tet1(af115)
(onvert(((+)1
Parse 3 = (80...... ......99--11
For E [k]:
Denote of the d- prefix associated with Also denote P - hat)
Parse 3 = (g6 .............................. ... 8B-1)
Denote o1 - 83 - s (a'115) + tap (a"ll)) for E [8].
Denote ( (1) (-1)au(a8)...
If (x(e) 0, set
CWd+1
p|0] + Cpior(ar)) (0]l:-)10eo1 1).
Else, set
CWd+1 p|l] + (-1)rala') 10100))-61111111 1611-.1((-1))aal -BB-1-
10. For remaining set CW randomly
11. Set CWd+1 = |..,| and CW = CW ||CW [Aa]+ ... hha41 well as ko so CoW
12. return (ko. k1), (0)
Figure 7: Gen generates DPF keys for k-block-sparse vector of dimension d log B with blocks of size B and security parameter X, where G' is a PRG that takes an input of size À bits and outputs bit string of length B log [G]. The values B of the non-zero entries in the vector correspond to elements of group G.
if these extra DPFs are indeed one-sparse and sum up the vector of correction bits, then that vector must be k-sparse. We remark that we are agnostic to the field used for secret- sharing these additional DPFs (the secret shares of the correction bits are treated as the 0 and the element in the field being used). Soundness and zero-knowe prro-knowwedge follow from the properties of the DPF of [BGI16). The communication O A), the client runtime is (k: poly (d, X)), and the server runtime is (k- 2d poly (d, A)). The soundness error Ok//2>)
correction bits:
Proving k-sparsity of the output blocks. Given that at most of the correction bits are non-zero, the client needs to prove that there are most & non-zero blocks in the output. Consider the final layer of the DPF tree: in zero block, the two PRG seeds held by the servers are identical, whereas in non-zero block, they are different. Rather than expanding the seeds B group elements (as the vanilla construction above), we add another À bits to the output, and we also add À corresponding bits each correction word. We refer these as the check-bits of the PRG outputs / correction words, and we refer to the original outputs (the B group elements) as the payload bits. In the zero blocks the check-bit vector. In each non-zero blocks, the check-bits of the (appropriate) correction word are chosen so that subtracting them from the (subtraction of the) check-bits of the PRG outputs also results in zero vector. Thus, in our proof system, the servers verify that, in each block, the appropriate
the outputs should be identical: subtracting them should results in a zero
39

---

GenNext
GenNezt((a f:-1, us-1, Qi-1, 04 Pa-1; hi 9t, 9c+1):
Group by entries with the same (i 1)-bit prefix. each group:
Denote af_1 the (i - 1)-bit prefix associated with that group
//lp u 1aa_a//l111((((_____ [|1) t- ((s-1(a(-1))
Expand and parse
Expand and parse (ç [|00)]//((a_==11)))]]
4(a(-a||1) [1) <- ((4-1(((-1))
2. For each group of (i 1 prefixes:
Denote of the 1)-bit prefix associated with that group, Also denote P
hz(a(_1).
If contains values with prefixes af-1 and of-il set (oantof random
Else if contains values with prefixes af-1l10, set (plax(of 1ill <((of-1111) +
Else if a contains values with prefixes d111 set Colatoof i = si(af-1110) +
{(((-11(0)
For E [2]:
If a contains value with prefix af- Ili. set molo, () u. - +
and Polsctof (]( (f (111 - (a (1b))
3++1(a_1llb))
Else, set m plonnta (i) u((af_ill>) + (a( and pfla.tof_ -ب
(((a{=111)) + (a/
3. For all indeces E that have not been set yet, set new random sample, and set (j) and pe(j) random bits for all j E [2].
Parse CW = co (0) (0)
[1)
|| ||cck-1l 10)0pa (0) max- (1)
5. Group by entries with the same (i - bit prefix of_,. For each group: For E [2]: If
a contains a value with prefix ilil::
Denote P h=(of_1).
Set (((o-=11))) + s((a(_1l1)) u--1(af-1) Sotol + 90-1(af-1)
Sppi and
4(af=1115) + (/ 115) + (af co/0 + r c2(1)
Set
ur(af + u'(af 115) + + u (J) 9: 9-
(j)
v((af_1l1)) < <((a/- + v.- (a/_ ) ( (i)
Set
(af__illi) dl(af_ [b/) + u (a4 Poto (1) 9 Ppp (i),
r + r((af=1lb)) + (Pto ( (A)
Return CW", 81, 4i, us, v:
Figure S: GenNext computes the seed and bit components of nodes at the next tree layer, where G is a PRG that each take an input of size X bits and outputs bit string of length 2(A + 2).
40

---

Eval, h-sparse DPF
Evallb, 9. kb, x. B,
1. Parse kg =0000)) /o].)|/c" (0()) b.g. 9-
11.41. Let wo(0) b (1 g) and
2. for from to d:
Denote -;-1 the (i bi- prefixx of x and (.( the tuple of r correction indices.
Parse CW'
mck-1(1) (1)))
Expand the seed associated with x;- -
Parse: CW? Aا = - (0) |aall
for j (0,1)
Compute r' r¹ @ 14-1 (4-1(22-1) CW plo @ (-1((=-1) CW p[uj- applying the two
correction words
Parse r¹ с {0, 1] [)²((++));
+' = = 0) [,,
Denote i d and - the bit prefix
prefii of æ. Also denote p hu (xI-1).
Parse CW
Expand and parse ((0===/000))-11166=--=--
G'(sa(xi-1))
Convert <((--1l)))) == connor((((((:==111)))
[B]
7. For E [B], compute a = (=-1 9aty (1) + (=-()=)))
())
8. Return (-1)" sc(x)
Figure 9: Eval evaluates one path x given DPF key ky corresponding to server b for k-block- sparse vectors with block size B, where G and G' are PRGs that each take an input of size X bits and output a bit string of length 2(A + 2) and B log [G], respectively. defines which correction word will be applied in the first layer. Also, let convert of length log |G] and outputs a group element in G.
function that takes as input bit string
subtraction of the check-bits in the two PRG outputs together with the check-bits of the appropriate correction word (if any) are zero. Building on the notation of Section H. taking x E {0, 1] to be node in the final layer of the DPF tree, and taking 8 cch((r)) and thhk (x) to be the check-bits of the PRG output on the node for the two servers (respectively) and taking em to be the check-bits of the m-th correction word, the servers check that for each node x in the final layer:
chk (x) s
1ghh (x)
((Ma(z) + va(a)) chk (x)1())(())
((qa(x) - chk (as1())))
To verify that equality to zero holds for all simultancously, the servers take random linear combination of their individual summands and check only that the linear combination equals zero (this boils down to computing linear function over their secret shared values, the random linear combination can be derandomized by taking the powers of a random field element). This only requires exchanging a constant number of field elements.
This part of the proof maintains zero knowledge. The new information revealed to the servers are the check-bits in the correction words. The concern could be that these expose something about locations or the values of non-zero blocks. However, the check bits of the correction words are pseudorandom even given all seeds held by single server, and given all the payload values of all correction words, and thus each server's view can be simulated and krowllneweeee is maintained.
The above construction is appealing, but it is not quite sound: intuitively, given that there are only l active correction bits (within the k correction bit pairs), the correction words are only applied to at most i of the blocks. If the check passes, this means that the check bits of all but at most k of the blocks had to have been (except for small error probability in the choice of the linear combination). However, it might be the case that the check-bits are 0, but the payload is not: i.e. we have two PRG seeds whose outputs are identical in their À bit suffix, but not the prefix. One way to resolve this issue would be by assuming that the PRG is injective (in its suffix), or collision intractable. This type of approach was taken by Castro and Polychroniadou [CCP22a) (albeit in different construction). We prefer not to make such assumptions, and instead use an additional round
41

---

of interaction to ensure that soundness holds (the interaction can be eliminated using the Fiat-Shamir heuristic). The interactive construction is follows:
1. The client sends all information for the DPF except the correction words (payload and check bits) for the last layer (B group elements and À bits per node).
2. The servers choose a PRG to the same space and reveal it to the client.
function h mapping the range of the last layer's
3. The client computes the correction words for the last layer, where the PRG used for that layer is the composition (h o G") (the pairwise independent hash function applied to the PRG's output).
Zero-knowledge is maintained because (h o G') is still a PRG. Soundness now holds because the seeds for the final layer are determined before chosen. The probability that two non-identical seeds collide in their last À bits, taken over the choice of h, is 2 We take a union bound over all the seed pairs and soundness follows.
Additional Details on Experiments
We provide more details about our experimental results in Section J.I and provide additional exper- iments and plots in Section L.2
J.1 Experimental setup for private model training
Here we provide the full details for our private training experiments that were used to produce the plots in Figure
Noise comparison for DP-SGD Figure 5a). For our experiment that compares the standard de- viation of the noise of the Gaussian mechanism and our approach, we consider private training setup where we have a model of size D 22 se 10 and number of data points n = 6 10 We user standard setting of the parameters of DP-SGD where we have clipping norm 1.0, 1.0, 5 = 10-6, and number of epochs 10. We calculate the standard deviation of the noise required for the Gaussian mechanism using the dp-accounting library in python. For our approach, culate the standard deviation based on our description in the paper using the Renyi DP accounting techniques of (FS25b) (for the remove direction) and (DCO25) (for the add direction) together with RDP bounds for Poisson subsampling in [2W19] (we rely on RDP-based bounds since (8, bbassed bounds are worse when composition over numerous batches is required). For our method, we fix the communication cost k B = 32768 and then plot the ratio of the noise needed for our method over the noise of the Gaussian mechanism as function of the block size B. We repeat this for different values of batch size in (512, 1028, 4096, 6 109} and report the results in Figure 5a
cal-
MNIST experiment Figure 5b). For MNIST, we follow the experimental setup of [ANN+23 23 and train a neural network with 69050 parameters (see full description in Table Th. We run DP- SGD with fixed learning rate 0.1, momentum 0.9, and batch size 600 for 10 epochs. To privatize the gradients at each batch, we clip each individual gradient to have Eg norm at most 1 and use the standard Gaussian mechanism or our partitioned subsampling approach release private gradients. We calculate the standard deviation of the noise required for the Gaussian mechanism using the dp accoccnnnnn library in python. We set our privacy parameters to be 2.0 and 10 For our partitioned subsampling approach, we use block size B 920 and number of blocks k = 20, and clip the & norm of each block to be at most 7, = 1.02 B B/D D where D 69050 is the number of parameters in the model. We repeat this process 10 times, each time recoding the accuracy per epoch for each method, and plot the median accuracy with 90% confidence intervals in Figure 5b
CIFAR10 experiment (Figure 5c). For CIFAR, we produce CLIP embedding (using the version ViT-B/32) for the CIFARTO images and train a simple two-layer neural network with 66954 param- eters: our network is a sequence of two fully connected layers: the first has dimensions 512 128 and the second 1 128 x 10. Then, we run DP-SGD with initial learning rate 4.0, momentum 0.9, weight decay 5 10-4 and full batch for 10 epochs. We use Stepl.R scheduler for the learning rate which reduces the learning rate by factor of 0.9 every 5 epochs. Similarly to MNIST, use the
42

---

Layer
Parameters
Convolution + tanh
16 filters of 8 x 8, stride 2, padding 2
Average pooling
x 2, stride
Convolution + tanh
32 filters of 4 x 4, stride 2, padding 0
Average pooling
x 2, stride
Fully connected + tanh
32 units
Fully connected tanh
10 units
Table I: Architecture for convolutional network model.
X Easectin
X. Beasin 3
Bertiooeddccuurringg 3-234
bestleedscuerrnng 3-220
20
20
25
20
(a)
(b)
(c)
Figure 10: The off between the standard deviation of the error (per coordinate) and per-elient communi-
a cation C = kB, when computing the sum of n = 10 vectors with dimension (a) D = (b) D = 2 and
(c) D = 2 with (1.0, 10 10-0)-00000 )-DP. The blue "x" shows the baseline approach of sending the whole vector.
Gaussian mechanism and our partitioned subsampling approach to release private gradients, where have clipping norm for the gradients,
2.0 and 5 = 10-6 For partitioned subsampling approach, we use a block size B = 920 and number of blocks k = 25, and clip the & norm of each block to be at most I, = 1.02 /02/B/1 B/D where D = 66954 is the number of parameters in the model. We repeat this process 10 times, each time recoding the accuracy per epoch for each method, and plot the median accuracy with 90% confidence intervals in Figure 5c
All of our experiments were run locally a Macbook Pro equipped with Apple M1 Pro chip (with 10 cores), and 32GB RAM. The time for each epoch depends on the mechanism, dataset choice and batch size. For the Gaussian mechanism, each epoch takes from few seconds up to 30 seconds, while for the partitioned subsampling approach each epochs takes about 1-2 minutes.
J.2 Additional experiments
In this section, we present additional experimental results in different regimes than the ones pre- sented in the main paper. We begin in Fig. 10 where compare our approach to the Gaussian mechanism and plot the error for estimating the sum of unit vectors different dimensions. We see that even for small communication complexity, sometime factor of 32 smaller than the dimension, our approach becomes competitive with the Gaussian mechanism. |Fig. II presents a similar plot where show that the same behavior holds for different number of samples
In Fig. 12 we compare the performance of the partitioned subsampling scheme and the truncated Poisson, where the plots show that each method is favorable in different regimes: the truncated Poisson obtains better error if more communication is allowed, getting closer to the error of the Gaussian mechanism. This is partly due to the analysis of partitioned subsampling building RDP analysis, which even for the Gaussian mechanism yields standard deviation bounds slightly larger than the analytic Gaussian mechanism. The truncated Poisson analysis uses the tighter PRV accounting.
Furthermore, we evaluate our method for estimating the mean of real data. Specifically, we compare our method to the Gaussian mechanism for estimating the average gradient particular epoch during the training of model over the CIFAR10 dataset with CLIP embeddings. We save 1024 gradients, each of dimension D 66954, and employ our alternative method to estimate the average gradient under (2.0, 1 We present the results in Fig. 13 These results corroborate our
43

---

Gaunkn merssnsiiosnnni -1130
Guarii
20
27
27
(b)
(c)
Figure 11: The trade-off between the standard deviation of the (per coordinate) and per-client
nication C = BB, when computing the sum D) 2 -dmeensiona vectors with sample size (a) n 10", (b) 10,, and (c) n 10", with (1.0, 10 J-DP. The blue 'x' shows the baseline approach of sending the whole vector.
8.0
Partitioned Subsampling
7.5
Partitioned Subsampling
treer
8
6.0
7-
5.5
214
215
233
237
21
21
220
2.1
2
211
22
217
215
222
2
2
212
203
Cost
Communicatiio
(b)
Figure 12: The trade-off between the standard deviation of the error (per coordinate) and per-client commu- nication for the Partitioned Subsampling scheme and the Truncated Poisson. These plots are for aggregating 10 vectors with dimension D) 22 (b) 2 block size 22 and (1.0, 10--100..0.. DD-DP.
findings in the main paper for synthetic data (see Fig. 4c demonstrating that the same behavior is observed for realistic data.
we present additional experiments for private model training on CIFAR10 using CLIP embeddings, employing the ResNet50 architecture. This experiment adheres the same setup and parameters as Fig. 5c Furthermore, we experiment with batch size of 1024 and a learning rate of 0.5 (while maintaining other parameters the same values). We run each method times and
Finally, Fig. 14
2.6
Caussan
Gaussian
Partilianed Subsampling (8 64)
Partitioned Scbsampling (8 64) Subsampling
Subsampling
1.8
Partitioree Subsempling (8 512)
Partitioned Subsampling
-W-
Partilioned Subsampling (8 1024)
1.6
Partitioned Subsampling (8 1024)
1.4
1.2
1.6
1.0
1.4
1.2
242
224
2
222
241
2
Commurication
(a)
(b)
Figure 13: Error for estimating the average gradient during private model training of the CIFARIO experiment where the model has D 66954 parameters, comparing the Gaussian mechanism and partitioned subsampling for different communication costs, for (a) and (b)
44

---

0.01
0.92
0.4
0.76
(Sauzda))
BP-GGa (Gaumbar)
DP SCp (ur MorMMurer butwamp
sup theztonnc bulsemping!
Epoch
Epach
(b)
Figure 14: Comparison between PREAMBLE and the Gaussian mechanism for private model training over the CIFAR10 dataset using CL.IP emheddings (version RN50 or Resnet5(). We plot 90% confidence intervals for (a) batch size of 1024 and (b) full batch.
report the median accuracy as a function of epoch. Our plots demonstrate that our method performs similarly the Gaussian mechanism for small batch size and full batch, with significant reduction in communication.
K Broader Impact
This paper presents work whose goal advance the field of Differentially Private Machine Learn- ing. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
45


Reviews:
[{"review_id": "zBaennKyUF", "reviewer": "Reviewer_pAwE", "summary": "This paper studies the private communication of vectors from each client to an aggregating server under differential privacy, while taking communication cost into account. In particular, the authors propose an extension from 1-block sparse vectors to k-block sparse vectors. Each client divides their vector into B blocks, randomly selects k of them, and sends only those to the server. Assuming each block has a bounded ℓ₂ norm, they show that the DP release of the k-block sparse vector can approximate the sum of all client vectors, up to an error term. By appropriately choosing parameters, they demonstrate that the noise from DP-SGD will dominate this approximation error. The authors also provide theoretical privacy guarantees, which depend on a parameter c, although its construction or approximation is not fully understood. They validate their theoretical results experimentally on toy examples and compare DP-SGD with the block-sparse vector approach using numerical privacy accounting.", "questions": "- How can we approximate the constant c?\n- Can you perform an ablation study with varying levels of Gaussian noise added, specifically in the low and medium privacy regimes and if so what would be the utility gap between DP SGD and the proposed work?", "limitations": "NA", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The paper addresses an important and timely problem in differentially private (DP) communication.\n- The theoretical results support the proposed approach for DP k-sparse communication. The explanations of the sparsification algorithm, hashing, and decoding mechanisms are clear and well-presented.\n\nWeaknesses:\n\n\n\n-  In the numerical comparisons with DP-SGD, the authors mention that both algorithms operate under the same privacy budget (via numerical accounting), but they do not specify the values of ε and δ. Moreover, there is no discussion of how the results are impacted in lower-privacy regimes — the ones typically desired in practice.\n\n- The privacy guarantee relies on a parameter -c- that can be arbitrarily small. While it's theoretically appealing to have a guarantee without approximation, the practical value of such a guarantee is questionable.\n\n- While some parts of the paper provide thoughtful discussions of the results, other sections merely restate the findings in a verbal form without offering deeper insights or analysis e.g. after theorem 3.1 when it is explained in what scenario the noise from DP takes over without any explanation of whether such scenario is reasonable other than not.", "was_revised": true, "final_justification": "Given the authors' reposes and their proposed additions to the paper I have updated my score.", "rebuttal": "We thank the reviewer for their positive evaluation and their valuable feedback that we will incorporate in an updated version of the paper. Below we address some of the reviewer’s questions.\n\n **Privacy parameters** : We missed adding privacy parameters in the main paper, and will bring these forward from the supplementary material. The details for our DP-SGD experiments are presented in the Appendix (Section I.1). In particular, for figure 5, we use the privacy parameters $\\varepsilon = 2.0, \\delta = 10^−6$. \n\n **Constant $c$** : While the constant $c$ in Thm 3.2 can be explicitly calculated, the analytic formula is primarily valuable for giving intuition for the asymptotics. It is off by constant factors and hence is not used in practice. In practice (even for simple DP-SGD), one uses numerical accounting methods, and we do the same in our work.\n\n**Low-privacy Regime** : We believe that our DP-SGD results demonstrate that the _shape_ of the noise in PREAMBLE does not impact the convergence of DP-SGD, and one can focus on the _scale_ of the noise. In Figure 13 in the appendix, we evaluate gradient estimation error for $\\varepsilon=1$ and $2$ per batch, and this should allow us to evaluate the impact on DP-SGD convergence in the low privacy regime. \n \n In particular, DP-SGD in the low privacy regime typically uses per-batch sigma in the range [0.6,2]. If the per-batch privacy sigma is 1.0, and batch size is 10k, Theorem 3.1 implies that sending 100k coordinates per user will ensure an overall sigma of about 1.05. By taking a slightly larger batch of 11k, the effective sigma can be brought back down to 1.0, so that the utility is equivalent to non-compressed DP-SGD. The privacy analysis can then be done with this slightly larger batch and using PREAMBLE. This privacy analysis of the scheme will now need to account for two levels of sampling (sampling a batch of users, and sampling of blocks), and we can use [FS25] to handle this and compute the final (\\eps,\\delta) parameters. This privacy analysis will incur a small overhead compared to the Moments accountant (and a slightly larger overhead compared to PRV accountants), and for typical parameters, we expect this increase to be small. This is the analysis in our current plots, and we will add examples of this overhead for some parameter settings from recent works in the final version of the paper.\n\nWe remark that mean estimation is a really wide-spread primitive in private learning and statistics well beyond DP-SGD, with applications ranging from learning histograms over dictionaries both big and small, using such histograms in adaptive algorithms for learning heavy hitters over very large dictionaries, training small and large ML models, running k-means and similar clustering algorithms, running Bayesian inference algorithms, etc. Indeed learning histograms is the most widely-used application of Federated learning by far and Fig. 4(c) captures the benefits of our approach for this application. The parameters of interest here: the batch size, the dimension, and the DP noise scale will vary considerably in these applications, and our approach will provide benefits in some of these cases when dimension is larger than the batch size. Our theorem 3.1 provides some guidance on what compression one can expect for a given setting of parameters. We will add more discussion of this in the updated paper."}, {"review_id": "KxsoG2ThFW", "reviewer": "Reviewer_QZmP", "summary": "This paper studies the problem of private aggregation of high-dimensional vectors. In this problem, there is a data set of high-dimensional vectors distributed among some large number of clients, and there are two servers whose goal is to compute and output a private estimate of their sum. The main goal of this paper is to reduce the communication cost of protocols that achieve this. One approach from prior work is to randomly sparsify and scale the vectors so that in expectation they are preserved, and then to communicate the lightweight sparse vector. The authors state that this approach still leads to a communication cost of $m \\lambda \\log D$, where $D$ is the dimensionality of the vectors, $m$ is the number of coordinates subsampled during sparsification, and $\\lambda$ is a security parameter used in secret sharing.\n\nThe approach taken by the authors is to use block-sparsity, i.e. instead of randomly picking some $m$ coordinates to sample, the vector is divided into blocks of size $m/k$ and some $k$ of these blocks are sampled and picked for communication. By doing so they state that they get communication cost $O(m + k\\lambda \\log D)$, potentially with some other side-costs which can be dealt with separately.\n\nFurther, since the final goal is differentially private aggregation, the authors show that one of the advantages of their method is that by using block sparsity and privacy amplification by subsampling, the potentially high sensitivity of the subsampled and scaled vector can be offset leading to a reasonable privacy utility trade-off.\n\nIn order to construct their protocol that requires the destination servers to aggregate and privatize the sparsified and encrypted vectors, the authors rely upon zero knowledge proofs to ensure that the clients can prove that their vectors are indeed $k$-block sparse.\n\nFinally, some experiments are conducted showing that they are indeed able to reduce communications costs and truncation error with blocking, and that it works well with privacy by conducting a numerical privacy accounting.", "questions": "1. I understand that this is a hybrid trust model of sorts - the communication between the clients and the two servers is cryptographically secure, and the output of the servers is privacy-preserving in the sense of differential privacy. At the outset you mention how it is only required that one of the two servers is assumed to be honest. If a server is malicious but receives some secret shares of the sparsified vector, what exactly is the privacy promise that is achieved here? Is only the final output private or has the malicious server gained some private information?\n2. In your Overview section you give an example of a secret share using Distributed Point Functions that seems to use 15MB of communication. Is it easy to see what your approach would give here? It might be good to place this in that section for an easy comparison.\n3. What exactly are the Zero Knowledge Proofs needed for, is this proof of sparsity necessary for reasons of privacy? Also what is the total round complexity of your protocol?\n4. Would the gains made from privacy amplification by subsampling also extend to the prior work which uses randomly sparsified vectors, potentially offsetting the high worst case sensitivity?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1. The problem being considered is interesting and impactful.\n2. The high-level approach makes sense and the gains made seem to be significant.\n\nWeaknesses:\n1. Although the paper is well-written, it is hard for someone not familiar with Prio to easily gauge correctness, or understand all the roadblocks being encountered and how they are resolved.\n2. The collaborative computation between the servers for the private output is not clear from the pseudocode.", "was_revised": true, "final_justification": "I think the author's comments addressed my questions well and increased my confidence in the paper, which is why I have increased my score from a 4 to a 5.", "rebuttal": "We thank the reviewer for their positive evaluation of our work and will incorporate their valuable feedback in the updated version of the paper. Below we address their specific questions.\n\n**Collaborative computation**: We acknowledge the complexity of the cryptographic parts of the protocol, and have attempted to give a high-level view of the roadblocks and their resolution in Sec. H in the appendix. We will rework the pseudocode of the collaborative decoding to make it clearer.\n\n**Hybrid Trust Model**: That is a great question, and we will add more discussion of this. Prio guarantees that as long as one server is honest, the other server (even if they were malicious) learns nothing except for the published aggregate. So from the privacy point of view, we have the strong privacy guarantee: nothing except the differentially-private aggregate can be learnt by any of the parties as long as one of the servers is honest. A malicious server can corrupt the output of course, but cannot impact privacy.\n\n\n**Concrete numbers for the example**: That is a great suggestion. We will add some numbers here, and make this example more consistent with the example on lines 78-81. Holding m=kB=50000 constant and choosing $B\\approx1000$, our communication would be ~400KB in this example, if the field size is 64 bits.\n\n\n**The need for Zero knowledge proofs (ZKPs)**: That is a great question and we will add more discussion of this. The primary reason to have ZKPs here is to make the protocol robust to malicious clients. Absent proofs, a single client can change the whole aggregate arbitrarily. Proofs can ensure that a malicious client can only change the output by a bounded amount. Our protocol has 2 rounds, but as we discuss in section H.2, it can be made single round using Fiat-Shamir (and Fiat-Shamir is provably secure for our protocols in the random oracle model).\n\n**Would the gain extend to other uses of randomly-sparsified vectors**: Yes and no. Privacy amplification analysis will help in case of random sparsification whenever we can make sure that the adversary cannot learn which coordinates a client contributes to. In single server settings (or in typical MPC-amongst-clients protocols), this is seldom the case, though one can imagine protocols can be designed to ensure this. This need to hide the sparsity pattern is the reason we use DPFs in our work."}, {"review_id": "vJVvUOGXHw", "reviewer": "Reviewer_ghcW", "summary": "The authors propose a method for efficient and private aggregation of high-dimensional vectors in the two-server model. They introduce a new cryptographic primitive based on block-sparse distributed point functions to reduce communication and computational overhead. By leveraging block sparsity, random sampling, and privacy amplification by sampling, PREAMBLE achieves strong privacy guarantees with communication costs significantly lower than prior work. The method is particularly relevant in settings like private FL, where clients must send large gradient vectors.", "questions": "- Could you provide insights or preliminary discussions on how PREAMBLE performs with larger models (e.g., ResNet or ViT) and more complex datasets?\n\n- Could you provide a detailed breakdown of runtime or resource usage for both the client and the servers? \n\n- Could you provide direct comparison with recent alternatives like [CSOK23]?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n+ The paper is well-written and easy to read. Ideas and analysis have been clearly presented.  \n+ The paper addresses a practical bottleneck in private FL, high communication costs for secure aggregation. \n+ The abstraction of k-block sparse vectors and their integration into DPFs is innovative and leads to notable efficiency gains. The authors have also combined formal privacy guarantees with empirical utility assessments. \n\nWeaknesses\n\n- While training machine learning models with differential privacy is inherently challenging, the evaluation in this paper is limited to relatively small-scale tasks, which may not fully demonstrate the method’s scalability or practical applicability. The evaluated models are relatively small, which may limit the generalizability of the results to more complex architectures commonly used in practical federated learning scenarios. Does the conclusion change when we have a more complicated task, e.g., a large model on ImagNet level classification?\n\n- While communication is reduced, the paper may potentially downplay the increased client and server-side computational cost due to PRG evaluations and zero-knowledge proofs. A detailed breakdown of computational costs would be helpful.\n\n- Though many baselines are mentioned, it lacks a direct comparison with recent alternatives like [CSOK23]. It would be helpful to include more results and discussion.", "was_revised": true, "final_justification": "The authors' response was satisfactory. I agree with the other reviewers that this is a good paper and will keep my original score of Accept.", "rebuttal": "We thank the reviewer for their positive evaluation of our work and will address their feedback in the updated version. Below we address their specific questions.\n\n**Performance on larger models**: We believe that our DP-SGD results demonstrate that the _shape_ of the noise in PREAMBLE does not impact the convergence of DP-SGD, and one can focus on the _scale_ of the noise. In Figure 13 in the appendix, we evaluate gradient estimation error for $\\varepsilon=1$ and $2$ per batch, and this should allow us to evaluate the impact on DP-SGD convergence for any model.  In particular, DP-SGD in the low privacy regime typically uses per-batch sigma in the range [0.6,2]. If the per-batch privacy sigma is 1.0, and batch size is 10k, Theorem 3.1 implies that sending 100k coordinates per user will ensure an overall sigma of ~1.05. By taking a slightly larger batch of 11k, the effective sigma can be brought back down to 1.0, so that the utility is equivalent to non-compressed DP-SGD. The privacy analysis can then be done with this slightly larger batch and using PREAMBLE. This privacy analysis of the scheme will now need to account for two levels of sampling (sampling a batch of users, and sampling of blocks), and we can use [FS25] to handle this and compute the final (\\eps,\\delta) parameters. This privacy analysis will incur a small overhead compared to the Moments accountant (and a slightly larger overhead compared to PRV accountants), and for typical parameters, we expect this increase to be small. We will add examples of this overhead for some parameter settings from recent works in the final version of the paper.\n\nWe remark that mean estimation is a really wide-spread primitive in private learning and statistics well beyond DP-SGD, with applications ranging from learning histograms over dictionaries both big and small, using such histograms in adaptive algorithms for learning heavy hitters over very large dictionaries, training small and large ML models, running k-means and similar clustering algorithms, running Bayesian inference algorithms, etc. Indeed learning histograms is the most widely-used practical application of Federated learning by far, and Fig. 4(c) captures the benefits of our approach for this application.\n\n\n**Runtime and Resource usage for client and server**: The decreased communication in PREAMBLE does come at a computation cost for clients and servers; however, we introduce improvements to existing DPF constructions to keep this computation very modest. The main computational overhead for clients and servers is the evaluation of PRGs from a small seed - we describe the construction at a high level at the start of Section 4 and in more detail in Appendix H. The total computation, dominated by length-doubling PRG evaluations, is done in a tree-like structure, where the client must evaluate k paths in this tree and the server must evaluate the entire tree. \n\nTo give some intuition of the runtime of the PRG operations, we quickly benchmarked the PRG instantiated with AES-128 on an Apple M2 laptop with 16GB of memory. Using the command line tool openssl speed, we measured a time of approximately 2ms for server computation and 0.5ms for client computation. To obtain these numbers, we consider a group of size $2^64$ in the final layer and set  $\\lambda = 128$, $D=10^6$, $B=2^{10}$, and $k=2^8$.\n\nThe asymptotic computation cost is stated in the table below. The improvement in server computation stems from constraining the sparsity structure to have k non-zero blocks instead of $kB$ non-zero coordinates overall, resulting in $k\\log(D/B)$ calls to a length-doubling PRG and $k$ calls to a PRG whose output is $B\\times$ the size of the input. This change could also be applied to existing approaches for multi-point DPFs in the other rows of the table, but this is not a focus of those previous works. The asymptotic notation for server computation in the probabilistic batch codes approach hides a multiplicative constant of approximately 3, while our approach requires approximately D PRG evaluations (1.03D in practice), avoiding the constant overhead. \n\n\n\n----------\n| | Server Computation | Client Computation |\n|:-------------|:-----:|:-----:|\n|Repeated DPFs [BGI16] | $O(kBD)$ |  $O(kB\\log(D))$ |\n|Probabilistic Batch Codes [BCGI18] | $O(D)$| $O(kB\\log(D))$ |\n|PREAMBLE | $O(D)$ | $O(kB+\\log(D/B))$|\n\n\n**Comparison with [CSOK23]**: [CSOK23] operates in the multi-message shuffle model and thus relies on different trust assumptions than PREAMBLE. Similarly to their work, PREAMBLE exploits the fact that the sparsity pattern of vectors can be hidden. However, our work crucially relies on blocking to reduce the sparsity, and is necessary to make the DPF construction significantly more efficient. Blocking helps significantly with the truncation error, as we show in Section 5. Sparsity constraints also make regular Poisson subsampling, which is used by [CSOK23], less suitable for our application and necessitate the use of sampling schemes that require a more involved privacy analysis."}, {"review_id": "6GtCUJqyxN", "reviewer": "Reviewer_z8gp", "summary": "This paper introduces **block-sparseness** as a principled abstraction for private aggregation, striking a balance between accuracy and efficiency. The authors extend distributed point function (DPF) constructions to support *$k$-block-sparse vector secret sharing*, achieving significantly reduced communication and computation overhead—transmitting only \\$kB\\$ field elements instead of full sparse vectors. They integrate their scheme with *sampling-based privacy accounting* and demonstrate that it achieves privacy-utility trade-offs *comparable to the Gaussian mechanism* while drastically reducing communication costs. For example, on 8-million dimensional data, their method compresses communication from 64MB to 1MB with only a modest increase in noise for $(1, 10^{-6})$-DP.", "questions": "* Can you comment on how sensitive your protocol's performance is to violations of the block-sparsity assumption? \n\n* Are there heuristics or preprocessing techniques to induce block structure when it is not present?", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths:\n\n1. **Principled Use of Block-Sparsity**:\n   The paper introduces *block-sparsity* as a natural and effective abstraction for high-dimensional vector aggregation, striking a balance between expressiveness and efficiency. This insight enables meaningful communication and computation reductions without compromising accuracy.\n\n2. **Communication Efficiency**:\n   By extending DPF constructions to handle block-sparse vectors, the authors reduce communication costs from *tens of megabytes (e.g., 64MB)* to as low as *~1MB*, making the approach highly practical for large-scale systems.\n\n3. **Improved Server-Side Efficiency**:\n   The protocol minimizes server workload by leveraging *cuckoo hashing* and *probabilistic batch codes*, reducing server-side PRG evaluations from $O(mD)$ to $O(D)$, a significant scalability improvement.\n\n4. **Compatible with DP Accounting and Utility Guarantees**:\n   The authors show that their block-sparse aggregation integrates well with *privacy amplification by subsampling* and *numerical DP accounting*, leading to utility comparable to the Gaussian mechanism, despite the structural constraints.\n\n5. **Efficient Zero-Knowledge Proofs**:\n   The paper includes a *zero-knowledge proof system* for validating block-sparse commitments, which does not inflate asymptotic runtime or communication cost, a valuable feature for ensuring integrity in adversarial environments.\n\n6. **Deployment-Oriented Design**:\n   The use of counter-mode PRG evaluations and linear or near-linear runtime makes the construction well-suited for *practical, scalable deployment*, especially in two-party and federated learning settings.\n\nWeaknesses:\n\n1. **Lack of Some Definitions**:\nClearly, this paper must have been written by one or more crypto experts. PRG (assuming it stands for Pseudorandom Generator) is referenced a few times without an actual definition. See line 118 where it first appears...\n\n2. **Implementation Complexity**:\n   The protocol’s reliance on advanced cryptographic components (e.g., DPFs, cuckoo hashing, batch codes, ZKPs) may introduce *engineering complexity* that could hinder adoption without reference implementations.", "was_revised": true, "final_justification": "I think it's a strong submission sitting at the intersection of machine learning and cryptography.", "rebuttal": "We thank the reviewer for their positive review, and will update the paper to address their valuable feedback. Below we address some of their questions.\n\n**Missing definitions**: We apologize for the oversight, and will add definitions of any cryptographic terms that we use.\n\n**Additional complexity**: The reviewer is correct that much like Prio itself, the use of complex cryptographic components will introduce additional engineering complexity. We hope that PREAMBLE will be implemented in the standard libraries that implement various prio protocols, such as libprio and daphne, reducing the overhead. Overall, we believe that PREAMBLE enables larger dimensional mean estimation than was feasible with prior techniques, and the incremental engineering complexity over prio can be justified in scenarios when such aggregates are needed.\n\n\n\n\n**Violations of Block-sparsity assumption**: In PREAMBLE, block sparsity is not an assumption on the input, but rather ensured by our sub-sampling process. The cryptographic part of the algorithm requires inputs to be block-sparse. However, given an arbitrary input, PREAMBLE first subsamples the right number of blocks to ensure that block-sparsity holds. Indeed this subsampling can be viewed as a pre-processing technique to induce the block-sparse structure."}]

Author rebuttal:

Meta-review: This paper studies aggregation of vectors satisfying cryptographic and differential privacy guarantees, introducing a new aggregation method extending 1-block sparse vectors to k-block sparse vectors. All four reviewers appreciated the paper's algorithms, exposition, and improved communication and utility guarantees. A possible point of improvement for the final camera-ready is to better clarify some of the paper's cryptographic details and framing for the largely ML audience at NeurIPS.
Decision: Accept (poster)