Session J1: Outsourcing

CCS’17, October 30-November 3, 2017, Dallas, TX, USA

Ligero: Lightweight Sublinear Arguments
Without a Trusted Setup
Scott Ames

Carmit Hazay

University of Rochester
sames@cs.rochester.edu

Bar-Ilan University
carmit.hazay@cs.biu.ac.il

Yuval Ishai

Muthuramakrishnan Venkitasubramaniam

Technion and UCLA
yuvali@cs.technion.ac.il

University of Rochester
muthuv@cs.rochester.edu

ABSTRACTa concretely efficient argument protocol for NP whose communication complexity is proportional to the square root of the size ofa circuit verifying the NP witness. Our argument system is in facta zero-knowledge argument of knowledge, and it only requires
the verifier to send public coins to the prover. The latter feature
implies that it can be made non-interactive via the Fiat-Shamir transform [19], yielding an efficient implementation of zero-knowledge
succinct non-interactive arguments of knowledge (zk-SNARKs [11])without a trusted setup.
To put our work in the proper context, we give some relevant
background. The last half decade has seen tremendous progress indesigning and implementing efficient systems for verifiable computation (see [4, 47] for recent surveys). These efforts can be divided
into three broad categories according to the underlying combinatorial machinery.

We design and implement a simple zero-knowledge argument protocol for NP whose communication complexity is proportional to
the square-root of the verification circuit size. The protocol canbe based on any collision-resistant hash function. Alternatively, it
can be made non-interactive in the random oracle model, yielding
concretely efficient zk-SNARKs that do not require a trusted setup
or public-key cryptography.
Our protocol is attractive not only for very large verification
circuits but also for moderately large circuits that arise in applications. For instance, for verifying a SHA-256 preimage in zeroknowledge with 2−40 soundness error, the communication complexity is roughly 44KB (or less than 34KB under a plausible conjecture),
the prover running time is 140 ms, and the verifier running time is
62 ms. This proof is roughly 4 times shorter than a similar proofof ZKB++ (Chase et al., CCS 2017), an optimized variant of ZKBoo(Giacomelli et al., USENIX 2016).
The communication complexity of our protocol is independent of
the circuit structure and depends only on the number of gates. For
2−40 soundness error, the communication becomes smaller than thecircuit size for circuits containing roughly 3 million gates or more.
Our efficiency advantages become even bigger in an amortizedsetting, where several instances need to be proven simultaneously.
Our zero-knowledge protocol is obtained by applying an optimized version of the general transformation of Ishai et al. (STOC
2007) to a variant of the protocol for secure multiparty computation of Damgård and Ishai (Crypto 2006). It can be viewed asa simple zero-knowledge interactive PCP based on “interleaved”
Reed-Solomon codes.

1

Doubly efficient interactive proofs: This line of work, initiatedby Goldwasser, Kalai, and Rothblum [23] (following a rich lineof work on interactive proofs with computationally unbounded
provers [24, 37, 44]), provides sublinear communication, efficiently
verifiable proofs for low-depth polynomial-time computations.1
See [15, 41, 45, 46] and references therein for a survey of works
along this line.
Probabilistically checkable proofs (PCPs) and their interactive variants: Originating from the works of Kilian [36] and Micali [39], recent works [4, 6, 8] have shown how to obtain efficientsublinear arguments for NP from PCPs [1–3]. Classical PCPs havebeen extended to allow additional interaction with the prover, firstin the model of interactive PCP (IPCP) [35] and then in the moregeneral setting of interactive oracle proofs (IOP) [9], also known
as probabilistically checkable interactive proofs (PCIP) [41]. Arguments obtained via PCPs and IOPs have the advantages of not
relying on public-key cryptography, not requiring a trusted setup,and offering conjectured security against quantum attacks. However, current implementations along this line are still quite far fromhaving good concrete efficiency.

INTRODUCTION

Verifying outsourced computations is important for tasks and scenarios when there is an incentive for the party performing thecomputation to report incorrect answers. In this work, we present

Linear PCPs: This line of work, initiated by Ishai, Kushilevitz, andOstrovsky [28] (in the interactive or designated verifier setting) andby Groth [27] (in the non-interactive, public verification setting of
SNARKs) obtains sublinear arguments for NP with preprocessing by

Permission to make digital or hard copies of all or part of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor profit or commercial advantage and that copies bear this notice and the full citationon the first page. Copyrights for components of this work owned by others than ACM
must be honored. Abstracting with credit is permitted. To copy otherwise, or republish,
to post on servers or to redistribute to lists, requires prior specific permission and/or afee. Request permissions from permissions@acm.org.
CCS’17, Oct. 30–Nov. 3, 2017, Dallas, TX, USA.
© 2017 ACM. ISBN 978-1-4503-4946-8/17/10. . . $15.00
DOI: http://dx.doi.org/10.1145/3133956.3134104

1 The GKR technique has been recently extended to the case of NP statements by Zhang

et al. [48]. However, the communication complexity of the resulting arguments still
grows with the verification circuit depth, and moreover their efficient instantiation
requires the use of public-key cryptography.

2087

Session J1: Outsourcing

CCS’17, October 30-November 3, 2017, Dallas, TX, USA

combining linear PCPs with homomorphic public-key cryptography.
In a linear PCP the verifier can obtain a small number of linear
combinations of a proof vector. Linear PCPs are simpler to constructthan classical PCPs and have served as the basis for some of thefirst implementations of verifiable computation protocols [43]. Avery efficient construction of linear PCPs for NP that serves as thebasis for most current SNARK implementations, including the ones
used in zerocash [7], was given by Gennaro, Gentry, Parno, andRaykova in [21]. (The view of these SNARKs as being based onlinear PCPs is due to Bitansky et al. [12] and Setty et al. [42].) Two
practical disadvantages of the protocols along this line are that they
are quite slow on the prover side (due to a heavy use of public-key
cryptography), and their soundness in the non-interactive setting
crucially relies on the existence of a long and “structured” common
reference string that needs to either be generated by a trusted party
or by an expensive distributed protocol.
Our goal in this work is to combine the best features of previous
approaches to the extent possible:
Obtain a simple, concretely efficient, sublinear communication zero-knowledge argument system for
NP, without any setup, complex PCP machinery, or
expensive public-key operations.
As discussed above, all prior works fall short of meeting theabove goal on one or more counts.

1.1

ZKIPCP by applying a more efficient variant of the IKOS transformation in the spirit of the IPS compiler [32]. In a nutshell, the maindifference with respect to the original IKOS transformation is that
we restrict the topology of the MPC network in a way that leads
to a better trade-off between soundness error and communication
complexity.
A key feature of the underlying MPC protocol is that its total
communication complexity is roughly equal to the size of the circuit
being evaluated, independently of the number of parties. Letting
the number of parties be the square root of the circuit size, the communication per party is also roughly the square root of the circuit
size. This translates into a ZKIPCP with similar parameters. See
Section 4 for a self-contained presentation of the ZKIPCP obtained
via the above approach.
The recent work of Giacomelli, Madsen and Orlandi [22] andits improvement due to Chase et al. [13] already demonstrated
that the IKOS transformation can lead to concretely efficient zeroknowledge arguments, but where the communication is bigger thanthe verification circuit size. In the present work, we obtain a sublinear variant of this result by modifying both the IKOS transformationand the underlying MPC machinery.
To summarize, using the above approach we obtain a simple
proof of the following theorem with good concrete efficiency:

Our Results

The main result of this work is a zero-knowledge argument protocol
for NP with the following features.
• It is sublinear, in the sense that the asymptotic communication complexity is roughly the square root of the verification circuit size.
• It is simple to describe and analyze in a self-contained way.
• It only employs symmetric-key primitives (collision-resistanthash-functions) in a black-box way. Moreover, the protocol
can be made non-interactive in the random oracle modelby using the Fiat-Shamir transform [19], thus providing alight-weight implementation of (publicly verifiable) zeroknowledge SNARKs.
• It does not require any trusted setup, even in the noninteractive case.
• It is concretely efficient. We demonstrate its concrete efficiency via an implementation.
• In the multi-instance setting where many instances forthe same NP verification circuit are required, we obtain
improved amortized communication complexity with sublinear verification time.
Our protocol can be seen as a light-weight instance of the second
category of protocols discussed above. However, instead of directly
applying techniques from the PCP literature, we combine efficient
protocols for secure multiparty computation (MPC) with a variantof the general transformation of Ishai, Kushilevitz, Ostrovsky, andSahai (IKOS) [29] that transforms such MPC protocols to zeroknowledge interactive PCPs (ZKIPCP).
More concretely, we instantiate the MPC component with an
optimized variant of the protocol of Damgård and Ishai [16] (similar
to the one described in Appendix C of [33]) and transform it into a

2088

Theorem 1.1 (Informal). Assume the existence of collision-resistanthash-functions. Then there is a public-coin zero-knowledge argument
for provingpthe satisfiability of a circuit C with communication complexity Õ( |C|).
Concrete efficiency. We now give more detailed information about
the concrete efficiency of our implementation. The following numbers apply either to interactive zero-knowledge protocols based oncollision-resistant hash functions or to non-interactive zk-SNARKs
in the random oracle model obtained via the Fiat-Shamir transform.
We refer the reader to Section 6 for more details and give only a
few representative figures below.
The communication complexity of proving the satisfiability ofan arithmetic circuit with s > 30000 gates over a finite field F of√
size |F| ≥ 2128 with soundness error 2−40 consists of roughly 95 s√
field elements (or 70 s elements under Conjecture 4.1). For the case√√of 2−80 error, the communication is roughly 140 s (or 120 s under
Conjecture 4.1).
In the case of Boolean circuits, the communication complexity
becomes smaller than the circuit size for circuits with more thanroughly 3 million gates. One concrete benchmark that has been usedin prior works is verifying a SHA-256 preimage in zero-knowledge.
For this benchmark, the communication complexity of our protocol
with 2−40 soundness error is roughly 44KB (or less than 34KB
under a Conjecture 4.1), the prover running time is 140 ms, andthe verifier running time is 62 ms. This is roughly 4 times lesscommunication than a similar proof of ZKB++ [13], an optimized
variant of ZKBoo [22]. Requiring 2−80 soundness error doubles thecommunication (as in [13, 22]).
Our protocol easily extends to a multi-instance setting to provide additional benefits. In this setting, we can handle N instancesof a circuit of size s with soundness error 2−κ at an amortizedcommunication cost per instance smaller than s when N = Ω(κ 2 ).

Session J1: Outsourcing

CCS’17, October 30-November 3, 2017, Dallas, TX, USA

Moreover, the amortized verification time in the multi-instancesetting is sublinear, involving a total of O(s log s + N log N ) field
operations. Finally, the prover’s running time grows linearly with
the number of instances but still remains practically feasible forreasonable number of instances. For the SHA-256 circuit, we showthat the amortized communication over 4096 instances is 2KB withamortized prover time of 151 ms and verification time of 500 µs.
This amortization is relevant to natural applications, e.g., in thecontext of cryptocurrencies [7, 18].

final outcome (i.e., the root) to the value given at the commitment
phase.
The binding property of a Merkle hash tree is due to collisionresistance. Intuitively, this says that it is infeasible to efficiently finda pair (x, x 0 ) so that H (x) = H (x 0 ), where H ← Hκ for sufficiently
large κ. In fact, one can show that collision-resistance of {Hκ }κ ∈N
carries over to the Merkle hashing. Formally, we say that a family ofhash functions {Hκ }κ is collision-resistant if for any PPT adversary
A the following experiment outputs 1 with probability negl(κ): (i)A hash function H is sampled from Hκ ; (ii) The adversary A isgiven H and outputs x, x 0 ; (iii) The experiment outputs 1 if andonly if x , x 0 and H (x) = H (x 0 ).
In the random oracle model, Merkle tree can be computed byreplacing the function H with a random oracle ρ where statisticalbinding follows due to the hardness of finding a collision in thismodel. We denote this algorithm by CommitRO.
M

Related work. In a concurrent and independent work [5], BenSasson et al. use different techniques to construct concretely efficient IOPs that imply “transparent” proof systems, referred toas zk-STARKs, of the same type we obtain here. These zk-STARK
constructions significantly improve over the previous ones from [4].
A preliminary comparison with the concrete efficiency of our construction suggests that our construction is generally more attractive
in terms of prover computation time and also in terms of proof
size for smaller circuits (say, of size comparable to a few SHA-256
circuits), whereas the construction from [5] is more attractive interms of verifier computation time and proof size for larger circuits.
We leave a more thorough comparison between the two approaches
for future work.

2

2.2

We denote by hA(w), B(z)i(x) the random variable representing
the (local) output of machine B when interacting with machine A
on common input x, when the random-input to each machine isuniformly and independently chosen, and A (resp., B) has auxiliary
input w (resp., z).
Definition 2.1 (Interactive argument system). A pair of PPTinteractive machines hP, Vi is called an interactive proof system
for a language L if there exists a negligible function negl such thatthe following two conditions hold:(1) Completeness: For every x ∈ L there exists a string w suchthat for every z ∈ {0, 1}∗ ,PRELIMINARIES

Basic notations. We denote the security parameter by κ. We saythat a function µ : N → N is negligible if for every positive polyno1 . We
mial p(·) and all sufficiently large κ’s it holds that µ(κ) < p(κ)
use the abbreviation PPT to denote probabilistic polynomial-timeand denote by [n] the set of elements {1, . . . , n} for some n ∈ N.
For an NP relation R, we denote by R x the set of witnesses of x
and by L R its associated language. That is, R x = {w | (x, w) ∈ R}
and L R = {x | ∃ w s.t . (x, w) ∈ R}.

2.1

Zero-Knowledge Arguments

Pr[hP(w), V(z)i(x) = 1] ≥ 1 − negl(|x |).
(2) Soundness: For every x < L, every interactive PPT machineP ∗ , and every w, z ∈ {0, 1}∗
Pr[hP ∗ (w), V(z)i(x) = 1] ≤ negl(|x |).

Collision-Resistant Hashing and Merkle
Trees

