Prio: Private, Robust, and Scalable Computation of Aggregate Statistics
Henry Corrigan-Gibbs and Dan Boneh
Stanford University
March 14, 2017

Abstract. This paper presents Prio, a privacy-preserving
system for the collection of aggregate statistics. Each Prioclient 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 Prioservers 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 theface 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. Prioextends 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

Our smartphones, cars, and wearable electronics are constantly sending telemetry data and other sensor readings
back to cloud services. With these data in hand, a cloudservice can compute useful aggregate statistics over theentire population of devices. For example, navigation app
providers collect real-time location data from their users
to identify areas of traffic congestion in a city and route
drivers along the least-crowded roads [80]. Fitness tracking services collect information on their users’ physicalactivity so that each user can see how her fitness regimen compares to the average [75]. Web browser vendors
collect lists of unusually popular homepages to detect
homepage-hijacking adware [57].
Even when a cloud service is only interested in learning
aggregate statistics about its user population as a whole,such services often end up collecting private data fromeach client and storing it for aggregation later on. These
centralized caches of private user data pose severe security and privacy risks: motivated attackers may steal anddisclose clients’ sensitive information [84,117], cloud services may misuse the clients’ information for profit [112],and intelligence agencies may appropriate the data fortargeting or mass surveillance purposes [65].
This is the extended version of a paper by the same title that appeared at
NSDI 2017. This version includes additional security analysis, corrects
typos, and fixes an error in the proceedings version.

To ameliorate these threats, major technology companies, including Apple [72] and Google [57, 58], have
deployed privacy-preserving systems for the collectionof user data. These systems use a “randomized response”
mechanism to achieve differential privacy [54, 118]. For
example, a mobile phone vendor may want to learn how
many of its phones have a particular uncommon but sensitive app installed (e.g., the AIDSinfo app [113]). In thesimplest variant of this approach, each phone sends thevendor a bit indicating whether it has the app installed,
except that the phone flips its bit with a fixed probability
p < 0.5. By summing a large number of these noisy bits,
the vendor can get a good estimate of the true number ofphones that are running the sensitive app.
This technique scales very well and is robust even if
some of the phones are malicious—each phone can influence the final sum by ±1 at most. However, randomizedresponse-based systems provide relatively weak privacy
guarantees: every bit that each phone transmits leakssome private user information to the vendor. In particular,when p = 0.1 the vendor has a good chance of seeing thecorrect (unflipped) user response. Increasing the noiselevel p decreases this leakage, but adding more noise also
decreases the accuracy of the vendor’s final estimate. As
an example, assume that the vendor collects randomized
responses from one million phones using p = 0.49, andthat 1% of phones have the sensitive app installed. Even
with such a large number of responses, the vendor will
incorrectly conclude that no phones have the app installedroughly one third of the time.
An alternative approach to the data-collection problem
is to have the phones send encryptions of their bits to aset of servers. The servers can sum up the encrypted bits
and decrypt only the final sum [48, 56, 81, 92, 99, 100].
As long as all servers do not collude, these encryptionbased systems provide much stronger privacy guarantees:
the system leaks nothing about a user’s private bit to thevendor, except what the vendor can infer from the final
sum. By carefully adding structured noise to the final
sum, these systems can provide differential privacy aswell [56, 92, 107].
However, in gaining this type of privacy, many secretsharing-based systems sacrifice robustness: a malicious
client can send the servers an encryption of a large integer
value v instead of a zero/one bit. Since the client’s value
v is encrypted, the servers cannot tell from inspecting theciphertext that v > 1. Using this approach, a single malicious client can increase the final sum by v, instead of by 1.
Clients often have an incentive to cheat in this way: an
app developer could use this attack to boost the perceived
popularity of her app, with the goal of getting it to appear
on the app store’s home page. It is possible to protect
against these attacks using zero-knowledge proofs [107],but these protections destroy scalability: checking theproofs requires heavy public-key cryptographic operations at the servers and can increase the servers’ workload
by orders of magnitude.
In this paper, we introduce Prio, a system for private
aggregation that resolves the tension between privacy,
robustness, and scalability. Prio uses a small number ofservers; as long as one of the Prio servers is honest, thesystem leaks nearly nothing about clients’ private data (ina sense we precisely define), except what the aggregate
statistic itself reveals. In this sense, Prio provides a strong
form of cryptographic privacy. This property holds evenagainst an adversary who can observe the entire network,
control all but one of the servers, and control a large
number of clients.
Prio also maintains robustness in the presence of an
unbounded number of malicious clients, since the Prioservers can detect and reject syntactically incorrect client
submissions in a privacy-preserving way. For instance, a
car cannot report a speed of 100,000 km/h if the systemparameters only allow speeds between 0 and 200 km/h.
Of course, Prio cannot prevent a malicious client from
submitting an untruthful data value: for example, a faulty
car can always misreport its actual speed.
To provide robustness, Prio uses a new technique that
we call secret-shared non-interactive proofs (SNIPs).
When a client sends an encoding of its private data to thePrio servers, the client also sends to each server a “share”
of a proof of correctness. Even if the client is malicious
and the proof shares are malformed, the servers can use
these shares to collaboratively check—without ever seeing the client’s private data in the clear—that the client’s
encoded submission is syntactically valid. These proofs
rely only upon fast, information-theoretic cryptography,
and require the servers to exchange only a few hundred
bytes of information to check each client’s submission.
Prio provides privacy and robustness without sacrificing scalability. When deployed on a collection of five
servers spread around the world and configured to compute private sums over vectors of private client data, Prio
imposes a 5.7× slowdown over a naïve data-collection
system that provides no privacy guarantees whatsoever.
In contrast, a state-of-the-art comparison system that uses
client-generated non-interactive zero-knowledge proofsof correctness (NIZKs) [22, 103] imposes a 267× slowdown at the servers. Prio improves client performance as
well: it is 50-100× faster than NIZKs and we estimatethat it is three orders of magnitude faster than methods
based on succinct non-interactive arguments of knowledge (SNARKs) [16,62,97]. The system is fast in absoluteterms as well: when configured up to privately collect the
distribution of responses to a survey with 434 true/false
questions, the client performs only 26 ms of computation,and our distributed cluster of Prio servers can processeach client submission in under 2 ms on average.
Contributions. In this paper, we:• introduce secret-shared non-interactive proofs (SNIPs),a new type of information-theoretic zero-knowledge
proof, optimized for the client/server setting,• present affine-aggregatable encodings, a frameworkthat unifies many data-encoding techniques used inprior work on private aggregation, and• demonstrate how to combine these encodings with
SNIPs to provide robustness and privacy in a largescale data-collection system.
With Prio, we demonstrate that data-collection systems
can simultaneously achieve strong privacy, robustness tofaulty clients, and performance at scale.

2

System goals

A Prio deployment consists of a small number of infrastructure servers and a very large number of clients. In
each time epoch, every client i in the system holds aprivate value xi . The goal of the system is to allow theservers to compute f (x1 , . . . , xn ), for some aggregation
function f , in a way that leaks as little as possible about
each client’s private xi values to the servers.
Threat model. The parties to a Prio deployment must
establish pairwise authenticated and encrypted channels.
Towards this end, we assume the existence of a publickey infrastructure and the basic cryptographic primitives(CCA-secure public-key encryption [43, 108, 109], digital
signatures [71], etc.) that make secure channels possible.
We make no synchrony assumptions about the network:
the adversary may drop or reorder packets on the networkat will, and the adversary may monitor all links in the network. Low-latency anonymity systems, such as Tor [51],provide no anonymity in this setting, and Prio does notrely on such systems to protect client privacy.
Security properties. Prio protects client privacy as longas at least one server is honest. Prio provides robustness (correctness) only if all servers are honest. We summarize our security definitions here, but please refer toAppendix A for details.
Anonymity. A data-collection scheme maintains client
anonymity if the adversary cannot tell which honest client
submitted which data value through the system, even

if the adversary chooses the honest clients’ data values,
controls all other clients, and controls all but one server.
Prio always protects client anonymity.
Privacy. Prio provides f -privacy, for an aggregation function f , if an adversary, who controls any number of clientsand all but one server, learns nothing about the honest
clients’ values xi , except what she can learn from the valuef (x1 , . . . , xn ) itself. More precisely, given f (x1 , . . . , xn ),every adversary controlling a proper subset of the servers,
along with any number of clients, can simulate its viewof the protocol run.
For many of the aggregation functions f that Prio implements, Prio provides strict f -privacy. For some aggregation functions, which we highlight in Section 5,
Prio provides fˆ-privacy, where fˆ is a function that outputs slightly more information than f . More precisely,fˆ(x1 , . . . , xn ) = f (x1 , . . . , xn ), L(x1 , . . . , xn ) for somemodest leakage function L.
Prio does not natively provide differential privacy [54],since the system adds no noise to the aggregate statistics
it computes. In Section 7, we discuss when differential
privacy may be useful and how we can extend Prio toprovide it.
Robustness. A private aggregation system is robust if a
coalition of malicious clients can affect the output of thesystem only by misreporting their private data values; acoalition of malicious clients cannot otherwise corrupt thesystem’s output. For example, if the function f (x1 , . . . , xn )counts the number of times a certain string appears in theset {x1 , . . . , xn }, then a single malicious client should be
able to affect the count by at most one.
Prio is robust only against adversarial clients—not
against adversarial servers. Although providing robustness against malicious servers seems desirable at firstglance, doing so would come at privacy and performancecosts, which we discuss in Appendix B. Since there could
be millions of clients in a Prio deployment, and only ahandful of servers (in fixed locations with known administrators), it may also be possible to eject faulty servers
using out-of-band means.

3

A simple scheme

Let us introduce Prio by first presenting a simplified version of it. In this simple version, each client holds a
one-bit integer xi and the servers want to compute theP
sum of the clients’ private values i xi . Even this very
basic functionality has many real-world applications. For
example, the developer of a health data mobile app could
use this scheme to collect the number of app users who
have a certain medical condition. In this application, thebit xi would indicate whether the user has the condition,and the sum over the xi s gives the count of affected users.

The public parameters for the Prio deployment include
a prime p. Throughout this paper, when we write “c =a+b ∈ F p ,” we mean “c = a+b (mod p).” The simplified
Prio scheme for computing sums proceeds in three steps:
1. Upload. Each client i splits its private value xi
into s shares, one per server, using a secret-sharing
scheme. In particular, the client picks random integers [xi ]1 , . . . , [xi ] s ∈ F p , subject to the constraint:
xi = [xi ]1 + · · · + [xi ] s ∈ F p . The client then sends,
over an encrypted and authenticated channel, one
share of its submission to each server.
2. Aggregate. Each server j holds an accumulator
value A j ∈ F p , initialized to zero. Upon receiving ashare from the ith client, the server adds the uploaded
share into its accumulator: A j ← A j + [xi ] j ∈ F p .
3. Publish. Once the servers have received a sharefrom each client, they publish their accumulator values. Computing the sum of the accumulator valPP
ues j A j ∈ F p yields the desired sum i xi of theclients’ private values, as long as the modulus p isPlarger than the number of clients (i.e., the sum i xi
does not “overflow” the modulus).
There are two observations we can make about thisscheme. First, even this simple scheme provides privacy:Pthe servers learn the sum i xi but they learn nothing else
about the clients’ private inputs. Second, the scheme does
not provide robustness. A single malicious client cancompletely corrupt the protocol output by submitting (forexample), a random integer r ∈ F p to each server.
The core contributions of Prio are to improve this basic
scheme in terms of security and functionality. In termsof security, Prio extends the simple scheme to provide
robustness in the face of malicious clients. In terms offunctionality, Prio extends the simple scheme to allow
privacy-preserving computation of a wide array of aggregation functions (not just sum).

4

Protecting correctness with SNIPs

Upon receiving shares of a client’s data value, the Prioservers need a way to check if the client-submitted value
is well formed. For example, in the simplified protocolof Section 3, every client is supposed to send the servers
the share of a value x such that 0 ≤ x ≤ 1. However,since the client sends only a single share of its value x toeach server—to preserve privacy—each server essentially
receives an encrypted version of x and cannot unilaterally
determine if x is well formed. In the more general setting,each Prio client submits to each server a share [x]i of avector x ∈ FL , for some finite field F. The servers hold avalidation predicate Valid(·), and should only accept theclient’s data submission if Valid(x) = 1 (Figure 1).

x1 x2 x3 …

(a) The client sends a share of
its encoded submission and SNIP
proof to each server.

f(x1, …, xn)

xn

Verify(b) The servers validate the client’s
SNIP proof to ensure that the submission is valid.

✓OK(c) If the checks pass, the servers
update their local accumulatorswith the client-provided data.

(d) After accumulating many packets, the servers publish their accumulators to reveal the aggregate.

Figure 1: An overview of the Prio pipeline for processing client submissions.

To execute this check in Prio, we introduce a new cryptographic tool called secret-shared non-interactive proofs(“SNIPs”). With these proofs, the client can quickly proveto the servers that Valid(x) = 1, for an arbitrary function
Valid, without leaking anything else about x to the servers.
Building blocks. All arithmetic in this section takes place
in a finite field F, or modulo a prime p, if you prefer. We
use a simple additive secret-sharing scheme over F: tosplit a value x ∈ F into s shares, choose random values([x]1 , . . . , [x] s ) ∈ F s subject to the constraint that x =P
i [x]i ∈ F. In our notation, [x]i denotes the ith share of x.
An adversary who gets hold of any subset of up to s − 1shares of x learns nothing, in an information-theoretic
sense, about x from the shares.
This secret-sharing scheme is linear, which means thatthe servers can perform affine operations on shares without communicating. That is, by adding shares [x]i and[y]i , the servers can locally construct shares [x+y]i . Givena share [x]i , the servers can also construct shares [αx + β]i ,for any constants α, β ∈ F. (This is a classic observationfrom the multi-party computation literature [15].)
Our construction uses arithmetic circuits. An arithmetic circuit is like a boolean circuit except that it uses
finite-field multiplication, addition, and multiplicationby-constant gates, instead of boolean and, or, and notgates. See Appendix C.1 for a formal definition.

4.1

Overview

A secret-shared non-interactive proof (SNIP) protocol
consists of an interaction between a client (the prover)and multiple servers (the verifiers). At the start of the
protocol:– each server i holds a vector [x]i ∈ FL ,P
– the client holds the vector x = i [x]i ∈ FL , and– all parties hold an arithmetic circuit representing a
predicate Valid : FL → F.
The client’s goal is to convince the servers that Valid(x) =1, without leaking anything else about x to the servers. To
do so, the client sends a proof string to each server. After
receiving these proof strings, the servers gossip amongst
themselves and then conclude either that Valid(x) = 1(the servers “accept x”) or not (the servers “reject x”).

For a SNIP to be useful in Prio, it must satisfy thefollowing properties:
Correctness. If all parties are honest, the servers will
accept x.
Soundness. If all servers are honest, and if Valid(x) , 1,
then for all malicious clients, even ones running insuper-polynomial time, the servers will reject x withoverwhelming probability. In other words, no matter
how the client cheats, the servers will almost always
reject x.
Zero knowledge. If the client and at least one server arehonest, then the servers learn nothing about x, exceptthat Valid(x) = 1. More precisely, there exists a simulator (that does not take x as input) that accurately
reproduces the view of any proper subset of malicious
servers executing the SNIP protocol.
See Appendix D for formal definitions.
These three security properties are nearly identical tothe properties required of a zero-knowledge interactive
proof system [70]. However, in the conventional zeroknowledge setting, there is a single prover and single
verifier, whereas here we have a single prover (the client)and many verifiers (the servers).
Our contribution. We devise a SNIP that requires minimal
server-to-server communication, is compatible with any
public Valid circuit, and relies solely on fast, informationtheoretic primitives. (We discuss how to hide the Valid
circuit from the client in Section 4.4.)
To build the SNIP, we first generalize a “batch verification” technique of Ben-Sasson et al. [19] and thenshow how a set of servers can use it to verify an entire
circuit computation by exchanging a only few field elements. We implement this last step with a new adaptationof Beaver’s multi-party computation (MPC) protocol tothe client/server setting [9].
Related techniques. Prior work has studied interactive
proofs in both the many-prover [14, 60] and many-verifier
settings [1, 10]. Prior many-verifier protocols require relatively expensive public-key primitives [1] or require anamount of server-to-server traffic that grows linearly inthe size of the circuit for the Valid function [10]. In con-

current independent work, Boyle et al. [25] construct what
we can view as a very efficient SNIP for a specific Validfunction, in which the servers are semi-honest (“honest
but curious”) [25]. They also use a Beaver-style MPC multiplication; their techniques otherwise differ from ours.

