PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Henry Corrigan-Gibbs, Dan Boneh

arXiv:1703.06255v1cs.CR

TL;DR

Prio addresses the challenge of computing useful aggregate statistics without exposing individual client data or allowing malicious submissions to corrupt results. It combines private aggregation with secret-shared non-interactive proofs, achieving strong privacy, robustness against malicious clients, and practical scalability. Its guarantees remain bounded by assumptions including an honest server and limitations of some aggregation encodings.

  • Problem

    Aggregate-statistics services often collect and retain private client data, creating security and privacy risks, while encryption-based aggregation can sacrifice robustness and zero-knowledge defenses can hurt scalability.

  • Method

    Prio combines private aggregation with secret-shared non-interactive proofs (SNIPs) that let servers privately verify syntactic validity of encoded client submissions.

  • Results

    Prio simultaneously achieves strong privacy, robustness to faulty clients, and performance at scale, including a 5.7× slowdown versus naïve collection compared with 267× for a NIZK-based system.

  • Takeaways & Limitations

    Prio supports private collection of a large class of useful statistics, including high-dimensional least-squares regression, without seeing client data in the clear.

  • Takeaways & Limitations

    Prio’s robustness requires all servers to be honest, and some aggregation functions require large affine-aggregatable encodings.

Abstract

from arXiv · show

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.

1 Introduction

Prio addresses the privacy, robustness, and scalability challenges of collecting aggregate statistics from private client data. It uses secret-shared proofs and private aggregation to protect data while rejecting malformed submissions and maintaining practical performance.

  • Motivation: Centralized collection of private telemetry creates risks of theft, misuse, and surveillance even when services need only aggregate statistics.Examples include location, fitness, and homepage data collected for population-level analyses.
  • Motivation: Randomized response scales and limits each malicious client’s influence, but weak privacy requires a trade-off between leakage and estimate accuracy.With p = 0.1, the vendor often sees the correct response; adding noise reduces leakage but also accuracy.
  • Motivation: Encryption-based aggregation hides individual bits unless servers collude, but malicious clients can submit oversized encrypted values that distort results.Zero-knowledge protections address this attack but can increase server workload by orders of magnitude.
  • Prio: Prio provides privacy against extensive client and server compromise as long as one server remains honest, while revealing only what the aggregate statistic reveals.The adversary may observe the network, control all but one server, and control many clients.
  • Prio: SNIPs let servers verify encoded client submissions privately, even with malformed proof shares, using fast information-theoretic cryptography.Servers exchange only a few hundred bytes per client submission during checking.
  • Evaluation: 5.7× server slowdown beats a 267× NIZK-based comparison, while clients are 50-100× faster than NIZKs and Prio supports large-scale statistics.A 434-question survey requires 26 ms of client computation, and servers process each submission in under 2 ms on average.

2 System goals

Prio’s system goals are to compute aggregate functions while minimizing client-data leakage, preserving anonymity, and defining robustness against malicious clients. Its guarantees depend on the server threat model and do not natively include differential privacy.

  • Goals: A Prio deployment uses a small server set and many clients to compute f(x1, ..., xn) while revealing as little as possible about each private xi.The deployment assumes pairwise authenticated and encrypted channels and no network synchrony.
  • Privacy: Prio always protects client anonymity even when the adversary chooses honest clients’ values, controls other clients, and controls all but one server.Anonymity means the adversary cannot identify which honest client submitted which value.
  • Privacy: Prio provides f-privacy when an adversary controlling any number of clients and all but one server learns nothing beyond f(x1, ..., xn).For some functions, the guarantee is instead ˆf-privacy, which permits slightly more information than f.
  • Scope: Prio does not natively provide differential privacy because it adds no noise to its aggregate statistics.The paper discusses extending Prio with differential privacy separately.
  • Robustness: Robustness means malicious clients can affect an aggregate only by misreporting their private values, such as changing a count by at most one.The definition excludes other ways of corrupting the system’s output.
  • Robustness: Prio provides robustness only when all servers are honest and is not robust against adversarial servers.Protecting against faulty servers would incur privacy and performance costs.