Definition 2.2 (Zero-knowledge). Let hP, Vi be an interactive
proof system for some language L. We say that hP, Vi is computational zero-knowledge with respect to an auxiliary input if forevery PPT interactive machine V ∗ there exists a PPT algorithm S,
running in time polynomial in the length of its first input, such that0

Let {Hκ }κ ∈N = {H : {0, 1}p(κ) → {0, 1}p (κ) }κ be a family of hashfunctions, where p(·) and p 0 (·) are polynomials so that p 0 (κ) ≤ p(κ)
for sufficiently large κ ∈ N. For a hash function H ← Hκ a Merkle
hash tree [38] is a data structure that allows to commit to ` = 2dmessages by a single hash value h such that revealing any message
requires only to reveal O(d) hash values.
A Merkle hash tree is represented by a binary tree of depth
d where the ` messages m 1 , . . . , m ` are assigned to the leavesof the tree; the values assigned to the internal nodes are computed using the underlying hash function H that is applied on
the values assigned to the children, whereas the value h that commits to m 1 , . . . , m ` is assigned to the root of the tree. To open
the commitment to a message mi , one reveals mi together withall the values assigned to nodes on the path from the root to mi ,and the values assigned to the siblings of these nodes. We denotethe algorithm of committing to ` messages m 1 , . . . , m ` by h :=CommitM (m 1 , . . . , m ` ) and the opening of mi by (mi , path(i)) :=OpenM (h, i). Verifying the opening of mi is carried out by essentially recomputing the entire path bottom-up and comparing thec{hP(w), V ∗ (z)i(x)}x ∈ L,w ∈R x ,z ∈ {0,1}∗ ≈ {hSi(x, z)}x ∈ L,z ∈ {0,1}∗(when the distinguishing gap is considered as a function of |x |). Specifically, the left term denote the output of V ∗ after it interacts with P
on common input x whereas, the right term denote the output of S
on x.
Our zero-knowledge protocols in fact satisfy the additional proofof knowledge property, which is important for some applications.
See full version for more details.

2.3Interactive PCPs

An interactive PCP [35] (IPCP) is a combination of a traditional PCP
with an interactive proof. An IPCP is a special case of interactive
oracle proofs (IOP) [9] (also known as probabilistically checkableinteractive proofs [41]). We will be interested in zero-knowledge
interactive PCPs [25] in which the verifier reads a small number of2089

Session J1: Outsourcing

CCS’17, October 30-November 3, 2017, Dallas, TX, USA

bits from the PCP and exchanges a small number of bits with theprover P. We formalize this notion below.

only way the servers may communicate with each other is via abroadcast. In our actual MPC protocol, the servers will never utilize
such a broadcast. Nevertheless, our transformation from MPC to ZK
can be easily extended to allow for the servers to invoke a broadcast.
For simplicity, in our actual transformation, we will restrict theservers to not communicate with each other at all.
We consider the security of protocols in both the honest-butcurious (passive) and the malicious (active) models. In the former
model, one may break the security requirements into the following
correctness and privacy requirements.

Definition 2.3 (Interactive PCP). Let R(x, w) be an NP relation corresponding to an NP language L. An interactive PCP (IPCP)
system for R with parameters (q, l, ϵ) is a pair of PPT interactive
machines hP, Vi with the following properties.
(1) Syntax: On common input x and prover input w, the prover
P computes in time poly(|x |) a bit string π (referred to as
the PCP). The prover P and verifier V then interact, wherethe verifier has oracle access to π .
(2) Completeness: If (x, w) ∈ R thenDefinition 3.1 (Correctness). We say that Π realizes a deterministic n + 1-party functionality (x, r 1 , . . . , r n ) with perfect (resp.,
statistical) correctness if for all inputs (x, r 1 , . . . , r n ), the probability
that the output of some player is different from the output of f is 0
(resp., negligible in κ), where the probability is over the independent
choices of the random inputs r 1 , . . . , r n .

π

Pr[(P(x, w), V (x)) = 1] = 1.
(3) Soundness: For every x < L, every (unbounded) interactive
machine P ∗ and every π̃ ∈ {0, 1}∗ ,Pr [(P ∗ , V π̃ (x)) = 1] ≤ ϵ(|x |).

Definition 3.2 (tp -Privacy). Let 1 ≤ tp < n. We say that Π
realizes f with perfect tp -privacy if there is a PPT simulator S suchthat for any inputs (x, r 1 , . . . , r n ) and every set of corrupted players
T ⊂ [n], where |T | ≤ tp , the joint view ViewT (x, r 1 , . . . , r n ) of
players in T is distributed identically to S(T , x, {r i }i ∈T , fT (x, r 1 ,. . . , r n )).

(4) Complexity: In the interaction (P(x, w), V π (x)) at mostl(|x |) bits are communicated and V reads at most q(|x |) bitsof π .
A public-coin IPCP is one where every message sent by the verifier
simply consists of fresh random bits.
The notion of IPCP can be extended to additionally guarantee
zero-knowledge. Our zero-knowledge variants of IPCP will achieve
perfect zero-knowledge against honest verifiers. We present thedefinition of zero-knowledge IPCP next.

With respect to our MPC model defined above, we consider
privacy in the presence of a static passive adversary that corrupts
the receiver R and at most tp servers.
In the malicious model, in which corrupted players may behave
arbitrarily, security cannot be generally broken into correctness
and privacy as above. However, for our purposes we only need theprotocols to satisfy a weaker notion of security in the malicious
model that is implied by the standard general definition. Specifically,
it suffices that Π be tp -private as above, and moreover it should
satisfy the following notion of correctness in the malicious model.

Definition 2.4 (Zero-knowledge IPCP). Let hP, Vi be an interactive PCP for R. We say that hP, Vi is an (honest verifier, perfect)
zero-knowledge IPCP (or ZKIPCP for short) if there exists an expected
polynomial time algorithm S, such that for any (x, w) ∈ R, the output of S(x) is distributed identically to the view of V in the interaction(P(x, w), V π (x)).

Definition 3.3 (Statistical tr -Robustness). We say that Π
realizes f with statistical tr -robustness if it is perfectly correct in thepresence of a honest-but-curious adversary as in Definition 3.1, andfurthermore for any (unbounded) active adversary that adaptively
corrupts a setT of at most tr players, and for any inputs (x, r 1 , . . . , r n ),the following robustness property holds. If there is no (r 1 , . . . , r n ) suchthat f (x, r 1 , . . . , r n ) = 1, then the probability that R outputs 1 in an
execution of Π in which the inputs of the honest players are consistent
with (x, r 1 , . . . , r n ) is negligible in κ where κ is a statistical parameterthat the protocol Π receives as input.

3 FROM MPC TO ZKIPCP
3.1 Our MPC Model
As mentioned in the introduction, the efficiency of our constructions
can be distilled to identifying the right MPC model and designingan efficient protocol in this model. In this regards we deviate fromthe original work of [29] which provided a general transformationfrom any honest majority MPC protocol that can compute arbitrary
functionalities. In particular, our model is more in line with thewatchlist mechanism (a-la [32]). We begin with the description of
the MPC model and the protocol specifications that we will needto design our zero-knowledge protocol. In Section 4, we use such
MPC protocols based on the works [14, 16, 32, 33].
In our model, we consider a sender client S, n servers P1 , . . . , Pn
and a receiver client R. The sender has input x and a witness w withrespect to some NP relation R. The receiver and the servers do notreceive any input, where the servers obtain random shares from thesender and evaluate the computed circuit. Upon receiving (x, w)
from the sender, the functionality computes R(x, w) and forwards
the result to the receiver R. We consider the specific network where
we restrict the communication to a single message between S andthe servers at the beginning of the protocol and a single message
from the servers to the receiver R at the end of the protocol. The

Our main theorems about our two-party ZK protocol are provenin the presence of a static active adversary, that corrupts the proverat the onset of the execution. Nevertheless, our proof relies on
the security of the underlying MPC protocol (utilized in the MPCin-the-head paradigm) being robust against an active adversarythat adaptively corrupts a subset of the servers in the underlying
MPC protocol. Concretely, with respect to our MPC model defined
above, we consider robustness in the presence of an adaptive active
adversary that corrupts the sender S and at most tr servers.
Finally, when used in the MPC-in-the-head paradigm, we need
the notion of consistent views between servers and the receiverthat we define below.

2090

Session J1: Outsourcing

CCS’17, October 30-November 3, 2017, Dallas, TX, USA

and an additional input w received from S, the functionality delivers
R(x, w) to R. Suppose that Π is a two-phase protocol in the MPC model
specified in Section 3.1 that realizes f with statistical tr -robustness (inthe malicious model) and perfect tp -privacy (in the honest-but-curious
model), where tr < d n2 e − 1. Then protocol ΠZKIPCP described above is tp+ δ (κ)a ZKIPCP for NP relation R, with soundness error 1 − tnr
where δ (κ) is the robustness error of Π.

Definition 3.4 (Consistent views). We say that a pair of views
Vi , Vj are consistent (with respect to the protocol Π and some public
input x) if the outgoing messages implicit in Vi are identical to theincoming messages reported in Vj and vice versa.

3.2

ZKIPCP for NP - The General Case

Next, we provide our compilation from an MPC protocol satisfying
the requirements specified in Section 3.1 to an interactive PCP. We
note that while the transformation presented in this section works
for any MPC in the model as described in the previous section, we
will simplify our MPC model as follows:
Two-phase: The protocol we consider will proceed in two phases:
In Phase 1, the servers receive inputs from the sender andonly perform local computation. After Phase 1, the servers
obtain a public random string r of length l sampled via
a coin-flipping oracle and broadcast to all servers. The
servers use this in Phase 2 for their local computation at
the end of which each server sends a single output message
to the receiver R.
No broadcast: The servers never communicate with each other.
Each server simply receives inputs from the sender at the
beginning of Phase 1, then receives a public random stringin Phase 2, and finally delivers a message to R.
Formally, let L be an NP-language with NP relation R. Let x an
NP statement that is the common input and let w be the private
input of the prover. Our construction Π ZKIPCP proceeds as follows:Let Π be any MPC protocol in our model. We will now design a
ZKIPCP protocol ΠZKIPCP that meets Definition 2.3.

Proof: Our proof follows by establishing completeness, soundness
and zero-knowledge as required in Definitions 2.3-2.4.
Completeness: Completeness follows directly from the correctness of the underlying MPC protocol.
Soundness: Consider a statement x < L R . We will show thatno prover P ∗ can convince V beyond a negligible probability toaccept a false statement. We will argue soundness by following anapproach similar to [29] where we first identify an inconsistency
graph and then invoke the properties of the underlying MPC. Moreprecisely, we consider an inconsistency graph G based on the nviews V1 , . . . , Vn and the view of the receiver R which contains themessages from servers P1 , . . . , Pn to R. Here, the servers and thereceiver correspond to nodes in G and inconsistency between every
pair of nodes is defined as in Definition 3.4. Then there are twocases depending on the graph G:
Case 1: There are more than tr edges in G. In this case, we willargue that with high probability the set of servers opened by theverifier will hit one of these edges. Recall that the view of R isprovided to the verifier. Therefore, for any edge in G between R
and Vi , if the corresponding server Pi falls in Q, then the verifier
rejects. The probability that all tp servers chosen by the verifier tp
misses all inconsistent edges is at most 1 − tnr.

Protocol Π ZKIPCP .
• Input: The prover P and the verifier V share a common input statement x and a circuit description C that realizes R. P
additionally has input w such that R(x, w) = 1.
• Oracle π : The prover runs the MPC protocol Π “in-its-head” asfollows. It picks a random input r S and invokes S on (x, w; r S )and a random input r i for every server Pi . The prover computes
the views of the servers up to the end of Phase 1 in Π, denoted by(V1 , . . . , Vn ), and sets the oracle as the n symbols (V1 , . . . , Vn ).
• The interactive protocol.
(1) V picks a random challenge r of length l and sends it to
the sender.
(2) Upon receiving the challenge r , prover P sends the view V
of R.2(3) V computes the output of R from the view and checks if
R does not abort. It then picks a random subset Q of [n] ofsize tp uniformly at random (with repetitions) from [n], andqueries the oracle on Q.
(4) V obtains from the oracle the views of the servers in Q.
(5) V aborts if the views of the servers are inconsistent withthe view of R. Otherwise, it accepts and halts.
We are now ready to prove the following theorem.

Case 2: There are fewer than tr edges in G. In this case, we willargue that by the statistical tr -robustness of the underlying MPC
protocol Π, the verifier will reject except with probability δ (κ). Moreprecisely, for every cheating strategy P ∗ in the ZK proof we will
demonstrate an adversarial strategy A attacking the underlying
MPC protocol such that the probability with which V accepts afalse statement when interacting with P ∗ on a false statement will
be bounded by the probability that R outputs 1 in an execution of
the underlying MPC protocol with adversary A.
More precisely, consider an adversary A that is participating in
the MPC protocol with n servers, a sender and a receiver. Internally,
A incorporates the code of P ∗ while emulating the roles of theoracle and V. When the protocol begins, P ∗ set the oracle with theviews of the servers as in Phase 1 of Π. These views simply containthe inputs sent to the servers (as all computations are local). Uponobtaining the views of the servers A will corrupt the sender in theexternal MPC execution, and acting as the sender, it will send as
input to server Pi the value that was internally generated by P ∗as the view of that server, namely Vi . Next, recall that in the MPC
protocol the servers receive a random string from the coin-flipping
oracle (in our protocol the verifier picks r as the challenge in Step
1). A will internally forward this string r to P ∗ as the message
provided by the verifier. Next internally, P ∗ will generate the viewof the receiver R from which A computes the inconsistency graph

Theorem 3.5. Let f be the following functionality for a sender S
and n servers P1 , . . . , Pn and receiver R. Given a public statement x
2 As the prover possesses all information about the servers, and the verifier always

receives the broadcast message from each server, these broadcast messages can besent directly from the prover to the verifier.

2091

Session J1: Outsourcing

CCS’17, October 30-November 3, 2017, Dallas, TX, USA

G. Recall that an edge is present between a server Pi and the receiver
R in this graph if the view of Pi is inconsistent with the view of R
and randomness r . Let T1 be the set of the servers of size t ∗ that areconnected to an edge in G. If t ∗ > tr , then A aborts.
Otherwise, A proceeds with the internal execution by selecting
tp indices for the verifier’s challenge, for which the oracle will
reveal the views of these corresponding servers. If V rejects in
the internal execution because any of these views are inconsistent,
then A aborts. Otherwise, A continues with the external execution.
Recall that in Phase 2, each server sends a single message to R. Thenjust before the servers send these messages, A (adaptively) corrupts
the servers in T1 and replaces their (honestly generated) messages
sent to R by what was internally reported in the view of R, namely
the messages sent by P ∗ to the verifier in the proof. Upon sending
the message in Phase 2, let T2 of size t 0∗ be the set of the serversthat are inconsistent with the view o R. If |T1 ∪ T2 | > tr , then A
aborts. Otherwise, A (adaptively) corrupts the servers in t 0∗ andcontinues as above.
It follows from this description that the acceptance conditionof the verifier in the internal emulation with A is identical to the
output of R in the external MPC execution. Since the underlying
MPC protocol is tr -robust and the number of parties corrupted by
A is t ∗ such that |t ∗ | ≤ tr , we have that R outputs 0 except withprobability at most δ (κ).
We conclude that the verifier in the internal emulation by P ∗accepts the proof of a false statement except with probability at
most δ (κ). Next, we observe that the view of the verifier emulated
by A in the internal emulation is identically distributed to the viewof an honest verifier in an interactive with P ∗ . Therefore, we canconclude that an honest verifier accepts a false statement in thiscase with probability at most δ (κ).
Applying a union bound, we conclude that the verifier accepts a tpfalse statement with probability at most 1 − tnr+ δ (κ).

optimized version of the protocol obtained by applying our variantof the general “MPC to ZK” transformation from [30] (see Section 3)
to the honest-majority MPC protocol from [16].
Coding notation. For a code C ⊆ Σn and vector v ∈ Σn , denoteby d(v, C) the minimal distance of v from C, namely the numberof positions in which v differs from the closest codeword in C,
and by ∆(v, C) the set of positions in which v differs from such aclosest codeword (in case of ties, take the lexicographically firstclosest codeword). We further denote by d(V , C) the minimal distance between a vector set V and a code C, namely d(V , C) =minv ∈V {d(v, C)}. Our ZKIPCP protocol uses Reed-Solomon (RS)codes, defined next.
Definition 4.1 (Reed-Solomon Code). For positive integers n, k,finite field F, and a vector η = (η 1 , . . . , ηn ) ∈ Fn of distinct field
elements, the code RSF,n,k,η is the [n, k, n − k + 1] linear code over F
that consists of all n-tuples (p(η 1 ), . . . , p(ηn )) where p is a polynomialof degree < k over F.
At a very high level, our ZKIPCP protocol proves the satisfiabilityof an arithmetic circuit C of size s in the following way. The prover
arranges (a slightly redundant representation of) the s wire values√√of C on a satisfying assignment in an O( s) × O( s) matrix, andencodes each row of this matrix using an RS code. The verifier√challenges the prover to reveal O( s) linear combinations of theentries of the codeword matrix, and checks their consistency witht randomly selected columns of this matrix, where t is a security
parameter. In the following we describe the ZKIPCP construction
in a bottom-up fashion, first addressing the case of IPCP (with nozero-knowledge) and then introduce the modifications required formaking it zero-knowledge.

4.1

We start by describing and analyzing a simple interactive proverassisted protocol for simultaneously testing the membership ofmultiple vectors in a given linear code L. It will be convenient toview m-tuples of codewords in L as codewords in an interleaved
code Lm . We formally define this notion below.

Zero-knowledge: The zero-knowledge property follows from thetp -privacy of the underlying MPC protocol Π. Namely, we constructa simulator S that invokes the simulator for the MPC protocol,
denoted by SΠ . In the simulation SΠ is required to produce the viewof R upon receiving a challenge r and then, upon obtaining the tp
indexes that the verifier requests to open, outputs the views of thesetp servers, where SΠ simulates an adversary A that adaptively
corrupts these servers at the end of the computation.
Definition 4.2 (Interleaved code). Let L ⊂ Fn be an [n, k, d]linear code over F. We let Lm denote the [n, mk, d] (interleaved) codeover Fm whose codewords are all m × n matrices U such that every
row Ui of U satisfies Ui ∈ L. For U ∈ Lm and j ∈ [n], we denote by
U [j] the jth symbol (column) of U .

Communication complexity: The main source of complexity isin revealing the view of R in the third message and revealing theview of the tp servers in the last message. If the maximum size ofthe view of each server Pi for i ∈ tp , is v size , and the size of theview of R is v R , then the total communication complexity from theprover is tp · v size + v R .
We can adjust the parameters of the protocol we use in Section
4 subject to the constraint that v sizev R = O(|C|). To minimize thecommunication complexity, if we set tp · v size and v R to be roughly
equal then we obtain the optimum complexity of our approach.

4

Testing Interleaved Linear Codes

To test the membership of U in Lm , V challenges P to reveal a
random linear combination of the rows Ui , and then checks thatthe revealed codeword is consistent with a randomly selected setof t columns of U .3
Test-Interleaved(F, L[n, k, d], m, t; U )3 This test is implicitly used in the verifiable secret sharing sub-protocol of efficient

MPC protocols from the literature, and in particular in the protocols from [16, 33]
on which we build. Its soundness requires the MPC protocol to be adaptively secure
to accommodate P ’s ability to make the locations of inconsistencies depend on V ’s
random challenge; when the MPC adversary is adaptive, it can potentially corrupt all
parties observing such inconsistencies. Indeed, the compiler from statistically secure
MPC to ZK proofs from [30] relies on the adaptive security of the underlying MPC
protocol.

A DIRECT ZKIPCP CONSTRUCTION

In this section we give a self-contained description of our zeroknowledge interactive PCP protocol. This protocol is a slightly

2092

Session J1: Outsourcing

CCS’17, October 30-November 3, 2017, Dallas, TX, USA• Oracle: A purported Lm -codeword U . Depending on the context,
we may view U either as a matrix in Fm×n in which each row
Ui is a purported L-codeword, or as a sequence of n symbols(U [1], . . . , U [n]), U [j] ∈ Fm .
• Interactive testing:(1) V picks a random linear combinations r ∈ Fm and sends r
to P.
(2) P responds with w = r T U ∈ Fn .
(3) V queries a set Q ⊂ [n] of t random symbols U [j], j ∈ Q.
(4) V accepts iff w ∈ L and w is consistent with UQ and r . ThatÍis, for every j ∈ Q we have m
i=1 r j · Ui, j = w j .
The following lemma follows directly from the linearity of L.

elements of E we get that Prw ∗ ∈R L ∗ [d(w ∗ , L) ≤ e] ≤ (e + 1)/|F| asrequired.

We now prove the soundness of the testing procedure when thegiven oracle is far from Lm .
Theorem 4.3. Let e be a positive integer such that e < d/4. Suppose d(U ∗ , Lm ) > e. Then, for any malicious P strategy, the oracle
U ∗ is rejected by V except with ≤ (1 − e/n)t + (e + 1)/|F| probability.
Proof: Letting w ∗ = r T U ∗ , it follows from Lemma 4.2 that
Pr[V accepts U ∗ ]≤+ Pr[d(w ∗ , L) ≤ e]

Lemma 4.1. If U ∈ Lm and P is honest, then V always accepts.

≤

Our soundness analysis will rely on the following lemma.

≤

Lemma 4.2. Let e be a positive integer such that e < d/4. Supposed(U ∗ , Lm ) > e. Then, for a random w ∗ in the row-span of U ∗ , wehavePr[d(w ∗ , L) ≤ e] ≤ (e + 1)/|F|.

n−e−1t+ (e + 1)/|F|ntt(1 − e/n) + (e + 1)/|F|

as required.

In Appendix A we present a simple generalization of the testingalgorithm that uses σ linear combinations to amplify soundness.
4.1.1 A Tighter Analysis? We conjecture that the requiremente < d/4 in Theorem 4.3 can be relaxed to e < d/3 or possibly evene < d/2 with essentially the same soundness error bound. In fact,
it suffices for this to hold for RS codes. Such a stronger version ofTheorem 4.3 would yield roughly up to 25% improvement in thesize of our ZK arguments. We leave the confirmation (or refutation)of this conjecture to future work. Below we reduce such a stronger
version of Theorem 4.3 to a simple conjecture about the distance ofpoints on an affine line from an RS code.
We start by showing that for any linear code over a sufficiently
large field, when e < d/3 we can restrict the attention to Case 1
from the proof of Lemma 4.2.

Proof: Let L∗ be the row-span of U ∗ . We consider two cases.
Case 1: There exists v ∗ ∈ L∗ such that d(v ∗ , L) > 2e. In this case,we show thatPr [d(w ∗ , L) ≤ e] ≤ 1/|F|.

Pr[V accepts | d(w ∗ , L) > e](1)w ∗ ∈R L ∗Indeed, using a basis for L∗ that includes v ∗ , a random w ∗ ∈ L∗
can be written as αv ∗ + x, where α ∈R F and x is distributed
independently of α. We argue that conditioned on any choice of x,
there can be at most one choice of α such that d(αv ∗ + x, L) ≤ e,which implies (1). This follows by observing that if d(αv ∗ +x 0 , L) ≤ e
and d(α 0v ∗ + x 0 , L) ≤ e for α , α 0 , then by the triangle inequality
we have d((α − α 0 )v ∗ , L) ≤ 2e, contradicting the assumption thatd(v ∗ , L) > 2e.

Lemma 4.3. Let L be an [n, k, d] linear code over F. Let e be apositive integer such that e < d/3 and |F| ≥ e. Suppose d(U ∗ , Lm ) >e. Then, there exists v ∗ ∈ L∗ such that d(v ∗ , L) > e, where L∗ is therow-span of U ∗ .

Case 2: For every v ∗ ∈ L∗ , d(v ∗ , L) ≤ 2e. We show that in this casePrw ∗ ∈R L ∗ [d(w ∗ , L) ≤ e] ≤ (e + 1)/|F|. Let Ui∗ be the i-th row of U ∗and let Ei = ∆(Ui∗ , L). Note that, since 2e < d/2, each Ui∗ can be
written uniquely as Ui∗ = ui + χi where ui ∈ L and χi is nonzero∗ mexactly in its Ei entries. Let E = ∪mi=1 Ei . Since d(U , L ) > e, wehave |E| > e. We show that for each j ∈ E, except with 1/|F|probability over a random choice of w ∗ from L∗ , either j ∈ ∆(w ∗ , L)or d(w ∗ , L) > e, from which the claim will follow.
Suppose j ∈ Ei . As before, we write w ∗ = αUi∗ + x for α ∈R F
and x distributed independently of α. Condition on any possible
choice x 0 of x. Define a bad set

Proof: Assume towards a contradiction that d(v ∗ , L) ≤ e for allv ∗ ∈ L∗ . Suppose v 0∗ ∈ L∗ maximizes the distance from L. Sinced(U ∗ , Lm ) > e, there must be a row Ui∗ such that ∆(Ui∗ , L)\∆(v 0∗ , L) ,∅. Let v 0∗ = u 0 + χ 0 and Ui∗ = ui + χi for u 0 , ui ∈ L and χ0 , χiof weight ≤ e. We argue that there exists α ∈ F such that forv̂ = v 0∗ + αUi∗ we have d(v̂, L) > d(v 0∗ , L), contradicting the choiceof v 0∗ . This follows by a union bound, noting that for any j ∈∆(v 0∗ , L) ∪ ∆(Ui∗ , L) there is at most one choice of α such that v̂ j = 0.
Given Lemma 4.3 it suffices to show that in any affine subspaceof Fn , either all points are e-close to L or almost all are not. This
reduces to showing the same for 1-dimensional spaces. We state an
explicit version of the conjecture for the case of RS codes.

B j = {α : j < ∆(αUi∗ + x 0 , L) ∧ d(αUi∗ + x 0 , L) ≤ e}.
We show that |B j | ≤ 1. Suppose towards contradiction that there are
two distinct α, α 0 ∈ F such that for z = αUi∗ +x 0 and z 0 = α 0Ui∗ +x 0
we have d(z, L) ≤ e, d(z 0, L) ≤ e, j < ∆(z, L), and j < ∆(z 0, L). Sinced > 4e, for any z ∗ in the linear span of z and z 0 we have j < ∆(z ∗ , L).
Since Ui∗ is in this linear span, we have j < ∆(Ui∗ , L), in contradiction
to the assumption that j ∈ Ei .
We have shown that for each j ∈ E, conditioned on every possible
choice of x, either j ∈ ∆(w ∗ , L) or d(w ∗ , L) > e except with 1/|F|probability over the choice of α. It follows that the same holds fora random choice of x. Taking a union bound over the first e + 1

Conjecture 4.1. Let L = RSF,n,k,η be a Reed-Solomon code withminimal distance d = n − k + 1. Let e be a positive integer suchthat e < d/3. Then for every u, v ∈ Fn , defining an affine line
`u,v = {u + αv : α ∈ F}, either (1) for every x ∈ `u,v we haved(x, L) ≤ e, or (2) for at most d points x ∈ `u,v we have d(x, L) ≤ e.
We do not have a counterexample to Conjecture 4.1 even whene < d/2 and even when L is a general linear code. Moreover, even2093

Session J1: Outsourcing

CCS’17, October 30-November 3, 2017, Dallas, TX, USA

if the conjecture holds with a relaxed version of condition (2) (say,where d is replaced by n 2 ), this relaxed version is still almost as
good in the context of the efficiency of our ZKIPCP.
The following conjectured stronger version of Lemma 4.2 follows from Lemma 4.3 by extending Conjecture 4.1 from lines togeneral affine subspaces. This extension follows from the fact that
if a subspace has a point that is far from L, then we can partition
the subspace (minus the point) into lines containing this point. Assuming the conjecture for lines, each line should be almost entirely
far from the code, so the subspace should be almost entirely far
from the code.

To further simplify the description and analysis of the testing algorithm, we assume that U is promised to be e-close to Lm . Our final
IPCP we will run Test-Interleaved to ensure that if the promise
is violated, this is caught with high probability.
Test-Linear-Constraints-IRS(F, L = RSF,n,k,η , m, t, ζ , A, b; U )• Oracle: A purported Lm -codeword U that should encode a message x ∈ Fm` satisfying Ax = b.
• Interactive testing:(1) V picks a random vector r ∈ Fm` and sends r to P.
(2) V and P computer T A = (r 11 , . . . , r 1` , . . . , rm1 , . . . , rm` )Lemma 4.4. Suppose Conjecture 4.1 holds. Let L = RSF,n,k,η bea Reed-Solomon code with minimal distance d = n − k + 1 and e a
positive integer such that e < d/3. Suppose d(U ∗ , Lm ) > e. Then, fora random w ∗ in the row-span of U ∗ , we have

and, for i ∈ [m], let r i (·) be the unique polynomial of degree< ` such that r i (ζc ) = r ic for every c ∈ [`].
(3) P sends the k + ` − 1 coefficients of the polynomial definedÍby q(•) = m
i=1 r i (•) · pi (•), where pi is the polynomial of
degree < k corresponding to row i of U .
(4) V queries a set Q ⊂ [n] of t random symbols U [j], j ∈ Q.
(5) V accepts if the following conditions hold:ÍÍ(a) c ∈[`] q(ζc ) = i ∈[m],c ∈[`] r ic bic .
Í(b) For every j ∈ Q, m
i=1 r i (η j ) · Ui, j = q(η j ).
We will analyze the test under the promise that the (possibly badly
formed) U is close to Lm .
The following lemma easily follows by inspection.

Pr[d(w ∗ , L) ≤ e] ≤ d/|F|.
Lemma 4.4 implies the following conjectured stronger versionof Theorem 4.3.
Theorem 4.4. Suppose Conjecture 4.1 holds. Let e be a positive
integer such that e < d/3. Suppose d(U ∗ , Lm ) > e. Then, for any
malicious P strategy, the oracle U ∗ is rejected by V except with≤ (1 − e/n)t + d/|F| probability.

4.2

Testing Linear Constraints over Interleaved
Reed-Solomon Codes

Lemma 4.5. If U ∈ Lm , U encodes x such that Ax = b, and P ishonest, V always accepts.

In this section we describe an efficient procedure for testing thata message encoded by an interleaved RS code satisfies a given setof linear constraints. This generalizes a procedure from [26, 33]
for testing that such an encoded message satisfies a given set of
replication constraints.
In the following we assign a message in F` to each codeword
in Fn by considering a fixed set of ` evaluation points of the polynomial defined by the codeword. Note that while each codeword
has a unique message assigned to it, several different codewords
can be “decoded” into the same message. However, if the degree ofthe polynomial corresponding to the codeword is restricted to besmaller than `, the encoding becomes unique.

Soundness is argued by the following lemma.
Lemma 4.6. Let e be a positive integer such that e < d/2. Supposethat a (badly formed) oracle U ∗ is e-close to a codeword U ∈ Lm
encoding x ∈ Fm` such that Ax , b. Then, for any malicious P
strategy, U ∗ is rejected by V except with at most ((e +k +`)/n)t +1/|F|probability.
Proof: Let q be the polynomial generated in Step 3 following thehonest P strategy on input U . Since we assume Ax , b, we have
Prr [r T Ax = r T b] = 1/|F|. It follows that except with probability
1/|F| over the choice of r in Step 1, the polynomial q fails to satisfy
Íthe condition in Step 5(a). Indeed, we have c ∈[`] q(ζc ) = (r T A)xÍ
and i ∈[m],c ∈[`] r ic bic = r T b.
Next, we analyze the probability that a malicious P strategy isrejected conditioned on q failing in this way. Let q 0 be the polynomial sent by the prover. If q 0 = q, the V rejects in Step 5(a).
If q 0 , q, then using the fact that q and q 0 are of degree at mostk + ` − 2, we have that the number of indices j ∈ [n] for whichq(η j ) = q 0 (η j ) is at most k + ` − 2. Let Q 0 be the set of indices on
which they agree. Then V rejects in Step 5(b) whenever Q selectedin Step 4 contains an index i < Q 0 ∪ E. This fails to happen with n
probability at most e+k +`−2/ t ≤ ((e + k + `)/n)t . The lemmat
now follows by a union bound.


