Plaintext
T HEORY OF C OMPUTING, Volume 10 (5), 2014, pp. 107–131
www.theoryofcomputing.org
Competing-Provers Protocols
for Circuit Evaluation
Gillat Kol† Ran Raz‡
Received September 14, 2011; Revised May 18, 2014; Published August 9, 2014
Abstract: Let C be a (fan-in 2) Boolean circuit of size s and depth d, and let x be an input
for C. Assume that a verifier, that knows C but does not know x, can access the low-degree
extension of x at one random point. Two competing provers try to convince the verifier that
C(x) = 0 and C(x) = 1, respectively, and it is assumed that one of the provers is honest.
For any r ≥ 1, we construct1 an r-round protocol with communication complexity
d 1/r poly log (s) that convinces the verifier of the correct value of C(x) (with small probability
of error). In particular, when we allow only one round, the protocol exchanges d · poly log (s)
bits, and when we allow r = O(log(d)/log log(s)) rounds, the protocol exchanges only
poly log (s) bits. Moreover, the complexity of the verifier and the honest prover in this
protocol is poly(s), and if in addition the circuit is log(s)-space uniform, the complexity of
the verifier is d 1/r poly log (s). The protocol is obtained by combining the delegation protocol
of Goldwasser, Kalai, and Rothblum (STOC 2008), the competing-provers protocols of Feige
and Kilian (STOC 1997), and some new techniques.
We suggest two applications of these results:
A conference version of this paper appeared in the Proceedings of the 4th Innovations in Theoretical Computer Science
conference (ITCS), 2013 [8].
† Research supported by Israel Science Foundation (ISF) grant.
‡ Research supported by Israel Science Foundation (ISF) grant.
1 We have learned that a result similar to ours for the case r = 1, as well as the motivation of delegating computation to
competing clouds, was independently obtained by Canetti, Riva, and Rothblum (ICITS 2012).
ACM Classification: H.4, F.0
AMS Classification: 68Q10, 68Q15
Key words and phrases: communication complexity, competing provers, delegation, complexity theory
© 2014 Gillat Kol and Ran Raz
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2014.v010a005
G ILLAT KOL AND R AN R AZ
Delegating computation to competing clouds: The main motivation behind the protocol
of GKR’08 was delegating computation to a cloud. Using our new protocol, a verifier can
delegate computation to two (or more) competing clouds. If at least one of the clouds is
reliable the verifier can trust that the computation is correct (with high probability). The
advantage over the protocol of GKR’08 is that the communication complexity and the
number of rounds in our protocol are significantly lower.
Communication complexity with competing provers, and circuit lower bounds: Aaron-
son and Wigderson (2009) suggested the model of communication complexity with com-
peting provers, where two competing provers try to convince two players that f (x, y) = 0
and f (x, y) = 1, respectively, where x is an input held by the first player and y is an input
held by the second player. By scaling down the competing-provers protocols of FK’97, they
showed that strong enough lower bounds for the communication complexity of f , in this
model, imply lower bounds for the computational complexity of f .
Our results strengthen this connection. More precisely, we show that if f can be computed
by a Boolean circuit of size s and depth d then for any r ≥ 1 there is an r-round protocol for
f , in this model, with communication complexity d 1/r poly log (s). This can be viewed as
a possible direction towards proving circuit lower bounds. For instance, in order to prove
f∈ / NC, it suffices to show that any one-round protocol for f , in this model, requires the
exchange of ω (poly log (n)) bits. This gives a relatively simple combinatorial property that
implies strong circuit lower bounds.
1 Introduction
The model of refereed games, or, interactive proofs with competing provers, was first introduced by
Feige, Shamir and Tennenholtz [4]. Informally, given a language L and an input x, an efficient verifier
interacts (that is, exchanges private messages) with two computationally unbounded provers in order to
decide whether or not x ∈ L. One prover tries to convince the verifier that x ∈ L, while the other prover
tries to convince the verifier that x ∈
/ L. (The assumption is that the prover who is right is honest and
follows the protocol, while the other is untrusted.) The seminal paper of Feige and Kilian [3] shows
that the class of languages with a single round refereed games is exactly PSPACE, and the class of
languages with poly(n)-round refereed games is exactly EXP. (The fact that EXP contains all languages
with poly(n)-round refereed games was shown in [9].)
Let C be a (fan-in 2) Boolean circuit of size s and depth d, and let x be an input for C. Assume that a
verifier that knows C but does not know x can access the low-degree extension of x (see Section 2.4 for a
definition) at one random point. The verifier tries to decide whether or not x satisfies C. Two competing
provers try to convince the verifier that C(x) = 0 and C(x) = 1, respectively. As before, we assume that
one of the provers is honest.
Problems of this type in the model of interactive proofs with a single prover were studied in [6, 5].
In particular, the beautiful paper of Goldwasser, Kalai, and Rothblum [5] gives a protocol where the
prover convinces the verifier of the correct value of C(x) (with a small probability of error), and where
the number of rounds and the communication complexity are both d · poly log (s), and the complexity of
the prover is poly(s). Moreover, maybe the most interesting aspect of their protocol is that if in addition
T HEORY OF C OMPUTING, Volume 10 (5), 2014, pp. 107–131 108
C OMPETING -P ROVERS P ROTOCOLS FOR C IRCUIT E VALUATION
one assumes that the circuit C is log(s)-space uniform, the complexity of the verifier in the protocol is
d · poly log (s). That is, the complexity of the verifier may be significantly smaller than the size of the
circuit. In other words, the computation was delegated to the prover, while the verifier is still convinced
that the computation is correct.
1.1 Our results
As before, let C be a (fan-in 2) Boolean circuit of size s and depth d, and let x be an input for C. Assume
that a verifier that knows C but does not know x can access the low-degree extension of x at one random
point. Two competing provers try to convince the verifier that C(x) = 0 and C(x) = 1, respectively.
For any r ≥ 1, we give an r-round protocol with communication complexity d 1/r poly log (s) that
convinces the verifier of the correct value of C(x) (with small probability of error). In particular,
when we allow only one round, the protocol exchanges d · poly log (s) bits, and when we allow r =
O(log(d)/log log(s)) rounds, the protocol exchanges only poly log (s) bits. Moreover, the complexity
of the verifier and (honest) provers in this protocol is poly(s), and if in addition the circuit is log(s)-
space uniform, the complexity of the verifier is d 1/r poly log (s). The protocol is obtained by combining
the delegation protocol of Goldwasser, Kalai, and Rothblum [5] and the one-round competing-provers
protocols for PSPACE of Feige and Kilian [3], together with some new techniques.
We have learned that a result similar to ours for the case r = 1, as well as the motivation of delegating
computation to competing clouds, was independently obtained by Canetti, Riva and Rothblum [2].
1.2 Delegating computation to competing clouds
As mentioned above, the main motivation behind the protocol of Goldwasser, Kalai, and Rothblum [5]
was delegating computation to a cloud. Consider the case of log-space uniform circuits. In particular, the
class of languages decidable by log-space uniform circuits of polynomial size is exactly P. As mentioned
above, the complexity of the verifier in this case is relatively small, assuming that she has access to
the low degree extension of x at a random point. Moreover, even if the verifier does not have access to
the low-degree extension of x (but rather knows x), she can compute the low-degree extension of x at a
random point by herself in almost linear time (that is, in time n · poly log(n)), which can be significantly
smaller than the size of the circuit. Thus, the computation was delegated to the prover, while the verifier
is convinced (with high probability) that the computation was performed correctly.
Using our new protocol, a verifier can delegate computation to two (or more) competing clouds,
viewing each cloud as a separate prover. If at least one of the clouds is reliable, the verifier will be
able to identify the correct answer and trust that the computation is correct (with high probability). The
advantage over the protocol of [5] is that the communication complexity and the number of rounds in our
protocol are significantly lower.
1.3 Communication complexity with competing provers and circuit lower bounds
Aaronson and Wigderson [1] suggested the model of communication complexity with two competing
provers.
T HEORY OF C OMPUTING, Volume 10 (5), 2014, pp. 107–131 109
G ILLAT KOL AND R AN R AZ
Recall that the standard setting of communication complexity involves two separated, computationally
unbounded players, Alice and Bob, each holding a private n-bit input string. Assume that Alice holds
x ∈ {0, 1}n and Bob holds y ∈ {0, 1}n . Let f : {0, 1}2n → {0, 1} be a Boolean function known to both
Alice and Bob, and let x ◦ y ∈ {0, 1}2n denote the concatenation of x and y. The players’ mutual goal is to
compute f (x ◦ y) with the least amount of communication between them.
In the model of communication complexity with competing provers the players may communicate,
via private channels, with two provers that are assumed to know f , as well as both x and y. The two
provers try to convince the players that f (x ◦ y) = 0 and f (x ◦ y) = 1, respectively. The communication
complexity of a protocol is the total number of bits exchanged between all the parties (players and provers).
In this paper we are interested in both the number of rounds and the communication complexity of the
suggested protocols.
By scaling down the competing-provers protocols of [3], Aaronson and Wigderson showed that
strong enough lower bounds for the communication complexity of f , in this model, imply lower bounds
for the computational complexity of f . More precisely, they showed that for any language L ∈ P
there are protocols in this model with poly-logarithmic rounds and communication complexity, and
for any language L ∈ LOGSPACE there are one-round protocols with poly-logarithmic communication
complexity.
Our results strengthen this connection and relates the communication complexity of f in this model
to the circuit complexity of f . More precisely, our results imply that if f can be computed by a Boolean
circuit of size s and depth d, then for any r ≥ 1 there is an r-round protocol for f , in this model, with
communication complexity d 1/r poly log (s). In particular, as before, when we allow only one round, the
protocol exchanges d · poly log (s) bits, and when we allow r = O(log(d)/log log(s)) rounds, the protocol
exchanges only poly log (s) bits.
This can be viewed as a possible direction towards proving circuit lower bounds. For instance, in
order to prove f ∈ / NC, it suffices to show that any one-round protocol for f , in this model, requires the
exchange of ω (poly log (n)) bits. The one-round case is very appealing as it gives a relatively simple
combinatorial condition that implies strong circuit lower bounds.
We also consider the model of communication complexity with one prover, where a single prover tries
to convince the players that f (x, y) = 1. We observe that the result of [5] (combined with the approach
of [1]) implies a connection between the communication complexity of f in this model and the circuit
complexity of f . More precisely, their result implies that if f can be computed by a Boolean circuit
of size s and depth d, then there are protocols for f , in this model, with d · poly log (s) rounds and the
exchange of d · poly log (s) bits.
2 Our settings
We study the query complexity and communication complexity settings in the presence of (untrusted)
provers. In this section we present the formal settings used in the paper.
We start by reviewing the standard query and communication complexity settings (Section 2.1). We
present a generalized framework for interaction between players and provers, called general commu-
nication protocols (Section 2.2). We describe the settings for query and communication complexity
with provers (Sections 2.3 and 2.4). Finally, we discuss the relations between query and communication
T HEORY OF C OMPUTING, Volume 10 (5), 2014, pp. 107–131 110
C OMPETING -P ROVERS P ROTOCOLS FOR C IRCUIT E VALUATION
complexity with provers (Section 2.5).
Let Fn be the set of Boolean functions on n bits, Fn = { f | f : {0, 1}n → {0, 1}}.
2.1 Query and communication complexity
2.1.1 Query complexity
In the query complexity setting, we are given a function f ∈ Fn and an input x ∈ {0, 1}n . We are then
asked to compute f (x) by reading the least number of bits from x.
2.1.2 Communication complexity
The communication complexity setting involves two separated, computationally unbounded players, Alice
and Bob, that attempt to evaluate a function f ∈ F2n known to both. Alice receives a private n-bit string x,
and Bob receives a private n-bit string y. Let x ◦ y ∈ {0, 1}2n denote the concatenation of the strings x and
y. The goal is for one of the players (for concreteness, say Alice) to compute and output f (x ◦ y), with
the least amount of communication between them.
2.2 General communication protocols
We consider the setting in which a set of players and provers, each holding a private input (bit-string),
communicate. A general communication protocol (GCP) prescribes a probabilistic strategy for each
participant. During the execution of the protocol, any player may exchange messages (bit-strings) with
any of the other players or provers through a private channel. We assume that there is no communication
between the provers.
At the end of the protocol, the first player must output a value in {0, 1, ⊥}. Informally speaking, this
value should be the result of the evaluation of a Boolean function on the players’ inputs. A 0 or 1 output
is interpreted as the actual value of the function, while ⊥ indicates that one of the provers did not follow
his prescribed strategy.
A GCP proceeds in rounds. Each round consists of three sets of messages sent in the following order
(where messages may be empty):
1. Players interact: Each player sends a message to each of the other players, according to some
pre-specified order.
2. Players send questions: Each player sends a message (question) to each of the provers.
3. Provers reply: Each prover sends a message (answer) to each of the players.
The communication complexity of a GCP is defined as the maximal number of bits exchanged by all the
involved parties (provers and players) in any execution. An (r, c)-GCP is a GCP with at most r rounds,
and communication complexity at most c.
T HEORY OF C OMPUTING, Volume 10 (5), 2014, pp. 107–131 111
G ILLAT KOL AND R AN R AZ
2.3 Query and communication complexity with provers
Next, we formally define the settings used in the paper. We define two variants of the query complexity
model, called QCP (Query Complexity with a Prover) and QCCP (Query Complexity with Competing
Provers), as well as the two variants of the communication complexity model, called CCP (Communication
Complexity with a Prover) and CCCP (Communication Complexity with Competing Provers).
In the CCP and CCCP models, the players attempt to compute the value of a function f ∈ F2n on an
input x ◦ y ∈ {0, 1}2n . We assume that the prover(s) know both x and y, while Alice has only x, and Bob
has only y.
In the QCP and QCCP models, the player attempts to compute the value of a function f ∈ Fn on an
input x ∈ {0, 1}n . We assume that the prover(s) have the input x, while the player has an oracle access to
a (possibly a more “elaborate”) version of x. That is, the player has access to a string y = g (x), where g
is a function that possibly “stretches” x. We mention that in this paper g (x) will always be the low-degree
extension of x (see Section 2.4).
In the QCP model, we require the player to output one of the values f (x) or ⊥ with probability at
least 1 − ε, regardless of the behavior of the prover (that is, the player is only allowed to make a mistake
with probability at most ε). If the prover is truthful (i. e., follows the prescribed strategy), we require the
player to always output f (x). The requirements for the CCP model are similar.
In the QCCP model, we assume that at least one of the provers is truthful (i. e., follows the prescribed
strategy), and require the player to output f (x) with probability at least 1 − ε, regardless of the behavior
of the other prover. Note that, without loss of generality, we may assume that one prover tries to convince
the player that f (x) = 1, while the other tries to convince the player that f (x) = 0. The requirements for
the CCCP model are similar.
For the rest of the section let ε ∈ [0, 1], n, r, c, q, ` ∈ N, F be a field, and g : {0, 1}n → F` .
Definition 2.1 (QCP). QCPε,g (r, c, q) is the set of functions f ∈ Fn that can be computed by an (r, c)-
GCP between a player and a prover, in the following sense: The prover is given an input x ∈ {0, 1}n ,
while the player is given the input y = g (x).
For any strategy of the prover, a player who follows the protocol reads at most q symbols from y and,
with probability at least 1 − ε, outputs either f (x) or ⊥. If the prover also follows the protocol, then the
player always outputs f (x).
Definition 2.2 (CCP). CCPε (r, c) is the set of functions f ∈ F2n that can be computed by an (r, c)-GCP
between two players, Alice and Bob, and a prover, in the following sense: Alice is given an input
x ∈ {0, 1}n and Bob is given an input y ∈ {0, 1}n , while the prover is given the input x ◦ y.
If both players follow the protocol, then for any strategy of the prover, with probability at least 1 − ε,
Alice outputs either f (x ◦ y) or ⊥. If the prover also follows the protocol, then Alice always outputs
f (x ◦ y).
Definition 2.3 (QCCP). QCCPε,g (r, c, q) is the set of functions f ∈ Fn that can be computed by an
(r, c)-GCP between a player and a pair of provers, in the following sense: Both provers are given (the
same) input x ∈ {0, 1}n , while the player is given the input y = g (x).
Assume that for any fixed f and x, one of the provers, whose identity maybe unknown to the player,
always follows the protocol. That is, this prover runs the probabilistic strategy prescribed to him by the
T HEORY OF C OMPUTING, Volume 10 (5), 2014, pp. 107–131 112
C OMPETING -P ROVERS P ROTOCOLS FOR C IRCUIT E VALUATION
protocol. Then, for any strategy of the other prover, a player who follows the protocol reads at most q
symbols from y and, with probability at least 1 − ε, outputs f (x).
Definition 2.4 (CCCP). CCCPε (r, c) is the set of functions f ∈ F2n that can be computed by an (r, c)-
GCP between two players, Alice and Bob, and a pair of provers, in the following sense: Alice is given the
input x ∈ {0, 1}n and Bob is given the input y ∈ {0, 1}n , while both provers are given x ◦ y.
Assume that for any fixed f , x and y, one of the provers, whose identity maybe unknown to the
players, always follows the protocol. That is, this prover runs the probabilistic strategy prescribed to him
by the protocol. For any strategy of the other prover, if both players follow the protocol, Alice outputs
f (x ◦ y) with probability at least 1 − ε.
2.4 Low-degree extension (LDE)
Recall that in the QCP and QCCP models, the prover(s) have an input x, while the player has access to
y = g (x). As mentioned before, in this paper, g (x) is always the low-degree extension of x. In this section
we define the function g (x) = LDE (x), that maps x to its low-degree extension.
Let H = {0, . . . , h − 1} be a set and F = {0, . . . , p − 1} be a field satisfying h ≤ p ∈ N. Recall that the
Low-Degree Extension (LDE) of a function x : Hm → F is the unique m-variate polynomial x̃ : Fm → F
that agrees with x on Hm (i. e., x̃ |Hm = x), and has degree at most h − 1 in each of its m variables.
We sometimes refer to x and x̃ as truth-table strings instead of functions. More precisely, we identify
m
x with the vector in Fh whose jth coordinate is x (h j ), where h j is the jth element in the lexicographic
m
ordering of Hm . Similarly, we identify x̃ with the vector in F p whose jth coordinate is x̃ (p j ), where p j
is the jth element in the lexicographic ordering of Fm .
Let s ∈ N. We define a set Hs = {0, . . . , hs − 1} and a field Fs = {0, . . . , ps − 1} satisfying hs ≤ ps ∈ N.
Let hs = dlog (s)e. Let ms ∈ N be the minimal such that hm s ≥ s. Let Fs be the field of smallest
s
3
size satisfying ps ≥ 12ms hs . Note that hs , ps ≤ poly log (s), ms = O(log(s)/log log(s)) and s ≤ hm s ,
s
m
ps ≤ poly (s).
s
ms
For n < s ∈ N, we define the function LDEs : {0, 1}n → Fsps as follows: Given x ∈ {0, 1}n , we
ms
pad x with 1’s to get an hm 0 hs 0 0
s -size string x ∈ Fs . That is, x is defined by: ∀i ∈ [n] : xi = xi , and
s
∀i ∈ {n + 1, . . . , hm 0
s } : xi = 1. We remark that we pad x with 1’s and not with 0’s to make the proof of
s
Lemma 5.1 (below) simpler. Finally, we define LDEs (x) to be the low-degree extension x̃0 of x0 .
2.5 Connection between query and communication complexity with provers
The following observation made by [1] shows that results for the query complexity model (with g (x) =
LDEs (x)) imply analogous results for the communication complexity model. More precisely, in the
communication complexity setting, any point in the low-degree extension of the concatenated input x ◦ y,
can be computed by the players by the exchange of a single field element.
Let S be a set, and let c ∈ N. Consider the simple generalization of the standard communication
complexity setting that allows Alice and Bob to exchange symbols from the set S (instead of just bits).
We denote by CCS (c) the class of all functions f : {0, 1}2n → S that can be computed by having Alice
and Bob exchange at most c elements of S.
T HEORY OF C OMPUTING, Volume 10 (5), 2014, pp. 107–131 113
G ILLAT KOL AND R AN R AZ
2n
Proposition 2.5 (Aaronson and Wigderson). Fix n, s ∈ N, s > 2n, and z ∈ Fm
s . Let f : {0, 1} → Fs be
s
given by f (x ◦ y) = (LDEs (x ◦ y)) (z). Then, f ∈ CCFs (1).
The proof of Proposition 2.5 follows easily by the fact that the low-degree extension is a linear
function.
We say that a QCP or a QCCP protocol is non-adaptive if the queries to y = g (x) made by the
player only depend on the player’s random string. We mention that protocols presented in this paper are
non-adaptive.
The following is an easy corollary of the above proposition.
Corollary 2.6. Let f ∈ F2n , r, c, q, s ∈ N, 2n < s, and ε ∈ [0, 1].
1. Assume f ∈ QCPε,LDEs (r, c, q), with a non-adaptive protocol. Then
f ∈ CCPε (r, c + O (q · log (s))) .
2. Assume f ∈ QCCPε,LDEs (r, c, q), with a non-adaptive protocol. Then
f ∈ CCCPε (r, c + O (q · log (s))) .
Corollary 2.7. In the above CCP and CCCP protocols for f , the players exchange c bits with the
prover(s), and O (q · log (s)) bits among themselves.
3 Our results
Let Fs,d be the set of all functions f ∈ F2n that have an s (n) size, d (n) depth, Boolean circuit of fan-in 2.
The main result of this paper is that functions in Fs,d can be computed with low query and communication
cost in the QCCP model, and therefore (due to Corollary 2.6) with low communication cost in the CCCP
model.
The first theorem claims that in the QCP and CCP models, d · poly log (s) communication bits suffice
in order to compute any f ∈ Fs,d with high probability. The QCP part of the theorem is a restatement of
the main theorem of [5], while the CCP part of it follows as in Corollary 2.6.
Remark 3.1. In all the protocols below, the players and honest provers run in time at most poly (s).
Theorem 3.2 (Goldwasser, Kalai, and Rothblum). Let n, s, d ∈ N and ε = 1/log(s). There exists a field
F of size poly (d, log (s)) and a function1 g : {0, 1}2n → Fpoly(s) , such that for every function f ∈ Fs,d it
holds that
f ∈ QCPε,g (d · poly log (s) , d · poly log (s) , 1)
and
f ∈ CCPε (d · poly log (s) , d · poly log (s)) .
1 The function g is a low-degree extension with different parameters than the ones we have here.
T HEORY OF C OMPUTING, Volume 10 (5), 2014, pp. 107–131 114
C OMPETING -P ROVERS P ROTOCOLS FOR C IRCUIT E VALUATION
Our next theorem shows that the computation of f ∈ Fs,d can be done with even lower communication
complexity in the competing-provers models. The theorem offers a trade-off between the number of
rounds and the communication complexity of the protocol. Namely, for every r ∈ N, there is a protocol
that computes f with high probability, and only requires r rounds and d 1/r poly log (s) communication
bits.
Theorem 3.3 (Main). Let f ∈ Fs,d and ε = 1/log(s). For every r ∈ N, 1 ≤ r ≤ blog (d)c, it holds that
f ∈ QCCPε,LDEs r, d 1/r poly log (s) , 1 and f ∈ CCCPε r, d 1/r poly log (s) .
The next two theorems are easy corollaries of Theorem 3.3 that are obtained by taking r to extreme
values. Theorem 3.4 takes r to be 1, and claims that f can be computed by the exchange of d ·
poly log (s) bits and with only a single communication round. Theorem 3.5 shows that by choosing
r = O(log (d)/log log(s)) we can reduce the communication complexity of the protocol to poly log (s) at
the price of having O(log(d)/log log(s)) rounds.
Theorem 3.4. Let f ∈ Fs,d and ε = 1/log(s). Then,
f ∈ QCCPε,LDEs (1, d · poly log (s) , 1) and f ∈ CCCPε (1, d · poly log (s)) .
Theorem 3.5. Let f ∈ Fs,d and ε = 1/log(s). Then,
log(d) log(d)
f ∈ QCCPε,LDEs O log log(s) , poly log (s) , 1 and f ∈ CCCPε O log log(s) , poly log (s) .
In order to prove Theorem 3.3, we first prove the special case for r = 1 given by Theorem 3.4
(Section 6). We then show how to use additional rounds to reduce the communication complexity
(Section 7).
The next theorem claims that if f is given by a log (s)-space uniform circuit of size s and depth d,
then the player(s) in Theorem 3.3 can be very efficient and run in time d 1/r poly log (s).
Theorem 3.6. Let f ∈ Fs,d with a log (s)-space uniform circuit, and let ε = 1/log(s). ∀r ∈ N the claim
of Theorem 3.3 holds with players that run in time d 1/r poly log (s) (and honest provers that run in time
poly (s)), and error 2ε.
Remark 3.7. Our protocols work with error ε = 1/log(s). We mention that [2] offer an error reduction
method for similar settings based on parallel repetition.
4 Preliminaries
Fix a size s depth d circuit C, and an input x for C. Set ε = 1/log(s). From now on, we omit the subscript
s and write H, F, h, p, m instead of Hs , Fs , hs , ps , ms . We enumerate the layers of C such that layer 0 is
the output layer and layer d is the input layer. Note that since s is the number of wires in C, the number
of gates in each of the layers cannot exceed s.
We add gates to each of the layers of C, so that each will contain exactly hm > s gates. We label the
gates in every layer by elements of Hm . The gates added to every layer i (i ∈ {0, . . . , d}), are all “special”
T HEORY OF C OMPUTING, Volume 10 (5), 2014, pp. 107–131 115
G ILLAT KOL AND R AN R AZ
gates that always return 1. The fact that every layer contains such a gate makes the proof of Lemma 5.1
(below) simpler.
m
We associate with every layer i ∈ {0, . . . , d} the vector Vi ∈ {0, 1}h (in particular, Vi can be viewed
m
as Vi ∈ Fh ) that consists of the values of the layer’s gates when C is evaluated on x. That is, for j ∈ [hm ],
the jth coordinate of Vi is the value, when C is evaluated on x, of the gate in layer i whose label is the jth
m
element in the lexicographic ordering of Hm . We denote by Ṽi ∈ F p the low-degree extension of Vi .
We may assume, without loss of generality, that the output layer, layer 0, originally consists of a
single gate whose label is now 0m . The player’s task can now be rephrased as computing Ṽ0 (0m ).
Let I = {0, . . . , d} and L = {0, . . . , 2m}. Given a set A and an element a ∈ A, we denote A−a = A\ {a}.
Let φ ∈ F0 be the unique zero-coordinates vector. Whenever we say that a curve or a polynomial is of
degree k, we mean that it is of degree at most k. A line is a degree-1 curve. All logarithms are taken with
base 2.
We will use the Schwartz-Zippel Lemma that bounds the probability that two different polynomials
will agree at randomly selected test points.
Lemma 4.1 (Schwartz-Zippel Lemma). Let F be a field and let P, Q ∈ F[x1 , . . . , xn ] be two different
polynomials of total degree d. Let S ⊆ F be any finite subset. Then, by picking y1 , . . . , yn independently
and uniformly at random from S,
d
Pr[P(y1 , . . . , yn ) = Q(y1 , . . . , yn )] ≤ .
|S|
5 Reducing computation of layer i to layer i + 1
In this section we follow the lines of [5] and show that the problem of computing Ṽi on a point in Fm can
be reduced to the task of computing Ṽi+1 on two points in Fm , using a sum-check protocol.
5.1 Ṽi is a quadratic polynomial in the values of Vi+1
Let i ∈ I−d . The next lemma claims that Ṽi is a degree-2 polynomial in the values of Vi+1 . The reason is
that since Ṽi is the low-degree extension of Vi , for every z ∈ Fm , the value Ṽi (z) is a linear combination of
the values of Vi on Hm . That is, it is a linear combination of the values of the gates of layer i. In addition,
the value of a gate in layer i is a degree-2 polynomial in the values of its two children in layer i + 1.
Lemma 5.1. For every i ∈ I−d , there exists a function βi : Fm × (Hm )2 → F that does not depend on the
input x to the circuit, such that:
1. ∀z ∈ Fm : Ṽi (z) = ∑ βi (z, w0 , w1 )Vi+1 (w0 )Vi+1 (w1 ) ;
w0 ,w1 ∈Hm
2. for every fixed w0 , w1 ∈ Hm , and every j ∈ [m], the function βi (z1 . . . zm , w0 , w1 ) is a polynomial of
degree at most h − 1 in z j .
Proof. Fix i ∈ I−d and let z ∈ Fm . The value Ṽi (z) can be written as
Ṽi (z) = ∑ β 0 (z, p) ·Vi (p) ,
p∈Hm
T HEORY OF C OMPUTING, Volume 10 (5), 2014, pp. 107–131 116
C OMPETING -P ROVERS P ROTOCOLS FOR C IRCUIT E VALUATION
where β 0 (z, p) : Fm × Hm → F is the following 2m-variable function
m
β 0 (z, p) = β 0 (z1 . . . zm , p1 . . . pm ) = ∏ ∏ (z j − q j ) · (p j − q j )−1 .
j=1 q j ∈H\{ p j }
Note that for every j ∈ [m] and every fixed p0 ∈ Hm , the function β 0 (z1 . . . zm , p0 ) is a degree-(h − 1)
polynomial in z j .
The value of gate p ∈ Hm in layer i depends on the values of its two child gates in layer i + 1. Recall
that every layer of C contains at least one “special” gate, that returns 1 on every input. Conclude that
there exists a function c : (Hm )3 → F (depending on the circuit C) such that
Vi (p) = ∑ c (p, w0 , w1 )Vi+1 (w0 )Vi+1 (w1 ) .
w0 ,w1 ∈Hm
For example, if gate p in layer i is an OR gate whose children are gates w0 , w1 ∈ Hm in layer i + 1,
and gate w∗ ∈ Hm in layer i + 1 is a gate that always returns 1, then
Vi (p) = Vi+1 (w0 )Vi+1 (w∗ ) +Vi+1 (w1 )Vi+1 (w∗ ) −Vi+1 (w0 )Vi+1 (w1 ) .
Putting it all together,
!
0
Ṽi (z) = ∑ β (z, p) · ∑ c (p, w0 , w1 )Vi+1 (w0 )Vi+1 (w1 )
p∈Hm w0 ,w1 ∈Hm
!
0
= ∑ ∑ β (z, p) · c (p, w0 , w1 ) Vi+1 (w0 )Vi+1 (w1 ) .
w0 ,w1 ∈Hm p∈Hm
Finally, we denote
βi (z, w0 , w1 ) = ∑ β 0 (z, p) · c (p, w0 , w1 ) ,
p∈Hm
and get
Ṽi (z) = ∑ βi (z, w0 , w1 )Vi+1 (w0 )Vi+1 (w1 ) .
w0 ,w1 ∈Hm
Since β 0 (z1 . . . zm , p) is of degree at most h − 1 in z j for every j ∈ [m], it is also the case that βi is of
degree at most h − 1 in z j .
5.2 Computing Ṽi given Ṽi+1 by sum-check
Let i ∈ I−d . The following lemma shows that for every z ∈ Fm , verifying a claimed value for Ṽi (z) can be
done by a sum-check protocol that only requires the values of Ṽi+1 on two points in Fm .
Lemma 5.2. For every i ∈ I−d , there exists a function β̃i : (Fm )3 → F that does not depend on the input x
to the circuit, such that the function Φi : (Fm )3 → F given by
Φi (z, w0 , w1 ) = β̃i (z, w0 , w1 ) Ṽi+1 (w0 ) Ṽi+1 (w1 )
satisfies:
T HEORY OF C OMPUTING, Volume 10 (5), 2014, pp. 107–131 117
G ILLAT KOL AND R AN R AZ
1. ∀z ∈ Fm : Ṽi (z) = ∑ Φi (z, w0 , w1 );
w0 ,w1 ∈Hm
2. Φi is of degree at most 2 (h − 1) in each of its 3m variables.
Proof. Fix i ∈ I−d , let z, w0 , w1 ∈ Fm , and let βi : Fm ×(Hm )2 → F be the function promised by Lemma 5.1.
We denote by β̃i : (Fm )3 → F the low-degree extension of βi (z, w0 , w1 ) with respect to w0 and w1 . That
is, fix z ∈ Fm , and let βi,z : H2m → F be given by βi,z (w0 , w1 ) = βi (z, w0 , w1 ). Let β̃i,z : F2m → F be the
low-degree extension of βi,z . Finally, let β̃i (z, w0 , w1 ) = β̃i,z (w0 , w1 ).
Due to Lemma 5.1, it holds that
∀z ∈ Fm : Ṽi (z) = ∑ Φi (z, w0 , w1 ) .
w0 ,w1 ∈Hm
Furthermore, Φi (z, w0 , w1 ) is of low degree in each of its 3m variables, as the following argument
demonstrates. Let z = z1 . . . zm , w0 = w0,1 . . . w0,m , w1 = w1,1 . . . w1,m , and fix j ∈ [m]. Since β̃i is the
low-degree extension of βi (with respect to w0 and w1 ), it is of degree at most h − 1 in w0, j and w1, j . Since
Ṽi+1 is a low-degree extension of Vi+1 , it is of degree at most h − 1 in each of its m variables. Conclude
that Φi is of degree at most 2 (h − 1) in w0, j and w1, j .
Fix w0 , w1 ∈ Hm . By Lemma 5.1, the function βi (z1 . . . zm , w0 , w1 ) is a polynomial of degree h − 1 in
z j . Again, using the fact that β̃i is the low-degree extension of βi , it holds that β̃i (z, w0 , w1 ) is a linear
combination of the values βi (z, w00 , w01 ) (w00 , w01 ∈ Hm ) with coefficients that depend only on w0 , w1 , w00 , w01
(and are independent of z).
For every w00 , w01 ∈ Hm , the value βi (z, w00 , w01 ) is a polynomial of degree at most h − 1 in z j . Thus,
any linear combination of these values, and in particular β̃i (z, w0 , w1 ), is a polynomial of degree at most
h − 1 in z j . Conclude that Φi is of degree at most h − 1 in z j .
For i ∈ I−d , let Φi be the function defined in Lemma 5.2. For every i ∈ I−d and ` ∈ L, we define the
partial-sum function Φi,` (z, x) : Fm × F` → F as follows:
Φi,` (z, x1 . . . x` ) = ∑ Φi (z, x1 . . . x2m ) .
x`+1 ,...,x2m ∈H
Note that Φi,` (z1 . . . zm , x1 . . . x` ) is of degree at most 2 (h − 1) in each of its m + ` variables, and that
Ṽi (z) = Φi,0 (z, φ ) (5.1)
and
Φi (z, w0 , w1 ) = Φi,2m (z, w0 ◦ w1 ) . (5.2)
Also observe that a sum-check protocol can be used to reduce the computation of Ṽi (z) = Φi,0 (z, φ ) to
the computation of Φi (z, w0 , w1 ) = Φi,2m (z, w0 ◦ w1 ). Since β̃i does not depend on the input to the circuit
x, the player can compute Φi,2m (z, w0 ◦ w1 ) by herself given Ṽi+1 (w0 ) and Ṽi+1 (w1 ). In other words, the
evaluation of Ṽi on z can be reduced, by a sum-check protocol, to the computation of Ṽi+1 on the pair of
points w0 , w1 ∈ Fm .
T HEORY OF C OMPUTING, Volume 10 (5), 2014, pp. 107–131 118
C OMPETING -P ROVERS P ROTOCOLS FOR C IRCUIT E VALUATION
6 One-round protocol
In this section we prove Theorem 3.4. Namely, we show that for any f ∈ Fs,d it holds that f ∈
QCCPε,LDEs (1, d · poly log (s) , 1), where ε = 1/log(s). We describe a protocol that, given a size s
depth d circuit C on n bits and an input x ∈ {0, 1}n , outputs C (x) with probability at least 1 − ε. The
protocol consists of a single round, requires the exchange of d · poly log (s) bits, and makes a single query
to x̃ = LDEs (x).
The protocol consists of three steps: (i) The player sends questions to the provers (Section 6.1).
(ii) The provers reply (Section 6.2). (iii) Using the provers’ answers, the player decides on the value of
C (x) (Section 6.4). Section 6.3 contains observations that are used in Section 6.4 in order to show the
correctness of the player’s decision.
We assume that one of the provers claims that C (x) = 1, while the other claims C (x) = 0. Otherwise,
if both claim that C (x) = b (b ∈ {0, 1}), then since at least one of the provers is truthful, it must be the
case that indeed C (x) = b. In the protocol below we assume that the player knows the identity of the
prover claiming that C (x) = 1 (we call him P1 ), and the identity of the prover claiming that C (x) = 0 (we
call him P0 ). This assumption is justified as the player may require each prover to add his claimed value
for C (x) to his reply message. (The proof for the case that P1 claims C (x) = 0 and P0 claims C (x) = 1 is
similar.)
For the rest of the section let β ∈ F\H be an arbitrary element.
Remark 6.1 (Functions representation). During the execution of the protocol, the participants exchange
a set of curves and polynomials. Each of the exchanged curves is of degree (at most) h. Each exchanged
polynomial is either of the form F (r) = Ṽi (Z (r)) (i ∈ I) or of the form F (r,t) = Φi,` (Z (r) , X (t))
(i ∈ I−d , ` ∈ L), where Z (r) : F → Fm and X (t) : F → F` are two previously exchanged degree-h curves.
In other words, the exchanged polynomials are all restrictions of Ṽi and Φi,` to degree-h curves.
The polynomial Ṽi (z) is of degree at most h − 1 in each of its m variables, as it is the low-degree
extension of Vi . The polynomial Φi,` (z, x1 . . . x` ) is of degree at most 2 (h − 1) in each of its m + ` variables
(see Section 5.2). Therefore, each exchanged polynomial is of total degree at most h · 2 (h − 1) · (m + `) <
6mh2 . We require each such polynomial to be sent in a canonical representation, as a sequence of at most
6mh2 coefficients. Curves will be sent as sequences of polynomials.
6.1 The player’s questions
For every i ∈ I−d and ` ∈ L, the player constructs a degree-h curve Ci,` : F → F` , and a line Di,` : F → F` .
For every i ∈ I, the player constructs a degree-2 curve Zi : F → Fm , and a point zi ∈ Fm . The curves Zi
(i ∈ I) and Ci,` (i ∈ I−d , ` ∈ L) are given to P1 , while the points zi (i ∈ I) and the lines Di,` (i ∈ I−d , ` ∈ L)
are given to P0 .
Let Z0 : F → Fm be the constant 0m curve. That is, ∀r ∈ F : Z0 (r) = 0m . Randomly select ζ0 ∈R
F\ {0, 1}. Set z0 = Z0 (ζ0 ) = 0m .
Recall that β ∈ F\H is an arbitrary element. For i = 0, . . . , d − 1 we construct the additional needed
curves and points in the following order:
The curves (Ci,` )`∈L and (Di,` )`∈L are constructed recursively:
T HEORY OF C OMPUTING, Volume 10 (5), 2014, pp. 107–131 119
G ILLAT KOL AND R AN R AZ
• Construct Ci,0 , Di,0 : Define Ci,0 , Di,0 : F → F0 by ∀t ∈ F : Ci,0 (t) = Di,0 (t) = φ .
• Construct Ci,` given Di,`−1 (` ∈ L−0 ):
1. Randomly select δi,`−1 ∈R F\ {0} and set ai,`−1 = Di,`−1 (δi,`−1 ).
2. Let Ci,` be a random degree-h curve satisfying ∀α ∈ H : Ci,` (α) = ai,`−1 ◦ α, chosen as
follows: Randomly select ci,` ∈R F` , and let Ci,` be the degree-h curve satisfying ∀α ∈ H :
Ci,` (α) = ai,`−1 ◦ α and Ci,` (β ) = ci,` .
• Construct Di,` given Ci,` (` ∈ L−0 ):
1. Randomly select γi,` ∈R F\H.
2. Let Di,` be a random line satisfying Di,` (0) = Ci,` (γi,` ), chosen as follows: Randomly select
di,` ∈R F` , and let Di,` be the line satisfying Di,` (0) = Ci,` (γi,` ) and Di,` (1) = di,` .
The curve Zi+1 is constructed as follows:
1. Randomly select δi,2m ∈R F\ {0} and set ai,2m = Di,2m (δi,2m ). Denote ai,2m = wi,0 ◦ wi,1 where
wi,0 , wi,1 ∈ Fm .
2. Let Zi+1 be a random degree-2 curve satisfying Zi+1 (0) = wi,0 and Zi+1 (1) = wi,1 , chosen as
follows: Randomly select wi+1 ∈R Fm , and let Zi+1 be the degree-2 curve satisfying Zi+1 (0) = wi,0 ,
Zi+1 (1) = wi,1 and Zi+1 (2) = wi+1 .
The point zi+1 is selected as follows: Randomly select ζi+1 ∈R F\ {0, 1}. Set zi+1 = Zi+1 (ζi+1 ).
6.2 The provers’ answers
P1 ’s reply. For i ∈ I−d and ` ∈ L−0 , denote by T ∗i,` : F × F → F the polynomial
T ∗i,` (r,t) = Φi,` (Zi (r) ,Ci,` (t)) .
For i ∈ I−0 , denote by U ∗i : F → F the polynomial U ∗i (r) = Ṽi (Zi (r)). P1 replies with a set of polynomials
Ti,` : F × F → F (i ∈ I−d , ` ∈ L−0 ), and a set of polynomials U i : F → F (i ∈ I−0 ). The honest P1 should
reply with Ti,` = T ∗i,` and Ui = U ∗i .
P0 ’s reply. For i ∈ I−d and ` ∈ L, denote by Q∗i,` : F → F the polynomial
Q∗i,` (t) = Φi,` (zi , Di,` (t)) .
P0 replies with a set of polynomials Qi,` : F → F (i ∈ I−d , ` ∈ L). The honest P0 should reply with
Qi,` = Q∗i,` .
T HEORY OF C OMPUTING, Volume 10 (5), 2014, pp. 107–131 120
C OMPETING -P ROVERS P ROTOCOLS FOR C IRCUIT E VALUATION
6.3 Propositions
This section contains propositions that will be useful in the analysis of the player’s decision in Section 6.4.
Propositions 1 and 2 claim that the information given to P1 by the player is independent of the pairs of
values (ζi , γi,` ). Propositions 3 and 4 claim that the information given to P0 by the player is independent
of the values δi,` .
Denote by Inf1 and Inf0 the random variables describing the information given to P1 and P0 (respec-
tively):
Inf1 = (Zi )i∈I , (Ci,` )i∈I−d ,`∈L and Inf0 = (zi )i∈I , (Di,` )i∈I−d ,`∈L .
In the proofs below, whenever we say “object” we mean a field element, point or curve selected by the
player while constructing the questions to the provers.
Proposition 1. Let i ∈ I−d and ` ∈ L−0 . It holds that γi,` is independent of Inf1 . That is, γi,` is uniformly
distributed in F\H, even given Inf1 .
Proof. Let X be a random variable consisting of all the curves Zi0 and Ci0 ,`0 selected by the player before
γi,` is selected. Let Y be a random variable consisting of all the curves Zi0 and Ci0 ,`0 selected after γi,` .
Clearly, γi,` is selected independently of X. We will show that Y is independent of the pair (X, γi,` ). This
implies that Inf1 is independent of γi,` .
The line Di,` was selected to be a random line satisfying Di,` (0) = Ci,` (γi,` ). Therefore, for every
fixed δ ∈ F\ {0}, the value Di,` (δ ) is uniformly distributed in F` , even given all the objects selected
before Di,` . In particular, ai,` = Di,` (δi,` ) is uniformly distributed in F` , even given all objects selected
before Di,` .
The player can select all the objects selected after Di,` by only knowing ai,` . Since ai,` is uniformly
distributed in F` , even given all objects selected before Di,` , it holds that the objects selected after Di,` are
independent of all objects selected before Di,` . In particular, Y is independent of the pair (X, γi,` ).
Proposition 2. Let i ∈ I−d and ` ∈ L−0 . It holds that ζi is independent of the pair (Inf1 , γi,` ). That is, ζi is
uniformly distributed in F\ {0, 1}, even given (Inf1 , γi,` ). Furthermore, ζd is independent of Inf1 .
Proof. Clearly, ζi is uniformly distributed, even given all the previously selected objects. In addition,
all the objects selected after ζi (and after zi was set) are independent of all the objects selected up to ζi
(including ζi ).
Proposition 3. Let i ∈ I−d and ` ∈ L−2m . It holds that δi,` is independent of Inf0 . That is, δi,` is uniformly
distributed in F\ {0}, even given Inf0 .
Proof. Let X be a random variable consisting of all the points zi0 and curves Di0 ,`0 selected by the player
before δi,` is selected. Let Y be a random variable consisting of all the points zi0 and curves Di0 ,`0 selected
after δi,` . Clearly, δi,` is selected independently of X. We will show that Y is independent of the pair
(X, δi,` ). This implies that Inf0 is independent of δi,` .
The curve Ci,`+1 was selected to be a random degree-h curve satisfying ∀α ∈ H : Ci,`+1 (α) = ai,` ◦ α.
Therefore, for every fixed γ ∈ F\H, the value Ci,`+1 (γ) is uniformly distributed in F`+1 , even given all
objects selected before Ci,`+1 . In particular, Ci,`+1 (γi,`+1 ) is uniformly distributed in F`+1 , even given all
objects selected before Ci,`+1 .
T HEORY OF C OMPUTING, Volume 10 (5), 2014, pp. 107–131 121
G ILLAT KOL AND R AN R AZ
The player can select all the objects selected after Ci,`+1 by only knowing Ci,`+1 (γi,`+1 ). Since
Ci,`+1 (γi,`+1 ) is uniformly distributed in F`+1 , even given all objects selected before Ci,`+1 , it holds that
the objects selected after Ci,`+1 are independent of all objects selected before Ci,`+1 . In particular, Y is
independent of the pair (X, δi,` ).
Proposition 4. Let i ∈ I−d . It holds that δi,2m is independent of Inf0 . That is, δi,2m is uniformly distributed
in F\ {0}, even given Inf0 .
Proof. Clearly, δi,2m is uniformly distributed, even given all the previously selected objects in Inf0 . In
addition, all the objects selected after zi+1 are independent of all the objects selected up to zi+1 (including
zi+1 ). Therefore, it suffices to show that zi+1 itself is independent of all the objects selected up to δi,2m
(including δi,2m ).
The curve Zi+1 was selected to be a random degree-2 curve satisfying Zi+1 (0) = wi,0 and Zi+1 (1) =
wi,1 . Therefore, for every fixed ζ ∈ F\ {0, 1}, the value Zi+1 (ζ ) is uniformly distributed in Fm , even
given all the objects selected before Zi+1 . In particular, zi+1 = Zi+1 (ζi+1 ) is uniformly distributed in Fm ,
even given all the objects selected up to δi,2m (including δi,2m ).
Let i ∈ I−d and ` ∈ L−2m . Proposition 5 shows that if P1 responds with the correct polynomial Ti,`+1 ,
then the player can compute by herself the correct value of Qi,` (δi,` ).
Proposition 5. Let i ∈ I−d and ` ∈ L−2m . It holds that
∑ T ∗i,`+1 (ζi , α) = Q∗i,` (δi,` ) .
α∈H
Proof.
∑ T ∗i,`+1 (ζi , α) = ∑ Φi,`+1 (Zi (ζi ) ,Ci,`+1 (α))
α∈H α∈H
= ∑ Φi,`+1 (zi , ai,` ◦ α)
α∈H
= Φi,` (zi , ai,` )
= Φi,` (zi , Di,` (δi,` ))
= Q∗i,` (δi,` ) .
Fix strategies for P1 and P0 . Formally, a strategy for P1 is a probabilistic algorithm that gets the sets
of curves Zi and Ci,` as inputs, and outputs the sets of polynomials Ti,` and Ui . A strategy for P0 is a
probabilistic algorithm that gets the set of points zi and set of curves Di,` as inputs, and outputs the set of
polynomials Qi,` . For the rest of the section probabilities will be taken over P1 ’s random string R1 , P0 ’s
random string R0 , and the player’s random string.
Provers following the reply protocol should each send a set of polynomials to the player. The player’s
decision protocol checks the correctness of these polynomials in a pre-determined order. Given the sets
of polynomials sent by the provers, we call a pair F = ( j, G) a “reply polynomial” if the jth polynomial
to be checked by the player is G. We will sometimes abuse notations and refer to G itself as a reply
polynomial (suppressing the index j).
T HEORY OF C OMPUTING, Volume 10 (5), 2014, pp. 107–131 122
C OMPETING -P ROVERS P ROTOCOLS FOR C IRCUIT E VALUATION
Let F = ( j, G) be a reply polynomial. Denote by EF the event that F is the first incorrect reply
polynomial checked by the protocol. In other words, EF is the event that all the j − 1 reply polynomials
checked prior to F are correct, but F is incorrect (that is, had the provers followed the reply protocol, the
jth polynomial to be checked by the player should not have been G).
Proposition 6. Let F be a reply polynomial sent by P1 . Let X be a random variable that is independent
of the pair (Inf1 , R1 ). Then, X is independent of (Inf1 , R1 , IEF ), where IEF is the random variable that gets
the value 1 if EF occurs, and 0 otherwise.
The same holds when the parts of P1 and P0 are switched.
Proof. Assume that EF occurs with positive probability. P1 is dishonest as he sent an incorrect polynomial
F with positive probability. Since we assume that at least one prover is honest, it must be P0 . Therefore,
all the reply polynomials sent by P0 are correct. This implies that the event EF depends solely on Inf1
and R1 . That is, IEF is a function of Inf1 and R1 . Since X is independent of (Inf1 , R1 ), it is independent of
(Inf1 , R1 , IEF ).
6.4 The player’s decision
First, the player queries x̃ (zd ); denote the value of this query by vd . Note that x̃ = LDEs (x) = Ṽd , and
thus vd = Ṽd (zd ). Next, the player iterates over the layers of C, from the layer adjacent to the input layer
(layer i = d − 1), to the output layer (layer i = 0). The iteration that handles layer i (simply referred
to as “iteration i”) assumes that the variable vi+1 is set to the value Ṽi+1 (zi+1 ). The goal of iteration i
is to calculate the value vi = Ṽi (zi ). At the end of the loop the player returns v0 , which is, supposedly,
v0 = Ṽ0 (z0 ) = Ṽ0 (0m ) = C (x).
In order to compute vi , iteration i proceeds in a series of “check steps” (tests), each designed to check
the correctness of one of the reply polynomials for layer i. Let F be a reply polynomial, and let SF be the
check step designed to check F. If SF succeeds, the protocol proceeds to the next check step. If SF fails,
the player outputs the value of C (x) claimed by the prover that did not send F. The reason is that we
assume that at least one of the provers is honest. Since F is incorrect, the prover that did not send F must
be the honest one.
Recall that EF denotes the event that F is the first incorrect reply polynomial checked by the protocol.
Denote by CF the event that all reply polynomials checked up to F (including F) are correct. In order to
prove Theorem 3.4 it suffices to show that, for every reply polynomial F, the following holds:
1. If CF occurs, then SF always succeeds.
2. If EF occurs, then SF fails with probability at least 1 − ε.
3. If all the reply polynomials are correct, then the player returns C (x).
Next, we describe the check steps that constitute iteration i, and show that each of them satisfies both (1)
and (2). Assume for simplicity that the reply polynomial F depends on only one variable. The check step
SF does the following: It computes F (σ ), where σ ∈ F is a field element that cannot be predicted by
the prover that sent F. It then compares F (σ ) against the supposed value of F ∗ (σ ). (This latter value is
computed by earlier check steps.) If F is correct then F = F ∗ , and the test succeeds. If F is incorrect, F
T HEORY OF C OMPUTING, Volume 10 (5), 2014, pp. 107–131 123
G ILLAT KOL AND R AN R AZ
and F ∗ are different low-degree polynomials. Thus, it is likely that F (σ ) 6= F ∗ (σ ), and the test is likely
to fail.
We assume by induction (on the layers i) that if all the reply polynomials checked by iterations
d − 1, . . . , i + 1 are correct, then at the beginning of iteration i it holds that vi+1 = Ṽi+1 (zi+1 ).
Check Ui+1 : Check Ui+1 (ζi+1 ) = vi+1 . If not, return 0.
If CUi+1 occurs: By assumption, vi+1 = Ṽi+1 (zi+1 ) = Ṽi+1 (Zi+1 (ζi+1 )) = U ∗i+1 (ζi+1 ). Since Ui+1 is
correct, the test passes.
If EUi+1 occurs: Using Propositions 2 and 6, ζi+1 is uniformly distributed in F\ {0, 1}, even given
Inf1 , R1 and EUi+1 . Since Ui+1 only depends on Inf1 and R1 , it holds that when EUi+1 occurs, ζi+1 is
uniformly distributed, even given Ui+1 .
As explained above, vi+1 = U ∗i+1 (ζi+1 ). Since Ui+1 is incorrect, Ui+1 6= U ∗i+1 . Since both Ui+1 and
U ∗i+1 are of degrees less than 6mh2 (see the remark regarding functions representation at the beginning of
the section), U i+1 (ζ ) can only agree with Ui+1∗ (ζ ) on less than 6mh2 elements ζ ∈ F.
Recall that when EUi+1 occurs, ζi+1 is uniformly distributed in F\ {0, 1}, even given Ui+1 , and we get
∗ (ζ 2 3
that the probability that U i+1 (ζi+1 ) = Ui+1 i+1 ) = vi+1 is less than 6mh /|F\ {0, 1}|. Since |F| ≥ 12mh ,
it holds that
6mh2 6mh2 1 1
< 1 ≤ ≤ =ε.
|F\ {0, 1}| 2 |F|
h log (s)
Check Qi,2m : Calculate the supposed value φi,2m of Φi,2m (zi , ai,2m ) = Φi (zi , wi,0 ◦ wi,1 ) (see equa-
tion (5.2) and Lemma 5.2) using Ui+1 (0) as Ṽi+1 (wi,0 ) and Ui+1 (1) as Ṽi+1 (wi,1 ). Check Qi,2m (δi,2m ) =
φi,2m . If not, return 1.
If CQi,2m occurs: Since Ui+1 is correct Ui+1 (0) = U ∗i+1 (0) = Ṽi+1 (Zi+1 (0)) = Ṽi+1 (wi,0 ), and simi-
larly Ui+1 (1) = Ṽi+1 (wi,1 ). Thus, φi,2m is set to Φi,2m (zi , ai,2m ) = Φi,2m (zi , Di,2m (δi,2m )) = Q∗i,2m (δi,2m ).
Since Qi,2m is correct, the test passes.
If EQi,2m occurs: Using Propositions 4 and 6, δi,2m is uniformly distributed in F\ {0}, even given Inf0 ,
R0 and EQi,2m . Since Qi,2m only depends on Inf0 and R0 , it holds that when EQi,2m occurs, δi,2m is uniformly
distributed, even given Qi,2m .
As explained above, φi,2m is set to Q∗i,2m (δi,2m ). Since Qi,2m is incorrect, Qi,2m 6= Q∗i,2m . An argument
similar to the one used in check step SUi+1 shows that the probability that Qi,2m (δi,2m ) = Q∗i,2m (δi,2m ) =
φi,2m is less than ε.
Check Ti,2m : Check Ti,2m (ζi , γi,2m ) = Qi,2m (0). If not, return 0.
If CTi,2m occurs:
∗
Ti,2m (ζi , γi,2m ) = Φi,2m (Zi (ζi ) ,Ci,2m (γi,2m )) = Φi,2m (zi , Di,2m (0)) = Q∗i,2m (0) .
Since Qi,2m and Ti,2m are correct, the test passes.
If ETi,2m occurs: Using Propositions 1, 2 and 6, the pair (ζi , γi,2m ) is uniformly distributed in
(F\ {0, 1}) × (F\H), even given Inf1 , R1 and ETi,2m . Since Ti,2m only depends on Inf1 and R1 , it holds that
when ETi,2m occurs, the pair (ζi , γi,2m ) is uniformly distributed, even given Ti,2m .
T HEORY OF C OMPUTING, Volume 10 (5), 2014, pp. 107–131 124
C OMPETING -P ROVERS P ROTOCOLS FOR C IRCUIT E VALUATION
Since Qi,2m is correct but Ti,2m is incorrect, it holds that Qi,2m = Q∗i,2m and Ti,2m 6= T ∗i,2m . Using the
Schwartz-Zippel Lemma (Lemma 4.1), since both Ti,2m and T ∗i,2m are of total degree less than 6mh2 (see
the remark regarding functions representation at the beginning of the section), Ti,2m (ζ , γ) can only agree
∗ (ζ , γ) on less than 6mh2 /|F|-fraction of the points (ζ , γ) ∈ F2 .
with Ti,2m
Recall that when ETi,2m occurs, the pair (ζi , γi,2m ) is uniformly distributed in (F\ {0, 1}) × (F\H), even
given Ti,2m , and we get that the probability that Ti,2m (ζi , γi,2m ) = T ∗i,2m (ζi , γi,2m ) = Q∗i,2m (0) = Qi,2m (0) is
less than
6mh2 · |F|
.
|(F\ {0, 1}) × (F\H)|
Since |F| ≥ 12mh3 , it holds that
6mh2 · |F| 6mh2 · |F| 1 1
< 1 2 ≤ ≤ =ε.
|(F\ {0, 1}) × (F\H)| |F| h log (s)
2
Check Qi,2m−1 : Check Qi,2m−1 (δi,2m−1 ) = ∑α∈H Ti,2m (ζi , α). If not, return 1.
If CQi,2m−1 occurs: Using Proposition 5, since Ti,2m and Qi,2m−1 are correct, we have that the test
passes.
If EQi,2m−1 occurs: Using Propositions 3 and 6, δi,2m−1 is uniformly distributed in F\ {0}, even given
Inf0 , R0 and EQi,2m−1 . Since Qi,2m−1 only depends on Inf0 and R0 , it holds that when EQi,2m−1 occurs,
δi,2m−1 is uniformly distributed, even given Qi,2m−1 .
Using Proposition 5, since Ti,2m is correct,
∑ T i,2m (ζi , α) = Q∗i,2m−1 (δi,2m−1 ) .
α∈H
Since Qi,2m−1 is incorrect, Qi,2m−1 6= Q∗i,2m−1 . An argument similar to the one used in check step SUi+1
shows that the probability that Qi,2m−1 (δi,2m−1 ) = Q∗i,2m−1 (δi,2m−1 ) = ∑α∈H Ti,2m (ζi , α) is less than ε.
Repeat the last two steps to check Ti,2m−1 , Qi,2m−2 , . . . , Ti,1 , Qi,0 .
Set vi = Qi,0 (β ). Note that if Qi,0 is correct, then using equation (5.1), vi = Qi,0 (β ) = Q∗i,0 (β ) =
Φi,0 (zi , Di,0 (β )) = Ṽi (zi ), and the induction hypothesis holds. In particular, if all reply polynomials are
correct then v0 = Ṽ0 (z0 ) = Ṽ0 (0m ) = C (x).
7 Trade-off protocol
In this section we prove Theorem 3.3. We describe a protocol that given a size s depth d circuit C on
n bits, and an input x ∈ {0, 1}n , outputs C (x) with probability at least 1 − ε. The new protocol uses the
one-round protocol described in Section 6 as a building block. The new protocol consists of r rounds,
requires the exchange of d 1/r · poly log (s) bits, and makes a single query to LDEs (x).
1/r
Let 1 ≤ r ≤ blog (d)c. Set k = 2 d . The new protocol consists of two stages. The goal of the first
stage (Section 7.1) is to find two “close” layers i0 , i00 ∈ I with i0 > i00 and i0 − i00 ≤ k, such that the provers
T HEORY OF C OMPUTING, Volume 10 (5), 2014, pp. 107–131 125
G ILLAT KOL AND R AN R AZ
agree on a point on Ṽi0 , but disagree on a point on Ṽi00 . Note that such layers exist, as the provers agree on
the input x for C (and thus on LDEs (x) = Ṽd ), but disagree on the output C (x) (and therefore on Ṽ0 ).
Finding layers i0 and i00 is done by running a version of a binary search that in every round partitions
the search range into k (almost equal) intervals (instead of just two). Note that r − 1 search rounds suffice
in order to find such layers i0 and i00 satisfying i0 − i00 ≤ k: Each search round reduces the range of indices
searched by a factor of at least k/2. Thus, after r − 1 rounds we are left with a range of at most
−(r−1) m−(r−1) −(r−1)
k l
(d + 1) · = (d + 1) d 1/r ≤ 2d d 1/r ≤ 2d · d (1−r)/r = 2d 1/r ≤ k .
2
Let C0 be a subcircuit composed of layers i0 , . . . , i00 of C, and let x0 = Vi0 . The provers agree on a point
on the input layer LDEs (x0 ) = Ṽi0 of C0 , but disagree on a point on the output layer Ṽi00 of C0 .
Stage 2 of the new protocol (Section 7.2) runs the one-round protocol described in Section 6 with C0
and x0 as inputs in order to determine which of the provers is truthful.
7.1 Stage 1: Search
First, the player constructs questions for the provers as in Section 6.1. That is, the player constructs the
curves Ci,` and Di,` (i ∈ I−d and ` ∈ L), and the curves Zi and points zi (i ∈ I). For i ∈ I, let Ui∗ : F → F be
the function Ui∗ (r) = Ṽi (Zi (r)), and let u∗i ∈ F be the value u∗i = Ṽi (zi ).
Next, the protocol proceeds in r − 1 search rounds. In each round the player constructs a set of k
indices M ⊆ I (M contains indices that partition the remaining search range into almost equal parts).
The player sends the curves Zi (i ∈ M) to P1 , and the points zi (i ∈ M) to P0 . Prover P1 replies with the
functions Ui : F → F (i ∈ M), and P0 replies with the values ui ∈ F (i ∈ M). The honest P1 should reply
with Ui = Ui∗ , and the honest P0 should reply with ui = u∗i .
The goal of Stage 1 is to find two layers i0 > i00 ∈ I with i0 − i00 ≤ k such that Ui0 (ζi0 ) = ui0 , but
Ui00 (ζi00 ) 6= ui00 . By comparing the values of Ui (ζi ) and ui (i ∈ M), the player decides on the smaller search
range for the next round, until the desired layers i0 and i00 are found.
Note that during the first round the player checks the provers agreement on the input and output
layers. If U0 (ζ0 ) = u0 (which indicates that the provers agree on the output C (x)), then since at least one
of the provers is truthful, the player outputs u0 . If Ud (ζd ) 6= ud (which indicates that the provers disagree
on a point in the low-degree extension x̃ = Ṽd of the input), the player queries x̃ (zd ). Since at least one
of the provers is truthful, the queried value x̃ (zd ) is either Ud (ζd ) or ud . If x̃ (zd ) = Ud (ζd ), the player
outputs 1. If x̃ (zd ) = ud , the player outputs 0.
7.2 Stage 2: Run the one-round protocol
Let C0 be the circuit composed of layers i0 , . . . , i00 of C. Run the one-round protocol on C0 and x0 = Vi ,
using the questions that were already constructed in Stage 1, and with the following changes. Return the
obtained value.
• Instead of querying LDEs (x0 ) at the point zi0 , use the value ui0 .
• Instead of returning the computed value v0 in the last step, return 0 if v0 = ui00 and 1 otherwise.
T HEORY OF C OMPUTING, Volume 10 (5), 2014, pp. 107–131 126
C OMPETING -P ROVERS P ROTOCOLS FOR C IRCUIT E VALUATION
8 Very efficient player
In this section we prove Theorem 3.6. That is, we assume in addition to the previous assumptions that the
circuit C is log (s)-space uniform and show that in this case the player can run in time d 1/r poly log (s).
First observe that each of the check steps of the protocol described in Section 6, excluding the check
steps SQi,2m (i ∈ I−d ), can be preformed by the player in poly log (s) time and without knowing the circuit
C. The only check steps that require knowing the circuit C are the check steps SQi,2m (i ∈ I−d ), as explained
next.
The check step SQi,2m (i ∈ I−d ) requires the player to compute the value Φi (zi , wi,0 , wi,1 ) given
the (supposed) values of Ṽi+1 (wi,0 ) and Ṽi+1 (wi,1 ). Recall that Φi was defined in Lemma 5.2 as
Φi (z, w0 , w1 ) = β̃i (z, w0 , w1 ) Ṽi+1 (w0 ) Ṽi+1 (w1 ). Therefore, in order to compute Φi (zi , wi,0 , wi,1 ), the
player needs to know β̃i (zi , wi,0 , wi,1 ). Note that β̃i depends on the circuit C, and that for a general size s
depth d circuit C, the evaluation of β̃i may be pricey and require poly (s) time. Moreover, even in the case
where the circuit C is log (s)-space uniform, the evaluation of β̃i by the player may require poly (s) time.
The crucial observation is that in the case of a log (s)-space uniform circuit C, the function β̃i is
computable in space O (log (s)). Note, that the inputs for the function β̃i are themselves of length
O (log (s)). Hence, the function β̃i can be computed in space polynomial in the length of its inputs, that is
β̃i ∈ PSPACE.
Recall that for every language in PSPACE, Feige and Kilian give a one-round competing-provers
protocol that only requires polynomial communication complexity [3]. Therefore, there is a one-round
competing-provers protocol that computes β̃i , with communication complexity polynomial in the length
of the inputs for β̃i , that is, communication complexity of poly log (s). Thus, the player cannot evaluate
the function β̃i in time poly log (s) by herself, but she can do that with the help of the two competing
provers.
This naturally leads to an (r + 2)-round protocol (rather than the r-round protocol that we want). We
start by describing the (r + 2)-round protocol and then show how to collapse the last two rounds of the
protocol to round r of the protocol.
Remark 8.1. We remark that when applying the competing-provers protocol of Feige and Kilian for
log (s)-space, the provers’ running time may be super-polynomial in s, and thus not efficient enough for
our purposes. Therefore, for the rest of the paper we consider an updated version of the Feige and Kilian
protocol, obtained using our protocol, as follows. A similar approach was taken in [5] (and see also [7]).
By Lemma 3.4.3 of [10], any log (s)-space language has a poly(s)-size poly log(s)-depth arithmetic
circuit C, for which the associated functions β̃i have poly log(s)-size arithmetic circuits. Therefore, the
following is a competing-provers protocol for log (s)-space, with efficient parties: Given a log (s)-space
language, the parties run our 1-round competing-provers protocol with the circuit C. Observe that since C
has poly(s)-size and poly log(s)-depth, the provers run in time poly (s). In addition, since the associated
functions β̃i have poly log(s)-size circuits, the player can evaluate β̃i by herself in poly log(s) time.
8.1 The (r + 2)-round protocol
The first r rounds of the protocol run the r rounds of the protocol of Section 7, except for the player’s
decision that is still not made. In order to make her decision, the player needs to evaluate β̃i (zi , wi,0 , wi,1 )
T HEORY OF C OMPUTING, Volume 10 (5), 2014, pp. 107–131 127
G ILLAT KOL AND R AN R AZ
for each of the at most k layers i ∈ {i00 , . . . , i0 − 1} that round r of the protocol considers (see Section 7.2).
In order to compute the needed values of β̃i (zi , wi,0 , wi,1 ), the player sends in round r + 1 the values
(zi , wi,0 , wi,1 ) (for i ∈ {i00 , . . . , i0 − 1}) to both provers, and asks each prover to reply with the values of
β̃i (zi , wi,0 , wi,1 ) (for i ∈ {i00 , . . . , i0 − 1}). If the provers agree on all the values β̃i (zi , wi,0 , wi,1 ), the player
knows that these values are correct (because at least one of the provers is honest), and can proceed with
her decision. If the provers disagree on one or more of the values β̃i (zi , wi,0 , wi,1 ), the player picks one
such value and applies in round r + 2 the PSPACE protocol of Feige and Kilian in order to identify the
correct value and decide which prover is honest.
Next, we show how to reduce the number of rounds from r + 2 to r.
8.2 Collapsing round r + 1 to round r
We now describe how to collapse round r + 1 of the protocol to round r. We cannot just send all the values
(zi , wi,0 , wi,1 ) (for i ∈ {i00 , . . . , i0 − 1}) to both provers at the beginning of round r, because this would give
each prover additional information that may enable him to cheat in round r.
Note, however, that at the beginning of round r, the prover P1 gets all the curves Zi (for i ∈ {i00 , . . . , i0 }).
Hence, for i ∈ {i00 , . . . , i0 − 1}, the prover P1 already knows the needed values of wi,0 , wi,1 (since Zi+1 (0) =
wi,0 and Zi+1 (1) = wi,1 ), aswell as the curve Zi that contains the point zi . Thus, we can just ask P1 for
the values of β̃i z0i , wi,0 , wi,1 for all the points z0i on the image of Zi .
In addition, at the beginning of round r, the prover P0 gets all the points zi as well as the curves Di,2m
(for i ∈ {i00 , . . . , i0 − 1}). Hence, for i ∈ {i00 , . . . , i0 − 1}, the prover P0 already knows the needed value of
zi , as well as the curve Di,2m that contains wi,0 ◦ w i,1 (since Di,2m (δi,2m ) = ai,2m = wi,0 ◦ wi,1 ). Thus, we
can just ask P0 for the values of β̃i zi , w0i,0 ◦ w0i,1 = β̃i zi , w0i,0 , w0i,1 for all the points w0i,0 ◦ w0i,1 on the
image of Di,2m .
Denote by A∗i , B∗i : F → F the following restrictions of the function β̃i to curves:
A∗i (t) = β̃i (Zi (t) , wi,0 , wi,1 ) and B∗i (t) = β̃i (zi , Di,2m (t))
(for i ∈ {i00 , . . . , i0 − 1}). The new protocol asks P1 to add to his reply message in round r the polynomials
A∗i , and asks P0 to add to his reply message in round r the polynomials B∗i (for i ∈ {i00 , . . . , i0 − 1}).
Suppose that P1 replied with Ai : F → F and that P0 replied with Bi : F → F (for i ∈ {i00 , . . . , i0 − 1}).
Observe that A∗i (ζi ) = β̃i (Zi (ζi ) , wi,0 , wi,1 ) = β̃i (zi , wi,0 , wi,1 ) and that B∗i (δi,2m ) = β̃i (zi , Di,2m (δi,2m )) =
β̃i (zi , ai,2m ) = β̃i (zi , wi,0 , wi,1 ). If for every i ∈ {i00 , . . . , i0 − 1} it holds that Ai (ζi ) = Bi (δi,2m ), the player
may use the value Ai (ζi ) = Bi (δi,2m ) as β̃i (zi , wi,0 , wi,1 ) and complete her decision protocol. Otherwise,
she proceeds to round r + 2.
Thus, we showed how to collapse round r + 1 of the protocol to round r.
8.3 Collapsing round r + 2 to round r
We now show how to collapse round r + 2 to round r, resulting in an r-round protocol. Round r + 2
is only reached if there exists j ∈ {i00 , . . . , i0 − 1} such that A j (ζ j ) 6= B j (δ j,2m ). In this case, in order to
decide which of the provers is truthful, the player runs the one-round protocol of [3].
In round r + 2, if reached, the player and provers run the one-round protocol of [3] in order to
determine the value of β˜j (z j , w j,0 , w j,1 ), for some j ∈ {i00 , . . . , i0 − 1} and some z j , w j,0 , w j,1 , where P0
T HEORY OF C OMPUTING, Volume 10 (5), 2014, pp. 107–131 128
C OMPETING -P ROVERS P ROTOCOLS FOR C IRCUIT E VALUATION
claims that the value is B = B j (δ j,2m ) and P1 claims that the value is A = A j (ζ j ). We would like to
collapse round r + 2 to round r, but the problem is that after the questions part of round r, the values of
j, z j , w j,0 , w j,1 , A, B are still not all known to the player or the provers. Note, however, that the number of
possibilities for these values is small from the point of view of each of the parties.
First note that j can take at most k values and A, B can each take at most p = |F| values. Also, after
the questions part of round r, the player and P1 already know w j,0 , w j,1 , and from the point of view of P0
the element w j,0 ◦ w j,1 can take at most p values (as w j,0 ◦ w j,1 is on the image of D j,2m , which is of size
at most p). As for z j , after the questions part of round r, the player and P0 already know z j , and from the
point of view of P1 the point z j can take at most p values (as z j is on the image of Z j , which is of size at
most p).
Let Λ be the set of all λ = j0 , z0j0 , w0j0 ,0 , w0j0 ,1 , A0 , B0 , such that, j0 ∈ {i00 , . . . , i0 − 1}, and z0j0 is on the
image of Z j0 , and w0j0 ,0 ◦ w0j0 ,1 is on the image of D j0 ,2m , and A0 , B0 ∈ F. For every λ ∈ Λ, let Q (λ ) =
(Q0 (λ ) , Q1 (λ )) be independently chosen pair of questions for the Feige-Kilian protocol corresponding to
λ (that is, for λ = j0 , z0j0 , w0j0 ,0 , w0j0 ,1 , A0 , B0 , the Feige-Kilian protocol for evaluating β˜j0 z0j0 , w0j0 ,0 , w0j0 ,1
when P0 claims that the value is B0 and P1 claims that the value is A0 ).
We can now collapse round r + 2 to round r as follows. In the questions part of round r, in addition
to the questions of the original protocol of Section 7, the player will send to P0 the pair (λ , Q0 (λ )), for
every λ = j , z j0 , w j0 ,0 , w j0 ,1 , A , B ∈ Λ, such that, z0j0 = z j0 . In the same way, the player will send to P1
0 0 0 0 0 0
the pair λ , Q1 (λ ) , for every λ = j0 , z0j0 , w0j0 ,0 , w0j0 ,1 , A0 , B0 ∈ Λ, such that, w0j0 ,0 , w0j0 ,1 = w j0 ,0 , w j0 ,1 .
Note that this does not give the provers additional information about the questions of the original protocol
of Section 7, because each prover could have constructed by himself questions that are distributed the
same as the additional questions that he received. In the reply part of round r, the prover P0 will send his
reply for the question Q0 (λ ) for the Feige-Kilian protocol corresponding to λ , for every pair (λ , Q0 (λ ))
that he received. This is in addition to the replies for the questions of the original protocol of Section 7,
and in addition to the functions Bi (required in order to collapse round r + 1 to round r, as discussed
above). In the same way, the prover P1 will send his reply for the question Q1 (λ ) for the Feige-Kilian
protocol corresponding to λ , for every pair (λ , Q1 (λ )) that he received (this is in addition to the replies
for the questions of the original protocol of Section 7, and in addition to the functions Ai ). Denote the
reply of P0 for the question Q0 (λ ) by R0 (λ ), and denote the reply of P1 for the question Q1 (λ ) by
R1 (λ ).
The decision made by the player is as follows. If for every i ∈ {i00 , . . . , i0 − 1} it holds that Ai (ζi ) =
Bi (δi,2m ), the player may use the value Ai (ζi ) = Bi (δi,2m ) as β̃i (zi , wi,0 , wi,1 ) and make her decision
according to the decision part of the original protocol of Section 7. If for some j ∈ {i00 , . . . , i0 − 1} it holds
that A j (ζ j ) 6= B j (δ j,2m ), the player decides according to the decision part of the Feige-Kilian protocol
corresponding to λ = ( j, z j , w j,0 , w j,1 , A j (ζ j ) , B j (δ j,2m )). This can be done since both provers have sent
replies R0 (λ ) and R1 (λ ), respectively.
Thus, we obtained an r-round protocol. Note that the size of Λ is k · poly log (s). Hence, the total
communication of the new protocol is d 1/r poly log (s), as required. Since the error of the original protocol
of Section 7 is ε, and the error of the protocol of Feige and Kilian is negligible and in particular is smaller
than ε/|Λ|, the total error of the new protocol is at most 2ε (by the union bound).
T HEORY OF C OMPUTING, Volume 10 (5), 2014, pp. 107–131 129
G ILLAT KOL AND R AN R AZ
8.4 Running time of the player
The running time of the player in the protocol described in the previous sections is d · poly log (s), rather
than the desired d 1/r poly log (s). This is because in the original protocol of Section 7, the player generates
for every layer i ∈ I−d the corresponding curves and points, at the beginning of the protocol, which takes
time d · poly log (s). To reduce the running time of the player to d 1/r poly log (s), note that the player only
needs to generate the curves and points corresponding to layers i ∈ I−d that are actually used.
More precisely, define the questions corresponding to layer i ∈ I−d to be the set of curves Ci,` and
Di,` (` ∈ L), the curve Zi+1 , and the point zi+1 . Note that the questions for layer i can be generated
independently of the questions for all the other layers.
We change the protocol, so that the player generates the questions corresponding to layer i only if
and when layer i is used. That is, the questions corresponding to layer i are generated during round
r0 ∈ [r] if and only if i is one 0
of the k indices queried in round r . Note that since only a total number of
O (r · k) ≤ O log (d) · d 1/r indices are queried, the player only spends d 1/r poly log (s) time constructing
questions.
References
[1] S COTT A ARONSON AND AVI W IGDERSON: Algebrization: A new barrier in complexity theory.
ACM Trans. on Computation Theory, 1(1):2, 2009. Preliminary version in STOC’08. See also at
ECCC. [doi:10.1145/1490270.1490272] 109, 110, 113
[2] R AN C ANETTI , B EN R IVA , AND G UY N. ROTHBLUM: Refereed delegation of computation.
Inform. and Comput., 226:16–36, 2013. Preliminary version in ICITS’12. See also at Cryptology
ePrint Archive. [doi:10.1016/j.ic.2013.03.003] 109, 115
[3] U RIEL F EIGE AND J OE K ILIAN: Making games short (extended abstract). In Proc. 29th STOC, pp.
506–516. ACM Press, 1997. [doi:10.1145/258533.258644] 108, 109, 110, 127, 128
[4] U RIEL F EIGE , A DI S HAMIR , AND M OSHE T ENNENHOLTZ: The noisy oracle problem. In
Proc. 8th Ann. Internat. Crypto. Conf. (CRYPTO’88), volume 403 of LNCS, pp. 284–296, 1988.
[doi:10.1007/0-387-34799-2_22] 108
[5] S HAFI G OLDWASSER , YAEL TAUMAN K ALAI , AND G UY N. ROTHBLUM: Delegating com-
putation: interactive proofs for muggles. In Proc. 40th STOC, pp. 113–122. ACM Press, 2008.
[doi:10.1145/1374376.1374396] 108, 109, 110, 114, 116, 127
[6] YAEL TAUMAN K ALAI AND R AN R AZ: Interactive PCP. In Proc. 35th Internat. Colloq. on
Automata, Languages and Programming (ICALP’08), volume 5126 of LNCS, pp. 536–547. Springer,
2008. See also at ECCC. [doi:10.1007/978-3-540-70583-3_44] 108
[7] YAEL TAUMAN K ALAI , R AN R AZ , AND RON D. ROTHBLUM: How to delegate computations:
The power of no-signaling proofs. In Proc. 46th STOC, pp. 485–494. ACM Press, 2014. See also at
ECCC. [doi:10.1145/2591796.2591809] 127
T HEORY OF C OMPUTING, Volume 10 (5), 2014, pp. 107–131 130
C OMPETING -P ROVERS P ROTOCOLS FOR C IRCUIT E VALUATION
[8] G ILLAT KOL AND R AN R AZ: Competing provers protocols for circuit evaluation. In Proc. 4th
Symp. Innovations in Theoretical Computer Science (ITCS’13), pp. 473–484. ACM Press, 2013.
See also at ECCC. [doi:10.1145/2422436.2422487] 107
[9] DAPHNE KOLLER AND N IMROD M EGIDDO: The complexity of two-person zero-sum games
in extensive form. Games and Economic Behavior, 4(4):528–552, 1992. [doi:10.1016/0899-
8256(92)90035-Q] 108
[10] G UY N. ROTHBLUM: Delegating Computation Reliably: Paradigms and Constructions. Ph. D.
thesis, Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science,
2009. DSpace@MIT. 127
AUTHORS
Gillat Kol
Institute for Advanced Study (IAS), Princeton, NJ
gillat kol gmail com
Ran Raz
Weizmann Institute of Science, Israel
ran raz mail gmail com
http://www.wisdom.weizmann.ac.il/~/ranraz/
ABOUT THE AUTHORS
G ILLAT KOL is a postdoctoral researcher at the School of Mathematics at the Institute for
Advanced Study (IAS), Princeton. She received her Ph. D. in 2013 from the Weizmann
Institute, Israel under the supervision of Irit Dinur. Her main research area is complexity
theory, with a focus on Information Theory and Interactive Communication.
R AN R AZ received his Ph. D. in 1992 from Hebrew University under the supervision of
Michael Ben-Or and Avi Wigderson. Since 1994, he has been a faculty member in the
Faculty of Mathematics and Computer Science at the Weizmann Institute. His main
research area is complexity theory, with emphasis on proving lower bounds for computa-
tional models. More specifically, he is interested in Boolean circuit complexity, arithmetic
circuit complexity, communication complexity, propositional proof theory, probabilisti-
cally checkable proofs, quantum computation and communication, and randomness and
derandomization.
T HEORY OF C OMPUTING, Volume 10 (5), 2014, pp. 107–131 131