3 A simple scheme

The simple Prio scheme secret-shares each client’s value across servers, aggregates shares independently, and publishes accumulators whose sum yields the private-data sum. This baseline provides privacy but lacks robustness until the full system adds further mechanisms.

  • Upload: Each client splits its private value xi into one share per server over Fp and sends the shares through encrypted, authenticated channels.The shares sum to xi modulo p.
  • Aggregate: Each server adds the received share to its accumulator, which starts at zero.The accumulation is performed modulo p.
  • Publish: After receiving all client shares, servers publish their accumulators, whose sum reconstructs the clients’ sum when p exceeds the number of clients.This avoids modular overflow for one-bit client values.
  • Security: The basic scheme provides privacy because servers learn the sum of clients’ private inputs but nothing else.The described functionality targets one-bit client values and a private sum.
  • Limitations: Without robustness, one malicious client can submit a random field element and completely corrupt the protocol output.The full Prio system extends this baseline with robustness against malicious clients and support for many aggregation functions.

4 Protecting correctness with SNIPs

Prio uses secret-shared non-interactive proofs to let servers verify that private client submissions satisfy an arbitrary public predicate without revealing the data. The construction provides soundness and privacy with low server communication, while its main limitation is vulnerability to selective denial of service by malicious servers.

  • SNIP overview: SNIPs let clients prove that Valid(x) = 1 without leaking anything else about x to the servers.The client sends proof strings to multiple servers, which gossip and accept or reject the submission.
  • Construction: The construction uses arithmetic circuits, additive secret sharing, polynomial interpolation, and an adaptation of Beaver’s MPC multiplication protocol.Servers derive affine wire shares locally and exchange only a few field elements to verify the circuit computation.
  • Security properties: SNIPs provide soundness against malicious clients: malformed submissions are rejected except with probability at most (2M+1)/|F|.Here, M is the number of multiplication gates in Valid; choosing |F| ≈ 2^128 or repeating the test makes failure probability extremely small.
  • Limitations: A malicious server can falsely reject a well-formed submission, creating a selective denial-of-service attack against an honest client.The protocol does not require completeness or soundness in the presence of malicious servers.
  • Security properties: As long as at least one server is honest, the SNIP reveals no information about client data or internal Valid(x) wire values.This privacy guarantee is unconditional and information-theoretic.
  • Efficiency: Server-to-server communication grows neither with verification-circuit complexity nor with the size of x, while client-to-server communication grows linearly with circuit size.Server computation is essentially the cost of evaluating Valid locally.

5 Gathering complex statistics

Prio combines affine-aggregatable encodings with SNIPs so servers can validate secret-shared client data, sum encodings, and decode many private aggregate statistics. The framework supports basic statistics, machine-learning tasks, and a proven limitation on encoding size for exact median computation.

  • System construction: Prio combines private summation, secret-shared validation, and affine-aggregatable encodings to compute complex statistics from encoded client data.Clients encode values, servers validate submissions and sum encodings, then decode the aggregate.
  • Affine-aggregatable encodings: Affine-aggregatable encodings provide Encode, Valid, and Decode algorithms that recover an aggregate from summed, truncated encodings while supporting privacy definitions based on the revealed function.The encoding uses k components for validation and k′ components for decoding; randomized variants may provide approximate answers or fail with small probability.
  • Affine-aggregatable encodings: Prio unifies prior encodings for sums, standard deviations, counts, and least-squares regression, while reducing Valid-circuit multiplication gates to shorten SNIP proofs.The encodings are designed both to limit leakage beyond the aggregate and to reduce validation-circuit cost.
  • Limitations: Exact median computation has an encoding-size lower bound: k′ must not be o(n / log n) field elements when |F| ≈ n^d.Otherwise, summed encodings would yield an impossible single-pass, space-o(n) exact-median streaming algorithm.
  • Basic data types: Variance computation encodes each integer as (x, x^2), validates the square relation, and derives variance from E[X^2] − (E[X])^2.The same summation AFE is applied to both components.
  • Machine learning: Prio extends private summation to robustly train linear models, including least-squares regression on d-dimensional feature vectors.The regression AFE outputs coefficients and additional covariance information, while the one-dimensional version computes c0 and c1 from truncated encoded sums.