Definition 4.5 (Encoded message). Let L = RSF,n,k,η be an
RS code and ζ = (ζ 1 , . . . , ζ ` ) be a sequence of distinct elementsof F for ` ≤ k. For u ∈ L we define the message Decζ (u) to be(pu (ζ 1 ), . . . , pu (ζ ` )), where pu is the polynomial (of degree < k) corresponding to u. For U ∈ Lm with rows u 1 , . . . , um ∈ L, we let Decζ (U )be the length-m` vector x = (x 11 , . . . , x 1` , . . . , xm1 , . . . , xm` ) suchthat (x i1 , . . . , x i ` ) = Decζ (u i ) for i ∈ [m]. Finally, when ζ is clear
from the context, we say that U encodes x if x = Decζ (U ).
We now describe a simple testing algorithm for checking that themessage x encoded by U satisfies a given system of linear equations
Ax = b, for A ∈ Fm`×m` and b ∈ Fm` . (We will always apply thistest with a sparse matrix A containing O(m`) nonzero entries.) The
test simply picks a random linear combination r ∈ Fm` and checks
that (r T A)x = r T b. Note that if Ax , b, the test will only passwith 1/|F| probability. To make the test sublinear, we let the prover
provide a polynomial encoding (r T A)x and check its consistency
with r T b and with U on t randomly chosen symbols.

4.3

Testing Quadratic Constraints over
Interleaved Reed-Solomon Codes

In this section we describe a simple test for verifying that vectors
x, y, z ∈ Fm` , encoded by U x , U y , U z ∈ Lm respectively, satisfy the2094Session J1: Outsourcing

CCS’17, October 30-November 3, 2017, Dallas, TX, USA

constraints x y + a z = b for some known a, b ∈ Fm` , where
denotes pointwise product. Letting L = RSF,n,k,η , Ua = Enc(a) andUb = Enc(b), this reduces to checking that U x U y +U a U z −U bencodes the all-0 message 0m` in the (interleaved extension of) L̂ =RSF,n,2k −1,η . This could be done using the general membership test
for interleaved linear codes (Test-Interleaved from Section 4.1),
since the set of codewords in L̂ that encode the all-0 message is alinear subcode of L̂. In the following we present this test in a selfcontained way, exploiting the promise that U x , U y , U z are close to
Lm for a tighter analysis.

are of degree at most 2k − 2, we have that the number of indicesj ∈ [n] for which p0 (η j ) = p00 (η j ) is at most 2k − 2. Let Q 0 be theset of indices on which p0 and p00 agree. Then V rejects in Step5(b) whenever Q selected in Step 4 contains an index i < Q 0 ∪ E,
where E = ∆(U ∗ , L3m ). This fails to happen with probability at−2 n / t ≤ ((e + 2k)/n)t . The lemma now follows by amost e+2ktunion bound.


4.4

Test-Quadratic-Constraints-IRS(F, L = RSF,n,k,η , m, t, ζ , a, b; U x ,Uy,U z)• Oracle: Purported Lm -codewords U x , U y , U z that should encode messages x, y, z ∈ Fm` satisfying x y + a z = b.
• Interactive testing:(1) Let U a = Encζ (a) and U b = Encζ (b).
(2) V picks a random linear combinations r ∈ Fm and sends r
to P.
(3) P sends the 2k − 1 coefficients of the polynomial p0 definedÍyxaby p0 (•) = m
i=1 r i ·pi (•), where pi (•) = pi (•)·pi (•)+pi (•)·
y
x
z
z
b
pi (•) − pi (•), and where pi , pi , pi are the polynomials ofdegree < k corresponding to row i of U x , U y , U z , and pia , pib
are the polynomials of degree < ` corresponding to row iof U a , U b .
(4) V picks a random index set Q ⊂ [n] of size t, and queries
U x [j], U y [j], U z [j], j ∈ Q.
(5) V accepts if the following conditions hold:(a) p0 (ζc ) = 0 for every c ∈ [`].
(b) For every j ∈ Q, it holds that
m
h
i
Õ
y
r i · Ui,x j · Ui, j + Ui,aj · Ui,z j − Ui,b j = p0 (η j ).
i=1

satisfying x

y +a

In this section, we provide our IPCP for arithmetic circuits. Fix
a large finite field F. Let C : Fni → F be an arithmetic circuit.
Without loss of generality, we will assume that the circuit contains
only ADD and MULTIPLY gates with fan-in two. We show how a
prover can convince a verifier that C(w) = 1.
Protocol IPCP(C, F).
• Input: The prover P and the verifier V share a common input arithmetic circuit C : Fni → F and input statement x. P
additionally has input α = (α 1 , . . . , α ni ) such that C(α) = 1.
• Oracle π : Let m, ` be integers such that m · ` > ni + s where s isthe number of gates in the circuit. Then P generates an extended
witness w ∈ Fm` where the first ni + s entries of w are(α 1 , . . . , α ni , β 1 , . . . , βs )where βi is the output of the i t h gate when evaluating C(α).
P defines a system of constraints that contains the following
constraint for every multiplication gate д in the circuit C
β a · βb − β c = 0
and for every addition gate, the constraint
β a + βb − β c = 0
where βa and βb are the input values to the gate д and βc isthe output value in the extended witness. For the output gate
we include the constraint βa + βb − 1 = 1 if the final gate is anaddition gate, and βa · βb − 1 = 0 if it is a multiplication gate. P
constructs vectors x, y and z in Fm` where the j t h entry of x, y
and z contains the values βa , βb , and βc corresponding to thej t h multiplication gate in w. P and V construct matrices Px , Py
and Pz in Fm`×m` such that

The following lemma follows again directly from the description.
Lemma 4.7. If U x , U y , U z

IPCP for Arithmetic Circuits∈ Lm encode vectors x, y, z ∈ Fm`

z = b and P is honest, V always accepts.

Soundness is argued by the following lemma.
Lemma 4.8. Let e be a positive integer such that e < d/2. Let
U x ∗ , U y∗ , U z∗ be badly formed oracles and let U ∗ ∈ F3m×n be thematrix obtained by vertically juxtaposing the corresponding m × n
matrices. Suppose d(U ∗ , L3m ) ≤ e, and let U x , U y , U z , respectively,
be the (unique) codewords in Lm that are closest to U x ∗ , U y∗ , U z∗ .
Suppose U x , U y , U z encode x, y, z such that x y + a z , b. Then,for any malicious P strategy, (U x ∗ , U y∗ , U z∗ ) is rejected by V except
with at most 1/|F| + ((e + 2k)/n)t probability.

x = Px w, y = Py w, z = Pz w.
Finally, it constructs matrix Padd ∈ Fm`×m` such that the j t hposition of Paddw equals βa + βb − βc where βa , βb , and βc correspond to the j t h addition gate of the circuit in w. Let U w , U x , U y , U z ∈Lm respectively encode w, x, y, z where L = RSF,n,k,η . P sets
the oracle π as U ∈ L4m which is set as the vertical juxtapositionof the following four matrices U w , U x , U y , U z ∈ Lm .
• Notation: We denote by (−1)m` (respectively, 0m` ) the vector
in Fm` whose entries are all equal to −1 (respectively, equal to0). We further denote by In , the n × n identity matrix.
• The interactive protocol:
V and P run the following tests.
(1) // Test if U is e-close to a code in L4m
Test-Interleaved(F, L, 4m, t; U )Proof: Let p0 be the polynomial generated in Step 3 following thehonest P strategy on U x , U y , U z . Since x, y, z do not satisfy theconstraints, except with probability 1/|F| over the choice of r in
Step 2, the polynomial p0 fails to satisfy the condition in Step 5(a).
ÍIndeed, we have p0 (•) = m
i=1 r i · pi (•) and there must exists an iand ζc such that pi (ζc ) , 0. Next, we analyze the probability that amalicious P strategy is rejected conditioned on p0 failing in thisway.
Let p00 be the polynomial sent by the prover. If p00 = p0 , V
rejects in Step 5(a). If p00 , p0 , then using the fact that p0 and p00

2095

Session J1: Outsourcing

CCS’17, October 30-November 3, 2017, Dallas, TX, USA(2) // Test if addition gates are correct.
Theorem 4.6. Fix parameters n, m, `, k, t, e such that e < (n−k)/4.
Test-Linear-Constraints-IRS
Let C : Fni → F be an arithmetic circuit of size s, where |F| ≥ n and(F, L, m, t, ζ , Padd , 0m` ; U w )m · ` > ni + s. Then protocol IPCP(C, F) satisfies the following:(3) // Test if multiplication gates are correct.
• Completeness: If α is such that C(α) = 1 and oracle π is
– Test-Linear-Constraints-IRS x 
generated honestly as described in the protocol, thenU
F, L, 2m, t, ζ , Im` | − Px , 02m` ; w
Pr[(P(C, w), V π (C)) = 1] = 1.
U
• Soundness: If there is no α is such that C(α) = 1, then for– Test-Linear-Constraints-IRS  2m` U y
every (unbounded) prover strategy P ∗ and every π̃ ∈ F4mn ,F, L, 2m, t, ζ , Im` | − Py , 0; w
Pr [(P ∗ , V π̃ (C)) = 1] ≤ (e + 6)/|F| + (1 − e/n)t + 5((e +U– Test-Linear-Constraints-IRS2k)/n)t .
  2m` U a
• Complexity: The number of field operations performed isF, L, 2m, t, ζ , Im` | − Pz , 0; wUpoly(|C|, n). The number of field elements communicated by– Test-Quadratic-Constraints-IRS
P to V is n + 4 · (k + ` − 1) + 2 · k − 1 whereas V reads t(F, L, m, t, ζ , (−1)m` , 0m` ; U x , U y , U z )symbols from F4m .
Since all the tests open the same number of columns t in Uw , Ux , Uy , Uz ,the V will simply open t columns of U . V rejects if it rejects in
The first term in the communication cost is the communication
any of the tests above.
incurred by the test-interleaved protocol, the second term is due tothe four linear-constraints tests and the final term results from our
The completeness of our IPCP follows from the following lemma.
quadratic-constraint test.
Lemma 4.9. If U w , U x , U y , U z ∈ Lm encode vectors w, x, y, z ∈We remark here that we can improve the communication of theFm` satisfying
protocol by letting s only count the number of multiplication gatesby incorporating the linear constraints resulting from the addition
x = Px w, y = Py w, z = Pz w, x y+(−1)m` z = 0m` , Paddw = 0m`
gates into the linear constraints used to define the vectors x, y andand P is honest, V always accepts.
z.
The proof follows directly from Lemmas 4.1, 4.5 and 4.7. Next,
soundness is argued by the following lemma.
4.5 IPCP for Boolean Circuits
Lemma 4.10. Let e be a positive integer such that e < d/4 andsuppose that there exists no α such that C(α) = 1. Then, for any
maliciously formed oracle Ub and any malicious prover strategy, theverifier rejects except with at most (e + 6)/|F| + (1 − e/n)t + 5((e +2k)/n)t probability.
Proof: On a high-level, soundness will essentially follow by thesoundness of the individual tests and the overall soundness error
follows by a direct application of a union bound over the soundnessof these tests. In more detail, let U be the vertical juxtaposition of
U w ∗ , U x ∗ , U y∗ , U z∗ . Then we argue soundness by considering thefollowing cases and applying a union bound:
Case d(U , L4m ) > e: Since e < d/4, we can conclude from Lemma 4.2that the verifier rejects in Test-Interleaved executed in
Step 1 except with probability (1 − e/n)t + (e + 1)/|F|.
Case d(U , L4m ) ≤ e: Next, let U w , U x , U y , U z ∈ Lm be the codesthat are respectively close to U w ∗ , U x ∗ , U y∗ , U z∗ and encode the messages w, x, y, z. Recall that there exists now, x, y, z that satisfy all the following constraints:
x = Px w, y = Py w, z = Pz w,
x y + (-1)m` z = 0m` and Paddw = 0m` .
Then we can conclude from Lemmas 4.6 and 4.8 by applying a union bound on the corresponding tests that theverifier rejects except with probability:
5/|F| + 4 · ((e + k + `)/n)t + ((e + 2k)/n)t< 5 · 1/|F| + ((e + 2k)/n)t .

The following theorem follows from the construction describedabove and the preceding Lemmas.

2096

In order to obtain the benefits in soundness from running our IPCP
over a large field F, we show how we can prove the validity of a
Boolean circuit C : {0, 1}ni → {0, 1} by encoding the witness inany larger field F. First, in the witness, the prover will map the
Boolean 0 to the additive identity ϵ0 in F and 1 to the multiplicative
identity ϵ1 in F. Now, we can enforce that each element in thewitness is a 0 or 1, by introducing a quadratic constraint β 2 − β = 0.
Given that binary constraints are already enforced, next, we
proceed to demonstrating how we incorporate the constraints from
XOR and ADD gates.
In fact, we will show all gate constraints can be expressed asa linear relation on the witness bits. Let x be a column vector
consisting of the witness string to the evaluation of the circuit. We
will construct a matrix A and a column vector w such that if w isbinary and is a valid witness then the elements of Aw will all be
0, and if w is binary and is not a valid witness then at least one
element of Aw will be nonzero. For each XOR and AND gate in
the circuit we will create a row of the matrix corresponding to theenforcement of that relation in the witness. The vector w besides
including the input bits x, will include one additional bit for each
XOR and AND gate in the circuit. We explain the purpose of these
extra bits next.
Given integers b1 and b2 consider the arithmetic constraint b1 +b2 = r 0 + 2 · r 1 over integers. In this constraint, if we enforce thatall values are bits then r 0 is the XOR of b1 and b2 and r 1 is the ANDof b1 and b2 . If in our witness w we want to make sure that b1 XOR
b2 is b3 then we include an auxiliary bit d and enforce the linear
constraint b1 +b2 = b3 +2·d. A similar constraint can be established
for an AND relation analogously. To conclude, we observe that if thevalues have been enforced to be a binary constraint then checking

Session J1: Outsourcing

CCS’17, October 30-November 3, 2017, Dallas, TX, USA

it with r T b. Looking more carefully at our actual protocol, theverifier obtains a polynomial q(•) and checks whether the equalÍ
Í
ity c ∈[`] q(ζc ) = i ∈[m],c ∈[`] r ic bic holds. While the sum itself
does not reveal any additional information beyond what is alreadyknown, namely r T b, the individual evaluations of q, i.e. q(ζc ) themselves may reveal information about the inputs.
To hide this, a simple idea is for P to provide an additional
vector u 0 along with U that encodes a message (γ 1 , . . . , γ ` ) suchÍthat c ∈[`] γc = 0, and append to A constraints that sum the entries
in the message encoded in u 0 and check if it is equal to 0.
However, as before, this will yield less than optimal soundness
guarantee. Instead we take the following approach that provides
the same soundness guarantee as the original (non-affine versionof the) test. In We apply the algorithm Test-Linear-Constraints-IRS
to Lm+1 where L = RSF,n,k,η , with an extended oracle U 0 whose
first m rows contain U and whose last row is u 0 where additionallyÍ
u 0 encodes a message (γ 1 , . . . , γ ` ) such that c ∈[`] γc = 0. LettingÍmq(•) = i=1 r i (•)·pi (•)+r blind (•) be the polynomial obtained by V
where r blind (•) is a polynomial (of degree < k +` −1) corresponding
to u 0 , we can show that the soundness of the resulting scheme willbe the same as for Lemma 4.6. This “affine” variant of Test-LinearConstraints is described and analyzed in the full version.

the arithmetic constraints over integers can be done by checking
the equation modulo a sufficiently large prime (p ≥ 3).
We can also extend this idea to consider more complex gatessuch as addition modulo 232 over 32-bit inputs and outputs. Thiscan be expressed as a linear constraint over the bits. Suppose a =(a 0 , . . . , a 31 ), b = (b0 , . . . , b31 ) and c = (c 0 , . . . , c 31 ) are the input
and output bits, the constraint a + b = c mod 232 can be expressed
as
31
31
31
Õ
Õ
Õ
2i · ai +2i · bi = 232 · d +2i · c i
i=0

i=0

i=0

where d is an auxiliary input bit and all values are enforced to be
bits. However, this will require F with characteristic p > 233 .

4.6

Achieving Zero-Knowledge

Note first that the verifier obtains two types of information in
two different building blocks of the IPCP. First, it obtains linear
combinations of codewords in a linear code L. Second, it probes asmall number of symbols from each codeword. Since codewords
are used to encode the NP witness, both types of information givethe verifier partial information about the NP witness, and thus thebasic IPCP we described is not zero-knowledge.
Fortunately, making the IPCP zero-knowledge only requires introducing small modifications to the construction and analysis. The
second type of “local” information about codewords is made harmless by making the encoding randomized, so that probing just a
few symbols in each codeword reveals no information about theencoded message. The high level idea for making the first typeof information harmless is to use an additional random codeword
for blinding the linear combination of codewords revealed to theverifier. However, this needs to be done in a way that does not compromise soundness. Below we describe the modifications required
for each of the IPCP ingredients.

4.6.3 ZK Testing of Quadratic Constraints over Interleaved ReedSolomon Codes. We modify the quadratic constraint testing procedure in the same way as we modified the linear constraint testing.
Concretely, we apply the algorithm Test-Quadratic-Constraint
to L3m+1 where L = RSF,n,k,η , with an extended oracle U 0 whose
first 3m rows contain U x , U y , U z and whose last row is u 0 whereÍ
additionally u 0 encodes a message 0` . Letting p0 (•) = m
i=1 r i ·pi (•) + r blind (•) be the polynomial obtained by V where r blind (•) isa polynomial (of degree < 2k − 1) corresponding to u 0 , we can showthat the soundness of the resulting scheme will be the same as forLemma 4.8. This “affine” variant of Test-Quadratic-Constraints
is described and analyzed in the full version.

4.6.1 ZK Testing of Interleaved Linear Codes. Recall that in theverification algorithm Test-Interleaved from Section 4.1, V obtains a linear combination of the form w = r T U , where U ∈ Fm×n
is a matrix whose rows should be codewords in L. A natural approach for making this linear combination hide U is by allowing
the prover to add to the rows of U an additional random codeword
u 0 that is used for blinding.
A simple implementation of this idea that provides a slightly
inferior soundness guarantee is the following. Apply the algorithm
Test-Interleaved to Lm+1 , with an extended oracle U 0 whose firstm rows contain U and whose last row is u 0 . Letting w 0 = r T U +r 0u 0
be the random linear combination obtained by V, the test fails to be
zero-knowledge when r 0 = 0, which occurs with 1/|F| probability.
Alternatively, settling for a slightly worse soundness guarantee(where e/|F| is replaced by e/(|F| − 1)), one could just let r 0 be arandom nonzero field element, and get perfect zero-knowledge.
It turns out, however, that one could fix r 0 to 1 and still get thesame soundness guarantee about U as in Lemma 4.2 since we canapply the same the decomposition argument. This “affine” variantof Test-Interleaved is described and analyzed in Appendix C.

4.7

The Final ZKIPCPIn this section provide a self contained description of the final
ZKIPCP protocol, combining all of the previous sub-protocols. In
this section, we provide our ZKIPCP for arithmetic circuits over alarge field F. On a high-level, the protocol is essentially the IPCP
construction from Section 4.4 with the exception that we replace
all the tests with the generalized affine version (with repetitions).
Protocol ZKIPCP(C, F).
• Input: The prover P and the verifier V share a common input arithmetic circuit C : Fni → F and input statement x. P
additionally has input α = (α 1 , . . . , α ni ) such that C(α) = 1.
• Oracle π : Let m, ` be integers such that m · ` > ni + s wheres is the number of gates in the circuit. Then P generates anextended witness w ∈ Fm` where the first ni + s entries of w are(α 1 , . . . , α ni , β 1 , . . . , βs ) where βi is the output of the i t h gatewhen evaluating C(α). P constructs vectors x, y and z in Fm`
where the j t h entry of x, y and z contains the values βa , βb , andβc corresponding to the j t h multiplication gate in w. P and V
construct matrices Px , Py and Pz in Fm`×m` such that

4.6.2 ZK Testing of Linear Constraints over Interleaved ReedSolomon Codes. The verification algorithm for the linear constraints
Ax = b samples a random vector r , obtains r T Ax, and comparesx = Px w, y = Py w, z = Pz w.

2097

Session J1: Outsourcing

CCS’17, October 30-November 3, 2017, Dallas, TX, USA

Í4m− For every j ∈ Q we have i=1
rh [j] ·Ui, j +uh0 [j] = vh [j].
// Testing Interleaved Reed-Solomon CodesÍaddc ∈[`] qh (ζc ) = 0 and for every j ∈ Q we have
Í
add
add
w
add
uh [j] + m
i=1 r h,i (η j ) · Ui, j = qh (η j ).
// Testing Addition Gates− For every a ∈ {x, y, z},Íac ∈[`] qh (ζc ) = 0 and for every j ∈ Q we have
Í2m
Í
a
a
a
w
uha [j] + m
i=1 r h,i (η j ) · Ui, j + i=m+1 r h,i (η j ) · Ui−m, j =aqh (η j ).
p0,h (ζc ) = 0 for every c ∈ [`] and for every j ∈ Q,
h
i
Í
q
y
x
z
uh0 [j] + m
i=1 (r h )i · Ui, j · Ui, j − Ui, j = p 0,h (η j ).
// Testing Multiplication Gates

Finally, it constructs matrix Padd ∈ Fm`×m` such that the j t h
row of Paddw equals βa +βb −βc where βa , βb , and βc correspondto the j th addition gate of the circuit in w. The prover samples
random codewords U w , U x , U y , U z ∈ Lm where L = RSF,n,k,ηsubject to w = Decζ (U w ), x = Decζ (U x ), y = Decζ (U y ), z =Decζ (U z ) where ζ = (ζ 1 , . . . , ζ ` ) is a sequence of distinct eleyments disjoint from (η 1 , . . . , ηn ). Let uh0 , uhx , uh , uhz , uh0 , uhadd be
auxiliary rows sampled randomly from L for every h ∈ [σ ] whereyeach of uhx , uh , uhz , uhadd encodes an independently sampled ranÍdom ` messages (γ 1 , . . . , γ ` ) subject to c ∈[`] γc = 0 and uh0
encodes 0` . P sets the oracle as U ∈ L4m which is set as thevertical juxtaposition of the matrices U w , U x , U y , U z ∈ Lm .
• The interactive protocol:(1) For every h ∈ [σ ], V picks the following random elements
and sends them to P:− rh ∈ F4m ,// Testing Interleaved Reed-Solomon Codes− rhadd ∈ Fm` ,// Testing Addition Gatesyq− rhx , rh , rhz , ∈ Fm` , rh ∈ Fm .
// Testing Multiplication Gates(2) For every h ∈ [σ ], P responds with− vh = (rh )T U + uh0 ∈ Fn ,// Testing Interleaved Reed-Solomon Codes− Polynomial qhadd (•) of degree < k + ` − 1 whereadd (•) + Ím r add (•) · p (•),
qhadd (•) = r blind,hii=1 h,isuch that pi is the polynomial of degree < k corresponding
add (·) is the unique polynomial of degree
to row i of U w , rh,iThe completeness of our ZKIPCP follows from the next lemma.
Lemma 4.11. If U w , U x , U y , U z ∈ Lm encode vectors w, x, y, z ∈Fm` satisfying
x = Px w, y = Py w, z = Pz w, x y+(−1)m` z = 0m` , Paddw = 0m`
and P is honest, V always accepts.
Next, soundness is argued by the following lemma.
Lemma 4.12. Let e be a positive integer such that e < d/4. Supposethat there exists no α such that C(α) = 1. Then, for any maliciously
formed oracle U ∗ and any malicious prover strategy, the verifier
rejects except with at most (e + 6)/|F| σ + (1 − e/n)t + 5((e + 2k)/n)t
probability.
The proofs of the preceding two lemmas follow analogously tothe proofs of Lemma 4.9 and Lemma 4.10. The next lemma establishes the honest verifier zero-knowledge property.

add (ζ ) = ((r add )T P
< ` such that rh,icadd )ic for every c ∈ [`],hadd (•) is the polynomial of degree < k + ` − 1
and r blind,hcorresponding to uhadd .
// Testing Addition Gatesy− Polynomials qhx (•), qh (•), qhz (•) of degree < k + ` − 1,and p0,h (•) of degree < 2k − 1 where
Í
Í2m
x
x
x
x
qhx (•) = r blind,h(•) + mi=1 r h,i (•) · pi (•) + i=m+1 r h,i (•) ·pi−m (•)),
Í
Í2m
y
y
y
y
x
qh (•) = r blind,h (•) + m
i=1 r h,i (•) · pi (•) + i=m+1 r h,i (•) ·pi−m (•)),
Í
Í2m
z
z
x
z
qhz (•) = r blind,h(•) + mi=1 r h,i (•) · pi (•) + i=m+1 r h,i (•) ·pi−m (•)),