4.2

Constructing SNIPs

To run the SNIP protocol, the client and servers executethe following steps:
Set-up. Let M be the number of multiplication gates in
the arithmetic circuit for Valid. We work over a field Fthat is large enough to ensure that 2M + 2  |F|.
Step 1: Client evaluation. The client evaluates the Valid
circuit on its input x. The client thus knows the value thatevery wire in the circuit takes on during the computationof Valid(x). The client uses these wire values to constructthree randomized polynomials f , g, and h, which encode
the values on the input and output wires of each of the M
multiplication gates in the Valid(x) computation.
Label the M multiplication gates in the Valid(x) circuit, in topological order from inputs to outputs, with thenumbers {1, . . . , M}. For t ∈ {1, . . . , M}, let us define ut
and vt to be the values on the left and right input wiresof the t-th multiplication gate. The client chooses u0 andv0 to be values sampled independently and uniformly at
random from F. Then, we define f and g to be the lowestdegree polynomials such that f (t) = ut and g(t) = vt , forall t ∈ {0, . . . , M}. Then, we define the polynomial h as
h = f · g.
The polynomials f and g will have degree at most M,
and the polynomial h will have degree at most 2M. Sinceh(t) = f (t) · g(t) = ut · vt for all t ∈ {1, . . . , M}, h(t) is
equal to the value of the output wire (ut · vt ) of the t-th
multiplication gate in the Valid(x) circuit, for 1 ≤ t ≤ M.
In Step 1 of the checking protocol, the client executes
the computation of Valid(x), uses polynomial interpolation to construct the polynomials f and g, and multiplies
these polynomials to produce h = f · g. The client thensplits the random values f (0) = u0 and g(0) = v0 , using
additive secret sharing, and send shares [ f (0)]i and [g(0)]ito server i. The client also splits the coefficients of h andsends the ith share of the coefficients [h]i to server i.
Step 2: Consistency checking at the servers. Each
server i holds a share [x]i of the client’s private value x.
Each server also holds shares [ f (0)]i , [g(0)]i , and [h]i .
Using these values, each server can—without communicating with the other servers—produce shares [ f ]i and[g]i of the polynomials f and g.
To see how, first observe that if a server has a share ofevery wire value in the circuit, along with shares of f (0)and g(0), it can construct [ f ]i and [g]i using polynomialinterpolation. Next, realize that each server can reconstruct a share of every wire value in the circuit since eachserver:• has a share of each of the input wire values ([x]i ),• has a share of each wire value coming out of a multiplication gate (for t ∈ {1, . . . , M}, the value [h]i (t) isa share of the t-th such wire), and• can derive all other wire value shares via affine operations on the wire value shares it already has.
Using these wire value shares, the servers use polynomialinterpolation to construct [ f ]i and [g]i .
If the client and servers have acted honestly up to thispoint, then the servers will now hold shares of polynomials f , g, and h such that f · g = h.
In contrast, a malicious client could have sent theservers shares of a polynomial ĥ such that, for somet ∈ {1, . . . , M}, ĥ(t) is not the value on the output wire in
the t-th multiplication gate of the Valid(x) computation.
In this case, the servers will reconstruct shares of polynomials fˆ and ĝ that might not be equal to f and g. We
will then have with certainty that ĥ , fˆ · ĝ. To see why,
consider the least t0 for which ĥ(t0 ) , h(t0 ). For all t ≤ t0 ,fˆ(t) = f (t) and ĝ(t) = g(t), by construction. Sinceĥ(t0 ) , h(t0 ) = f (t0 ) · g(t0 ) = fˆ(t0 ) · ĝ(t0 ),it must be that ĥ(t0 ) , fˆ(t0 ) · ĝ(t0 ), so ĥ , fˆ · ĝ. (BenSasson et al. [19] use polynomial identities to check theconsistency of secret-shared values in a very different
MPC protocol. Their construction inspired our approach.)
Step 3a: Polynomial identity test. At the start of thisstep, each server i holds shares [ fˆ]i , [ĝ]i , and [ĥ]i of polynomials fˆ, ĝ, and ĥ. Furthermore, it holds that fˆ · ĝ = ĥif and only if the servers collectively hold a set of wire
value shares that, when summed up, equal the internal
wire values of the Valid(x) circuit computation.
The servers now execute a variant of the SchwartzZippel randomized polynomial identity test [104, 126]
to check whether this relation holds. The principle ofthe test is that if fˆ(t) · ĝ(t) , ĥ(t), then the polynomialt · ( fˆ(t) · ĝ(t) − ĥ(t)) is a non-zero polynomial of degree at
most 2M + 1. (Multiplying the polynomial fˆ · g − ĥ by t
is useful for the next step.) Such a polynomial can have at
most 2M + 1 zeros in F, so if we choose a random r ∈ F
and evaluate r · ( fˆ(r) · ĝ(r) − ĥ(r)), the servers will detectthat fˆ · ĝ , ĥ with probability at least 1 − 2M+1
|F| .
To execute the polynomial identity test, one of theservers samples a random value r ∈ F. Each server i thenevaluates her share of each of the three polynomials on
the point r to get [ fˆ(r)]i , [ĝ(r)]i , and [ĥ(r)]i . The servers
can perform this step locally, since polynomial evaluation
requires only affine operations on shares. Each server thenapplies a local linear operation to these last two shares to
produce shares of [r · ĝ(r)]i , and [r · ĥ(r)]i .

Assume for a moment that each server i can multiply
her shares [ fˆ(r)]i and [r · ĝ(r)]i to produce a share [r · fˆ(r) ·ĝ(r)]i . In this case, the servers can use a linear operation
to get shares σi = [r · ( fˆ(r) · ĝ(r) − ĥ(r))]i . The serversPthen publish these σi s and ensure that i σi = 0 ∈ F. The
P
servers reject the client’s submission if i σi , 0.
Step 3b: Multiplication of shares. Finally, the servers
must somehow multiply their shares [ fˆ(r)]i and [r · ĝ(r)]ito get a share [r · fˆ(r) · ĝ(r)]i without leaking anything
to each other about the values fˆ(r) and ĝ(r). To do so,
we adapt a multi-party computation (MPC) technique of
Beaver [9]. The details of Beaver’s MPC protocol are
not critical here, but we include them for reference inAppendix C.2.
Beaver’s result implies that if servers receive, from atrusted dealer, one-time-use shares ([a]i , [b]i , [c]i ) ∈ F3 ofrandom values such that a · b = c ∈ F (“multiplication
triples”), then the servers can very efficiently execute a
multi-party multiplication of a pair secret-shared values.
Furthermore, the multiplication protocol is fast: it requires
each server to broadcast a single message.
In the traditional MPC setting, the parties to the computation have to run an expensive cryptographic protocol
to generate the multiplication triples themselves [46]. In
our setting however, the client generates the multiplication triple on behalf of the servers: the client chooses(a, b, c) ∈ F3 such that a · b = c ∈ F, and sends shares ofthese values to each server. If the client produces sharesof these values correctly, then the servers can perform
a multi-party multiplication of shares to complete thecorrectness check of the prior section.
Crucially, we can ensure that even if the client sends
shares of an invalid multiplication triple to the servers,
the servers will still catch the cheating client with highprobability. First, say that a cheating client sends theservers shares ([a]i , [b]i , [c]i ) ∈ F3 such that a · b , c ∈ F.
Then we can write a · b = (c + α) ∈ F, for some constant
α > 0.
In this case, when the servers run Beaver’s MPC multiplication protocol to execute the polynomial identity
test, the result of the test will be shifted by α. (To confirm this, consult our summary of Beaver’s protocol in
Appendix C.2.) So the servers will effectively testingwhether the polynomialP̂(t) = t · ( fˆ(t) · ĝ(t) − ĥ(t)) + α
is identically zero. Whenever fˆ · ĝ , ĥ, it holds thatt · ( fˆ(t) · ĝ(t) − ĥ(t)) is a non-zero polynomial. So, if
fˆ · ĝ , ĥ, then P̂(t) must also be a non-zero polynomial.
(In constructing P̂, We multiply the term “ fˆ · ĝ − ĥ” by t,
to ensure that whenever this expression is non-zero, theresulting polynomial P̂ is non-zero, even if fˆ, ĝ, and ĥ areconstant, and the client chooses α adversarially.)

Since we only require soundness to hold if all servers
are honest, we may assume that the client did not know
the servers’ random value r when the client generated
its multiplication triple. This implies that r is distributed
independently of α, and since we only require soundness
to hold if the servers are honest, we may assume that r is
sampled uniformly from F as well.
So, even if the client cheats, the servers will still be
executing the polynomial identity test on a non-zero polynomial of degree at most 2M + 1. The servers will thus
catch a cheating client with probability at least 1 − 2M+1
|F| .
In Appendix D.1, we present a formal definition of thesoundness property and we prove that it holds.
Step 4: Output verification. If all servers are honest, at the start of the final step of the protocol, eachserver i will hold a set of shares of the values that the
Valid circuit takes on during computation of Valid(x):([w1 ]i , [w2 ]i , . . . ). The servers already hold shares of
the input wires of this circuit ([x]i ), so to confirm that
Valid(x) = 1, the servers need only publish their shares ofthe output wire. When they do, the servers can sum up
these shares to confirm that the value on the output wireis equal to one, in which case it must be that Valid(x) = 1,
except with some small failure probability due to the polynomial identity test.
Putting it all together, a SNIP proof consists of one
share of the tuple π = ( f (0), g(0), h, a, b, c).

4.3

Security and efficiency

The correctness of the scheme follows by construction. To
trick the servers into accepting a malformed submission,a cheating client must subvert the polynomial identity test.
This bad event has probability at most (2M +1)/|F|, where
M is the number of multiplication gates in Valid(·). By
taking |F| ≈ 2128 , or repeating Step 3 a few times, we canmake this failure probability extremely small.
We require neither completeness nor soundness to holdin the presence of malicious servers, though we do require
soundness against malicious clients. A malicious server
can thus trick the honest servers into rejecting a wellformed client submission that they should have accepted.
This is tantamount to the malicious server mounting a
selective denial-of-service attack against the honest client.
We discuss this attack in Section 7.
We prove in Appendix D.2 that, as long as there is
at least one honest server, the dishonest servers gain no
information—in an unconditional, information-theoretic
sense—about the client’s data values nor about the values
on the internal wires in the Valid(x) circuit.
Efficiency. The remarkable property of this SNIP construction is that the server-to-server communication costServers Client

Exps.
Muls.
Proof len.
Exps./Pairs.
Muls.
Data transfer

NIZK
M
0
M
M
0
M

SNARK
M
M log M
1
1
M
1

Prio (SNIP)0
M log MM
0
M log M
1

Table 2: An asymptotic comparison of Prio with standard zeroknowledge techniques showing that Prio reduces the computational burden for clients and servers. The client holds a vectorx ∈ F M , each server i holds a share [x]i , and the client convinces
the servers that each component of x is a 0/1 value in F. We
suppress the Θ(·) notation for readability.

grows neither with the complexity of the verification circuit nor with the size of the value x (Table 2). The computation cost at the servers is essentially the same as thecost for each server to evaluate the Valid circuit locally.
That said, the client-to-server communication cost doesgrow linearly with the size of the Valid circuit. An interesting challenge would be to try to reduce the client’s
bandwidth usage without resorting to relatively expensive
public-key cryptographic techniques [17, 18, 26, 41, 97].

4.4

Computation at the servers

Constructing the SNIP proof requires the client to compute Valid(x) on its own. If the verification circuit takes
secret server-provided values as input, or is itself a secretbelonging to the servers, then the client does not haveenough information to compute Valid(x). For example,
the servers could run a proprietary verification algorithm
to detect spammy client submissions—the servers would
want to run this algorithm without revealing it to the (possibly spam-producing) clients. To handle this use case,the servers can execute the verification check themselves
at a slightly higher cost.
This variant maintains privacy only against “honest
but curious” servers—in contrast, the SNIP-based variant
maintains privacy against actively malicious servers. See
Appendix E for details.

5

Gathering complex statistics

So far, we have developed the means to compute private
sums over client-provided data (Section 3) and to checkan arbitrary validation predicate against secret-shared data
(Section 4). Combining these two ideas with careful data
encodings, which we introduce now, allows Prio to compute more sophisticated statistics over private client data.
At a high level, each client first encodes its private data
value in a prescribed way, and the servers then privately
compute the sum of the encodings. Finally, the servers
can decode the summed encodings to recover the statisticof interest. The participants perform this encoding anddecoding via a mechanism we call affine-aggregatableencodings (“AFEs”).

5.1

Affine-aggregatable encodings (AFEs)

In our setting, each client i holds a value xi ∈ D, where
D is some set of data values. The servers hold an aggregation function f : Dn → A, whose range is a set ofaggregates A. For example, the function f might computethe standard deviation of its n inputs. The servers’ goal is
to evaluate f (x1 , . . . , xn ) without learning the xi s.
An AFE gives an efficient way to encode the data
values xi such that it is possible to compute the valuef (x1 , . . . , xn ) given only the sum of the encodings of
x1 , . . . , xn . An AFE consists of three efficient algorithms(Encode, Valid, Decode), defined with respect to a field F
and two integers k and k0 , where k0 ≤ k:
• Encode(x): maps an input x ∈ D to its encoding in Fk ,• Valid(y): returns true if and only if y ∈ Fk is a valid
encoding of some data item in D,P0• Decode(σ): takes σ = ni=1 Trunck0 Encode(xi ) ∈ Fk
as input, and outputs f (x1 , . . . , xn ). The Trunck0 (·) function outputs the first k0 ≤ k components of its input.
The AFE uses all k components of the encoding in validation, but only uses k0 components to decode σ. In manyof our applications we have k0 = k.
An AFE is private with respect to a function fˆ, or simply fˆ-private, if σ reveals nothing about x1 , . . . , xn beyond
what fˆ(x1 , . . . , xn ) itself reveals. More precisely, it is possible to efficiently simulate σ given only fˆ(x1 , . . . , xn ).
Usually fˆ reveals nothing more than the aggregation function f (i.e., the minimum leakage possible), but in somecases fˆ reveals a little more than f .
For some functions f we can build more efficient f private AFEs by allowing the encoding algorithm to berandomized. In these cases, we allow the decoding algorithm to return an answer that is only an approximation of
f , and we also allow it to fail with some small probability.
Prior systems have made use of specific AFEs forsums [56, 86], standard deviations [100], counts [28, 92],
and least-squares regression [82]. Our contribution is tounify these notions and to adopt existing AFEs to enable
better composition with Prio’s SNIPs. In particular, byusing more complex encodings, we can reduce the size ofthe circuit for Valid, which results in shorter SNIP proofs.
AFEs in Prio: Putting it all together. The full Priosystem computes f (x1 , . . . , xn ) privately as follows (seeFigure 1): Each client encodes its data value x using the
AFE Encode routine for the aggregation function f . Then,
as in the simple scheme of Section 3, every client splits
its encoding into s shares and sends one share to each of
the s servers. The client uses a SNIP proof (Section 4) toconvince the servers that its encoding satisfies the AFE
Valid predicate.
Upon receiving a client’s submission, the servers verify the SNIP to ensure that the encoding is well-formed.
If the servers conclude that the encoding is valid, every
server adds the first k0 components of the encoding shareto its local running accumulator. (Recall that k0 is a parameter of the AFE scheme.) Finally, after collecting
valid submissions from many clients, every server publishes its local accumulator, enabling anyone to run the
AFE Decode routine to compute the final statistic in theclear. The formal description of the system is presented
in Appendix H, where we also analyze its security.
Limitations. There exist aggregation functions for which
all AFE constructions must have large encodings. For
instance, say that each of n clients holds an integer xi ,where 1 ≤ xi ≤ n. We might like an AFE that computes
the median of these integers {x1 , . . . , xn }, working over a
field F with |F| ≈ nd , for some constant d ≥ 1.
We show that there is no such AFE whose encodings
consist of k0 ∈ o(n/ log n) field elements. Suppose, towards a contradiction, that such an AFE did exist. Then
we could describe any sum of encodings using at mostO(k0 log |F|) = o(n) bits of information. From this AFE,
we could build a single-pass, space-o(n) streaming algorithm for computing the exact median of an n-item stream.
But every single-pass streaming algorithm for computing
the exact median over an n-item stream requires Ω(n) bitsof space [74], which is a contradiction. Similar arguments
may rule out space-efficient AFE constructions for othernatural functions.

5.2

Aggregating basic data types