6 Evaluation

Prio’s evaluation shows that its privacy and robustness mechanisms remain practical across server deployments, application domains, and high-dimensional workloads. SNIPs substantially reduce robustness, bandwidth, and server-side costs relative to NIZK-based alternatives, while client encoding remains small in absolute terms.

  • Microbenchmarks: Prio’s throughput stays within 5× of the no-privacy scheme for many submission sizes and exceeds the NIZK-based scheme by more than an order of magnitude.
  • Microbenchmarks: Adding more servers barely affects Prio’s throughput because client-submission checking is load-balanced across the servers.A leader coordinates each check, while leadership responsibility is distributed across servers as the cluster grows.
  • Microbenchmarks: As submitted vectors grow, Prio provides a 4,000-fold server-bandwidth saving over NIZKs.Prio servers transmit a constant number of bits per submission, independent of submission size or Valid-routine complexity.
  • Application scenarios: Prio requires O(M log M) small-field multiplications for a Valid circuit with M multiplication gates, whereas discrete-log NIZKs require 2M exponentiations.The client performs only a single public-key encryption, making Prio substantially cheaper for practical M.
  • Machine learning: Prio’s privacy and robustness impose roughly a 50× client slowdown over the no-privacy scheme, but encoding still costs about one tenth of a second.
  • Application scenarios: On the server side, Prio incurs a 1-2× slowdown over no robustness and a 5-15× slowdown over no privacy, compared with 100-200× for NIZK robustness.

7 Discussion

Prio’s deployment discussion covers assumptions, practical server arrangements, and attacks that remain possible despite its privacy protections. The system requires enough honest client participation and all servers to be honest for robustness.

  • Prio preserves client privacy when at least one server behaves honestly, including against an adversary controlling the network, most servers, and many clients.
  • Deployment scenarios: Organizations can distribute Prio servers across operators, countries, or institutions to compute aggregates without centralizing clients’ data in cleartext.Examples include app-store/developer pairs, shared datasets, external auditors, and jurisdictionally diverse deployments.
  • Common attacks: A selective denial-of-service attack can isolate one honest client, allowing an adversary who knows malicious inputs to infer part or all of that client’s value.The attack prevents other honest clients from contacting the servers before an exact aggregate is produced.
  • Deployment scenarios: Servers should publish aggregates only after ensuring that many honest clients contributed, using registered-client thresholds or other out-of-band mechanisms.This limits attacks that exploit aggregates containing too few honest client values.
  • Common attacks: If client values remain constant over time, differencing aggregates can reveal an individual’s value; differential-privacy noise can mitigate this risk.The attack learns f(x1, . . . , xn)−f(x1, . . . , xn−1), which may expose client n’s value when f computes a sum.
  • Robustness against malicious servers: Prio provides robustness only when all servers are honest, because robustness against faulty servers weakens the privacy coalition threshold.The paper explicitly weighs stronger malicious-server robustness against its security and performance costs.

8 Related Work

Related systems trade off privacy, robustness, generality, anonymity, and scalability in different ways. Prio is positioned against secret-sharing, anonymity-network, differential-privacy, and general MPC approaches.

  • Secret-sharing data-collection systems commonly lack robustness against malicious clients, rely on expensive NIZKs, or fail to protect against actively malicious servers.
  • Mix-nets and DC-nets provide strong privacy but require expensive verifiable mixing or server work quadratic in the number of client messages.
  • Prio protects against an adversary that observes and controls the entire network, whereas Tor-based schemes remain vulnerable to traffic-analysis attacks.
  • Client-side differential privacy offers plausible deniability, but little noise weakens privacy while much noise can erase low-frequency events.Server-added noise is described as a way to ameliorate these problems.
  • General MPC can privately compute arbitrary functions, but its bandwidth and computational costs make large-scale aggregation potentially impractical.The paper contrasts full MPC with Prio’s five-server processing of millions of inputs in tens of minutes.