Í
q
y
0
x
z
p0,h (•) = r blind,h(•) + mi=1 r h i · pi (•) · pi (•) − pi (•)
where for a ∈ {x, y, z}, pia is the polynomial of degreea (·) be the unique< k corresponding to row i of U a , rh,iLemma 4.13. If k > ` + t, hP, Vi is an (honest verifier, perfect)
zero-knowledge IPCP.
Proof: To demonstrate zero-knowledge against honest verifier,
we need to provide a simulator S that can given the randomness
provided by the honest verifier V, be able to generate a transcript.
For every h ∈ [σ ], the simulator first generates:• random polynomial qhadd of degree < k + ` − 1 such thatÍaddc ∈[`] qh (ζc ) = 0.
• for a ∈ {x, y, z}, random polynomial qha of degree < k +`−1Ísuch that c ∈[`] qha (ζc ) = 0.
• random polynomial p0,h of degree < 2k − 1 such thatp0,h (ζc ) = 0 for every c ∈ [`].
• random vector vh ∈ Fn .

a (ζ ) = ((r a )T [Ipolynomial of degree < ` such that rh,icm` | −haPa ])ic for every c ∈ [`], r blind,h (•) is the polynomial ofyNext, it samples random elements from F for Uhx [j], Uh [j], Uhz [j], Uhw [j],for every j ∈ Q. Finally, given the random challenges from V, it
0ydegree < k + ` − 1 corresponding to uha and r blind,his thesets uh0 [j], uhadd [j], uhx [j], uh [j], uhz [j], uh0 [j] as follows:0
polynomial of degree < 2k − 1 corresponding uh .
Í4m
• uh0 [j] = i=1
rh [j] · Ui, j − vh [j].
// Testing Multiplication Gates
Í
add
w
add
• uhadd [j] = m(3) V picks a random index set Q ⊂ [n] of size t, and queries
i=1 r h,i (η j ) · Ui, j − qh (η j )
y
Í
x
z
w
a
a Í2m
a
U [j] that is the vertical juxtaposition of Uh [j], Uh [j], Uh [j], Uh [j],• for a ∈ {x, y, z}, uha [j] = m
i=1 r h,i (η j )·Ui, j + i=m+1 r h,i (η j )·ywauhx [j], uh [j], uhz [j], uhadd [j], uh0 [j], j ∈ Q and accepts if the folUi−m, j − qh (η j ).
hiÍlowing conditions hold for every h ∈ [σ ]:yqxz• uh0 [j] = m
i=1 (r h )i · Ui, j · Ui, j − Ui, j − p 0,h (η j ).

2098

Session J1: Outsourcing

CCS’17, October 30-November 3, 2017, Dallas, TX, USA

5.2

Our simulation achieves perfect zero knowledge. This follows fromthe fact that in an honest execution with the prover P, the distribuytion of {Uhx [j], Uh [j], Uhz [j], Uhw [j]}j ∈Q are uniformly distributedyand given that uh0 , uhadd , uhx , uh , uhz , uh0 are uniformly chosen, the
y z
add
x
polynomials qh , qh , qh , qh , p0,h and the vector vh are uniformly
distributed in their respective spaces.

The following theorem follows from the construction describedabove and the preceding Lemmas.
Theorem 4.7. Fix parameters n, m, `, k, t, e such that e < (n−k)/4.
Let C : Fni → F be an arithmetic circuit of size s, where |F| ≥ ` + n,
m · ` > ni + s and k > ` + t. Then protocol ZKIPCP(C, F) satisfies
the following:• Completeness: If α is such that C(α) = 1 and oracle π is
generated honestly as described in the protocol, then
Pr[(P(C, w), V π (C)) = 1] = 1.
• Soundness: If there is no α is such that C(α) = 1, then forevery (unbounded) prover strategy P ∗ and every π̃ ∈ F4mn ,Pr [(P ∗ , V π̃ (x)) = 1] ≤ (e + 6)/|F| σ + (1 − e/n)t + 5((e +2k)/n)t .
• Zero Knowledge: For every adversary verifier V ∗ , there∗
exists a simulator S such that the output of S V (C) is distributed identically to the view of V in the (P(C, w), V π (C)).
• Complexity: The number of field F operations performed ispoly(|C|, n). The number of field elements communicated by
P to V is σ · n + 4 · σ · (k + ` − 1) + σ · (2 · k − 1) whereas
V reads t symbols from F4m+5σ .

5FROM ZKIPCP TO ZKIn this section we describe variants of known transformations from(sublinear) zero-knowledge PCP to (sublinear) zero-knowledge argument. The latter can either be interactive using collision-resistanthash functions, or non-interactive in the random oracle model.

5.1

The Non-Interactive Variant

It is possible to directly compile our previous protocol into a noninteractive protocol using a random oracle, where the verifier’s
messages are emulated by applying the random oracle on the partial
transcript in each round following the Fiat-Shamir transform [19]. A
formal description and analysis of this transformation is presented
in [9] for interactive oracle proofs (IOP) model which generalizes(public-coin) IPCP.
In slight more detail, in this transformation the prover uses therandom oracle to generate the verifier’s messages and complete theexecution (computing its own messages) based on the emulated
verifier’s messages, where instead of using an oracle, the provercommits to its proof and messages using Merkle hash trees. Completeness follows directly. If we start with an IOP that additionallyis zero-knowledge (ZKIPCP in our case), [9] show that this transformation preserves (statistical) zero-knowledge property. Namely,
the resulting protocol can be proved to be zero-knowledge in the
random-oracle model.
In [9], the soundness of the transformed protocol is shown toessentially match the soundness of the original protocol up to an
additive term that roughly depends on the product of q 2 and 2−λwhere q is an upper bound on the number of queries made to therandom oracle by a malicious prover and λ is the output lengthof the random oracle. More precisely, [9] relates the soundness ofthe transformed protocol to the state restoration soundness of theunderlying IPCP and collision-probability of queries to the random
oracle. State-restoration soundness refers to the soundness of the
IOP protocol against cheating prover strategies that may rewind
the verifier back to any previously seen state, where every newcontinuation from a state invokes the next-message function of
the verifier with fresh randomness. In [9], they show that for any(IOP) the state-restoration soundness of an IOP protocol is bounded
by k T(x ) · ϵ(x) and the soundness of the transformed protocol isT2−λ where T bounds the number of queriesk (x ) · ϵ(x) + 3(T + 1) · 2
made by cheating provers to the random oracle, k(x) is the roundcomplexity of the IOP and ϵ(x) is the (standard) soundness of the
IOP.
In the full version, we tighten the analysis presented in [9] forthe particular ZKIPCP constructed in Section 4.7 and show that thesoundness of the transformed protocol is T · ϵ(x) + 3(T 2 + 1) · 2−λwhere ϵ(x) is the soundness of the ZKIPCP, T bounds the numberof queries made by cheating provers to the random oracle and λ isthe output length of the random oracle.

The Interactive Variant

General transformations from (non-interactive) ZKPCP to (interactive) ZK arguments that make a black-box use of collision-resistanthash functions were given in [31, 34]. Here we address the moregeneral case of ZKIPCP, where in addition to the proof oracle there
is additional interaction between the prover and the verifier.
Using the ZKIPCP, an honest-verifier ZK protocol proceeds asfollows. The prover commits to each entry of the proof oracle using
a statistically hiding commitment scheme and then compresses thecommitment using a Merkle hash tree (cf. Section 2.1). Note thatboth steps can be realized by making a black-box use of any family
H of collision-resistant hash functions. The rest of the ZK protocol
mimics the ZKIPCP, where the prover opens the committed values
that correspond to the verifier’s queries. Malicious verifiers canbe handled using standard techniques, as done in [31, 34]. See fullversion for more details.
The communication complexity of the ZK argument includes thecommunication complexity of the ZKIPCP protocol and communication resulting from committing the oracle Π and decommitting
to the queries Q.

5.3

Sublinear Zero-Knowledge Argument

In this section, we describe how to set the parameters of our zeroknowledge argument protocol to obtain communication that is
sublinear in the circuit size. We consider first an arithmetic circuit
over a large field F. Following our transformation, the communication complexity of the zero-knowledge protocol that is compiled
based on our ZKIPCP is[n · σ + 4 · σ · (k + ` − 1) + σ · (2 · k − 1)
+ t · (4 · m + 5 · σ )] · dlog |F|e + t · dlog ne · hwhere h is the output length of the hash-function. For security
parameter κ, when F is large (i.e. |F| > O(2κ )) we can set σ = 1

2099

Session J1: Outsourcing

CCS’17, October 30-November 3, 2017, Dallas, TX, USA

for 2−κ -security. The other terms in the soundness are (1 − e/n)tand ((e + 2k)/n)t where e < d/4 = (n − k)/4 and k = t + `. We
can optimize our parameters by setting k = O(κ), n = O(k) ande = (n − k)/4 to achieve 2−κ -security. The next constraint on theparameters requires that m · ` is at least as large as the witness size,
which is O(s) where s is the number of (addition and multiplication)
gates in the circuit. Optimal values for m and ` can be obtained byequating the dominating costs in the communication, p
namely, O(`)√
and O(t · m) which implies ` = O( sκ) and m = O( s/κ). Overall the communication complexity with these parameters will be√O( sκ dlog |F|e). In the full version we show that, the communication complexity of proving the satisfiability of an arithmetic circuitof size s > 30000 over a finite field F, |F| ≥ 2128 with soundness er√√ror 2−40 consists of roughly 95 s field elements (or 70 s elements
under Conjecture 4.1). If we want security 2−80 , the communication√√is roughly 140 s (or 120 s under Conjecture 4.1).
Optimizing for Boolean circuits requires additional effort. In thiscase there is yet another degree of freedom, namely the field size.
The only constraint on the field size is that there are sufficiently
many evaluation points, namely, we need |F| ≥ `+n. For a given statistical security parameter κ, we can show that for sufficiently
p largecircuits the optimal communication complexity is O(k · s log s)√
where |F| = O( s). For smaller circuits, the optimal value requiresa more careful analysis as the low order terms are significant and
we present our results in the next section.