This section presents the basic affine-aggregatable encoding schemes that serve as building blocks for the moresophisticated schemes. In the following constructions, theclients hold data values x1 , . . . , xn ∈ D, and our goal is tocompute an aggregate f (x1 , . . . , xn ).
In constructing these encodings, we have two goals.
The first is to ensure that the AFE leaks as little as possible
about the xi s, apart from the value f (x1 , . . . , xn ) itself. The
second is to minimize the number of multiplication gatesin the arithmetic circuit for Valid, since the cost of theSNIPs grows with this quantity.
In what follows, we let λ be a security parameter, suchas λ = 80 or λ = 128.
Integer sum and mean. We first construct an AFE for
computing the sum of b-bit integers. Let F be a finite
field of size at least n2b . On input 0 ≤ x ≤ 2b − 1, theEncode(x) algorithm first computes the bit representationof x, denoted (β0 , β1 , . . . , βb−1 ) ∈ {0, 1}b . It then treats thebinary digits as elements of F, and outputs
Encode(x) = (x, β0 , . . . , βb−1 ) ∈ Fb+1 .
To check that x represents a b-bit integer, the Validalgorithm ensures that each βi is a bit, and that the bits
represent x. Specifically, the algorithm checks that thefollowing equalities hold over F:Valid(Encode(x)) = x =

b−1
X
i=0

n 
 ^

2 βi ∧(βi − 1) · βi = 0 .
i

i=1The Decode algorithm takes the sum of encodings σ
as input, truncated to only the first coordinate. That is,P
σ = ni=1 Trunc1 Encode(x1 ) = x1 + · · · + xn . This σis the required aggregate output. Moreover, this AFE isclearly sum-private.
To compute the arithmetic mean, we divide the sum ofintegers by n over the rationals. Computing the productand geometric mean works in exactly the same matter,
except that we encode x using b-bit logarithms.
Variance and stddev. Using known techniques [30,100], the summation AFE above lets us compute thevariance of a set of b-bit integers using the identity:
Var(X) = E[X 2 ] − (E[X])2 . Each client encodes its integer x as (x, x2 ) and then applies the summation AFE toeach of the two components. (The Valid algorithm also
ensures that second integer is the square of the first.) The
resulting two values let us compute the variance.
This AFE also reveals the expectation E[X]. It is private with respect to the function fˆ that outputs both the
expectation and variance of the given set of integers.
When D = {0, 1} andBoolean or and and.
f (x1 , . . . , xn ) = or(x1 , . . . , xn ) the encoding operation
outputs an element of Fλ2 (i.e., a λ-bit bitstring) as:
if x = 0λ zeros
Encode(x) = a random element in Fλ if x = 1.
2
The Valid algorithm outputs “1” always, since all λ-bit
encodings are valid. The sum of encodings is simply
the xor of the n λ-bit encodings. The Decode algorithm
takes as input a λ-bit string and outputs “0” if and only if
its input is a λ-bit string of zeros. With probability 1 −2−λ , over the randomness of the encoding algorithm, thedecoding operation returns the boolean or of the encodedvalues. This AFE is or-private. A similar construction
yields an AFE for boolean and.

min and max. To compute the minimum and maximumof integers over a range {0, . . . , B − 1}, where B is small(e.g., car speeds in the range 0–250 km/h), the Encode
algorithm can represent each integer in unary as a lengthB vector of bits (β0 , . . . , βB−1 ), where βi = 1 if and only

if the client’s value x ≤ i. We can use the bitwise-or
construction above to take the or of the client-provided
vectors—the largest value containing a “1” is the maximum. To compute the minimum instead, replace or withand. This is min-private, as in the or protocol above.
When the domain is large (e.g., we want the max of
64-bit packet counters, in a networking application), we
can get a c-approximation of the min and max using asimilar idea: divide the range {0, . . . , B − 1} into b =logc B “bins” [0, c), [c, c2 ), . . . , [cb−1 , B). Then, use thesmall-range min/max construction, over the b bins, tocompute the approximate statistic. The output will bewithin a multiplicative factor of c of the true value. This
construction is private with respect to the approximate
min/max function.
Frequency count. Here, every client has a value x in asmall set of data values D = {0, . . . , B − 1}. The goal is to
output a B-element vector v, where v[i] is the number ofclients that hold the value i, for every 0 ≤ i < B.
Let F be a field of size at least n. The Encode algorithm encodes a value x ∈ D as a length-B vector(β0 , . . . , βB−1 ) ∈ FB where βi = 1 if x = i and βi = 0
otherwise. The Valid algorithm checks that each β value
is in the set {0, 1} and that the sum of the βs is exactly one.
The Decode algorithm does nothing: the final output is alength-B vector, whose ith component gives the numberof clients who took on value i. Again, this AFE is privatewith respect to the function being computed.
The output of this AFE yields enough information tocompute other useful functions (e.g., quantiles) of the
distribution of the clients’ x values. When the domain D
is large, this AFE is very inefficient. In Appendix G, wegive AFEs for approximate counts over large domains.
Sets. We can compute the intersection or union of setsover a small universe of elements using the boolean AFE
operations: represent a set of B items as its characteristic
vector of booleans, and compute an and for intersection
and an or for union. When the universe is large, theapproximate AFEs of Appendix G are more efficient.

5.3

Machine learning

We can use Prio for training machine learning models on
private client data. To do so, we exploit the observation ofKarr et al. [82] that a system for computing private sums
can also privately train linear models. (In Appendix G,
we also show how to use Prio to privately evaluate theR2 -coefficient of an existing model.) In Prio, we extend
their work by showing how to perform these tasks while
maintaining robustness against malicious clients.
Suppose that every client holds a data point (x, y) where
x and y are b-bit integers. We would like to train a modelthat takes x as input and outputs a real-valued prediction

Field size:
Mul. in field (µs)
L = 101
Prio
L
= 102
clienttime
L = 103

Workstation
87-bit 265-bit
1.013
1.485
0.003
0.004
0.024
0.036
0.221
0.344

Phone
87-bit 265-bit
11.218 14.930
0.017
0.024
0.112
0.170
1.059
2.165

Table 3: Time in seconds for a client to generate a Prio submission of L four-bit integers to be summed at the servers. Averaged
over eight runs.

ŷi = M(x) ∈ R of y. We might predict a person’s bloodpressure (y) from the number of steps they walk daily (x).
We wish to compute the least-squares linear fit h(x) =c0 + c1 x over all of the client points. With n clients, themodel coefficients c0 and c1 satisfy the linear relation:Pn    Pn n c0   i=1 yi i=1 xi 
P
(1)

Pn 2  ·   = Pnnc1
i=1 xii=1 xii=1 xi yi
To compute this linear system in an AFE, every client
encodes her private point (x, y) as a vector(x, x2 , y, xy,

β0 , . . . , βb−1 ,γ0 , . . . , γb−1 ) ∈ F2b+4 ,where (β0 , . . . , βb−1 ) is the binary representation of x and(γ0 , . . . , γb−1 ) is the binary representation of y. The validation algorithm checks that all the β and γ are in {0, 1},
and that all the arithmetic relations hold, analogously tothe validation check for the integer summation AFE. Finally, the decoding algorithm takes as input the sum of theencoded vectors truncated to the first four components:
Pn
Pn 2 PnPnσ=i=1 x,
i=1 x ,
i=1 y,
i=1 xy ,from which the decoding algorithm computes the required
real regression coefficients c0 and c1 using (1). This AFE
is private with respect to the function that outputs theleast-squares fit h(x) = c0 + c1 x, along with the mean andvariance of the set {x1 , . . . , xn }.
When x and y are real numbers, we can embed the reals
into a finite field F using a fixed-point representation, as
long as we size the field large enough to avoid overflow.
The two-dimensional approach above generalizes directly to perform linear regression on d-dimensional feature vectors x̄ = (x(1) , . . . , x(d) ). The AFE yields a leastsquares approximation of the form h( x̄) = c0 +c1 x(1) +· · ·+cd x(d) . The resulting AFE is private with respect to a function that reveals the least-square coefficients (c0 , . . . , cd ),P
along with the d × d covariance matrix i x̄i · ( x̄i )T .

6

Evaluation

In this section, we demonstrate that Prio’s theoreticalcontributions translate into practical performance gains.

We have implemented a Prio prototype in 5,700 linesof Go and 620 lines of C (for FFT-based polynomial
operations, built on the FLINT library [59]). Unless noted
otherwise, our evaluations use an FFT-friendly 87-bit field.
Our servers communicate with each other using Go’s TLS
implementation. Clients encrypt and sign their messages
to servers using NaCl’s “box” primitive, which obviates
the need for client-to-server TLS connections. Our codeis available online at https://crypto.stanford.edu/prio/.
We evaluate the SNIP-based variant of Prio (Section 4.1) and also the variant in which the servers keep the
Valid predicate private (“Prio-MPC,” Section 4.4). Our
implementation includes three optimizations described inAppendix I. The first uses a pseudo-random generator(e.g., AES in counter mode) to reduce the client-to-serverdata transfer by a factor of roughly s in an s-server deployment. The second optimization allows the servers toverify SNIPs without needing to perform expensive polynomial interpolations. The third optimization gives anefficient way for the servers to compute the logical-andof multiple arithmetic circuits to check that multiple Valid
predicates hold simultaneously.
We compare Prio against a private aggregation schemethat uses non-interactive zero-knowledge proofs (NIZKs)
to provide robustness. This protocol is similar to the“cryptographically verifiable” interactive protocol of Kursawe et al. [86] and has roughly the same cost, in terms ofexponentiations per client request, as the “distributed decryption” variant of PrivEx [56]. We implement the NIZK
scheme using a Go wrapper of OpenSSL’s NIST P256
code [50]. We do not compare Prio against systems, suchas ANONIZE [76] and PrivStats [100], that rely on an
external anonymizing proxy to protect against a network
adversary. (We discuss this related work in Section 8.)

6.1

Microbenchmarks

Table 3 presents the time required for a Prio client toencode a data submission on a workstation (2.4 GHz Intel
Xeon E5620) and mobile phone (Samsung Galaxy SIII,
1.4 GHz Cortex A9). For a submission of 100 integers,
the client time is roughly 0.03 seconds on a workstation,and just over 0.1 seconds on a mobile phone.
To investigate the load that Prio places on the servers,
we configured five Amazon EC2 servers (eight-core
c3.2xlarge machines, Intel Xeon E5-2680 CPUs) in five
Amazon data centers (N. Va., N. Ca., Oregon, Ireland,and Frankfurt) and had them run the Prio protocols. An
additional three c3.2xlarge machines in the N. Va. data
center simulated a large number of Prio clients. To maximize the load on the servers, we had each client send a
stream of pre-generated Prio data packets to the servers
over a single TCP connection. There is no need to use
TLS on the client-to-server Prio connection because Priopackets are encrypted and authenticated at the application
layer and can be replay-protected at the servers.
Figure 4 gives the throughput of this cluster in which
each client submits a vector of zero/one integers and theservers sum these vectors. The “No privacy” line on
the chart gives the throughput for a dummy scheme inwhich a single server accepts encrypted client data submissions directly from the clients with no privacy protection whatsoever. The “No robustness” line on the chart
gives the throughput for a cluster of five servers that use
a secret-sharing-based private aggregation scheme (à laSection 3) with no robustness protection. The five-server“No robustness” scheme is slower than the single-server“No privacy” scheme because of the cost of coordinating
the processing of submissions amongst the five servers.
The throughput of Prio is within a factor of 5× of the
no-privacy scheme for many submission sizes, and Priooutperforms the NIZK-based scheme by more than anorder of magnitude.
Figure 5 shows how the throughput of a Prio clusterchanges as the number of servers increases, when the system is collecting the sum of 1,024 one-bit client-submitted
integers, as in an anonymous survey application. For thisexperiment, we locate all of the servers in the same data
center, so that the latency and bandwidth between eachpair of servers is roughly constant. With more servers, anadversary has to compromise a larger number of machines
to violate Prio’s privacy guarantees.
Adding more servers barely affects the system’s
throughput. The reason is that we are able to load-balance
the bulk of the work of checking client submissions acrossall of the servers. (This optimization is only possible because we require robustness to hold only if all servers arehonest.) We assign a single Prio server to be the “leader”
that coordinates the checking of each client data submission. In processing a single submission in an s-servercluster, the leader transmits s times more bits than a nonleader, but as the number of servers increases, each serveris a leader for a smaller share of incoming submissions.
The NIZK-based scheme also scales well: as the number of servers increases, the heavy computational load ofchecking the NIZKs is distributed over more machines.
Figure 6 shows the number of bytes each non-leader
Prio server needs to transmit to check the validity of asingle client submission for the two Prio variants, andfor the NIZK scheme. The benefit of Prio is evident:
the Prio servers transmit a constant number of bits per
submission—independent of the size of the submission
or complexity of the Valid routine. As the submitted
vectors grow, Prio yields a 4,000-fold bandwidth saving
over NIZKs, in terms of server data transfer.

10

NIZK

1

100

NIZK

10

Figure 4: Prio’s SNIPs provide the robustness guarantees of zero-knowledge proofs at 20-50× less cost.

Figure 5: Prio is insensitive to thenumber of aggregation servers.

4

6

8

Browser

Prio

0 KiB

10

Figure 6: Prio’s use of SNIPs (§4)
reduces bandwidth consumption.

SurveyLinReg

(930)

BrCa

(174)

Heart

(434)

CPI-434(312)

PCSI-78(84)

Beck-21(1,410)HighRes(80)

LowRes(8,760)

Toyko(6,280)London(2,424)Chicago(868)

Seattle

(64)

SNARK
(Est.)
NIZK
Prio-MPC
Prio
GenevaClient time (s)Lower is better.

4 KiB

22 26 210 214
Submission length(field elements)

Number of servers (same data center)

2

Cell

64 KiB1

24 26 28 210 212 214 216
Submission length (field elements)

1000
100
10
1
0.1
0.01
0.001

1 MiB

Pr NI
io
-M ZK
PC

No privacy
No robustness
Prio
Prio-MPC

100

No privacy
No robustness
Prio
Prio-MPC

1000

Per-server data transfer

1000

Submissions processed/s

Submissions processed/s

10000

Figure 7: Client encoding time for different application domains when using Prio, a non-interactive zero-knowledge system (NIZK),or a SNARK-like system (estimated). Averaged over eight runs. The number of × gates in the Valid circuit is listed in parentheses.

6.2

Application scenarios

To demonstrate that Prio’s data types are expressive
enough to collect real-world aggregates, we have configured Prio for a few potential application domains.
Cell signal strength. A collection of Prio servers cancollect the average mobile signal strength in each gridcell in a city without leaking the user’s location history to
the aggregator. We divide the geographic area into a km2
grid—the number of grid cells depends on the city’s size—
and we encode the signal strength at the user’s present
location as a four-bit integer. (If each client only submits
signal-strength data for a few grid cells in each protocol
run, extra optimizations can reduce the client-to-serverdata transfer. See “Share compression” in Appendix G.)
Browser statistics. The Chromium browser uses the
RAPPOR system to gather private information about its
users [35, 57]. We implement a Prio instance for gathering a subset of these statistics: average CPU and memory
usage, along with the frequency counts of 16 URL roots.
For collecting the approximate counts, we use the countmin sketch structure, described in Appendix G. We experiment with both low- and high-resolution parameters(δ = 2−10 ,  = 1/10; δ = 2−20 ,  = 1/100).
Health data modeling. We implement the AFE for training a regression model on private client data. We use
the features from a preexisting heart disease data set(13 features of varying types: age, sex, cholesterol level,etc.) [78] and a breast cancer diagnosis data set (30 realvalued features using 14-bit fixed-point numbers) [120].
Anonymous surveys. We configure Prio to compute aggregates responses to sensitive surveys: we use the Beck
Depression Inventory (21 questions on a 1-4 scale) [4],the Parent-Child Relationship Inventory (78 questions
on a 1-4 scale) [63], and the California PsychologicalInventory (434 boolean questions) [42].
Comparison to alternatives. In Figure 7, we compare
the computational cost Prio places on the client to thecosts of other schemes for protecting robustness against
misbehaving clients, when we configure the system forthe aforementioned applications. The fact that a Prioclient need only perform a single public-key encryptionmeans that it dramatically outperforms schemes based on
public-key cryptography. If the Valid circuit has M multiplication gates, producing a discrete-log-based NIZK
requires the client to perform 2M exponentiations (orelliptic-curve point multiplications). In contrast, Prio requires O(M log M) multiplications in a relatively small
field, which is much cheaper for practical values of M.
In Figure 7, we give conservative estimates of the timerequired to generate a zkSNARK proof, based on timingsof libsnark’s [18] implementation of the Pinocchio system [97] at the 128-bit security level. These proofs haveEncoding time (s)Workstation