9 Conclusion and future work

The paper concludes that Prio combines private aggregation, client-misbehavior defenses, and near-baseline performance. It identifies broader aggregation functions and shorter SNIPs as future directions.

  • Prio computes aggregate statistics while preserving client privacy, defending against client misbehavior, and performing nearly as well as systems lacking these protections.
  • Future work includes extending Prio beyond summation to more general encoding-combination functions and determining which stronger aggregation functions this enables.
  • Current SNIP proofs grow linearly with the size of the Valid circuit, motivating investigation of sublinear-size information-theoretic proofs.

A Security definitions

The security definitions formalize privacy, anonymity, robustness, and symmetry requirements for aggregate computation. They show that symmetric functions support anonymity, while nonsymmetric functions cannot be anonymously computed.

  • Security definitions: f-privacy is defined for deployments with s servers and n client values included in the final aggregate.
  • Security boundary: Because the adversary learns the honest-client aggregate exactly, honest servers must use out-of-band means to ensure that many honest values enter the final output.
  • Security definitions: Anonymity is defined as f-privacy for SORT, which reveals the honest clients’ input list but not which client submitted each value.
  • Symmetry and anonymity: A symmetric function is invariant under permutations of its inputs, a property required for anonymous data collection.
  • Symmetry and anonymity: For symmetric f, f-privacy implies anonymity because a simulator can sort inputs, compute f, and simulate the protocol transcript from that output.
  • Symmetry and anonymity: No anonymous data-collection scheme can correctly compute a nonsymmetric function, because permuted inputs may require different outputs while anonymity supplies only their sorted values.
  • Robustness: Robustness permits malicious clients to choose arbitrary valid inputs but prevents them from influencing the aggregate in other ways when all servers are honest.

B Robustness against faulty servers

Prio protects client privacy when at least one server is honest, but its robustness guarantee applies only when all servers are honest. The system uses SNIPs to validate client submissions while preserving privacy, with soundness established against computationally unbounded adversaries.

  • At least one honest server suffices for Prio to reveal nothing about clients’ data beyond the aggregate statistic.
  • Prio provides robustness only when all servers are honest.Robustness against faulty servers would weaken privacy because dishonest servers could reconstruct an output from a single client’s submission.
  • Strengthening robustness against faulty servers would also impose performance costs by requiring Prio to abandon leader-based optimizations.A faulty leader can compromise robustness but not privacy.
  • The SNIP protocol is sound against adversaries that may be computationally unbounded.Its soundness error is bounded by (2M + 1)/|F|, where M is the number of multiplication gates in the Valid circuit.

D.2 Zero knowledge property

Prio’s zero-knowledge property ensures that malicious servers learn nothing about valid client inputs from SNIP verification when at least one server is honest. The proof uses simulation to show that adversarial views are identical to views generated without the client’s data.

  • When at least one server is honest, an adversary controlling the remaining servers learns nothing about a valid client’s data through SNIP verification.The adversary’s interaction can be perfectly simulated without knowledge of the client’s input.
  • Zero knowledge requires that no adversary, even a computationally unbounded one, can distinguish real and ideal protocol executions.The simulator receives the random evaluation point r but not the client’s private data.
  • For any two valid client inputs, the adversary’s protocol view is identically distributed.Consequently, the adversary cannot determine whether a candidate guess about the client’s value is correct.
  • The zero-knowledge property is required only when r is outside the set {1, . . . , M}.Sampling from a field with |F| ≫ 2M makes the probability of entering this bad set negligibly small.
  • The zero-knowledge argument relies on f(r) and g(r) being uniform and independent of the adversary’s initial view for relevant evaluation points.Random choices of f(0) and g(0) provide this independence, enabling perfect simulation.
  • Randomizing the polynomials f and g prevents malicious servers from testing validity predicates on shifted versions of a client’s input.Without this randomization, a malicious server could learn non-trivial information about x by deviating from the protocol.