5.4

experiments on Intel Core i7-4720HQ CPU 2.60 GHz, 4 cores, 8 GiB
RAM. For our collision resistant hash function we used SHA-256.
We primarily compare our work with ZKB++/ZKBoo [13, 22]that qualitatively match our result in most aspects. The crucial
advantage of our approach over ZKBoo/ZKB++ is that our communication is sublinear in the circuit size whereas ZKBoo/ZKB++
incurs communication that is proportional in the circuit size. Moreover, in the amortized setting, our approach provides significantly
better communication cost and runtimes over ZKBoo/ZKB++.
The primary Boolean predicate we used to demonstrate our
implementation was verifying a SHA-256 certificate as it is thecommon benchmark used in prior works. Namely, on a common
input a 256-bit string y and a private input x of the prover, theprover convinces the verifier that SHA256(x) = y.
Optimizations. A standard computation of the SHA certificate,involves AND and XOR gates and addition modulo 232 gates. One
approach is to simply realize the addition modulo 232 gates using Boolean AND and XOR gates. We follow a different approach,where we express the addition modulo 232 gate consistency as alinear constraint over the bits of the inputs and output of the gate.
Following Section 4.5, this can be efficiently realized if we rely on aprime field larger than 233 . However, as mentioned in the previous
section, to obtain optimal communication for a given witness size
requires choosing a field of a specific size. To handle this, we incorporate these addition gates by considering a word size of dlog |F|eand performing 32-bit additions using arithmetic over the smaller
word size. Following these optimizations, results in a witness sizeof 33928 bits for the SHA-256 certificate (for |F| ≥ 214 ). We ran our
protocol for different circuit sizes and for each size, we ran ad-hoc
optimizers to obtain optimal parameters for soundness 2−40 . We
remark that a tighter soundness error for the tests described in
Section 4 which in turn is used in our ZKIPCP can be obtained bydiscarding the last inequality in Lemma 4.2, 4.6 and 4.8. We reliedon these better bounds in our optimizer (as opposed to the cleaner
bounds that appear in the Lemma statements). For the case of 2−80
soundness error the communication and computation costs doubles(as in [13, 22]). For boolean circuits, the quadratic constraints only
involves checking if each element of the witness is binary and we
can simplify the test in Section 4.3 by eliminating x, y, z and having
Íthe prover compute p0 (•) = i r i · (piw (•) · piw (•) − piw (•)).
In Figure 1, we compare the prover and verifier running times
for verifying circuits of sizes varying from 2048 gates to 400000
gates.4 The computational complexity of both the prover and theverifier in the single instance setting are proportional to O(s log s)field operations, where s is the circuit size. The optimal field size
can be asymptotically shown to be O(log s) resulting in a overall
computational complexity of O(s log2 s). We remark here that if
we make uniformity assumptions on the circuit, then the verifier’s
computational complexity becomes sublinear in the circuit size. In
fact, the multi-instance setting can be seen as a uniformity assumption and here the verifier’s complexity is indeed smaller than thecomputational complexity.