100
10−1
10−2
10−3
10−4

Phone
Prio
No robustness
No privacy

2

6

10

2

6

Linear regression dimension d

10

d
2
4
6
8
10
12

No privacy
Rate
14,68815,426
14,773
15,975
15,58915,189No robustness
Rate
Priv. cost
2,687
5.5×
2,569
6.0×
2,600
5.7×
2,564
6.2×
2,639
5.9×
2,547
6.0×

Rate
2,608
2,165
2,048
1,606
1,430
1,312

Prio
Robust. cost
1.0×
1.2×
1.3×
1.6×
1.8×
1.9×

Tot. cost
5.6×
7.1×
7.2×
9.5×
10.9×
11.6×

Figure 8: Time for a client to encode a submission Table 9: The throughput, in client requests per second, of a global fiveconsisting of d-dimensional training example of 14-bit server cluster running a private d-dim. regression. We compare a scheme
values for computing a private least-squares regression. with no privacy, with privacy but no robustness, and Prio (with both).

the benefit of being very short: 288 bytes, irrespectiveof the complexity of the circuit. To realize the benefit ofthese succinct proofs, the statement being proved mustalso be concise since the verifier’s running time grows
with the statement size. To achieve this conciseness in the
Prio setting would require computing sL hashes “inside
the SNARK,” with s servers and submissions of length L.
We optimistically estimate that each hash computation
requires only 300 multiplication gates, using a subset-sum
hash function [2, 17, 67, 77], and we ignore the cost ofcomputing the Valid circuit in the SNARK. We then use
the timings from the libsnark paper to arrive at the costestimates. Each SNARK multiplication gate requires theclient to compute a number of exponentiations, so the costto the client is large, though the proof is admirably short.

6.3

Machine learning

Finally, we perform an end-to-end evaluation of Prio when
the system is configured to train a d-dimensional leastsquares regression model on private client-submitted data,in which each training example consists of a vector of 14bit integers. These integers are large enough to represent
vital health information, for example.
In Figure 8, we show the client encoding cost for Prio,along with the no-privacy and no-robustness schemes described in Section 6.1. The cost of Prio’s privacy androbustness guarantees amounts to roughly a 50× slowdown at the client over the no-privacy scheme due to theoverhead of the SNIP proof generation. Even so, the absolute cost of Prio to the client is small—on the order of
one tenth of a second.
Table 9 gives the rate at which the globally distributed
five-server cluster described in Section 6.1 can processclient submissions with and without privacy and robustness. The server-side cost of Prio is modest: only a 1-2×
slowdown over the no-robustness scheme, and only a 515× slowdown over a scheme with no privacy at all. In
contrast, the cost of robustness for the state-of-the-art
NIZK schemes, per Figure 4, is closer to 100-200×.

7

Discussion

Deployment scenarios. Prio ensures client privacy aslong as at least one server behaves honestly. We now
discuss a number of deployment scenarios in which thisassumption aligns with real-world incentives.
Tolerance to compromise. Prio lets an organization compute aggregate data about its clients without ever storingclient data in a single vulnerable location. The organization could run all s Prio servers itself, which would ensures data privacy against an attacker who compromises
up to s − 1 servers.
App store. A mobile application platform (e.g., Apple’s
App Store or Google’s Play) can run one Prio server, andthe developer of a mobile app can run the second Prioserver. This allows the app developer to collect aggregateuser data without having to bear the risks of holding thesedata in the clear.
Shared data. A group of s organizations could use Prio tocompute an aggregate over the union of their customers’
datasets, without learning each other’s private client data.
Private compute services. A large enterprise can contract
with an external auditor or a non-profit (e.g., the Electronic Frontier Foundation) to jointly compute aggregate
statistics over sensitive customer data using Prio.
Jurisdictional diversity. A multinational organization canspread its Prio servers across different countries. If law
enforcement agents seize the Prio servers in one country,
they cannot deanonymize the organization’s Prio users.
Common attacks. Two general attacks apply to all systems, like Prio, that produce exact (un-noised) outputs
while protecting privacy against a network adversary.
The first attack is a selective denial-of-service attack.
In this attack, the network adversary prevents all honest clients except one from being able to contact thePrio servers [105]. In this case, the protocol output isf (xhonest , xevil1 , . . . , xeviln ). Since the adversary knows thexevil values, the adversary could infer part or all of the one
honest client’s private value xhonest .

(a) RAPPOR [57] provides differential privacy [54] (not information-theoretic privacy)
by adding random noise to client submissions.

(b) ANONIZE [76] and PrivStats [100] relyon an anonymizing proxy, such as Tor [51], toprotect privacy against network eavesdroppers.

(c) Prio and other schemes using secret sharing [30,48,56,79,86,92] offer ideal anonymity
provided that the servers do not collude.

Figure 10: Comparison of techniques for anonymizing client data in private aggregation systems.

In Prio, we deploy the standard defense against this
attack, which is to have the servers wait to publish the aggregate statistic f (x1 , . . . , xn ) until they are confident thatthe aggregate includes values from many honest clients.
The best means to accomplish this will depend on the
deployment setting.
One way is to have the servers keep a list of publickeys of registered clients (e.g., the students enrolled ata university). Prio clients sign their submissions withthe signing key corresponding to their registered public
key and the servers wait to publish their accumulator
values until a threshold number of registered clients havesubmitted valid messages. Standard defenses [3, 114, 124,125] against Sybil attacks [52] would apply here.
The second attack is an intersection attack [20, 49, 83,122]. In this attack, the adversary observes the output
f (x1 , . . . , xn ) of a run of the Prio protocol with n honest
clients. The adversary then forces the nth honest clientoffline and observes a subsequent protocol run, in which0
the servers compute f (x10 , . . . , xn−1). If the clients’ values0
are constant over time (xi = xi ), then the adversary learns
the difference f (x1 , . . . , xn )− f (x1 , . . . , xn−1 ), which could
reveal client n’s private value xn (e.g., if f computes sum).
One way for the servers to defend against the attack is
to add differential privacy noise to the results before publishing them [54]. Using existing techniques, the servers
can add this noise in a distributed fashion to ensure thatas long as at least one server is honest, no server sees the
un-noised aggregate [55]. The definition of differential
privacy ensures that computed statistics are distributed
approximately the same whether or not the aggregate includes a particular client’s data. This same approach isalso used in a system by Melis, Danezis, and De Cristofaro [92], which we discuss in Section 8.
Robustness against malicious servers. Prio only provides robustness when all servers are honest. Providing
robustness in the face of faulty servers is obviously desirable, but we are not convinced that it is worth the security
and performance costs. Briefly, providing robustness necessarily weakens the privacy guarantees that the systemprovides: if the system protects robustness in the presenceof k faulty servers, then the system can protect privacy
only against a coalition of at most s − k − 1 malicious

servers. We discuss this issue further in Appendix B.

8Related Work

Private data-collection systems [30, 48, 53, 56, 79, 86, 92]
that use secret-sharing based methods to compute sums
over private user data typically (a) provide no robustness
guarantees in the face of malicious clients, (b) use expensive NIZKs to prevent client misbehavior, or (c) fail todefend privacy against actively malicious servers [33].
Other data-collection systems have clients send theirprivate data to an aggregator through a general-purpose
anonymizing network, such as a mix-net [27, 32, 47, 87]
or a DC-net [31, 38–40, 110]. These anonymity systems
provide strong privacy properties, but require expensive“verifiable mixing” techniques [8, 95], or require workat the servers that is quadratic in the number of client
messages sent through the system [38, 121].
PrivStats [100] and ANONIZE [76] outsource toTor [51] (or another low-latency anonymity system [61,88, 101]) the work of protecting privacy against a network
adversary (Figure 10). Prio protects against an adversarythat can see and control the entire network, while Torbased schemes succumb to traffic-analysis attacks [94].
In data-collection systems based on differential privacy [54], the client adds structured noise to its private
value before sending it to an aggregating server. The
added noise gives the client “plausible deniability:” if
the client sends a value x to the servers, x could be theclient’s true private value, or it could be an unrelated
value generated from the noise. Dwork et al. [55], Shi etal. [107], and Bassily and Smith [7] study this techniquein a distributed setting, and the RAPPOR system [57, 58],
deployed in Chromium, has put this idea into practice. A
variant of the same principle is to have a trusted proxy(as in SuLQ [21] and PDDP [34]) or a set of minimallytrusted servers [92] add noise to already-collected data.
The downside of these systems is that (a) if the clientadds little noise, then the system does not provide muchprivacy, or (b) if the client adds a lot of noise, then lowfrequency events may be lost in the noise [57]. Using
server-added noise [92] ameliorates these problems.
In theory, secure multi-party computation (MPC) protocols [11, 15, 68, 90, 123] allow a set of servers, with some

non-collusion assumptions, to privately compute any function over client-provided values. The generality of MPC
comes with serious bandwidth and computational costs:
evaluating the relatively simple AES circuit in an MPC requires the parties to perform many minutes or even hoursof precomputation [44]. Computing a function f on millions of client inputs, as our five-server Prio deployment
can do in tens of minutes, could potentially take an astronomical amount of time in a full MPC. That said, there
have been great advances in practical general-purpose
MPC protocols of late [12, 13, 23, 45, 46, 73, 89, 91, 93, 98].
General-purpose MPC may yet become practical for computing certain aggregation functions that Prio cannot(e.g., exact max), and some special-case MPC protocols [5, 29, 96] are practical today for certain applications.

9

Conclusion and future work

Prio allows a set of servers to compute aggregate statistics over client-provided data while maintaining client
privacy, defending against client misbehavior, and performing nearly as well as data-collection platforms thatexhibit neither of these security properties. The core idea
behind Prio is reminiscent of techniques used in verifiable computation [16, 37, 62, 69, 97, 115, 116, 119], but
in reverse—the client proves to a set of servers that itcomputed a function correctly. One question for future
work is whether it is possible to efficiently extend Prio
to support combining client encodings using a more general function than summation, and what more powerfulaggregation functions this would enable. Another task
is to investigate the possiblity of shorter SNIP proofs:
ours grow linearly in the size of the Valid circuit, but sublinear-size information-theoretic SNIPs may be feasible.
Acknowledgements. We thank the anonymous NSDI reviewers
for an extraordinarily constructive set of reviews. Jay Lorch, ourshepherd, read two drafts of this paper and gave us pages andpages of insightful recommendations and thorough comments.
It was Jay who suggested using Prio to privately train machinelearning models, which became the topic of Section 5.3. Ourcolleagues, including David Mazières, David J. Wu, Dima Kogan, Elette Boyle, George Danezis, Phil Levis, Matei Zaharia,
Saba Eskandarian, Sebastian Angel, and Todd Warszawski gave
critical feedback that improved the content and presentation of
the work. Any remaining errors in the paper are, of course, oursalone.
This work received support from NSF, DARPA, the Simons
Foundation, an NDSEG Fellowship, and ONR. Opinions, findings and conclusions or recommendations expressed in thismaterial are those of the authors and do not necessarily reflect
the views of DARPA.

References[1] Abe, M., Cramer, R., and Fehr, S. Non-interactive

distributed-verifier proofs and proving relations
among commitments. In ASIACRYPT (2002),
pp. 206–224.
[2] Ajtai, M. Generating hard instances of lattice problems. In STOC (1996), ACM, pp. 99–108.
[3] Alvisi, L., Clement, A., Epasto, A., Lattanzi, S.,
and Panconesi, A. SoK: The evolution of Sybil defense via social networks. In Security and Privacy(2013), IEEE, pp. 382–396.
[4] American Psychological Association.
Beckdepression inventory.
http://www.apa.org/
pi/about/publications/caregivers/practicesettings/assessment/tools/beck-depression.aspx.
Accessed 15 September 2016.
[5] Applebaum, B., Ringberg, H., Freedman, M. J.,
Caesar, M., and Rexford, J. Collaborative,
privacy-preserving data aggregation at scale. In
PETS (2010), Springer, pp. 56–74.
[6] Archer, B., and Weisstein, E. W. Lagrange interpolating polynomial. http://mathworld.wolfram.
com/LagrangeInterpolatingPolynomial.html. Accessed 16 September 2016.
[7] Bassily, R., and Smith, A. Local, private, efficient
protocols for succinct histograms. In STOC (2015),
ACM, pp. 127–135.
[8] Bayer, S., and Groth, J. Efficient zero-knowledge
argument for correctness of a shuffle. In EUROCRYPT (2012), Springer, pp. 263–280.
[9] Beaver, D. Efficient multiparty protocols using circuit randomization. In CRYPTO (1991), Springer,
pp. 420–432.
[10] Beaver, D. Secure multiparty protocols and zeroknowledge proof systems tolerating a faulty minority. Journal of Cryptology 4, 2 (1991), 75–122.
[11] Beaver, D., Micali, S., and Rogaway, P. The roundcomplexity of secure protocols. In STOC (1990),
ACM, pp. 503–513.
[12] Bellare, M., Hoang, V. T., Keelveedhi, S., andRogaway, P. Efficient garbling from a fixed-key
blockcipher. In Security and Privacy (2013), IEEE,
pp. 478–492.
[13] Ben-David, A., Nisan, N., and Pinkas, B. FairplayMP: a system for secure multi-party computation. In CCS (2008), ACM, pp. 257–266.

[14] Ben-Or, M., Goldwasser, S., Kilian, J., andWigderson, A. Multi-prover interactive proofs:
How to remove intractability assumptions. In
STOC (1988), ACM, pp. 113–131.
[15] Ben-Or, M., Goldwasser, S., and Wigderson,
A. Completeness theorems for non-cryptographic
fault-tolerant distributed computation. In STOC
(1988), ACM, pp. 1–10.
[16] Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer,E., and Virza, M. SNARKs for C: Verifying program executions succinctly and in zero knowledge.
In CRYPTO. Springer, 2013, pp. 90–108.
[17] Ben-Sasson, E., Chiesa, A., Tromer, E., and Virza,
M. Scalable zero knowledge via cycles of elliptic
curves. In CRYPTO (2014), Springer, pp. 276–294.
[18] Ben-Sasson, E., Chiesa, A., Tromer, E., and Virza,
M. Succinct non-interactive zero knowledge for a
von Neumann architecture. In USENIX Security(2014), pp. 781–796.
[19] Ben-Sasson, E., Fehr, S., and Ostrovsky, R. Nearlinear unconditionally-secure multiparty computation with a dishonest minority. In CRYPTO.
Springer, 2012, pp. 663–680.
[20] Berthold, O., and Langos, H. Dummy traffic
against long term intersection attacks. In Workshop on Privacy Enhancing Technologies (2002),
Springer, pp. 110–128.
[21] Blum, A., Dwork, C., McSherry, F., and Nissim, K.
Practical privacy: the SuLQ framework. In PODS
(2005), ACM, pp. 128–138.
[22] Blum, M., Feldman, P., and Micali, S. Noninteractive zero-knowledge and its applications. In
STOC (1988), ACM, pp. 103–112.
[23] Bogetoft, P., Christensen, D. L., Damgard, I.,
Geisler, M., Jakobsen, T., Krøigaard, M., Nielsen,
J. D., Nielsen, J. B., Nielsen, K., Pagter, J.,
Schwartzbach, M., and Toft, T. Multiparty computation goes live. In Financial Cryptography (2000).
[24] Boyle, E., Gilboa, N., and Ishai, Y. Function secretsharing. In CRYPTO (2015), Springer, pp. 337–
367.
[25] Boyle, E., Gilboa, N., and Ishai, Y. Function secretsharing: Improvements and extensions. In CCS(2016), ACM, pp. 1292–1303.
[26] Braun, B., Feldman, A. J., Ren, Z., Setty, S., Blumberg, A. J., and Walfish, M. Verifying computations with state. In SOSP (2013), ACM, pp. 341–
357.

