Paper 2025/490

PREAMBLE: Private and Efficient Aggregation of Block Sparse Vectors and Applications

Hilal Asi, Apple (United States)
Vitaly Feldman, Apple (United States)
Hannah Keller, Aarhus University
Guy N. Rothblum, Apple (United States)
Kunal Talwar, Apple (United States)
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: Private Efficient Aggregation Mechanism for Block-sparse Euclidean Vectors. PREAMBLE is a novel extension of distributed point functions that enables communication- and computation-efficient aggregation of block-sparse vectors, which are sparse vectors where the non-zero entries occur in a small number of clusters of consecutive coordinates. We then show that PREAMBLE 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
AggregationTwo-server modelDistributed Zero KnowledgeDifferential Privacy
Contact author(s)
hasi @ apple com
vitaly edu @ gmail com
hkeller @ cs au dk
gn_rothblum @ apple com
kunal @ kunaltalwar org
History
2025-03-17: approved
2025-03-14: received
See all versions
Short URL
https://ia.cr/2025/490
License
Creative Commons Attribution-NonCommercial-NoDerivs
CC BY-NC-ND

BibTeX

@misc{cryptoeprint:2025/490,
      author = {Hilal Asi and Vitaly Feldman and Hannah Keller and Guy N. Rothblum and Kunal Talwar},
      title = {{PREAMBLE}: Private and Efficient Aggregation of Block Sparse Vectors and Applications},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/490},
      year = {2025},
      url = {https://eprint.iacr.org/2025/490}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.