E Server-side Valid computation

The server-side Valid computation lets servers evaluate whether secret-shared client data satisfies an arithmetic-circuit predicate without revealing the data, while exposing only the predicate output under its stated security model.

  • Servers can compute Valid(x) on secret inputs without learning anything about x beyond the value of Valid(x).The client also learns nothing about the Valid circuit except its number of multiplication gates.
  • The server-side variant provides security only against honest-but-curious servers.Security against actively malicious servers is left as future work, with a possible client-assisted SPDZ-based extension mentioned.
  • A server-side Valid computation requires clients to provide multiplication-triple shares and a share of their private value.The circuit checks that each supplied triple satisfies c_t = a_t · b_t.
  • The computation exchanges Θ(M) field elements, with communication rounds proportional to the Valid circuit’s multiplicative depth.M denotes the number of multiplication gates in the Valid circuit.

G Additional AFEs

Prio’s additional AFEs support approximate counting, popular-string recovery, and private evaluation of regression-model accuracy. These constructions trade efficiency and functionality against explicitly described leakage or parameter-dependent approximation.

  • Approximate counts: The count-min sketch AFE supports large domains with counts that are at most an additive ϵn overestimate.It uses ln(1/δ) frequency-count instances, each over a set of size e/ϵ.
  • The count-min sketch AFE leaks the contents of the sketch containing all clients’ values.The frequency-count AFE also reveals the number of values having each bit set.
  • Most popular: The popular-string construction is efficient for a string held by more than n/2 clients, even when the string universe is large.For large universes, Prio uses a simplified bucket-based data structure rather than querying every possible string.
  • Most popular: The frequency-count AFE returns a string held by more than 50% of clients.Decode rounds summed encoded bits to recover the dominant bit string.
  • Evaluating an arbitrary ML model: Prio can privately compute the R2 coefficient for a public regression model from client-provided features and targets.The encoding includes y, y^2, (y−ŷ)^2, and x, while Valid checks the required relationships.
  • Evaluating an arbitrary ML model: The regression AFE is private relative to the R2 coefficient together with the expectation and variance of the client targets.

H Prio protocol and proof sketch

Prio lets clients secret-share encoded private values, validates submissions with SNIPs, aggregates selected components, and publishes a decoded aggregate. Its proof sketch establishes robustness, conditional f-privacy, and symmetry-dependent anonymity, while optimizations reduce sharing and verification costs.

  • Protocol: Clients encode private values, secret-share each encoding across servers, and attach shares of a SNIP proving the submission is well-formed.Servers jointly validate each submission and reject it when the SNIP check fails.
  • Protocol: Servers truncate each client share to k′ components, add shares into accumulators, and publish accumulator values whose sum is decoded as the aggregate.The protocol proceeds through upload, validation, aggregation, and publication.
  • Security: Robustness follows from SNIP soundness: honest servers correctly identify and reject client submissions that are not proper AFE encodings.The security sketch also models privacy by composing an AFE simulator with a simulator for the complete protocol.
  • Security: Under at least one correctly executing server, private AFE construction, and zero-knowledge SNIPs, the adversary learns only the aggregate function value on included honest clients.The claim is established by simulating protocol transcripts from the aggregate output and permitted adversarial interactions.
  • Security and optimizations: Anonymity follows when the aggregation function is symmetric and is impossible otherwise; PRG sharing and fixed-point verification reduce communication and computation costs.PRG sharing reduces shares from sL field elements to L+O(1), while fixed evaluation reduces interpolation and evaluation from Θ(M log M) to M multiplications per server.
Loading 1703.06255v1…