[27] Brickell, J., and Shmatikov, V.
Efficient
anonymity-preserving data collection. In KDD(2006), ACM, pp. 76–85.
[28] Broadbent, A., and Tapp, A. Information-theoretic
security without an honest majority. In ASIACRYPT (2007), Springer, pp. 410–426.
[29] Burkhart, M., Strasser, M., Many, D., and Dimitropoulos, X. SEPIA: Privacy-preserving aggregation of multi-domain network events and statistics.
USENIX Security (2010).
[30] Castelluccia, C., Mykletun, E., and Tsudik, G.
Efficient aggregation of encrypted data in wirelesssensor networks. In MobiQuitous (2005), IEEE,
pp. 109–117.
[31] Chaum, D. The Dining Cryptographers Problem:
Unconditional sender and recipient untraceability.
Journal of Cryptology 1, 1 (1988), 65–75.
[32] Chaum, D. L. Untraceable electronic mail, return
addresses, and digital pseudonyms. Communications of the ACM 24, 2 (1981), 84–90.
[33] Chen, R., Akkus, I. E., and Francis, P. SplitX:
High-performance private analytics. SIGCOMM
43, 4 (2013), 315–326.
[34] Chen, R., Reznichenko, A., Francis, P., andGehrke, J. Towards statistical queries over distributed private user data. In NSDI (2012), pp. 169–
182.
[35] Chromium source code.
https://chromium.
googlesource.com/chromium/src/+/master/
tools/metrics/rappor/rappor.xml. Accessed 15
September 2016.
[36] Cormode, G., and Muthukrishnan, S. An improved data stream summary: the count-min sketch
and its applications. Journal of Algorithms 55, 1(2005), 58–75.
[37] Cormode, G., Thaler, J., and Yi, K. Verifying computations with streaming interactive proofs. VLDB
5, 1 (2011), 25–36.
[38] Corrigan-Gibbs, H., Boneh, D., and Mazières, D.
Riposte: An anonymous messaging system handling millions of users. In Security and Privacy(2015), IEEE, pp. 321–338.
[39] Corrigan-Gibbs, H., and Ford, B. Dissent: accountable anonymous group messaging. In CCS(2010), ACM, pp. 340–350.

[40] Corrigan-Gibbs, H., Wolinsky, D. I., and Ford, B.
Proactively accountable anonymous messaging in
Verdict. In USENIX Security (2013), pp. 147–162.

[52] Douceur, J. R. The Sybil Attack. In International Workshop on Peer-to-Peer Systems (2002),
Springer, pp. 251–260.

[41] Costello, C., Fournet, C., Howell, J., Kohlweiss,M., Kreuter, B., Naehrig, M., Parno, B., and Zahur, S. Geppetto: Versatile verifiable computation.
In Security and Privacy (2015), IEEE, pp. 253–
270.

[53] Duan, Y., Canny, J., and Zhan, J. P4P: practicallarge-scale privacy-preserving distributed computation robust against malicious users. In USENIX
Security (Aug. 2010).

[42] CPP. California Psychological Inventory. https://www.cpp.com/products/cpi/index.aspx. Accessed
15 September 2016.
[43] Cramer, R., and Shoup, V. A practical public key
cryptosystem provably secure against adaptive chosen ciphertext attack. In CRYPTO (1998), Springer,
pp. 13–25.
[44] Damgård, I., Keller, M., Larraia, E., Miles, C.,
and Smart, N. P. Implementing AES via an actively/covertly secure dishonest-majority MPC protocol. In SCN (2012), Springer, pp. 241–263.
[45] Damgård, I., Keller, M., Larraia, E., Pastro, V.,
Scholl, P., and Smart, N. P. Practical covertly
secure MPC for dishonest majority–or: Breaking
the SPDZ limits. In ESORICS (2013), Springer,
pp. 1–18.
[46] Damgård, I., Pastro, V., Smart, N. P., and Zakarias, S. Multiparty computation from somewhat
homomorphic encryption. In CRYPTO (2012),
pp. 643–662.
[47] Danezis, G. Better anonymous communications.
PhD thesis, University of Cambridge, 2004.
[48] Danezis, G., Fournet, C., Kohlweiss, M., andZanella-Béguelin, S. Smart meter aggregation
via secret-sharing. In Workshop on Smart Energy
Grid Security (2013), ACM, pp. 75–80.
[49] Danezis, G., and Serjantov, A. Statistical disclosure or intersection attacks on anonymity systems.
In Information Hiding (2004), Springer, pp. 293–308.
[50] DEDIS Research Lab at EPFL. Advanced crypto
library for the Go language. https://github.com/
dedis/crypto.
[51] Dingledine, R., Mathewson, N., and Syverson,
P. Tor: the second-generation onion router. In
USENIX Security (2004), USENIX Association,
pp. 21–21.

[54] Dwork, C. Differential privacy. In ICALP (2006),
pp. 1–12.
[55] Dwork, C., Kenthapadi, K., McSherry, F.,
Mironov, I., and Naor, M. Our data, ourselves:
Privacy via distributed noise generation. In EUROCRYPT. Springer, 2006, pp. 486–503.
[56] Elahi, T., Danezis, G., and Goldberg, I. PrivEx:
Private collection of traffic statistics for anonymous
communication networks. In CCS (2014), ACM,
pp. 1068–1079.
[57] Erlingsson, Ú., Pihur, V., and Korolova, A.
RAPPOR: Randomized aggregatable privacypreserving ordinal response. In CCS (2014), ACM,
pp. 1054–1067.
[58] Fanti, G., Pihur, V., and Erlingsson, Ú. Building
a RAPPOR with the unknown: Privacy-preserving
learning of associations and data dictionaries.
PoPETS 2016, 3 (2016), 41–61.
[59] FLINT: Fast Library for Number Theory. http://www.flintlib.org/.
[60] Fortnow, L., Rompel, J., and Sipser, M. On the
power of multi-prover interactive protocols. Theoretical Computer Science 134, 2 (1994), 545–557.
[61] Freedman, M. J., and Morris, R. Tarzan: A peerto-peer anonymizing network layer. In CCS (2002),
ACM, pp. 193–206.
[62] Gennaro, R., Gentry, C., Parno, B., and Raykova,
M. Quadratic span programs and succinct NIZKs
without PCPs. In CRYPTO (2013), pp. 626–645.
[63] Gerard, A. B. Parent-Child Relationship Inventory.
http://www.wpspublish.com/store/p/
2898/parent-child-relationship-inventory-pcri. Accessed 15 September 2016.
[64] Gilboa, N., and Ishai, Y. Distributed point functions and their applications. In EUROCRYPT(2014), Springer, pp. 640–658.
[65] Glanz, J., Larson, J., and Lehren, A. W. Spy
agencies tap data streaming from phone apps.
http://www.nytimes.com/2014/01/28/world/spy-

agencies-scour-phone-apps-for-personaldata.html, Jan. 27, 2014. Accessed 20 September
2016.
[66] Goldreich, O. Foundations of Cryptography. Cambridge University Press, 2001.
[67] Goldreich, O., Goldwasser, S., and Halevi, S.
Collision-free hashing from lattice problems. Cryptology ePrint Archive, Report 1996/009, 1996.
http://eprint.iacr.org/1996/009.
[68] Goldreich, O., Micali, S., and Wigderson, A. How
to play any mental game. In STOC (1987), ACM,
pp. 218–229.
[69] Goldwasser, S., Kalai, Y. T., and Rothblum, G. N.
Delegating computation: Interactive proofs for
Muggles. Journal of the ACM 62, 4 (2015), 27.
[70] Goldwasser, S., Micali, S., and Rackoff, C. The
knowledge complexity of interactive proof systems.
SIAM Journal on Computing 18, 1 (1989), 186–
208.
[71] Goldwasser, S., Micali, S., and Rivest, R. L. A
digital signature scheme secure against adaptive
chosen-message attacks. SIAM Journal on Computing 17, 2 (1988), 281–308.
Apple’s ‘differential pri[72] Greenberg, A.
vacy’ is about collecting your data—but notyour data.
https://www.wired.com/2016/06/
apples-differential-privacy-collecting-data/, June
13, 2016. Accessed 21 September 2016.
[73] Gueron, S., Lindell, Y., Nof, A., and Pinkas, B.
Fast garbling of circuits under standard assumptions. In CCS (2015), ACM, pp. 567–578.
[74] Guha, S., and McGregor, A. Stream order and order statistics: Quantile estimation in random-orderstreams. SIAM Journal on Computing 38, 5 (2009),
2044–2059.
[75] Hilts, A., Parsons, C., and Knockel, J. Every step
you fake: A comparative analysis of fitness tracker
privacy and security. Tech. rep., Open Effect, 2016.
Accessed 16 September 2016.

[78] Janosi, A., Steinbrunn, W., Pfisterer, M., and Detrano, R. Heart disease data set. https://archive.ics.
uci.edu/ml/datasets/Heart+Disease, 22 July 1988.
Accessed 15 September 2016.
[79] Jawurek, M., and Kerschbaum, F. Fault-tolerant
privacy-preserving statistics. In PETS (2012),
Springer, pp. 221–238.
[80] Jeske, T. Floating car data from smartphones: What
Google and Waze know about you and how hackers
can control traffic. BlackHat Europe (2013).
[81] Joye, M., and Libert, B. A scalable scheme forprivacy-preserving aggregation of time-series data.
In Financial Cryptography (2013), pp. 111–125.
[82] Karr, A. F., Lin, X., Sanil, A. P., and Reiter, J. P.
Secure regression on distributed databases. Journalof Computational and Graphical Statistics 14, 2(2005), 263–279.
[83] Kedogan, D., Agrawal, D., and Penz, S. Limits ofanonymity in open environments. In Information
Hiding (2002), Springer, pp. 53–69.
[84] Keller, J., Lai, K. R., and Perlroth, N. How manytimes has your personal information been exposed
to hackers? http://www.nytimes.com/interactive/
2015/07/29/technology/personaltech/what-partsof-your-information-have-been-exposed-tohackers-quiz.html, July 29, 2015.
[85] Krawczyk, H. Secret sharing made short. In
CRYPTO (1993), pp. 136–146.
[86] Kursawe, K., Danezis, G., and Kohlweiss, M.
Privacy-friendly aggregation for the smart-grid. In
PETS (2011), pp. 175–191.
[87] Kwon, A., Lazar, D., Devadas, S., and Ford, B.
Riffle. Proceedings on Privacy Enhancing Technologies 2016, 2 (2015), 115–134.
[88] Le Blond, S., Choffnes, D., Zhou, W., Druschel,P., Ballani, H., and Francis, P. Towards efficienttraffic-analysis resistant anonymity networks. In
SIGCOMM (2013), ACM.

[76] Hohenberger, S., Myers, S., Pass, R., and shelat,
a. ANONIZE: A large-scale anonymous survey
system. In Security and Privacy (2014), IEEE,
pp. 375–389.

[89] Lindell, Y. Fast cut-and-choose-based protocols
for malicious and covert adversaries. Journal of
Cryptology 29, 2 (2016), 456–490.

[77] Impagliazzo, R., and Naor, M. Efficient cryptographic schemes provably as secure as subset sum.
Journal of Cryptology 9, 4 (1996), 199–216.

[90] Lindell, Y., and Pinkas, B. A proof of security of
Yao’s protocol for two-party computation. Journalof Cryptology 22, 2 (2009), 161–188.

[91] Malkhi, D., Nisan, N., Pinkas, B., Sella, Y., et al.
Fairplay–secure two-party computation system. In
USENIX Security (2004).

[104] Schwartz, J. T. Fast probabilistic algorithms forverification of polynomial identities. Journal of
the ACM 27, 4 (1980), 701–717.

[92] Melis, L., Danezis, G., and De Cristofaro, E. Efficient private statistics with succinct sketches. In
NDSS (Feb. 2016), Internet Society.

[105] Serjantov, A., Dingledine, R., and Syverson, P.
From a trickle to a flood: Active attacks on several
mix types. In Information Hiding (2002), Springer,
pp. 36–52.

[93] Mohassel, P., Rosulek, M., and Zhang, Y. Fastand secure three-party computation: The Garbled
Circuit approach. In CCS (2015), ACM, pp. 591–
602.

[106] Shamir, A. How to share a secret. Communicationsof the ACM 22, 11 (1979), 612–613.

[94] Murdoch, S. J., and Danezis, G. Low-cost traffic
analysis of Tor. In Security and Privacy (2005),
IEEE, pp. 183–195.
[95] Neff, C. A. A verifiable secret shuffle and its application to e-voting. In CCS (2001), ACM, pp. 116–
125.
[96] Nikolaenko, V., Ioannidis, S., Weinsberg, U., Joye,
M., Taft, N., and Boneh, D. Privacy-preserving matrix factorization. In CCS (2013), ACM, pp. 801–812.
[97] Parno, B., Howell, J., Gentry, C., and Raykova, M.
Pinocchio: Nearly practical verifiable computation.
In Security and Privacy (2013), IEEE, pp. 238–
252.
[98] Pinkas, B., Schneider, T., Smart, N. P., andWilliams, S. C. Secure two-party computation
is practical. In CRYPTO (2009), Springer, pp. 250–
267.
[99] Popa, R. A., Balakrishnan, H., and Blumberg, A. J.
VPriv: Protecting privacy in location-based vehicular services. In USENIX Security (2009), pp. 335–
350.

[107] Shi, E., Chan, T. H., Rieffel, E., Chow, R., andSong, D. Privacy-preserving aggregation of timeseries data. In NDSS (2011), vol. 2, Internet Society, pp. 1–17.
[108] Shoup, V. OAEP reconsidered. In CRYPTO (2001),
Springer, pp. 239–259.
[109] Shoup, V. A proposal for an ISO standard for public
key encryption (version 2.1). Cryptology ePrint
Archive, Report 2001/112 (2001). http://eprint.iacr.
org/2001/112.
[110] Sirer, E. G., Goel, S., Robson, M., and Engin,
D. Eluding carnivores: File sharing with strong
anonymity. In ACM SIGOPS European Workshop(2004), ACM, p. 19.
[111] Smart, N. FHE-MPC notes. https://www.cs.bris.
ac.uk/~nigel/FHE-MPC/Lecture8.pdf, Nov. 2011.
Scribed by Peter Scholl.
[112] Smith, B.
Uber executive suggests
digging up dirt on journalists.
https://www.buzzfeed.com/bensmith/uber-executivesuggests-digging-up-dirt-on-journalists, Nov. 17,
2014. Accessed 20 September 2016.
[113] U.S. Department of Health and Human Services.
AIDSinfo. https://aidsinfo.nih.gov/apps.

[100] Popa, R. A., Blumberg, A. J., Balakrishnan, H.,
and Li, F. H. Privacy and accountability forlocation-based aggregate statistics. In CCS (2011),
ACM, pp. 653–666.

[114] Viswanath, B., Post, A., Gummadi, K. P., and Mislove, A. An analysis of social network-based Sybil
defenses. SIGCOMM 40, 4 (2010), 363–374.

[101] Reiter, M. K., and Rubin, A. D. Crowds:
Anonymity for web transactions. TISSEC 1, 1
(1998), 66–92.

[115] Wahby, R. S., Setty, S. T., Ren, Z., Blumberg, A. J.,
and Walfish, M. Efficient RAM and control flowin verifiable outsourced computation. In NDSS
(2016).

[102] Rogaway, P., and Bellare, M. Robust computational secret sharing and a unified account of classical secret-sharing goals. In CCS (2007), ACM,
pp. 172–184.

[116] Walfish, M., and Blumberg, A. J. Verifying computations without reexecuting them. Communicationsof the ACM 58, 2 (2015), 74–84.

[103] Schnorr, C.-P. Efficient signature generation bysmart cards. Journal of Cryptology 4, 3 (1991),
161–174.

[117] Wang, G., Wang, B., Wang, T., Nika, A., Zheng, H.,
and Zhao, B. Y. Defending against Sybil devices
in crowdsourced mapping services. In MobiSys(2016), ACM, pp. 179–191.

[118] Warner, S. L. Randomized response: A survey technique for eliminating evasive answer bias.
Journal of the American Statistical Association 60,
309 (1965), 63–69.
[119] Williams, R. R. Strong ETH breaks with Merlinand Arthur: Short non-interactive proofs of batch
evaluation. In 31st Conference on Computational
Complexity (2016).
[120] Wolberg, W. H., Street, W. N., and Mangasarian, O. L. Wisconsin prognostic breast cancer
data set. https://archive.ics.uci.edu/ml/machinelearning-databases/breast-cancer-wisconsin/, Dec.
1995. Accessed 15 September 2016.
[121] Wolinsky, D. I., Corrigan-Gibbs, H., Ford, B., andJohnson, A. Dissent in numbers: Making strong
anonymity scale. In OSDI (2012), pp. 179–182.
[122] Wolinsky, D. I., Syta, E., and Ford, B. Hang withyour buddies to resist intersection attacks. In CCS(2013), ACM, pp. 1153–1166.
[123] Yao, A. C.-C. How to generate and exchange secrets. In FOCS (1986), IEEE, pp. 162–167.
[124] Yu, H., Gibbons, P. B., Kaminsky, M., and Xiao,
F. SybilLimit: A near-optimal social network defense against Sybil attacks. In Security and Privacy(2008), IEEE, pp. 3–17.
[125] Yu, H., Kaminsky, M., Gibbons, P. B., and Flaxman,
A. SybilGuard: defending against Sybil attacks via
social networks. In SIGCOMM (2006), vol. 36,
ACM, pp. 267–278.
[126] Zippel, R. Probabilistic algorithms for sparse polynomials. In Proceedings of the International Symposiumon on Symbolic and Algebraic Computation(1979), Springer-Verlag, pp. 216–226.