Multi-Instance Amortization

If we want to prove that C(x i , ·) is satisfiable for N public inputs x i ,we can simplify our ZKIPCP construction as follows. The prover
first computes the combined witness w = w 1 , . . . , w N that is comprised of N witnesses, each is computed as in the single instancecase. Next, it arranges the witnesses in blocks of size ` = N ,where block j contains the j t h bits of each of the N witnesses. The
public inputs x i define public blocks. The number of non-publicblocks equals the size of the witness of a single instance, which is
m = |w i | = O(s). The prover then encodes the blocks of messages
into U ∈ Lm .
Even for moderately large N , the multi-instance variant provides
significant savings in both computational and communication costs.
This is because we do not need to rearrange the wire values as we
do in the single instance case. The total communication complexity
is[n · σ + 4 · σ · (2N + t) + 2 · σ · (N + t − 2)+t · (4 · s + 5 · σ )] · dlog |F|e + t · dlog ne · h.
For sufficiently large fields, we can set t = O(κ) where if N >O(κ 2 ), then the proof length is shorter than sN bits. Note that thisthreshold is independent of the circuit size.

6

IMPLEMENTATION AND RESULTS

We implemented our protocol in C++ using Shoup’s NTL libraryfor the finite field operations. We used BOOST::MPI for emulatinga network. To pick the evaluation points, we chose a prime that
had sufficiently large power of two roots of unity and set ηi and ζ jvalues to be roots of unity. This enabled us to perform interpolationand evaluation using inverse FFT and FFT operations. We ran our

4 Note that our proof length and computation times are not influenced by circuit

topology and only depend on the witness size which in turn depends only on thenumber of gates. In fact, in the case of Boolean circuits, they are independent of gate
composition (assuming the circuit comprises of only XOR and AND gates).

2100

Session J1: Outsourcing

CCS’17, October 30-November 3, 2017, Dallas, TX, USA

3min

500
LigeroLigero-Strong
ZKB++ length
Circuit Size

Prover time
Verifier time

50s

Communication (KB)

10s
Run time (ms)

5s

1s
500

100

50

100
50
10
10
SHA256

5
103

104

105
s (circuit size)

106

5

107

103

104

105

106

G (# gates)1

3 · 106

1

Figure 1: Prover and verifier running times for verifying
a single instance of different circuit sizes.

Figure 2: Proof lengths for proving a single instance ofdifference circuit sizes.

102

104

Prover time (2048)
Verifier time (2048)
Prover time (SHA256)

101

2048 gate cir.
SHA256

Verifier time (SHA256)

Communication / instance (KB)

Run time / instance (ms)

103
100

10−1

10−2

10−3

102

101
SHA2561010−402048 gate cir.
1

10

100
N (instances)

1000

5000
1

1

2

4

8

16 32 64 128 256 29 210 211 212
N (instances)1

Figure 3: Amortized prover and verifier running times
for verifying multiple instances of 2048 and gate circuitand SHA-256 circuit.

Figure 4: Amortized proof lengths for multiple instancesof 2048 gate circuit and SHA-256 circuit.

In Figure 2, we provide the communication complexity in kilobytes (KB) of our zero-knowledge argument. We plot two instantiations of our protocol. We provide communication cost for our
provable variant labelled Ligero and the variant that assumes Conjecture 4.1 labelled as Ligero-Strong. We observe that Ligero-Strong

yields a 20% reduction in communication on the average. The communication for a SHA certificate is 44KB with Ligero and 34KB with
Ligero-Strong. We can also see in Figure 2 that beyond 3 million
gates our communication cost is smaller than the circuit size.

2101

Session J1: Outsourcing

CCS’17, October 30-November 3, 2017, Dallas, TX, USA

We compare our complexity with ZKB++ [13, 22]). We first notethat the complexity of ZKB++ only depends on the number ofBoolean AND gates (as XOR’s are for free). In our implementation
we relied on prime fields and our communication cost depends on
the number of AND and XOR gates. However, had we relied on
extension field of GF2 , we can eliminate the dependence on XOR
gates similar to ZKB++. In this variant of our protocol, each AND
gate will incur 3 bits in the witness. In Figure 2, in order to makea fair comparison with ZKB++ for a circuit of size s, we plot thecommunication cost incurred by the ZKB++ protocol for a circuitof size 2s/3. The idea is that for a circuit comprising of 2s/3 AND
gates the cost of ZKB++ is compared with the communication costof our protocol assuming a characteristic-2 FFT implementation.
The threshold for which our approach incurs lesser communication
than ZKB++ is roughly 3000 (AND) gates.
In Figures 3 and 4 we provide our prover and verifier runningtimes and communication for the multi-instance version of our
protocol. We take a 2048 gate circuit and the SHA-256 circuit toillustrate our performance. The heaviest part of the verification
involves performing FFTs over domains of sizes N and s where sis the circuit size. Since we considered 1 to 4096 instances, evenfor moderately sized circuits the FFT over domain of size s dominates the cost. The prover complexity, on the other hand, varies
as N s log s. We see a reduction in the amortized prover’s cost per
instance with periodic jumps because we perform FFT over a larger
domain, which is usually set to a power of 2.
The communication complexity varies additively in N and s. The
amortized communication cost per instance decreases linearly because, similar to the verifier complexity, s dominates the complexity
until N becomes significant compared to s.

7

for reducing the amortized cost of verifying multiple evaluationsof the same circuit. On the prover side, more than 50% of the total
prover time for small circuits and 66% for large circuits is spent on
computing the hashes of the leaves of the Merkle tree. This leaves
room for improvement by relying on space- and cache-efficienthashing algorithms.
Finally, it would be interesting to explore the concrete efficiency
of other approaches to lightweight sublinear zero-knowledge arguments. In particular, one could consider constructions of PCPs basedon bivariate polynomials such as the one of Polishchuk and Spielman [40] (see [8] for work in this direction), or the zero-knowledge
PCP obtained by applying our general transformation to the MPC
protocol from [17]. This type of constructions can be further simplified by applying an interactive procedure for testing linear constraints as we do in Section 4.2.
Acknowledgments. We thank Eli Ben-Sasson, Swastik Kopparty,
abhi shelat, Salil Vadhan, and Mike Walfish for useful discussions
and pointers, the anonymous CCS reviewers for helpful comments,
and Victor Shoup for his assistance with the NTL library.
The first and last authors were supported by Google Faculty Research Grant and NSF Awards CNS-1526377 and CNS-1618884. The
second author was supported by the European Research Council
under the ERC consolidators grant agreement n. 615172 (HIPS), andby the BIU Center for Research in Applied Cryptography and Cyber
Security in conjunction with the Israel National Cyber Bureau in
the Prime Minister’s Office. The third author was supported by
a DARPA/ARL SAFEWARE award, DARPA Brandeis program under Contract N66001-15-C-4065, NSF Frontier Award 1413955, NSF
grants 1619348, 1228984, 1136174, and 1065276, ERC grant 742754,
NSF-BSF grant 2015782, ISF grant 1709/14, BSF grant 2012378, aXerox Faculty Research Award, a Google Faculty Research Award,
an equipment grant from Intel, and an Okawa Foundation Research
Grant. This material is based upon work supported by the Defense
Advanced Research Projects Agency through the ARL under Contract W911NF-15-C-0205. The views expressed are those of theauthors and do not reflect the official policy or position of Google,
the Department of Defense, the National Science Foundation, or
the U.S. Government.

CONCLUSIONS AND FUTURE WORKWe designed and implemented a zero-knowledge argument for NP
that simultaneously offers good concrete efficiency and sublinear
communication in the circuit size. As the computational complexity of our protocol is dominated by polynomial evaluations andinterpolations, we can rely on efficient FFT implementations forminimizing its computational cost. In the following we mention
some additional optimizations that we have not fully explored.
The current implementation relies on prime fields. This allows us
to optimize arithmetics over integers by considering a sufficiently
large prime. Moreover, the witness includes two bits per gate forboth XOR and AND gates. If we instead rely on characteristic 2
fields, then the witness size will require three bits per AND gate and0 bits for XOR gates. Hence there is a tradeoff in choosing between
the two options. It is also unclear how the FFT algorithms compare
for characteristic 2 and prime fields, though fast implementations
for the characteristic 2 case are known [10, 20].
The verification of our zero-knowledge argument needs to evaluate a polynomial on a subset of the points in the domain. We
currently implement this by having the verifier evaluate the polynomial on the entire domain via FFT and extract the points in thissubset. Improving this will improve the verifier’s efficiency. Relying
on GPU for FFT computations can also bring significant savings.
Finally, one can exploit a repetitive circuit structure (“uniformity”)
to reduce verification time. We currently only take advantage of this

REFERENCES[1] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy.
1998. Proof Verification and the Hardness of Approximation Problems. J. ACM
45, 3 (1998), 501–555.
[2] Sanjeev Arora and Shmuel Safra. 1998. Probabilistic Checking of Proofs: A New
Characterization of NP. J. ACM 45, 1 (1998), 70–122.
[3] László Babai, Lance Fortnow, Leonid A. Levin, and Mario Szegedy. 1991. Checking
Computations in Polylogarithmic Time. In STOC. 21–31.
[4] Eli Ben-Sasson, Iddo Bentov, Alessandro Chiesa, Ariel Gabizon, Daniel Genkin,
Matan Hamilis, Evgenya Pergament, Michael Riabzev, Mark Silberstein, Eran
Tromer, and Madars Virza. 2017. Computational Integrity with a Public Random
String from Quasi-Linear PCPs. In EUROCRYPT. 551–579.
[5] Eli Ben-Sasson, Iddo Bentov, Ynon Horesh, and Michael Riabzev. 2017. Scalable,transparent, and post-quantum secure computational integrity. Manuscript.
(2017). Slides at https://people.eecs.berkeley.edu/~alexch/docs/pcpip_bensasson.
pdf.
[6] Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Michael Riabzev, and Nicholas
Spooner. 2016. Short Interactive Oracle Proofs with Constant Query Complexity,
via Composition and Sumcheck. IACR Cryptology ePrint Archive 2016 (2016),
324.
[7] Eli Ben-Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers,
Eran Tromer, and Madars Virza. 2014. Zerocash: Decentralized Anonymous

2102

Session J1: Outsourcing

CCS’17, October 30-November 3, 2017, Dallas, TX, USA

Payments from Bitcoin. In 2014 IEEE Symposium on Security and Privacy, SP 2014,
Berkeley, CA, USA, May 18-21, 2014. 459–474.
[8] Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, and Eran Tromer. 2013. On
the concrete efficiency of probabilistically-checkable proofs. In Symposium on
Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013.
585–594.
[9] Eli Ben-Sasson, Alessandro Chiesa, and Nicholas Spooner. 2016. Interactive
Oracle Proofs. In TCC. 31–60.
[10] Eli Ben-Sasson, Matan Hamilis, Mark Silberstein, and Eran Tromer. 2016. Fast
Multiplication in Binary Fields on GPUs via Register Cache. In Proceedings of the2016 International Conference on Supercomputing, ICS 2016, Istanbul, Turkey, June
1-3, 2016. 35:1–35:12.
[11] Nir Bitansky, Ran Canetti, Alessandro Chiesa, and Eran Tromer. 2013. Recursive
composition and bootstrapping for SNARKS and proof-carrying data. In STOC.
111–120.
[12] Nir Bitansky, Alessandro Chiesa, Yuval Ishai, Rafail Ostrovsky, and Omer Paneth.
2013. Succinct Non-interactive Arguments via Linear Interactive Proofs. In TCC.
315–333.
[13] Melissa Chase, David Derler, Steven Goldfeder, Claudio Orlandi, Sebastian Ramacher, Christian Rechberger, Daniel Slamanig, and Greg Zaverucha. 2017. PostQuantum Zero-Knowledge and Signatures from Symmetric-Key Primitives. IACR
Cryptology ePrint Archive 2017 (2017), 279.
[14] Hao Chen and Ronald Cramer. 2006. Algebraic Geometric Secret Sharing Schemes
and Secure Multi-Party Computations over Small Fields. In CRYPTO. 521–536.
[15] Graham Cormode, Michael Mitzenmacher, and Justin Thaler. 2012. Practicalverified computation with streaming interactive proofs. In ITCS. 90–112.
[16] Ivan Damgård and Yuval Ishai. 2006. Scalable Secure Multiparty Computation.
In CRYPTO. 501–520.
[17] Ivan Damgård, Yuval Ishai, and Mikkel Krøigaard. 2010. Perfectly Secure Multiparty Computation and the Computational Overhead of Cryptography. In
EUROCRYPT. 445–465.
[18] George Danezis, Cédric Fournet, Markulf Kohlweiss, and Bryan Parno. 2013.
Pinocchio coin: building zerocoin from a succinct pairing-based proof system.
In PETShop’13, Proceedings of the 2013 ACM Workshop on Language Support forPrivacy-Enhancing Technologies, Co-located with CCS 2013, November 4, 2013,
Berlin, Germany. 27–30.
[19] Amos Fiat and Adi Shamir. 1986. How to Prove Yourself: Practical Solutions to
Identification and Signature Problems. In CRYPTO. 186–194.
[20] Shuhong Gao and Todd Mateer. 2010. Additive Fast Fourier Transforms over
Finite Fields. IEEE Trans. Inf. Theor. 56, 12 (Dec. 2010), 6265–6272.
[21] Rosario Gennaro, Craig Gentry, Bryan Parno, and Mariana Raykova. 2013. Quadratic Span Programs and Succinct NIZKs without PCPs. In EUROCRYPT. 626–645.
[22] Irene Giacomelli, Jesper Madsen, and Claudio Orlandi. 2016. ZKBoo: Faster
Zero-Knowledge for Boolean Circuits. In USENIX. 1069–1083.
[23] Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum. 2015. Delegating
Computation: Interactive Proofs for Muggles. J. ACM 62, 4 (2015), 27:1–27:64.
[24] Shafi Goldwasser, Silvio Micali, and Charles Rackoff. 1985. The Knowledge
Complexity of Interactive Proof-Systems (Extended Abstract). In STOC. 291–
304.
[25] Vipul Goyal, Yuval Ishai, Mohammad Mahmoody, and Amit Sahai. 2010. Interactive Locking, Zero-Knowledge PCPs, and Unconditional Cryptography. In
CRYPTO. 173–190.
[26] Jens Groth. 2009. Linear Algebra with Sub-linear Zero-Knowledge Arguments.
In CRYPTO. 192–208.
[27] Jens Groth. 2010. Short Pairing-Based Non-interactive Zero-Knowledge Arguments. In ASIACRYPT. 321–340.
[28] Yuval Ishai, Eyal Kushilevitz, and Rafail Ostrovsky. 2007. Efficient Arguments
without Short PCPs. In CCC. 278–291.
[29] Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai. 2007. Zeroknowledge from secure multiparty computation. In STOC. 21–30.
[30] Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai. 2009. ZeroKnowledge Proofs from Secure Multiparty Computation. SIAM J. Comput. 39, 3(2009), 1121–1152.
[31] Yuval Ishai, Mohammad Mahmoody, and Amit Sahai. 2012. On Efficient ZeroKnowledge PCPs. In TCC. 151–168.
[32] Yuval Ishai, Manoj Prabhakaran, and Amit Sahai. 2008. Founding Cryptography
on Oblivious Transfer - Efficiently. In CRYPTO. 572–591.
[33] Yuval Ishai, Manoj Prabhakaran, and Amit Sahai. 2009. Secure Arithmetic
Computation with No Honest Majority. In TCC. 294–314. Full version: IACR
Cryptology ePrint Archive 2008: 465.
[34] Yuval Ishai and Mor Weiss. 2014. Probabilistically Checkable Proofs of Proximitywith Zero-Knowledge. In TCC. 121–145.
[35] Yael Tauman Kalai and Ran Raz. 2008. Interactive PCP. In ICALP. 536–547.
[36] Joe Kilian. 1992. A Note on Efficient Zero-Knowledge Proofs and Arguments(Extended Abstract). In STOC. 723–732.

[37] Carsten Lund, Lance Fortnow, Howard J. Karloff, and Noam Nisan. 1990. Algebraic Methods for Interactive Proof Systems. 2–10.
[38] Ralph C. Merkle. 1989. A Certified Digital Signature. In CRYPTO. 218–238.
[39] Silvio Micali. 1994. CS Proofs (Extended Abstracts). In FOCS. 436–453.
[40] Alexander Polishchuk and Daniel A. Spielman. 1994. Nearly-linear size holographic proofs. In Proceedings of the Twenty-Sixth Annual ACM Symposium on
Theory of Computing, 23-25 May 1994, Montréal, Québec, Canada. 194–203.
[41] Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum. 2016. Constant-roundinteractive proofs for delegating computation. In STOC. 49–62.
[42] Srinath T. V. Setty, Benjamin Braun, Victor Vu, Andrew J. Blumberg, Bryan
Parno, and Michael Walfish. 2013. Resolving the conflict between generality andplausibility in verified computation. In Eighth Eurosys Conference 2013, EuroSys’13, Prague, Czech Republic, April 14-17, 2013. 71–84.
[43] Srinath T. V. Setty, Richard McPherson, Andrew J. Blumberg, and Michael Walfish. 2012. Making argument systems for outsourced computation practical(sometimes). In 19th Annual Network and Distributed System Security Symposium,
NDSS 2012, San Diego, California, USA, February 5-8, 2012.
[44] Adi Shamir. 1990. IP=PSPACE. 11–15.
[45] Justin Thaler. 2013. Time-Optimal Interactive Proofs for Circuit Evaluation. In
CRYPTO. 71–89.
[46] Victor Vu, Srinath T. V. Setty, Andrew J. Blumberg, and Michael Walfish. 2013.
A Hybrid Architecture for Interactive Verifiable Computation. In SP. 223–237.
[47] Michael Walfish and Andrew J. Blumberg. 2015. Verifying computations without
reexecuting them. Commun. ACM 58, 2 (2015), 74–84.
[48] Yupeng Zhang, Daniel Genkin, Jonathan Katz, Dimitrios Papadopoulos, andCharalampos Papamanthou. 2017. vSQL: Verifying Arbitrary SQL Queries over
Dynamic Outsourced Databases. In 2017 IEEE Symposium on Security and Privacy,
SP 2017, San Jose, CA, USA, May 22-26, 2017. 863–880.

A

GENERALIZED INTERLEAVED CODETESTINGIn this section we present a generalized version of the testing algorithm that uses σ linear combinations to amplify soundness. Thisalgorithm is useful for obtaining better soundness over small fields.
Generalized-Test-Interleaved(F, L[n, k, d], m, t, σ ; U )• Oracle: A purported Lm -codeword U . Depending on the context, we may view U either as a matrix in Fm×n in which eachrow is a purported L-codeword, or as a sequence of n symbols(U1 , . . . , Un ), Ui ∈ Fm .
• Parameters:– Probing parameter t < n (number of symbols U j read by V).
– Repetition parameter σ (number of random linear combinations).
• Interactive testing:(1) V picks σ random linear combinations r 1 , . . . , r σ ∈ Fm andsends them to P.
(2) P responds with wh = rhT U ∈ Fn , h = 1, . . . , σ .
(3) V queries a set Q ⊂ [n] of t random symbols U j , j ∈ Q.
(4) V accepts iff all wh are in L and are consistent with UQ
and rh . That is, for every j ∈ Q and 1 ≤ h ≤ σ , we haveÍm
i=1 (r h ) j · Ui, j = (w h ) j .
Lemma A.1. If U ∈ Lm and P is honest, then V always accepts.
Lemma A.2. Let e be a positive integer such that e < d/4. Supposed(U ∗ , Lm ) > e. Then, for a random w ∗ in the row-span of U ∗ , wehavePr[d(w ∗ , L) ≤ e] ≤ (e + 1)/|F| σ .
Theorem A.1. Let e be a positive integer such that e < d/4.
Suppose d(U ∗ , Lm ) ≥ e. Then, for any malicious P strategy, theoracle U ∗ is rejected by V except with ≤ (1 − e/n)t + (e + 1)/|F| σprobability.
A proof of a generalization of this test appears in Section C.

2103

Session J1: Outsourcing

B

CCS’17, October 30-November 3, 2017, Dallas, TX, USA

Lemma C.2. Let e be a positive integer such that e < d/4. Supposed(U ∗ , Lm ) > e. Then, for arbitrary u 10 , . . . , u σ0 ∈ Fn and a randomw ∗ in the row-span of U ∗ , we have Pr[∀ h ∈ [σ ], d(w ∗ + uh0 , L) ≤e] ≤ (e + 1)/|F| σ .

AFFINE INTERLEAVED CODE TESTING

Affine-Test-Interleaved(F, L[n, k, d], m, t; U , u 0 )• Oracle: A purported Lm -codeword U and an additional auxiliaryrow vector u 0 ∈ Fn .
• Interactive testing:(1) V picks random linear combinations r ∈ Fm and sends r
to P.
(2) P responds with w = r T U + u 0 ∈ Fn .
(3) V queries a set Q ⊂ [n] of t random symbols U j , j ∈ Q, aswell as u j0 , j ∈ Q.
0 , and r .
(4) V accepts iff w ∈ L and w is consistent with UQ , uQÍm0That is, for every j ∈ Q we have i=1 r j · Ui, j + u j = w j .

Proof: The proof of Lemma C.2 is almost identical to the proof of
Lemma 4.2. The high level reason why the same argument works
is that the decomposition w ∗ = αv ∗ + x where x is independentof α still holds even for w ∗ + uh0 (since uh0 is a fixed vector, and so
uh0 + x is independent of α). We provide the full proof below.
Let L∗ be the row-span of U ∗ . We consider two cases similar toour proof of Lemma 4.2.
Case 1: There exists v ∗ ∈ L∗ such that d(v ∗ , L) > 2e. In this case,we show that

Lemma B.1. If U ∈ Lm , u 0 ∈ L, and P is honest, then V always
accepts.

Pr [∀ h ∈ [σ ], d(w ∗ + uh0 , L) ≤ e] ≤ 1/|F| σ .

Indeed, using a basis for L∗ that includes v ∗ , a random w ∗ ∈ L∗
can be written as αv ∗ + x, where α ∈R F and x is distributed
independently of α. We argue that conditioned on any choice of x,
there can be at most one choice of α such that d(αv ∗ +x +uh0 , L) ≤ e.
We can conclude the case from this as the probability over r 1 , . . . , rhthat d((rh )T U + uh0 , L) ≤ e holds for every h is at most 1/|F| σ .
This follows by observing that if d(αv ∗ + x 0 + uh0 , L) ≤ e andd(α 0v ∗ + x 0 + uh0 , L) ≤ e for α , α 0 , then by the triangle inequality
we have d((α − α 0 )v ∗ , L) ≤ 2e. Since, by assumption d(v ∗ , L) > 2eand this implies d(v ∗ , L) > 2e, we arrive at a contradiction.

Lemma B.2. Let e be a positive integer such that e < d/4. Supposed(U ∗ , Lm ) > e. Then, for arbitrary u 0 ∈ Fn and a random w ∗ in the
row-span of U ∗ , we have Pr[d(w ∗ , L) ≤ e] ≤ (e + 1)/|F|.
Theorem B.1. Let e be a positive integer such that e < d/4.
Suppose d(U ∗ , Lm ) ≥ e. Then, for an arbitrary u 0 ∈ Fn and any
malicious P strategy, the oracle U ∗ is rejected by V except with≤ (1 − e/n)t + (e + 1)/|F| probability.
A proof of a generalization of this test appears in the next section.

C(2)

w ∗ ∈R L ∗GENERALIZED AFFINE INTERLEAVED
CODE TESTING

Case 2: For every v ∗ ∈ L∗ , d(v ∗ , L) ≤ 2e. We show that in thiscase Prw ∗ ∈R L ∗ [∀ h ∈ [σ ], d(w ∗ + uh0 , L) ≤ e] ≤ (e + 1)/|F| σ . LetUi∗ be the i t h row of U ∗ and let Ei = ∆(Ui∗ , L). Note that, since
2e < d/2, each Ui∗ can be written uniquely as Ui∗ = ui + χi whereui ∈ L and χi is nonzero exactly in its Ei entries. Let E = ∪mi=1 Ei .
Since d(U ∗ , Lm ) > e, we have |E| > e. We show below that forj ∈ E, except with 1/|F| probability over a random choice of w ∗from L∗ , either j ∈ ∆(w ∗ + uh0 , L) or d(w ∗ + uh0 , L) > e. First, weconclude the case and the proof of Lemma assuming this holds. We
observe that this implies that with probability at most 1/|F | σ overthe choice of r 1 , . . . , r σ , it holds that, for all h, j < ∆((rh )T U +uh0 , L)and d((rh )T U +uh0 , L) ≤ e. Taking a union bound over the first e + 1
elements of E the claim follows.
Suppose j ∈ Ei and fix an arbitrary h ∈ [σ ]. As before, we writew ∗ = αUi∗ + x for α ∈R F and x distributed independently of α.
Condition on any possible choice x 0 of x. Define a bad set

For the purpose of obtaining a zero-knowledge IPCP, the following “affine” variant of Test-Interleaved is useful. Whenever V
requests a random linear combination of the rows of U , this linear
combination will be masked with an additional blinding vectoru 0 ∈ Fn . The vector u 0 , which is also given as part of the proof
oracle, will be picked by an honest P at random from L and will
therefore hide all information about U whose rows are from L. The
soundness of the test should hold even when u 0 is adversariallychosen and is not necessarily a codeword. We generalize it further following the previous section to achieve better soundness byrepetition.
Generalized-Affine-Test-Interleaved(F, L[n, k, d], m, t, σ ; U , u 0 )• Oracle: A purported Lm -codeword U and additional auxiliaryrow vectors u 10 , . . . , u σ0 ∈ Fn .
• Interactive testing:(1) V picks a random linear combinations r 1 , . . . , r σ ∈ Fm andsends r to P.
(2) P responds with wh = rhT U + uh0 ∈ Fn , h = 1, . . . , σ .
(3) V queries a set Q ⊂ [n] of t random symbols U j , j ∈ Q, aswell as (u σ )j , j ∈ Q.
(4) V accepts iff all wh ∈ L and are consistent with wh and UQ ,Íuh , and rh . That is, for every j ∈ Q we have m
i=1 (r h )j ·Ui, j + (uh0 )j = w j .
Completeness follows directly from the description. A formal
proof of our soundness is presented below.

B j = {α : j < ∆(αUi∗ + x 0 + uh , L) ∧ d(αUi∗ + x 0 + uh , L) ≤ e}.
We show that |B j | ≤ 1. Suppose for contradiction that there are
two distinct α, α 0 ∈ F such that for z = αUi∗ + x 0 + uh and z 0 =α 0Ui∗ + x 0 + uh we have d(z, L) ≤ e, d(z 0, L) ≤ e, j < ∆(z, L), andj < ∆(z 0, L). Since d > 4e, for any z ∗ in the linear span of z and z 0
we have j < ∆(z ∗ , L). Since (α − α 0 )Ui∗ = z − z 0 is in this linear span,
we have j < ∆(Ui∗ , L), in contradiction to the assumption j ∈ Ei . 
Theorem C.1. Let e be a positive integer such that e < d/4. Suppose d(U ∗ , Lm ) ≥ e. Then, for arbitrary u 10 , . . . , u σ0 ∈ F and any
malicious P strategy, the oracle U ∗ is rejected by V except with≤ (1 − e/n)t + (e + 1)/|F| σ probability.

Lemma C.1. If U ∈ Lm , u 10 , . . . , u σ0 ∈ L, and P is honest, then V
always accepts.

2104