Prio: Private, Robust, and Scalable Computation of Aggregate Statistics

By Henry Corrigan-Gibbs, Dan Boneh. 2017

436 citations recorded by the source corpus.

This paper presents Prio, a privacy-preserving system for the collection of aggregate statistics. Each Prio client holds a private data value (e.g., its current location), and a small set of servers compute statistical functions over the values of all clients (e.g., the most popular location). As long as at least one server is honest, the Prio servers learn nearly nothing about the clients' private data, except what they can infer from the aggregate statistics that the system computes. To protect functionality in the face of faulty or malicious clients, Prio uses secret-shared non-interactive proofs (SNIPs), a new cryptographic technique that yields a hundred-fold performance improvement over conventional zero-knowledge approaches. Prio extends classic private aggregation techniques to enable the collection of a large class of useful statistics. For example, Prio can perform a least-squares regression on high-dimensional client-provided data without ever seeing the data in the clear.

Subfields: Artificial Intelligence, Privacy & Security

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Privacy & Security

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, background): “There is a rich literature exploring secure aggregation in both the single-server setting (via pairwise additive masking [12, 188, 73], via threshold homomorphic encryption [356, 193, 92], and via generic secure multi-party computation [86]) as well as in the multiple non-colluding servers setting [”
Secure Federated Submodel Learning (2019, background): “These basic settings make the secure aggregation protocol different from other relevant work about oblivious addition [19]–[21], or, more generally, secure multiparty computation [63]–[66], which requires direct peer-to-peer communication between clients; assumes the availability of multiple noncoll”
Honeycrisp: large-scale differentially private aggregation without a trusted core (2019, methodology): “[22] does sketch a possible extension to add differential privacy; however, even with this addition, Prio’s proof processing means that it is not as scalable to massive user bases as Honeycrisp – Prio can process around 300 submissions per second (which remains roughly constant no matter the number ”
Private Aggregation from Fewer Anonymous Messages (2019, neutral): “, the PRIO system [9]; here the protocol is secure as long as at least one server is honest.”
Distributed Differential Privacy via Shuffling (2018, background): “[6] ; or (2) allow general computations, but require a network of servers, a majority of whom are assumed to behave honestly, as in Corrigan-Gibbs and Boneh [11].”
Encode, Shuffle, Analyze Privacy Revisited: Formalizations and Empirical Evaluation (2020, methodology): “Such anonymous summaries are less general than shufﬂed reports (from which they can be constructed by post-processing), but they can be practically computed using cryptographic means [10], [11], [30] and have seen formal analysis [19], [31].”
Practical and Robust Privacy Amplification with Multi-Party Differential Privacy (2019, methodology): “Our work shares similar threat models from work on secure aggregation such as the electronic voting [18] and statistic aggregation [17].”
Secure Byzantine-Robust Machine Learning (2020, background): “[11] proposes a private and robust aggregation system (Prio) based on secret-shared non-interactive proof (SNIP).”
PROCHLO: Strong Privacy for Analytics in the Crowd (2017, background): “Other cryptography-based privacy-protection systems, such as PDDP, Prio, and Secure Aggregation [11, 15, 18], mostly share ESA’s goals but differ greatly in their approach.”
Practical Secure Aggregation for Privacy-Preserving Machine Learning (2017, methodology): “The recently presented Prio system of Gibbs and Boneh [16] is, from the perspective of the client devices, noninteractive, and the computation among the servers is very lightweight.”
Improving utility and security of the shuffler-based differential privacy (2019, methodology): “ting without trusted hardware. Aggregation using Secure Computation. Our work shares similar threat models from work on secure aggregation such as the electronic voting [18] and statistic aggregation [17]. In particular, multiple users compute some information collaboratively without leaking informa”
zkLedger: Privacy-Preserving Auditing for Distributed Ledgers (2018, background): “Prio does not operate on distributed ledgers, and thus does not guarantee public verifiability.”
CrypTFlow: Secure TensorFlow Inference (2019, neutral): “recent results ([61], [75], [57], [25], [44]) in the area of secure machine learning, both in the 2-party [17], [67], [34], [55], [49], [58], [84], as well as in the 3-party setting [72], [60], [79], [12].”
Zero-Knowledge Proofs on Secret-Shared Data via Fully Linear PCPs (2019, methodology): “Hamming weight 1: Prio [39] O(n) 1 x̄ ∈ F,weight(x̄) = 1 Theorem 15 O( √ n) 2”