A

Security definitions

In this section we define f -privacy. We give an informal definition, for the sake of readability, that captures
the security properties we need. In what follows we use
the standard notions of negligible functions and computational indistinguishability (see, e.g., [66]). We often leave
the security parameter implicit.
Definition 1 ( f -Privacy). Say that there are s servers
in a Prio deployment, and say that n clients’ values areincluded in the final aggregate that the system outputs.
We say that the scheme provides f -privacy for a function
f , if for:• every subset of at most s − 1 malicious servers, and• every number of malicious clients m ≤ n,there exists an efficient simulator that, for every choice ofthe honest clients’ inputs (x1 , . . . , xn−m ), takes as input:• the public parameters to the protocol run (all participants’ public keys, the description of the aggregation
function f , the cryptographic parameters, etc.),• the indices of the adversarial clients and servers,• oracle access to the adversarial participants, and• the value f (x1 , . . . , xn−m ),and outputs a simulation of the adversarial participants’view of the protocol run whose distribution is computationally indistinguishable from the distribution of theadversary’s view of the real protocol run.
By engaging in the protocol, the adversary learns thevalue f (x1 , . . . , xn−m ) exactly. It is therefore critical thatthe honest servers ensure that the number n − m of honest
clients’ values included in the aggregate is “large enough.”
The honest servers must use out-of-band means to ensurethat many honest clients’ values are included in the final
aggregate. See discussion of this and related issues in
Section 7.
Let SORT be the function that takes n inputs and outputs them in lexicographically increasing order.
Definition 2 (Anonymity). We say that a data-collection
scheme provides anonymity if it provides f -privacy, inthe sense of Definition 1, for f = SORT.
A scheme that provides this form of anonymity leaks
to the adversary the entire list of honest clients’ inputs(x1 , . . . , xn−m ), but the adversary learns nothing about
which client submitted which value xi . For example, if
each client submits their location via a data-collection
scheme that provides anonymity, the servers learn thelist of submitted locations {`1 , . . . , `n−m }, but the servers
learn nothing about whether honest client x or y is in aparticular location `∗ .
Definition 3. A function f (x1 , . . . , xn ) is symmetricif, for all permutations π on n elements, the equality
f (x1 , . . . , xn ) = f (xπ(1) , . . . , xπ(n) ) holds.
Claim 4. Let D be a data-collection scheme that provides
f -privacy, in the sense of Definition 1, for a symmetricfunction f . Then D provides anonymity.
Proof sketch. The fact that D provides f -privacy implies the existence of a simulator S D that takes as
input f (x1 , . . . , xn−m ), along with other public values,
and induces a distribution of protocol transcripts indistinguishable from the real one. If f is symmetric,0f (x1 , . . . , xn−m ) = f (x10 , . . . , xn−m), where0(x10 , . . . , xn−m
) = SORT(x1 , . . . , xn−m ).

Using this fact, we construct the simulator required0
for the anonymity definition: on input (x10 , . . . , xn−m)=00
SORT(x1 , . . . , xn−m ), compute f (x1 , . . . , xn−m ), and feed
the output of f to the simulator S D . The validity of thesimulation is immediate.
The following claim demonstrates that it really only
makes sense to use an f -private data collection scheme
when the function f is symmetric, as all of the functions
we consider in Prio are.
Claim 5. Let f be a non-symmetric function. Then there
is no anonymous data collection scheme that correctlycomputes f .
Proof sketch. Let there be no malicious clients (m =0). Because f is not symmetric, there exists an input(x1 , . . . , xn ) in the domain of f , and a permutation π on nelements, such that f (x1 , . . . , xn ) , f (xπ(1) , . . . , xπ(n) ).
Let D be a data-collection scheme that implements
the aggregation function f (x1 , . . . , xn ). This D outputs
f (x1 , . . . , xn ) for all x1 , . . . , xn in the domain, and hencef (x1 , . . . , xn ) is part of the protocol transcript.
For D to be anonymous, there must be a simulator thattakes SORT(x1 , . . . , xn ) as input, and simulates the protocol transcript. In particular, it must output f (x1 , . . . , xn ).
But given SORT(x1 , . . . , xn ), it will necessarily fail to output the correct protocol transcript on either (x1 , . . . , xn ) or(xπ(1) , . . . , xπ(n) ).
Robustness. Recall that each Prio client holds a value
xi , where the value xi is an element of some set of data
items D. For example, D might be the set of 4-bit integers.
The definition of robustness states that when all servers
are honest, a set of malicious clients cannot influence thefinal aggregate, beyond their ability to choose arbitrary
valid inputs. For example, malicious clients can choose
arbitrary 4-bit integers as their input values, but cannot
influence the output in any other way.
Definition 6 (Robustness). Fix a security parameter λ >0. We say that an n-client Prio deployment provides
robustness if, when all Prio servers execute the protocol
faithfully, for every number m of malicious clients (with0 ≤ m ≤ n), and for every choice of honest client’s inputs(x1 , . . . , xn−m ) ∈ Dn−m , the servers, with all but negligible
probability in λ, output a value in the set:nof (x1 , . . . , xn ) | (xn−m+1 , . . . , xn ) ∈ Dm .

B

Robustness against faulty servers

If at least one of the servers is honest, Prio ensures thatthe adversary learns nothing about clients’ data, except
the aggregate statistic. In other words, Prio ensures client
privacy if at least one of servers is honest.

Prio provides robustness only if all servers are honest.
Providing robustness in the face of faulty servers is obviously desirable, but we are not convinced that it is worth
the security and performance costs. First, providing robustness necessarily weakens the privacy guarantees thatthe system provides: if the system protects robustness
in the presence of k faulty servers, then the system canprotect privacy only against a coalition of at most s − k − 1
malicious servers. The reason is that, if robustness holds
against k faulty servers, then s − k honest servers must
be able to produce a correct output even if these k faulty
servers are offline. Put another way: s − k dishonest
servers can recover the output of the system even without the participation of the k honest servers. Instead ofcomputing an aggregate over many clients ( f (x1 , . . . , xn )),the dishonest servers can compute the “aggregate” overa single client’s submission ( f (x1 )) and essentially learn
that client’s private data value.
So strengthening robustness in this setting weakens
privacy. Second, protecting robustness comes at a performance cost: some our optimizations use a “leader” server
to coordinate the processing of each client submission(see Appendix I). A faulty leader cannot compromise
privacy, but can compromise robustness. Strengthening
the robustness property would force us to abandon these
optimizations.
That said, it would be possible to extend Prio to provide robustness in the presence of corrupt servers using
standard techniques [10] (replace s-out-of-s secret sharing with Shamir’s threshold secret-sharing scheme [106],etc.).

C

MPC background

This appendix reviews the definition of arithmetic circuits and Donald Beaver’s multi-party computation protocol [9].

C.1

Definition: Arithmetic circuits

An arithmetic circuit C over a finite field F takes as input avector x = hx(1) , . . . , x(L) i ∈ FL and produces a single field
element as output. We represent the circuit as a directed
acyclic graph, in which each vertex in the graph is either
an input, a gate, or an output vertex.
Input vertices have in-degree zero and are labeled witha variable in {x(1) , . . . , x(L) } or a constant in F. Gate vertices have in-degree two and are labeled with the operation+ or ×. The circuit has a single output vertex, which has
out-degree zero.
To compute the circuit C(x) = C(x(1) , . . . , x(L) ), we walkthrough the circuit from inputs to outputs, assigning avalue in F to each wire until we have a value on the output

wire, which is the value of C(x). In this way, the circuit
implements a mapping C : FL → F.

its multiplication triple to compute the following values:

C.2

Each server i then broadcasts [d]i and [e]i . Using thebroadcasted shares, every server can reconstruct d and e
and can compute:

Beaver’s MPC protocol

This discussion draws on the clear exposition by
Smart [111].
Each server starts the protocol holding a share [x]i ofan input vector x. The servers want to compute C(x), forsome arithmetic circuit C.
The multi-party computation protocol walks throughthe circuit C wire by wire, from inputs to outputs. The
protocol maintains the invariant that, at the t-th time step,
each server holds a share of the value on the t-th wire in
the circuit. At the first step, the servers hold shares of the
input wires (by construction) and in the last step of the
protocol, the servers hold shares of the output wire. The
servers can then publish their shares of the output wires,
which allows them all to reconstruct the value of C(x). To
preserve privacy, no subset of the servers must ever haveenough information to recover the value on any internal
wire in the circuit.
There are only two types of gates in an arithmetic circuit (addition gates and multiplication gates), so we justhave to show how the servers can compute the shares ofthe outputs of these gates from shares of the inputs. Allarithmetic in this section is in a finite field F.
Addition gates. In the computation of an addition gate“y + z”, the ith server holds shares [y]i and [z]i of the input
wires and the server needs to compute a share of y + z. To
do so, the server can just add its shares locally[y + z]i = [y]i + [z]i .
Multiplication gates. In the computation of a multiplication gate, the ith server holds shares [y]i and [z]i andwants to compute a share of yz.
When one of the inputs to a multiplication gate is aconstant, each server can locally compute a share of theoutput of the gate. For example, to multiply a share [y]iby a constant A ∈ F, each server i computes their share of
the product as [Ay]i = A[yi ].
Beaver showed that the servers can use pre-computed
multiplication triples to evaluate multiplication gates [9].
A multiplication triple is a one-time-use triple of values(a, b, c) ∈ F3 , chosen at random subject to the constraintthat a · b = c ∈ F. When used in the context of multi-party
computation, each server i holds a share ([a]i , [b]i , [c]i ) ∈F3 of the triple.
Using their shares of one such triple (a, b, c), the servers
can jointly evaluate shares of the output of a multiplicationgate yz. To do so, each server i uses her shares [y]i and [z]iof the input wires, along with the first two components of[d]i = [y]i − [a]i;[e]i = [z]i − [b]i .

σi = de/s + d[b]i + e[a]i + [c]i .
Recall that s is the number of servers—a public constant—and the division symbol here indicates division (i.e., inversion then multiplication) in the field F. A few lines ofarithmetic confirm that σi is a sharing of the product yz.
To prove this we compute:
X
X

σi =
de/s + d[b]i + e[a]i + [c]iii= de + db + ea + c= (y − a)(z − b) + (y − a)b + (z − b)a + c= (y − a)z + (z − b)a + c= yz − az + az − ab + c= yz − ab + c= yz.
The last step used that c = ab (by construction of thePmultiplication triple), so: i σi = yz, which implies that
σi = [yz]i .
Since the servers can perform addition and multiplication of shared values, they can compute any function of
the client’s data value in this way, as long as they havea way of securely generating multiplication triples. The
expensive part of traditional MPC protocols is the process by which mutually distrusting servers generate these
triples in a distributed way.

D

SNIP security analysis

D.1

Soundness

We prove here that the SNIP construction of Section 4
is sound. We define soundness of the SNIP construction using the following experiment. The adversary’s
task is to produce an input x and a SNIP proof π =( f (0), g(0), h, a, b, c) shared amongst the servers, such that
Valid(x) , 1 and yet the servers accept x as valid. Assume, without loss of generality, that the output of the
Valid circuit is the value on the output wire of the last multiplication gate in the circuit, in topological order from
inputs to outputs.
Soundness. In the experiment, the adversary A plays
the role of a dishonest client interacting with honest
servers.

1. Run the adversary A. For each server i, theadversary outputs a set of values:• [x]i ∈ FL ,• ([ f (0)]i , [g(0)]i ) ∈ F2 ,• [h]i ∈ F[x] of degree at most 2M, and• ([a]i , [b]i , [c]i ) ∈ F3 .
2. Choose a random point r ←R F. For each serveri, compute [ f ]i and [g]i as in the real protocol,and evaluate [ f (r)]i , [r · g(r)]i , and [r · h(r)]i .
3. Define the following values, where s is a constant representing the number of servers:x=Pi [x]ia=Pf (r) =

Pi [ f (r)]ib=Pi [b]ir · g(r) =Pi [r · g(r)]ic=Pi [c]ih(M) =

Pi [h]i (M)d = f (r) − ai [a]ii de/s + d[b]i + e[a]i + [c]i − [r · h(r)]iP

Claim 8. When f · g = h, the value h(t) is equal tothe output of the value on the output wire of the t-th
multiplication gate in the Valid(x) circuit.
Proof. By induction on t.

e = r · g(r) − b
σ=degree at most 2M + 1, no matter how Q and (c − ab)are related. Furthermore, we know that the choice of r
is independent of (a, b, c) and Q = f · g − h, since theadversary must produce these values in the experiment
before r is chosen. The choice of r is then independentof the polynomial P. Since P is a non-zero polynomial of
degree at most (2M + 1), P can have at most 2M + 1 zeros
in F. This implies that the probability that P(r) = σ = 0,
for a random r independent of P, is at most (2M + 1)/|F|.
So, whenever f · g , h, Pr[W] ≤ (2M + 1)/|F|.
Let us now consider the case when f · g = h. Label thegates in the Valid circuit in topological order from inputs
to outputs.

= de + db + ea + c − h(r)= ( f (r) − a)(r · g(r) − b) + ( f (r) − a)b+ (r · g(r) − b)a + c − r · h(r)= r · ( f (r)g(r) − h(r)) + (c − ab).
4. We say that the adversary wins the game ifh(M) = 1, σ = 0, and Valid(x) , 1.

Let W be the event that the adversary wins the soundness game. We say that the SNIP protocol is sound if, forall adversaries A, even computationally unbounded ones,
Pr[W] ≤ (2M + 1)/|F|,where the probability is over the uniform choice of r in F
in Step 2. Here M is the number of multiplication gatesin the Valid circuit.
Theorem 7. The SNIP protocol of Section 4 is sound.
Proof. First, consider the probability that σ = 0, over the
choice of r in F. We can express the value of σ as theevaluation of the following polynomial P(t) at the point r:
P(t) = t · ( f (t) · g(t) − h(t)) + (c − ab)= t · Q(t) + (c − ab),for some polynomial Q(t). If f · g , h, then Q is nonzero and the polynomial P is a non-zero polynomial ofBase case (t = 1). The left and right inputs to the firstmultiplication gate in the circuit are affine functions AL,1and AR,1 of the input x. (These functions could also beconstant functions.) In constructing the polynomials f
and g in the experiment, we set:f (1) = AL,1 (x)andg(1) = AR,1 (x).

Since f · g = h, we have thath(1) = f (1) · g(1) = AL,1 (x) · AR,1 (x),and h(1) is truly the value on the output wire of the firstmultiplication gate in the Valid(x) circuit.
Induction step. The left and right inputs to the tth multiplication gate are affine functions AL,t and AR,t of x andthe outputs of all prior multiplication gates in the circuit:(h(1), . . . , h(t − 1)). By the induction hypothesis, the values (h(1), . . . , h(t − 1)) are the values on the output wiresof the first t − 1 multiplication gates in the Valid circuit.
In constructing f and g, we set:f (t) = AL,t (x, (h(1), . . . , h(t − 1))
g(t) = AR,t (x, (h(1), . . . , h(t − 1)).
These values are exactly the values on the left and right input wires to the tth multiplication gate in the Valid circuit.
Finally, since f · g = h, we have that h(t) = f (t) · g(t), so
the value h(t) is equal to the value on the output wire of
the tth multiplication gate in the Valid circuit.
Now, by Claim 8, when f · g = h, the value of h(M) is
the output of the Mth multiplication gate in the Valid(x)circuit, which is actually the value on the output wire of
the circuit. (Here we assume without loss of generalitythat the output value of the last multiplication gate is value

that the circuit outputs.) The probability that h(M) = 1
when Valid(x) , 1 is then zero. So, whenever f · g = h,
Pr[W] = 0.
We have shown that Pr[W] ≤ (2M + 1)/|F| no matter
whether f ·g = h. This concludes the proof of the theorem.
D.2

Zero knowledge property

In this section, we show that as long as one server ishonest, an adversary who controls the remaining servers
learns nothing about the client’s data by participating in
the SNIP verification protocol. Informally, we show thatfor all x ∈ FL such that Valid(x) = 1, an adversary who
controls a proper subset of the servers can perfectly simulate its interaction with the honest parties (the client andthe honest servers). The simulation is generated without knowledge of the client’s data x, proving that theadversary learns nothing about the client’s data from theprotocol.
We first precisely define the notion of security that
we require from our SNIP construction. We define a“real” world experiment, in which the adversary is given
data as in the real protocol, and an “ideal” world experiment, in which the adversary is given data generated bya simulator. We say that the SNIP protocol maintains
the zero-knowledge property if the adversary—even if
the adversary receives x as input—has no advantage at
distinguishing these two experiments.
Since the role of all servers is symmetric, and since
all values exchanged in the protocol are shared using
additive secret sharing, it is without loss of generality toprove security for the case of a single adversarial serverinteracting with a single honest server. For a value v ∈ F
we use [v]a and [v]h to denote the adversarial and honest
parties’ shares of v. Then [v]a + [v]h = v ∈ F.
In what follows, we denote the single Beaver triple thatthe servers use to execute the protocol by (a, b, c) ∈ F3 .
We let r ∈ F be the point that the servers use to executethe polynomial identity test. We assume that the Valid
circuit has M multiplication gates, and that the output of
the Mth multiplication gate is the value that the circuit
outputs.
Real-world experiment. The experiment is parameterized by an input x ∈ FL and a point r ∈ F. The
experiment is with an adversary (A1 , A2 ), representing the malicious server.
1. Choose random (a, b, c) ∈ F3 , subject to theconstraint that a · b = c. Construct polynomials
f , g, and h over F as in the real protocol. Compute f (r), g(r), and h(r). Split the values a, b, c,

x, f (0), g(0), and h into shares and compute[d]h = [ f (r)]h − [a]h[e]h = [r · g(r)]h − [b]h∈F∈F

msg1 = [a]a , [b]a , [c]a , [x]a , [ f (0)]a , [g(0)]a ,[h]a , [h(M)]h , [d]h , [e]h , .
Note that [h(M)]h is the honest server’s shareof the output wire of the Valid(x) circuit.
2. Run the first-stage adversary A1 :(stateA , [d̂]a , [ê]a ) ← A1 (x, r, msg1 ).
3. Compute the honest parties’ response by setting d̂ = [d̂]a + [d]h and ê = [ê]a + [e]h , andcomputing[σ̂]h = d̂ê/2+d̂[b]h +ê[a]h +[c]h −[r·h(r)]h ∈ F.
4. Outputβ̂ ← A2 (stateA , [σ̂]h ) ∈ {0, 1}.

Ideal-world experiment. This experiment is parameterized by an input x ∈ FL and a point r ∈ F. The
experiment is with an adversary (A1 , A2 ) and a simulator S = (S 1 , S 2 ). The simulator is only given r ∈ F
as input.
1. Run the simulator: (stateS , msg1 ) ← S 1 (r).

2. (stateA , [d̂]a , [ê]a ) ← A1 x, r, msg1 .
3. Run the simulator:[σ̂]h ← S 2 (stateS , [d̂]a , [ê]a ).
4. Output β̂ ← A2 (stateA , [σ̂]h ) ∈ {0, 1}.

We let Expreal (x, r) and Expideal (x, r) be a random variable indicating the adversary’s output in the real-world
and ideal-world experiments, respectively.
We say that the SNIP protocol is zero knowledge if
no adversary A, even a computationally unbounded one,can distinguish the real-world experiment from the idealworld experiment. That is, for all x ∈ FL such that
Valid(x) = 1, and for all r < {1, . . . , M} ∈ F, we require
that:
Pr[Expreal (x, r) = 1] − Pr[Expideal (x, r) = 1] = 0. (2)If the SNIP protocol satisfies this notion of security,even if the adversary has a candidate guess x∗ ∈ F forthe client’s private value x ∈ FL (where Valid(x) = 1),
the adversary learns nothing about x by participating inthe SNIP protocol. In particular, the adversary does notlearn whether her guess was correct, because her entire
view can be simulated perfectly without knowledge of x.
Condition (2) implies a notion of semantic security: forany two valid x0 , x1 ∈ FL , the adversary’s view of the
protocol is sampled identically, whether the client uses x0
or x1 to execute the SNIP protocol.
Note that we only require the zero knowledge property
to hold when r < {1, . . . , M}. Since we use a field F
such that |F|  2M, the probability that a uniformly
random r falls into this bad set is negligibly small. To
entirely avoid this bad event, the servers could sample
r with the constraint that r < {1, . . . , M}, which would
increase the soundness error of the proof system slightly,
to 1/(|F| − M).
To demonstrate that our SNIP construction satisfies
the zero-knowledge property, we must produce a simulator S = (S 1 , S 2 ) that renders the adversary unable todistinguish the real and ideal worlds.
We first describe our simulator, and then argue that thesimulation is accurate.
Simulator. The simulator S 1 (r) first• chooses random (a, b, c) ←R F3 , subject to theconstraint that a · b = c,
• chooses [x]a ←R FL ,• chooses f (r), g(r) ←R F,• chooses [ f (0)]a , [g(0)]a ←R F, and• chooses [h]a ←R F[x] of degree at most 2M bychoosing coefficients at random from F.
The simulator then sets:[h(M)]h ← (1 − [h]a (M))h(r) ← f (r) · g(r)[r · h(r)]h ← r · (h(r) − [h]a (r))∈ F,
∈ F, and∈ F.

The simulator computes shares ([a]a , [b]a , [c]a ) of
the multiplication triple, shares [ f (r)]h and [g(r)]h ,and the values[d]h = [ f (r)]h − [a]h∈F[e]h = [r · g(r)]h − [b]h∈ F.

Finally, the simulator produces the state
state = [a]h , [b]h , [c]h , [r · h(r)]h .



and outputs
state, ([a]a , [b]a , [c]a , [x]a ,[ f (0)]a , [g(0)]a , [h]a , [h(M)]h , [d]h , [e]h ) .

The simulator S 2 , on input (state, [d̂]a , [ê]a ) computes d̂ = [d̂]a + [d]h and ê = [ê]a + [e]h , and outputs
the unique value [σ̂]h ∈ F:[σ̂]h ← d̂ê/2 + d̂[b]h + ê[a]h + [c]h − [r · h(r)]h .

Theorem 9. The adversary’s view in the real world isdistributed identically to the adversary’s view in the ideal
world, in which the adversary interacts with the simulator S . Therefore (2) holds.
Proof. As a first step, notice that in the real protocol, thevalues f (r) and g(r) are distributed independently anduniformly at random, conditioned on all the informationthat the adversary has at the start of the protocol. To
see this, write the value f (r) in terms of the Lagrange
interpolating polynomials (λ0 (r), . . . , λ M (r)):
f (r) = λ0 (r) · f (0) +MXλi (r) · f (i).

(3)

i=1

Because the adversary knows x, it knows f (1), . . . , f (M).
However, in the real protocol, the honest client chooses
the value of f (0) ∈ F independently and uniformly at
random. Further, the value λ0 (r) is non-zero for all r <{1, . . . , M}. Therefore, by (3) we have that f (r) is uniform
in F and is independent of the adversary’s view. The
same argument applies to g(r). Thus, for all relevant
choices of r, f (r) and g(r) will be distributed uniformly
and independently of the adversary’s view at the start ofthe protocol. The simulator’s choices of f (r) and g(r) arethen distributed exactly as in the real protocol.
Next, notice that the simulation in the first flow of the
protocol of the shares of a, b, c, x, f (0), g(0), and h isperfect, since the secret-sharing scheme perfectly hides
these values in the real world.
The simulation of the share [h(M)]h is also perfect.
Since h(M) is the value on the output wire of the Valid
circuit, and since Valid(x) = 1 for all honest clients, itwill always be true in the real world that h(M) = 1. In particular, in the real world, the value [h(M)]h that the honest
client sends satisfies [h]a (M) + [h(M)]h = 1 ∈ F always.
The simulated value preserves this equality exactly.
The simulation of the shares of d and e is also perfect,
since [d]h and [e]h are masked by [a]h and [b]h , which
are equal to[a]h = a − [a]aand[b]h = b − [b]a ,for uniformly random values a and b unknown to theadversary.
Now, the only remaining claim we need to argue is thatthe simulation of the final value [σ̂]h is consistent with its

value in the real-world experiment. To do so, we need toargue that, irrespective of the adversary’s choice of [d̂]aand [ê]a , and conditioned on all other values the adversary
knows, the simulated value of [σ̂]h is distributed as in thereal world.
The values that the adversary should have sent, wereit honest, in the second step of a real run of the protocol
are:[d]a = [ f (r)]a − [a]aand[e]a = [r · g(r)]a − [b]a .

Say that instead the adversary shifts these values by ∆dand ∆e . The reconstructed values d̂ and ê will then also
be shifted:d̂ = d + ∆d

andê = e + ∆e .

In this case, the value that the adversary receives in thereal-world experiment from the honest parties is:[σ̂]h = d̂ê/2 + d̂[b]h + ê[a]h + [c]h − [r · h(r)]h .
Define the corresponding adversarial share:[σ̂]a = d̂ê/2 + d̂[b]a + ê[a]a + [c]a − [r · h(r)]a(4)

Claim 10. We have that[σ̂]h = f (r)∆e + r · g(r)∆d + ∆d ∆e − [σ̂]a .

(5)

Proof of claim. Consider the sum:[σ̂]a + [σ̂]h = d̂ê + d̂b + êa + c − r · h(r)= (d + ∆d )(e + ∆e ) + (d + ∆d )b+ (e + ∆e )a + ab − r · h(r)= de + e∆d + d∆e + ∆e ∆d + db
+ b∆d + ea + a∆e + ab − r · h(r)= (de + db + ea + ab) + d∆e + e∆d+ ∆d ∆e + b∆d + a∆e − r · h(r).
As in Beaver’s protocol (Appendix C.2), r · f (r) · g(r) =(de + db + ea + ab). Additionally, f (r) · g(r) = h(r) for all
honest clients, so[σ̂]a + [σ̂]h = r · f (r)g(r) + d∆e + e∆d+ ∆d ∆e + b∆d + a∆e − r · h(r)= d∆e + e∆d + ∆d ∆e + b∆d + a∆e= ( f (r) − a)∆e + (r · g(r) − b)∆d
+ ∆d ∆e + b∆d + a∆e= f (r)∆e + r · g(r)∆d + ∆d ∆e .
Which proves (5).

1. the adversary has no information about f (r) and g(r)at the start of the protocol,
2. the simulation of the first flow is perfect, and3. the contents of the first flow are independent of f (r)and g(r).
These three points together demonstrate that whatever
the adversary has learned after seeing the first flow, it
is independent of f (r) and g(r). So, ∆d , ∆e , and [σ̂]aare independent of f (r) and g(r), and f (r) and g(r) are
independent random values.
In the real world, there are two cases:• When ∆d = ∆e = 0, we have that [σ̂]a = −[σ̂]h .
• Otherwise, f (r)∆e + r · g(r)∆d is a random value
independent of everything else that the adversary
has seen so far. Therefore by (5), so is [σ̂]h .
Our simulation in the ideal world produces the same behavior. To see this, observe that the simulator computes[σ̂]h exactly as in the real protocol, as long as all of thevalues upon which [σ̂]h depends are distributed as in thereal world, and we have already argued that they are. This
completes the proof of the theorem.


Now, the adversary knows ∆d and ∆e and, using theinformation that the adversary has learned after the firstflow in the protocol, the adversary can compute [σ̂]ausing (4). We know, by our arguments thus far, that

Why randomize the polynomials? If the client did notchoose f (0) and g(0) at random in F, that is, if the polynomials f and g were completely determined by the inputx ∈ FL , then the simulation would fail. The reason isthat f (r) and g(r) would then be known to the adversary(because the adversary knows x in the real-world experiment), but the simulator (in the ideal world) would notknow x. As a result, when ∆d , 0 or ∆e , 0, the simulator
S 2 could not generate the correct [σ̂]h to satisfy (5), andthe simulation would fail. By having the client choose
f (0) and g(0) at random we ensure that f (r) and g(r) are
independent of the adversary’s view, which enables thesimulator to properly generate [σ̂]h .
This simulation failure is not just an artifact of ourproof technique: if the SNIP used non-randomized polynomials f and g, a malicious server could learn non-trivial
information about x by participating in the protocol. The
idea of the attack is that a malicious verifier could, by
deviating from the protocol, learn whether Valid( x̂) = 1,
for some value x̂ related to x. To do so, the adversary
would essentially shift its share of x to a share of x̂ andthen would execute the rest of the SNIP protocol faithfully.
To compute the shifted share of x, the adversary would
locally compute: [ x̂]a = [x]a + ∆ x . (The adversary also
would need to shift its share of the polynomial h to a shareof ĥ, but this is also possible if the polynomials f , g, andh are not randomized.) At the end of the SNIP verification protocol, the adversary learns whether Valid( x̂) = 1,
rather than whether Valid(x) = 1.
Leaking Valid( x̂) to the adversary can potentially leakall of x to the adversary. For example, if x is a single

element of F and Valid(x) tests whether x ∈ {0, 1}, thenlearning Valid( x̂), for x̂ = x + 1 leaks x entirely. That is,
if x = 0, then
Valid( x̂) = Valid(x + 1) = Valid(1) = 1,
and if x = 1, then
Valid( x̂) = Valid(x + 1) = Valid(2) = 0.
An adversary who can learn Valid( x̂) can then completely
recover x. A variant of the attack allows the adversary to[test some related predicate Valid(x)(instead of Valid(x))
on the client’s input, which has essentially the same effect.
Randomizing the polynomials f and g prevents a malicious server from learning side information about x in
this way.

E

Server-side Valid computation

If the Valid predicate takes secret inputs from the servers,
the servers can compute Valid(x) on a client-provided input x without learning anything about x, except the valueof Valid(x). In addition, the client learns nothing about the
Valid circuit, except the number of multiplication gates in
the circuit.
Crucially, this server-side variant only provides security
against “honest-but-curious” servers, who execute theprotocol correctly but who try to learn everything possible
about the clients’ private data from the protocol execution.
It may be possible to provide security against actively
malicious servers using a client-assisted variant of the
SPDZ multi-party computation protocol [46], though weleave this extension to future work.
Let M be the number of multiplication gates in the
Valid circuit. To execute the Valid computation on theserver side, the client sends M multiplication triple shares(defined in Appendix C.2) to each server, along with ashare of its private value x. Let the t-th multiplication
triple be of the form (at , bt , ct ) ∈ F3 . Then define a circuit
M that returns “1” if and only if ct = at · bt , for all
1 ≤ t ≤ M.
The client can use a SNIP proof (Section 4.1) to convince the servers that all of the M triples it sent the servers
are well-formed. Then, the servers can execute Beaver’s
multiparty computation protocol (Section C.2) to evaluate the circuit using the M client-provided multiplication
triples. The security of this portion of the protocol, withrespect to “honest but curious” servers, follows directlyfrom the security of Beaver’s protocol.
Running the computation requires the servers to exchange Θ(M) field elements, and the number of roundsof communication is proportional to the multiplicative
depth of the Valid circuit (i.e., the maximum number ofmultiplication gates on an input-output path).

F

AFE definitions

An AFE is defined relative to a field F, two integers k
and k0 (where k0 ≤ k), a set D of data elements, a set
A of possible values of the aggregate statistic, and an
aggregation function f : Dn → A. An AFE scheme
consists of three efficient algorithms. The algorithms are:• Encode : D → Fk . Covert a data item into its AFEencoded counterpart.
• Valid : Fk → {0, 1}. Return “1” if and only if the
input is in the image of Encode.
0• Decode : Fk → A. Given a vector representing acollection of encoded data items, return the value ofthe aggregation function f evaluated at these items.
To be useful, an AFE encoding should satisfy the following properties:
Definition 11 (AFE correctness). We say that an AFE iscorrect for an aggregation function f if, for every choiceof (x1 , . . . , xn ) ∈ Dn , we have that:
DecodePi Trunck0 Encode(xi )= f (x1 , . . . , xn ).

Recall that Trunck0 (v) denotes truncating the vector v ∈Fkp to its first k0 components.
The correctness property of an AFE essentially statesthat if we are given valid encodings of data items(x1 , . . . , xn ) ∈ Dn , the decoding of their sum should bef (x1 , . . . , xn ).
Definition 12 (AFE soundness). We say that an AFE
is sound if, for all encodings e ∈ Fk : the predicate
Valid(e) = 1 if and only if there exists a data item x ∈ Dsuch that e = Encode(x).
An AFE is private with respect to a function fˆ, if theP
sum of encodings σ = i Trunck0 (Encode(xi )), given
as input to algorithm Decode, reveals nothing about theunderlying data beyond what fˆ(x1 , . . . , xn ) reveals.
Definition 13 (AFE privacy). We say that an AFE
is private with respect to a function fˆ : Dn →A0 if there exists an efficient simulator S such thatfor all input data (x1 , . . . , xn ) ∈ Dn , the distribution
S ( fˆ(x1 , . . . , xn )) is indistinguishable from the distributionP
σ = i Trunck0 (Encode(xi )).
Relaxed correctness. In many cases, randomized data
structures are more efficient than their deterministic counterparts. We can define a relaxed notion of correctness
to capture a correctness notion for randomized AFEs. In
the randomized case, the scheme is parameterized byconstants 0 < δ,  and the Decode algorithm may use
randomness. We demand that with probability at least1 − 2−δ , over the randomness of the algorithms, the encoding yields an “-good” approximation of f . In ourapplications, typically an -good approximation is within
a multiplicative or additive factor of  from the true value;
the exact meaning depends on the AFE in question.

G

Additional AFEs

Approximate counts. The frequency count AFE, presented in Section 5.2, works well when the client value
x lies in a small set of possible data values D. This AFE
requires communication linear in the size of D. Whenthe set D is large, a more efficient solution is to use arandomized counting data structure, such as a count-min
sketch [36].
Melis et al. [92] demonstrated how to combine a countmin sketch with a secret-sharing scheme to efficiently
compute counts over private data. We can make theirapproach robust to malicious clients by implementing acount-min sketch AFE in Prio. To do so, we use ln(1/δ)
instances of the basic frequency count AFE, each for aset of size e/, for some constants  and δ, and wheree ≈ 2.718. With n client inputs, the count-min sketchyields counts that are at most an additive n overestimateof the true values, except with probability e−δ .
Crucially, the Valid algorithm for this composed construction requires a relatively small number of multiplication gates—a few hundreds, for realistic choices of and δ—so the servers can check the correctness of theencodings efficiently.
This AFE leaks the contents of a count-min sketch data
structure into which all of the clients’ values (x1 , . . . , xn )have been inserted.
Share compression. The output of the count-min sketch
AFE encoding routine is essentially a very sparse matrixof dimension ln(1/δ) × (e/). The matrix is all zeros,
except for a single “1” in each row. If the Prio client uses
a conventional secret-sharing scheme to split this encoded
matrix into s shares—one per server—the size of eachshare would be as large as the matrix itself, even though
the plaintext matrix contents are highly compressible.
A more efficient way to split the matrix into shareswould be to use a function secret-sharing scheme [24,25, 64]. Applying a function secret sharing scheme toeach row of the encoded matrix would allow the size ofeach share to grow as the square-root of the matrix width(instead of linearly). When using Prio with only twoservers, there are very efficient function secret-sharing
constructions that would allow the shares to have length
logarithmic in the width of the matrix [25]. We leavefurther exploration of this technique to future work.
Most popular. Another common task is to return themost popular string in a data set, such as the most popular

homepage amongst a set of Web clients. When the universe of strings is small, it is possible to find the most popular string using the frequency-counting AFE. When theuniverse is large (e.g., the set of all URLs), this method is
not useful, since recovering the most popular string would
require querying the structure for the count of every possible string. Instead, we use a simplified version of a data
structure of Bassily and Smith [7].
When there is a very popular string—one that morethan n/2 clients hold, we can construct a very efficient
AFE for collecting it. Let F be a field of size at least n.
The Encode(x) algorithm represents its input x as a bbit string x = (x0 , x1 , x2 , . . . , xb−1 ) ∈ {0, 1}b , and outputs
a vector of b field elements (β0 , . . . , βb−1 ) ∈ Fb , whereβi = xi for all i. The Valid algorithm uses b multiplication
gates to check that each value βi is really a 0/1 value inF, as in the summation AFE.
The Decode algorithm gets as input the sum of n suchP
encodings σ = ni=1 Encode(xi ) = (e0 , . . . , eb−1 ) ∈ Fb .
The Decode algorithm rounds each value ei either down tozero or up to n (whichever is closer) and then normalizes
the rounded number by n to get a b-bit binary string σ ∈{0, 1}b , which it outputs. As long as there is a string σ∗with popularity greater than 50%, this AFE returns it. To
see why, consider the first bit of σ. If σ∗ [0] = 0, then thesum e0 < n/2 and Decode outputs “0.” If σ∗ [0] = 1, thenthe sum e0 > n/2 and Decode outputs “1.” Correctness
for longer strings follows
This AFE leaks quite a bit of information about thegiven data. Given σ, one learns the number of data values
that have their ith bit set to 1, for every 0 ≤ i < b. In fact,
the AFE is private relative to a function that outputs theseb values, which shows that nothing else is leaked by σ.
With a significantly more complicated construction, we
can adapt a similar idea to collect strings that a constantfraction c of clients hold, for c ≤ 1/2. The idea is to havethe servers drop client-submitted strings at random into
different “buckets,” such that at least one bucket has avery popular string with high probability [7].
Evaluating an arbitrary ML model. We wish to measure how well a public regression model predicts a target
y from a client-submitted feature vector x. In particular,
if our model outputs a prediction ŷ = M(x), we would
like to measure how good of an approximation ŷ is ofy. The R2 coefficient is one statistic for capturing thisinformation.
Karr et al. [82] observe that it is possible to reduce
the problem of computing the R2 coefficient of a public
regression model to the problem of computing private
sums. We can adopt a variant of this idea to use Prio
to compute the R2 coefficient in a way that leaks little
beyond the coefficient itself.
The R2 -coefficient of the model for client inputs
P{x1 , . . . , xn } is R2 = 1 − 2i=1 (yi − ŷi )2 /Var(y1 , . . . , yn ),where yi is the true value associated with xi , ŷi = M(xi ) is
the predicted value of yi , and Var(·) denotes variance.
An AFE for computing the R2 coefficient works as follows. On input (x, y), the Encode algorithm first computes
the prediction ŷ = M(x) using the public model M. The
Encode algorithm then outputs the tuple (y, y2 , (y − ŷ)2 , x),embedded in a finite field large enough to avoid overflow.
Given the tuple (y, Y, Y ∗ , x) as input, the Valid algorithm
ensures that Y = y2 and Y ∗ = (y−M(x))2 . When the model
M is a linear regression model, algorithm Valid can be
represented as an arithmetic circuit that requires only two
multiplications. If needed, we can augment this with acheck that the x values are integers in the appropriate
range using a range check, as in prior AFEs. Finally,
given the sum of encodings restricted to the first threecomponents, the Decode algorithm has the information it
needs to compute the R2 coefficient.
This AFE is private with respect to a function that
outputs the R2 coefficient, along with the expectation andvariance of {y1 , . . . , yn }.

H

Prio protocol and proof sketch

We briefly review the full Prio protocol and then discuss
its security.
The final protocol. We first review the Prio protocol
from Section 5. Let there be m malicious clients whose
values are included in the final aggregate. We assume thatevery honest client i, for i ∈ {1, . . . , n − m}, holds a private
value xi that lies in some set of data items D. We wantto compute an aggregation function f : Dn−m → A on
these private values using an AFE. The AFE encoding
algorithm Encode maps D to Fk , for some field F and anarity k. When decoding, the encoded vectors in Fk are
first truncated to their first k0 components.
The Prio protocol proceeds in four steps:
1. Upload. Each client i computes yi ← Encode(xi ) andsplits its encoded value into s shares, one per server. To
do so, the client picks random values [yi ]1 , . . . , [yi ] s ∈Fk , subject to the constraint: yi = [yi ]1 + · · · + [yi ] s ∈ Fk .
The client then sends, over an encrypted and authenticated channel, one share of its submission to eachserver, along with a share of a SNIP proof (Section 4)that Valid(yi ) = 1.
2. Validate. Upon receiving the ith client submission,
the servers verify the client-provided SNIP to jointly
confirm that Valid(yi ) = 1 (i.e., that client’s submission
is well-formed). If this check fails, the servers reject
the submission.
3. Aggregate. Each server j holds an accumulator value0
A j ∈ Fk , initialized to zero, where 0 < k0 ≤ k. Upon

receiving a share of a client encoding [yi ] j ∈ Fk , theserver truncates [yi ] j to its first k0 components, andadds this share to its accumulator:0

A j ← A j + Trunck0 ([yi ] j ) ∈ Fk .
Recall that Trunck0 (v) denotes truncating the vectorv ∈ Fkp to its first k0 components.
4. Publish. Once the servers have received a share fromeach client, they publish their accumulator values. TheP0
sum of the accumulator values σ = j A j ∈ Fk yields
P
the sum i Trunck0 (yi ) of the clients’ private encodedvalues. The servers output Decode(σ).
Security. We briefly sketch the security argument forthe complete protocol. The security definitions appear in
Appendix A.
First, the robustness property (Definition 6) follows
from the soundness of the SNIP construction: as long as
the servers are honest, they will correctly identify andreject any client submissions that do not represent proper
AFE encodings.
Next, we argue f -privacy (Definition 1). Define thefunctiong(x1 , . . . , xn−m ) =

n−m
X


Trunck0 Encode(xi ) .

i=1

We claim that, as long as:• at least one server executes the protocol correctly,• the AFE construction is private with respect to f , inthe sense of Definition 13, and• the SNIP construction satisfies the zero-knowledge
property (Section 4.1),
the only information that leaks to the adversary is thevalue of the function f on the private values of the honest
clients included in the final aggregate.
To show this, it suffices to construct a simulator S thattakes as input σ = g(x1 , . . . , xn−m ) and outputs a transcriptof the protocol execution that is indistinguishable froma real transcript. Recall that the AFE simulator takesf (x1 , . . . , xn−m ) as input and simulates σ. Composing thesimulator S with the AFE simulator yields a simulator forthe entire protocol, as required by Definition 1.
On input σ, the simulator S executes these steps:• To simulate the submission of each honest client, thesimulator invokes the SNIP simulator as a subroutine.
• To simulate values produced by adversarial clients, thesimulator can query the adversary (presented to thesimulator as an oracle) on the honest parties’ values
generated so far.
• The simulator must produce a simulation of the values
produced by the honest servers in Step 4 of the protocol.

Let σ be the sum of the honest clients’ encodings. For
the simulation to be accurate, the honest servers must
publish values A j such that the honest servers’ accumulators sum to (1) all of the shares of encodings given
to the honest servers by adversarial clients plus (2) σminus (3) the shares of honest clients’ simulated encodings given to adversarial servers.
Let [yi ] j be the jth share of the encoding sent by client i.
Let ServA be the set of indices of the adversarial servers
and ClientA be the set of indices of the adversarial
clients. Let ServH and ClientH be the set of indices of
the honest servers and clients, respectively. Then theaccumulators A j must satisfy the relation:
X
j∈ServH X
A j = σ + 

X

j∈ServH i∈ClientA[yi ] j  X− 

X

j∈ServA i∈ClientH[yi ] j  .

The simulator can pick random values for the honest
servers’ A j s subject to this constraint, since the simulator knows σ, it knows the values that the honest clients’sent to the adversarial servers, and it knows the values
that the adversarial clients sent to the honest servers.
To argue that the simulator S correctly simulates a run of
the real protocol:• The existence of the SNIP simulator implies that everything the adversarial servers see in the SNIP checking
step, when interacting with an honest client, is independent of the honest client’s private value xi , provided
that Valid(xi ) = 1. This property holds even if the malicious servers deviate from the protocol in a way thatcauses an honest client’s submission to be rejected by
the honest servers.
• The simulation of the aggregation step of the protocol
is perfect. In the real protocol, since the adversary sees
only s − 1 shares of each client submission, the values A j are just random values subject to the constraint
above.
Finally, anonymity (Definition 2) follows by Claim 4
whenever the function f is symmetric. Otherwise,
anonymity is impossible, by Claim 5.

I

Additional optimizations

Optimization: PRG secret sharing. The Prio protocol
uses additive secret sharing to split the clients’ private data
into shares. The naïve way to split a value x ∈ FL into s
shares is to choose [x]1 , . . . , [x] s−1 ∈ FL at random andP s−1then set [x] s = x − i=1[x]i ∈ FL . A standard bandwidthsaving optimization is to generate the first s − 1 sharesusing a pseudo-random generator (PRG) G : K → FL ,such as AES in counter mode [85, 102]. To do so, picks − 1 random PRG keys k1 , . . . , k s−1 ∈ K, and define thefirst s − 1 shares as G(k1 ), G(k2 ), . . . , G(k s−1 ). Rather thanrepresenting the first s − 1 shares as vectors in FL , we can
now represent each of the first s − 1 shares using a single
AES key. (The last share will still be L field elements inlength.) This optimization reduces the total size of theshares from sL field elements down to L + O(1). For s = 5
servers, this 5× bandwidth savings is significant.
Optimization: Verification without interpolation. In
the course of verifying a SNIP (Section 4.2, Step 2), eachserver i needs to interpolate two large polynomials [ f ]iand [g]i . Then, each server must evaluate the polynomials[ f ]i and [g]i at a randomly chosen point r ∈ F to executethe randomized polynomial identity test (Step 3).
The degree of these polynomials is close to M, where
M is the number of multiplication gates in the Valid circuit. If the servers used straightforward polynomial interpolation and evaluation to verify the SNIPs, the servers
would need to perform Θ(M log M) multiplications to process a single client submission, even using optimized FFT
methods. When the Valid circuit is complex (i.e., M ≈ 216
or more), this Θ(M log M) cost will be substantial.
Let us imagine for a minute that we could fix in advance the random point r that the servers use to executethe polynomial identity test. In this case, each server canperform interpolation and evaluation of any polynomial P
in one step using only M field multiplications per server,
instead of Θ(M log M). To do so, each server precomputes constants (c0 , . . . , c M−1 ) ∈ F M . These constants
depend on the x-coordinates of the points being interpolated (which are always fixed in our application) and on
the point r (which for now we assume is fixed). Then,
M−1
given points {(t, yt )}t=0
on a polynomial P, the servers
can evaluate P at r using a fast inner-product computation:PP(x) = t ct yt ∈ F. Standard Lagrangian interpolation
produces these ci s as intermediate values [6].
Our observation is that the servers can fix the “random”
point r at which they evaluate the polynomials [ f ]i and[g]i as long as: (1) the clients never learn r, and (2) theservers sample a new random point r periodically. The
randomness of the value r only affects soundness. Since
we require soundness to hold only if all Prio servers arehonest, we may assume that the servers will never reveal
the value r to the clients.
A malicious client may try to learn something overtime about the servers’ secret value r by sending a batchof well-formed and malformed submissions and seeing
which submissions the servers do or do not accept. A
simple argument shows that after making q such queries,
the client’s probability of cheating the servers is at most
(2M + 1)q/|F|. By sampling a new point after everyQ ≈ 210 client uploads, the servers can amortize the costof doing the interpolation precomputation over Q client
uploads, while keeping the failure probability bounded
above by (2M + 1)Q/|F|, which they might take to be 2−60
or less.
In Prio, we apply this optimization to combine theinterpolation of [ f ]i and [g]i with the evaluation of thesepolynomials at the point r.
In Step 2 of the SNIP verification process, each servermust also evaluate the client-provided polynomial [h]iat each point t ∈ {0, . . . , M}. To eliminate this cost, wehave the client send the polynomial [h]i to each server
i in point-value form. That is, instead of sending eachserver shares of the coefficients of h, the client sends eachserver shares of evaluations of h. In particular, the client
evaluates [h]i at all of the points t ∈ {0, . . . , 2M} and sends
the evaluations [h]i (0), [h]i (1), [h]i (2), . . . , [h]i (2M) to theserver. Now, each server i already has the evaluationsof [h]i at all of the points it needs to complete Step 2 of
the SNIP verification. To complete Step 3, each servermust interpolate [h]i and evaluate [h]i at the point r. We
accomplish this using the same fast interpolation-andevaluation trick described above for [ f ]i and [g]iCircuit optimization In many cases, the servers holdmultiple verification circuits Valid1 , . . . , ValidN and want
to check whether the client’s submission passes all N
checks. To do so, we have the Valid circuits return zero
(instead of one) on success. If W j is the value on thelast output wire of the circuit Valid j , we have the servers
choose random values (r1 , . . . , rN ) ∈ FN and publish theP
sum j r j W j in the last step of the protocol. If any W j , 0,then this sum will be non-zero with high probability andthe servers will reject the client’s submission.