research area Methods and Algorithms, research area Privacyconference USENIX Security
content type paperpublished July 2024

PINE: Efficient Norm-Bound Verification for Secret-Shared Vectors

AuthorsGuy N. Rothblum, Eran Omri, Junye Chen, Kunal Talwar

View publication

Secure aggregation of high-dimensional vectors is a fundamental primitive in federated statistics and learning. A two-server system such as PRIO allows for scalable aggregation of secret-shared vectors. Adversarial clients might try to manipulate the aggregate, so it is important to ensure that each (secret-shared) contribution is well-formed. In this work, we focus on the important and well-studied goal of ensuring that each contribution vector has bounded Euclidean norm. Existing protocols for ensuring bounded-norm contributions either incur a large communication overhead, or only allow for approximate verification of the norm bound. We propose Private Inexpensive Norm Enforcement (PINE): a new protocol that allows exact norm verification with little communication overhead. For high-dimensional vectors, our approach has a communication overhead of a few percent, compared to the 16-32x overhead of previous approaches.

Related readings and updates.

PREAMBLE: Private and Efficient Aggregation via Block Sparse Vectors

September 29, 2025research area Methods and Algorithms, research area Privacyconference NeurIPS

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…

Read more

Differential Secrecy for Distributed Data and Applications to Robust Differentially Secure Vector Summation

March 9, 2022research area Methods and Algorithms, research area Privacy

Computing the noisy sum of real-valued vectors is an important primitive in differentially private learning and statistics. In private federated learning applications, these vectors are held by client devices, leading to a distributed summation problem. Standard Secure Multiparty Computation (SMC) protocols for this problem are susceptible to poisoning attacks, where a client may have a large influence on the sum, without being detected. In…

Read more