J.

Cryptology (1994) 7: 1- 32 Journal o f

CRYPTOLOGY
9 1994 International Association for
Cryptologic Research
Definitions and Properties of Zero-Knowledge
Proof Systems*
Oded Goldreich and Yair Oren
Department of Computer Science, Technion,
Haifa, Israel
Communicated by Shaft Goldwasser
Received 26 February 1990 and revised 22 September 1992
Abstract. In this paper we investigate some properties of zero-knowledge proofs,
a notion introduced by Goldwasser, Micali, and Rackoff. We introduce and classify
two definitions of zero-knowledge: auxiliary-input zero-knowledge and blackbox-
simulation zero-knowledge. We explain why auxiliary-input zero-knowledge is a
definition more suitable for cryptographic applications than the original [GMR 1]
definition. In particular, we show that any protocol solely composed of sub-
protocols which are auxiliary-input zero-knowledge is itself auxiliary-input zero-
knowledge. We show that blackbox-simulation zero-knowledge implies auxiliary-
input zero-knowledge (which in turn implies the [GMR1] definition). We argue
that all known zero-knowledge proofs are in fact blackbox-simulation zero-
knowledge (i.e., we proved zero-knowledge using blackbox-simulation of the veri-
fier). As a result, all known zero-knowledge proof systems are shown to be auxiliary-
input zero-knowledge and can be used for cryptographic applications such as those
in [GMW2].
We demonstrate the triviality of certain classes of zero-knowledge proof systems,
in the sense that only languages in BPP have zero-knowledge proofs of these
classes. In particular, we show that any language having a Las Vegas zero-
knowledge proof system necessarily belongs to RP. We show that randomness of
both the verifier and the prover, and nontriviality of the interaction are essential
properties of (nontrivial) auxiliary-input zero-knowledge proofs.
Key words. Zero-knowledge, Computational complexity, Computational in-
distinguishability, Cryptographic composition of protocols.
1. Introduction
The fundamental notion of zero-knowledge was introduced by Goldwasser et al. in
[GMR1]. They considered a setting where a powerful pr over is proving a theorem
* This research was partially supported by the Fund for Basic Research Administered by the Israeli
Academy of Sciences and Humanities. Preliminary versions of this work have appeared in [O1] and [02].
2 o. Goldreich and Y. Oren
to a probabilistic polynomial-time veri f i er. Intuitively, a proof system is considered
zero-knowledge if whatever the verifier can compute while interacting with the
prover it can compute by itself without going through the protocol. The intriguing
nature of this notion has raised considerable interest and many questions to be
answered. Zero-knowledge proofs are of wide applicability in the field of crypto-
graphic protocols, as demonstrated by Goldreich e t al. in [ GMWl ] and [ GMW2] .
In this paper we investigate some aspects of these proof systems. We present new
definitions of zero-knowledge, discuss their importance, and investigate their rela-
tive power. In t he second part of the paper we demonstrate that certain properties
are essential to zero-knowledge interactive proofs.
1.1. De f i n i t i o n a l I s s u e s
The original definition of zero-knowledge was presented in [ GMR1] . This defini-
tion does not seem to capture fully the intuitive meaning of the concept of zero-
knowledge. For one thing, it would be expected that the sequential application
("composition") of protocols, each of which is zero-knowledge, would yield a
protocol which is itsdfzero-knowledge (in the same manner that summing any finite
number of zeros would leave the total at zero). However, as claimed by Feige and
Shamir [FS] and recently shown in [-GK], such a "composition theorem" cannot
be proved for the [ GMR1] definition.
Another problem with this definition concerns its applicability to cryptographic
protocols. Typically, zero-knowledge proof systems are used as subprotocols within
larger cryptographic protocols. In such a scenario it is natural that a dishonest part
(a "cheating" verifier in the zero-knowledge terminology) will compute its messages
based on information acquired be f or e the proof protocol began, possibly from
earlier stages of the protocol in which the zero-knowledge proof is a subprotocol.
We would like to require that even t h i s a d d i t i o n a l i n f o r ma t i o n will not enable the
verifier to obtain any knowledge from its interaction with the prover. (This is not
guaranteed by the original definition.)
In an effort to overcome these problems, we formulate the definition referred to
as a u x i l i a r y - i n p u t zero-knowledge. Intuitively, the definition requires that whatever
a verifier that has access to any information can compute when interacting with the
prover, it can also compute by itself when having access to the same information.
Apart from dealing with verifiers that "cheat" by means of using outside informa-
tion, the proposed definition also enables us to prove a composition theorem. The
fact that auxiliary-input zero-knowledge is closed under composition is crucial for
the use of zero-knowledge proofs in the modular design of cryptographic protocols.
In [ GMW2] a compiler is presented that transforms any protocol correct in a weak
adversarial model to a protocol correct in the strongest adversarial model. The
existence of such a compiler relies heavily on the existence of a u x i l i a r y - i n p u t zero-
knowledge proofs for every language in NP. On the other hand, the ability to derive
such a strong result indicates that the auxiliary-input zero-knowledge definition is
suitable for cryptographic purposes.
The requirements of the auxiliary-input definition may seem very restrictive.
However, all known zero-knowledge proof systems (e.g., [ GMR1] and I-GMWl ])
satisfy even a seemingly much stricter definition. All these protocols were proved
Definitions and Properties of Zero-Knowledge Proof Systems 3
zero-knowledge by presenting one algorithm that uses any verifier as a blackbox
to simulate the interaction of that verifier with the prover. In fact it is hard to
conceive an alternative way to prove a protocol zero-knowledge. We therefore
present the definition of blackbox-simulation zero-knowledge, which formalizes this
requirement. We show that blackbox-simulation zero-knowledge implies auxiliary-
input zero-knowledge. As a result, all known zero-knowledge proofs are auxiliary-
input zero-knowledge and can be used for cryptographic purposes such as those in
[ GMW2] .
Remark 1. 1. The fact that the [ GMR1] definition is not closed under composition,
and that "nonuniform" verifiers could be used to overcome this problem, was
observed independently by Goldwasser et al. [ GMR2] , Tompa and Woll [TW],
and Feige and Shamir [FS].
1.2. Essential Properties of Zero-Knowledoe
Other results in this paper concern the triviality of certain classes of zero-knowledge
proof systems. We consider a class of proof systems trivial in this context if only
languages in BPP can have zero-knowledge proof systems of this type. The reason
being that any BPP language has a trivial zero-knowledge proof: one in which the
verifier checks by himself whether x ~ L or not. Proving the triviality of some class
of proof systems can be thought of as demonstrating that some property (which this
class lacks) is essential to zero-knowledge.
In particular, we show that any language L possessing a Las Vegas zero-knowl-
edge proof system (i.e., a proof system that never causes the verifier to accept on
x r L) is in random polynomial time. It follows that the error probability on "no"
instances, existing in all known zero-knowledge proofs, is inevitable and essential
to the nontriviality of these proof systems. It is interesting to note that Les Vegas
interactive proofs can exist only for languages in NP (see [GMS]).
It is easy to see that the class of languages for which membership can be proved
by a deterministic prover equals that for which membership can be proved by a
probabilistic prover. (We can consider an optimal prover, i.e., one which always
maximizes the acceptance probability. This prover computes in each case the "best
possible" messages and can clearly be deterministic.) Thus, randomness of the
prover is not essential to the power of interactive proof systems as far as language
recognition is concerned. On the other hand, in all proof systems shown to be
zero-knowledge the prover is probabilistic, and this property seems essential to the
"zero-knowledgeness" of these proof systems. We show that this is no coincidence:
only languages in BPP can have auxiliary-input zero-knowledge interactive proofs
in which the prover is deterministic, and therefore randomness of the prover
is essential to the nontriviality of the zero-knowledge proof system. We thus
demonstrate a meaningful difference between general interactive proofs and zero-
knowledge interactive proofs.
Just as an error probability on "no" instances and randomness bot h of the prover
and the verifier are essential to zero-knowledge proof systems, so is the nontriviality
of the interaction. It can be easily shown that only languages in BPP can have
one-step interactive proofs which are zero-knowledge. We show that the same holds
4 O. Goldreich and Y. Oren
for two-step zero-knowledge proof systems under the auxiliary-input definition.
In contrast, Aiello and Hast ad [AH2] proved that, relative to some oracle A,
t wo-st ep zero-knowl edoe a c/z B p p A. Their proof holds for the original [ GMR1]
definition (actually for a stronger definition, see I-AH2]). The proof presents a
two-step protocol which is a zero-knowledge interactive proof system for some
language LA, but such that LA r BPP A. Since the prover in the protocol is determin-
istic, the result can also be interpreted as deterministic-prover zero-knowledoe A r
B P P A. Our proofs for the two-step and determinstic prover cases, both holding for
auxiliary-input zero-knowledge, relativize, and we can therefore conclude that
neither will extend to the [ GMR1] definition.
Not e that two-step protocols and determinstic-prover protocols can be zero-
knowledge with respect to the prespecified verifier V (e.g., the two-step protocols
for quadratic nonresiduosity [ GMR1] and graph nonisomorphism [ GMWl ] ) .
Therefore, unlike Fort now I F] and Aiello and Hast ad [AH1], who actually rely
only on the fact that the prespecified verifier V has a simulator, we must in this case
make use of the f ul l power of the definition of zero-knowledge: specifically, the
requirement that simulators for all verifiers, including the "cheaters," exist. Our
results extend to zero-knowledge arguments, introduced in [BCC]. Zero-knowledge
arguments differ from zero-knowledge interactive proofs, which are the main topic
of our investigations, in that the former have a relaxed soundness condition (rather
than requiring that it be impossible to fool the verifier into believing false statements,
it is only required that cheating the verifier be computationally infeasible).
Remar k 1. 2. We stress that if one-way functions exist, then every language in
I P = P S P A C E has a zero-knowledge proof system [ GMWl ] , [IY], IS]. These
proof systems have all the essential properties discussed above. Hence there seems
to be a big difference between proof systems possessing these properties and those
lacking them.
Oroanization o f the Paper. Section 2 contains some basic definitions and also an
extension of the notion of polynomial indistinouishability which is required for the
definitions presented in Section 3. In Section 3 we present our new definitions of
zero-knowledge and investigate their relative power. We also prove the composition
property of auxiliary-input zero-knowledge in that section. Section 4 contains our
triviality results.
2. Notation and Basic Definitions
Let S be a set. By e ~ RS we mean that an element e is chosen at random from the
set S with uniform probability distribution.
When describing a protocol between two parties, A and B, we write
A: action
to mean party A performs some internal action (computation), and
A ~ B : m
to mean that A sends message m to B.
Definitions and Properties of Zero-Knowledge Proof Systems 5
We recall the definition of interactive proof systems [ GMR1] (an alternative
definition due t o Babai [B] was shown to be equivalent by Gol dwasser and Sipser
IGS]): An interactive pr oof system for a l anguage L is a prot ocol (i.e., a pair of local
programs) for two probabilistic interactive machi nes called the prover and the
verifier. Initially bot h machi nes have access to a common i nput tape. The two
machi nes send messages to one anot her t hr ough two communi cat i on tapes. Each
machi ne onl y sees its own tapes, the common i nput tape and the communi cat i on
tapes. The verifier is bounded to a number of steps which is pol ynomi al in the length
of the common input, after which it stops in an accept state or in a reject state. We
i mpose no restrictions on the local comput at i on conduct ed by the prover, We
require that, whenever the verifier is following its predet ermi ned program, V, the
following two condi t i ons hold:
(1) Completeness of the interactive proof system. If the prover runs its predeter-
mi ned program, P, then, for every const ant c > 0 and large enough x ~ L, the
verifier accepts the common i nput x with probabi l i t y at least 1 - I x V c. In
ot her words, the prover can convince the verifier of x ~ L.
(2) Soundness of the interactive proof system. For every program P*, run by the
prover, for every const ant c > 0 and large enough x r L, the verifier rejects x
with probabi l i t y at least 1 - txl -c. In ot her words, the prover cannot fool the
verifier.
An interactive pr oof system havi ng P, V as programs is denot ed by ( P, V>.
Definition. A t-step interactive pr oof system is one in which a t ot al of t messages is
sent by the two parties.
Wi t hout loss of generality, we assume t hat the last message sent duri ng an inter-
active pr oof is sent by the prover. (A last message sent by the verifier can have no role
in convincing the verifier and therefore has absolutely no effect.) Thus, the prover
sends the last (and only) message in a one-step interactive proof while in a two-step
prot ocol the verifier sends a message first, followed by a response from the prover.
The not i on of polynomial indistinguishability of probabi l i t y distributions is used
in the definitions of zero-knowledge discussed in the next section. We ext end the
original [ GM] , l-Y] definition for the case of probability distributions indexed by
two parameters, which are treated differently. This extension is required for the
formal definition of auxiliary-input zero-knowledge presented in a later section. In
t hat case, x is the common i nput to the prot ocol while y is the auxi l i ary-i nput to
the verifier.
Definition (Pol ynomi al Indistinguishability). For every al gori t hm A, let pa ~
denot e the probabi l i t y t hat A out put s 1 on i nput (x, y) and an element chosen
accordi ng to the probabi l i t y di st ri but i on D(x, y). Denot e by Dom the domai n from
which the pairs x, y are chosen. The di st ri but i on ensembles {D(x, Y)}x~y~Oom and
{D'(x, Y)}x;y~oom are polynomially indistinguishable if, for every probabilistic algo-
ri t hm A which runs time pol ynomi al in the length of its first i nput (i.e., x), for every
const ant c > 0 there exists No such t hat for every x, Ixl > No, and for every y such
6 O. Goldreich and Y. Oren
t hat (x, y) ~ Dom,
I p f f ~ x . " - p f f ' r I < I x l - c .
No t e t ha t we d o not p u t a n y r es t r i ct i ons o n t he l engt h o f y, a n d i n pa r t i c ul a r we d o
not r equi r e [Yl > No. The or i gi nal def i ni t i on is o b t a i n e d f r om t he a b o v e defini-
t i on by omi t t i ng all me nt i on o f y. We oc c a s i ona l l y a v o i d speci f yi ng t he doma i n,
a nd wr i t e {D(x, y)}x;y i ns t ead of {D(x,y)}~;y~aom. Two di s t r i but i on ens embl es
{D(x, Y)}x;y~oom a nd {D' (x, Y)}x;y~oom ar e N O T pol ynomi a l l y i ndi s t i ngui s habl e i f
t her e exi st a pr oba bi l i s t i c pol ynomi a l - t i me a l gor i t hm A, a c o n s t a n t c > 0, a nd an
infinite s e que nc e Seq o f x ' s s uch t hat , f or ever y x ~ Seq, t her e exi st s ome y s uch t ha t
(x, y) ~ Dora a nd
p A o l i . " _ pAO'l~." > I x l - c .
Definition. Let c > 0 be a c ons t a nt a nd l et D(x, y) a n d D' (x, y) be p r o b a b i l i t y
di s t r i but i ons ove r st r i ngs of l engt h n > 1. We s ay t ha t an a l gor i t hm A c-distinguishes
be t we e n D(x, y) a nd D' (x, y) if
1
pAO~x., _ p ~ ' ~ x . , > n ~ "
Remark 2 . 1 . Th r o u g h o u t t hi s p a p e r we use t he phr as es " wi t h ver y hi gh pr oba bi l -
ity, " " wi t h ( non- ) negl i gi bl e pr oba bi l i t y, " a nd s o on, t o des cr i be t he b e h a v i o r of
al gor i t hms . The f or mal i nt e r pr e t a t i on of t he s t a t e me nt " t he a l gor i t hm be ha ve s t hi s
wa y wi t h ver y hi gh p r o b a b i l i t y " s houl d be t a ke n t o be " t he p r o b a b i l i t y t ha t t he
a l gor i t hm be ha ve s t hi s wa y on i nput of l engt h n is gr eat er t ha n 1 - 1/Q(n) f or a n y
(posi t i ve) p o l y n o mi a l Q a nd suffi ci ent l y l ar ge n." Accor di ngl y "negl i gi bl e p r o b a b i l -
i t y" is "l ess t ha n l / Q(n) f or a ny (posi t i ve) p o l y n o mi a l Q a nd suffi ci ent l y l ar ge n," a n d
"nonnegl i gi bl e p r o b a b i l i t y " me a ns " gr eat er t ha n 1/Q(n) f or s ome p o l y n o mi a l Q a n d
suffi ci ent l y l ar ge n." F o r conveni ence, we s a y t ha t a f unct i on p(n) is c-nonngeligible,
wher e c > 0, if p(n) > 1/n c f or i nfi ni t el y ma n y n's.
3. A Taxonomy of Zero-Knowledge Definitions
In t hi s s ect i on we pr es ent t wo al t er nat i ve def i ni t i ons of t he n o t i o n of z e r o- knowl -
edge, a nd i nvest i gat e t he r e l a t i ons hi p be t we e n t hem. We s t ar t b y defi ni ng history
descriptions a nd recal l i ng t he or i gi nal z e r o- knowl e dge def i ni t i on of [ GMRI - I .
Definition. A history description of a c onve r s a t i on be t we e n a ma c hi ne V* a nd t he
p r o v e r P cons i s t s of t he c ont e nt s o f all of V*'s r e a d- onl y t apes ( c o mmo n i nput ,
r a n d o m i nput , and, in t he cas e of auxi l i ar y- i nput z e r o- knowl e dge , al s o t he auxi l i ar y
i nput ) a nd of t he s equence of mes s ages sent b y t he p r o v e r dur i ng t he i nt er act i on.
We use [ x, r, m] f i x, y, r, m] ) t o d e n o t e hi s t or y des cr i pt i ons , wher e x is t he c o mmo n
i nput (y t he auxi l i ar y i nput ), r t he r a n d o m i nput t o t he verifier, a nd m t he s eqence
of mes s ages s ent by t he pr over . We d e n o t e by ( P( x ) , V*( x ) ) ( ( P( x ) , V*(x, y ) ) ) t he
p r o b a b i l i t y di s t r i but i on of hi s t or y des cr i pt i ons ge ne r a t e d b y t he i nt er act i on of V*
wi t h P on x e L.
Definitions and Properties of Zero-Knowledge Proof Systems 7
Definition [ GMR1] . An interactive proof system for a language L is zero-knowl-
edge if, for all probabilistic polynomial-time machines V*, there exists a probabilis-
tic polynomial-time algorithm My. that on input x produces a probability distri-
bution Mv.(x) such that {Mv,(X)}x,L and {(e(x), V*(x))}x~. are polynomially
indistinguishable.
Remark 3.1. If we require that the above two probability distributions be equal,
we obt ai n the definition referred to as perfect zero-knowledge. If we require them to
be statistically close, we obtain almost-perfect zero-knowledge. (The definitions
originate from [ GMR1] , and were named as above in IF].)
Remark 3.2. In the definition above we required My, to simulate the history of
V*'s interaction with P. An alternative definition is to require Mv. to generate the
output of V* when interacting with P. Clearly, the output of V* is determined given
the history, and therefore simulating the history is at least as hard as simulating the
output. The converse may not be true for a specific verifier (in particular for V, the
"honest" verifier). However, since, for every verifier V* there exists a verifier V'
whose out put is the history of the interaction of V* with P, it follows that, when
quantifying over all verifiers, the two formalizations are equivalent. We use the
history-based notion of zero-knowledge throughout this paper.
3.1. New Definitions
The first definition to be considered is motivated by cryptographic applications and
is referred to as the auxiliary-input zero-knowledge definition. Let us elaborate on
this motivation. Zero-knowledge interactive proofs are a powerful tool in the design
of cryptographic protocols. Typically, they are used by a party to prove that it is
computing its messages according to the protocol. It is crucial that these proofs are
carried out without yielding the prover' s secrets. In such a scenario it seems natural
to assume that an adversarial party playing the role of the "verifier" will try to gain
knowledge of interest to it. In order to do so the adversary may deviate from the
specified program and compute its messages in a manner suited to its goals. Most
probabl y it will want to base the comput at i on of its messages on previously acquired
information, possibly from earlier stages of the protocol in which the zero-knowl-
edge proof is a subprotocol. Intuitively, we require that the proof system be such
that even having this additional information cannot enable any V* to extract from
its conversations with P anything that it could not compute by itself having that
same information. To allow this possibility the interactive proof and zero-knowl-
edge definitions introduced in I-GMRI] should be modified so that the verifier can
have an auxiliary-input tape, through which the information that enables the
"verifier" to compute the desired messages will be entered.
Definition (Auxiliary-Input Zero-Knowledge). An interactive proof system for a
language L is auxiliary-input zero-knowledge if, for every probabilistic polynomial-
time machine V*, there exists a probabilistic polynomial-time machine My, such
that the distribution ensembles {<P(x), V*(x, Y))}x;y~o, and {Mr,(X, Y)}x;y~o, are
polynomially indistinguishable, where D 1 --- {(x, y)lx ~ L, y ~ {0, 1}*}.
8 o. Goldreich and Y. Oren
Not e that by saying that V* is polynomial time we mean that its running time is
bounded by a polynomial in the length of the common input. Machine V* has an
additional input tape containing the auxiliary input y. During an interaction of V*
on common input x, machine V* reads at most a pol y( x) . l ong prefix of its auxiliary
input 9 A similar convention holds for the simulator Mv , (i.e., its running time is
polynomial in the length of its first input, and consequently it may only read a prefix
of the second input).
The second definition we consider is referred to as bl ackbox-si mul at i on zero-
knowledge. This definition requires the existence of a single polynomial-time ma-
chine Mu which simulates the interaction of any polynomial-time machine V* with
the prover P on any x e L, using V* as a blackbox.
What do we mean by "use V* as a blackbox"? A probabilistic algorithm in general
can be viewed either as an algorithm which internally tosses coins or as a determin-
istic algorithm that has two inputs: a regular input and a random input. Two
corresponding interpretations of "using a probabilistic algorithm as a blackbox"
follow9 In the first case it means choosing an input and running the algorithm, while
the algorithm internally flips its coins. In the second case it means choosing bot h
inputs, and running the algorithm (the second input serves as the out come of
random coin tosses). Both these approaches extend naturally to probabilistic algo-
rithms which also interact with other machines, as in our ease. We choose to adopt
the second approach, that is, when using V* as a blackbox, the simulator Mu chooses
both inputs to V*. All known zero-knowledge protocols were proved zero-knowl-
edge using this approach. It is not clear if they could also be proved zero-knowledge
when adopting the first approach.
, I , ' *
Definition (Blackbox-Simulation Zero-Knowledge). Denot e by Ti mer (x) the run-
ning time of machine V* when interacting with P on input x. An interactive proof
system for a language L is bl ackbox-si mul at i on zero-knowledge if there exists a
probabilistic polynomial-time machine Mu such that, for every polynomial Q, the
distribution ensembles { ( P( x ) , V*( x) ) }x~ v* ~ o, and {Mu v*(x)}x~ v* ~ o2 are polyno-
mially indistinguishable even when the distinguishers are allowed blackbox access
9 V *
to V*, where D2 = {(x, V*)lx e L and Ti mer (x) < Q(x)}.
All known zero-knowledge protocols are in fact blackbox-simulation zero-
knowledge. It seems likely that in order to prove an interactive proof system
zero-knowledge with respect to any "verifier" V*, such a universal simulator would
have to be presented. Thus this definition is reasonable and not t oo restrictive.
Remar k 3.3. In Remark 3.2 of this section we claimed that the "history-based" and
the "output-based" versions of the [ GMR1] zero-knowledge definitions are equiva-
lent. This claim was established by pointing out that the distinguisher, given a
history description, can generate V*'s out put by using a built-in version of V*. The
same reasoning holds for the auxiliary-input definition. However, the distinguishers
in the case of blackbox-simulation cannot have a built-in version of what may be
an infinte number of I/*'s. Therefore distinguishers running on a history description
of an interaction by some machine V* must be allowed blackbox access to V*. This
Definitions and Properties of Zero-Knowledge Proof Systems 9
will clearly allow the distinguisher to reconstruct V*'s out put given the history of
the interaction.
Remark 3.4. We stress that saying that (P, V) is an auxiliary-input zero-knowledge
proof system does not mean that the honest verifier V may use the auxiliary input
as a legitimate stage in its operation: it is not. Rather, we mean that the prover
does not reveal knowledge even to cheating verifiers which do use an auxiliary input.
3.2. Relationship Between the Definitions
Let Cl(def) denote the class of all interactive proof systems satisfying the (zero-
knowledge) requirements of definition def. The following relationships seem rather
obvious:
Theorem 3.1.
(1) Cl(auxiliary-input) ~ CI([GMR1]).
(2) Cl(blackbox-simulation) ~_ CI([GMR1]).
Proof. In bot h cases (1) and (2) the [ GMR1] definition is less restrictive than the
other definitions in terms of its requirements from the simulation. In case (1) the
simulation is required by the [ GMR 1-I definition to be valid only when the auxiliary
input is empty. In case (2) the blackbox definition requires that all verifiers be
simulated by one machine M~ whereas the [ GMR1] definition allows each such
verifier to have its own specially tailored simulator. []
Next, we establish the relationship between the new definitions:
Theorem 3.2.
Cl(blackbox-simulation) ~_ Cl(auxiliary-input).
Proof. Let ( P, V) be an interactive proof system and assume ( P, V)
Cl(blackbox-simulation). That is, there exists a polynomial machine Mu such that,
for every x ~ L and V', machine Mu simulates the interaction of V' with P on input
x. We show (P, V) ~ Cl(auxiliary-input) by demonstrating how to construct a
simulator My, for every probabilistic polynomial-time V* having auxiliary input.
For every V* we construct My, as follows: Let Q be a polynomial such that, Yx,
TimeV*(x) <_ Q(x). The simulator My, will be a multiple-tape Turing machine. It will
have the code of V* built-in. My, will also have access to Mu, the universal simulator
guaranteed by the blackbox definition. Given x and auxiliary input y, machine My,
"incorporates" a prefix of y of length < Q(x) into the code of V*, forming a machine
Vy*. On input x, machine Vy* behaves as follows: it copies y to its input tape and
runs V*(x, y). Also, upon receiving a message "SEND AUXILIARY I NPUT, " Vy*
sends a message contained y (this feature is not required by the simulation, but is
used later by the distinguishers).
Having constructed Vy*, machine My, now simulates the comput at i on of M~ while
having the "blackbox" Vy*. It then outputs the out put of M~. Observe that the out put
10 O. Goldreich and Y. Oren
of M~ will be o f t he f o r m [ x, r, m] whi l e t he o u t p u t of Mv . mu s t be of t he f o r m
l-x, y, r, m]. The r e f or e M e. a dds y t o t he o u t p u t o f M u.
Cl ai m 3.2.1. Mv.(X, y) runs time polynomial in [xl, as required by the definition of
auxiliary-input zero-knowledge.
Pr oof . Th e t i me r e qui r e d t o s i mul at e one s t ep o f Vy*(x, y) is 0(I V*I + lY[). Th e
val ue of I V*I is c o n s t a n t as f ar as Mr . is c onc e r ne d, a n d t her ef or e one st ep r equi r es
O(lYl). Si nce y was t r u n c a t e d t o l engt h Q(Ixl), it f ol l ows t ha t lYl ~ O(Q(Ixl)). We
k n o w t ha t ~*(x), whi ch is essent i al l y t he s a me as V*(x, y), r uns at mos t Q(Ix[) steps.
All i n all, s i mul at i ng t he c o mp u t a t i o n o f Vy*(x) c a n be achi eved i n t i me b o u n d e d by
s ome pol ynomi a l Q v ( I x l ) .
My . s i mul at es t he c o mp u t a t i o n of Mu havi ng a bl a c kbox V 7. The n u mb e r o f st eps
r equi r ed by M~ is g u a r a n t e e d t o be pol ynomi a l i n I x l , wh e n c o u n t i n g t he act i vat i ons
of t he bl a c kbox Vy* at uni t cost. Let QM(Ixl) be t he r u n n i n g t i me of Mu.
The r u n n i n g t i me o f My . is b o u n d e d by QM(Ixl)' Q v(Ixl ) a n d is cl ear l y pol ynomi a l
in Ixl. [ ]
Cl ai m 3.2.2. The distribution ensemble {( P( x) , V*(x, Y))}x;y~o, is polynomially
indistinguishable f rom {Mr,(X, Y)}x;y~o,, where D1 = {(x, y)lx ~ L}.
Pr oof . As s ume t her e exi st a c ons t a nt c, a n a l gor i t hm A, a n d a n i nfi ni t e s equence
S o f pai r s (x, y) ~ D1 s uch t hat ,
1
V(X, y ) E S , p(A I"(xLV*(x'y)) -- p ~ " t ~ ' " > ixl---- ~.
We s how t h a t i n s uch a case t her e exist a pol ynomi a l Q, an a l gor i t hm A', a n d a n
i nfi ni t e s equence S' o f pai r s (x, Vy*) s uch t ha t
S' ___ {(x, Vy*)lx e L, Time~,,(x) < Q ( I x l ) } and,
9 1
V(x, v 7 ) ~ s ' , p < ~ , v ; ~ , _ p f . . , ~ >
I x l c '
c o n t r a r y t o t he a s s umpt i on t ha t M~ is a val i d bl a c kbox s i mul at or .
Let S' = {(x, Vy*)l(x, y) ~ S}, whe r e Vy* is as des cr i bed above. Cl ear l y,
V(x, Vy*) ~ S', TimeV;(x) = Q(lx[).
We c ons t r uc t A', t he " bl a c kbox- s i mul a t i on" di st i ngui sher , as follows: On i nput
I x, r, m] a n d a bl a c kbox Vy* (recall t ha t bl a c kbox di s t i ngui s her s have bl a c kbox
access t o t he verifiers), A' fi rst sends a mes s age " S E ND AUXI L I ARY I N P U T " t o
Vy*, t o obt a i n y. I t t h e n r uns A( [ x, y, r, m] ) a n d o u t p u t s t he o u t c o me of t hi s
c ompua t i on. I t is eas y t o see t ha t A' will di st i ngui sh, f or a n y pai r (x, Vy*) f or whi c h
A di st i ngui shes, t he c o r r e s p o n d i n g pai r (x, y). The cl ai m follows. [ ]
Thi s compl et es t he p r o o f of Th e o r e m 3.2. [ ]
Thi s is t he mos t i mp o r t a n t r es ul t o f t hi s sect i on, d u e t o its effect: all k n o wn
zer o- knowl edge pr ot ocol s, havi ng been pr oved zer o- knowl edge u n d e r t he bl ackbox-
Definitions and Properties of Zero-Knowledge Proof Systems 11
simulation definition, are shown to be auxiliary-input zero-knowledge, and as such
can be used for all cryptographic applications such as those given in [ GMW2] .
Remark 3.5. The relationships derived in the above theorems also hold for perfect
zero-knowledge and almost-perfect zero-knowledge.
Remark 3.6. It follows from Theorem 4.1 of [ GK] that Cl(auxiliary-input)c
CI([GMR1]). We do not know whether Cl(auxiliary-input) equals Cl(blackbox-
simulation). The following states clearly what is known:
Cl(blackbox-simulation) ~_ Ci(auxiliary-input) c CI ( [ GMRI ] ) .
3.3. Proof of the Sequential Composition Theorem for
Auxiliary-Input Zero-Knowledge
We first define the notion of a sequential composition of interactive proof systems:
Definition. Let (P1, Vl ) . . . . , ( Pk , Vk) be interactive proof systems for languages
L1, L2 . . . . . Lk, respectively. A sequential composition of the k protocols, denoted
( P, V), is defined as follows: The common input to ( P, V), x, will be a string of
the form XI%X2%"'%Xk%, where "%" is a delimiter. The execution of (P, V)
consists, at stage i, of P and V activating P~ and V, respectively, as subroutines on
x~. V accepts if all V~'s have accepted.
In a similar manner we can define concurrent compositions:
Definition. Let (PI, V~),..., (Pk, Vk) be interactive proof systems for languages
L1, L2 . . . . . Lk, respectively. Without loss of generality, assume that all protocols
are m-step protocols. A concurrent composition of the k protocols, ( P, V), is defined
as follows: ( P, V) will also be an m-step protocol. The common input to {P, V),
x, will be a string of the form Xl%X2%'"%Xk%, where "%" is a delimiter. The ith
message in ( P, V) will consist of the ith message of (P1, V1 ) . . . . , {Pk, Vk). V accepts
if all V~'s have accepted.
A
Remark 3.7. Clearly, the case in which a single protocol ( P, V) is iterated k times,
possibly on the same input ~ i s merely a restricted version of the above definitions,
in which, Vi, (Pi, V~) = ( P, V) and, Vi, x~ = ~.
It is easy to see that bot h compositions (sequential and concurrent) constitute
iteractive proofs for L. We now prove that a sequential composition of auxiliary-
input zero-knowledge protocols yields an auxiliary-input zero-knowledge pro-
tocol. Recently it was shown in [ GK] that the same is not true for concurrent
compositions.
Remark 3.8. In the following proofs k, the number of protocols, is assumed to be
constant. We demonstrate later how a slightly altered version of the proof can be
applied in the meaningful cases for which k is not a constant.
Theorem 3.3 (Sequential Composition Theorem). Let (P1, V1 ), ( t > 2 , V 2 ) . . . . .
( Pk, Vk ) be auxiliary-input zero-knowledge proof systems for languages L 1, L2 . . . . .
12 O. Goidreich and Y. Oren
L k, respectively. Let L = {xl~ ~ Li)}. Define (P, V) to be the
composition of (P1, V1), (P2, V2) . . . . . (Pk, Vk). Then (P, V) is an auxiliary-input
zero-knowledoe proof system for L.
Proof. It is easy t o see t hat ( P, V) is an iteractive pr oof system for L. We t herefore
concent r at e on showi ng t hat ( P, V) is auxi l i ary-i nput zero-knowl edge. Recall t hat
we are using the hi st ory-based not i on of zero-knowl edge. A hi st ory descri pt i on in
the case of an auxi l i ary i nput is of t he f or m Ix, y, r, m], where x is t he c ommon i nput ,
y is t he verifier' s auxi l i ary input, r is t he verifier' s r andom string, and m is t he
sequence of pr over messages.
The objective of the indented small-print paragraphs throughout the proof is to
provide insight and intuition to the otherwise rather formal proof.
In or der t o pr ove t hat ( P, V) is auxi l i ary-i nput zero-knowl edge we must show
how t o const r uct a si mul at or Mr. for each pol ynomi al - t i me probabi l i st i c V*. We
assume, wi t hout loss of generality, t hat V* initially copies t he cont ent s of all its i nput
tapes ( common input, r andom input, auxi l i ary input) t o its wor k t ape and never
at t empt s t o access these tapes again.
V*'s interaction with P can be conceptually divided into V*'s interaction with/' 1,
V*'s interaction with P2, and so on. Since the k individual protocols are auxiliary-input
zero-knowledge, machines Mv~., M 2 . . . . . . Nkv ,, which simulate the interaction of V*
with PI, P2 . . . . . Pk, respectively, must exist. Basically, Me. will activate these simulators
in sequence. However, in order for the overall simulation to be valid, the initial state
of V* when being simulated by My+. 1 should be its final state in the simulation by M[,..
This can be achieved by giving V*, as its auxiliary input to the (i + 1)th stage, informa-
tion which will enable it to reconstruct the final state of the ith stage. Obviously, we
cannot guarantee that any V* will in fact behave as described above (i.e., reconstruct
its state when having past history as its auxiliary input). Therefore, and instead of
making any technical assumptions on V*, we consider, for every V*, a modified verifier
V' which will exhibit the required behavior.
As a first step we consi der a verifier V' t hat has a built-in versi on of V* and t he
following addi t i onal propert y: on auxi l i ary i nput h, where h = Ix, y, r, m] is a
hi st ory descri pt i on of V*'s i nt eract i on with t he prover, V' brings its built-in versi on
of V* t o t he confi gurat i on (stage, wor k- t ape cont ent s, and head posi t i on) corre-
spondi ng t o this descri pt i on, and proceeds from t hat poi nt . In part i cul ar, if m = e
(the empt y string) and y is not itself a hi st ory descri pt i on, t hen V' onl y copies x, y,
r t o t he wor k t ape of its built-in versi on of V* and t hen "behaves" like V*. Machi ne
V' act ual l y always ignores its "real " r andom string. In all ot her senses V' is exact l y
like V*. In part i cul ar, for every x, y, t he pr obabi l i t y di st ri but i on of pr over messages
generat ed by r unni ng (P(x), V*(x, y)) is exact l y t hat generat ed by r andoml y
choosi ng a string r and r unni ng (P(x), V'(x, Ix, y, r, el ) ) .
Construction of the Simulator f or V*. Since t he i ndi vi dual pr ot ocol s are assumed
t o be auxi l i ary-i nput zero-knowl edge, machi nes MvL, M2,, . . . . Mkv,, whi ch simulate
t he hi st ory of V"s i nt er act i on with P1, P2 . . . . . Pk, respectively, exist. The out put
pr oduced by M~. on i nput pai r (x, h) will be of the f or m [x, h, r, m], where r is V"s
Defi ni t i ons and Pr oper t i es of Ze r o- Knowl e dge Pr oof Syst ems 13
r andom string (which is act ual l y ignored) in this si mul at i on and m is the sequence
of messages sent "on behal f" of the prover. Let s i s 2 denot e the concat enat i on of
strings sl and s2. We now describe M y . . On i nput x = x ~ % x 2 % ' " x k % and y,
machi ne M y . runs
c h o o s e r a n d o m s t r i n o r
ho ' -- [ x, y, r , ~]
h i *-" M ~ , ( x l , ho)
h z ~ M~, , (x2, h i )
. . .
hk *-- Mkv'(Xk, hk-t)
m ~ m 1 m 2 9 9 9 m s
O U T P U T ( [ x , y , r, m]).
(The m,'s are obt ai ned from the h,'s.)
We now show t hat M y . is indeed a "good" si mul at or for ( P, V*).
Lemma 3.3.1. T h e d i s t r i b u t i o n e n s e mb l e s { Mr . ( X , Y)}x,y, wh e r e M y . is a s d e s c r i b e d
abov e , a n d { ( P( x ) , V * ( x , y) ) }x.y a r e p o l y n o mi a l l y i n d i s t i n # u i s h a b l e .
Proof. Suppose t hey are not. That is, there exists a const ant c > 0 and a test
A t hat , for infinitely many pairs (x, y), will c-distinguish between M r . ( X , y) and
( P( x ) , V* ( x , y) ) .
We show that in such a case another constant c' and another test A ~~ exists that, for
some i and for infinitely many pairs (xi, y~), d-distinguishes between M~,,(xi, Yi) and
(P~(xi), V' (xi , yi ) ) , contrary to the assumption that Miv 9 correctly simulates the history
of V"s intersection with P~.
We consider the following h y b r i d s of the probabi l i t y di st ri but i ons M r . ( x , y) and
( P ( x ) , V* ( x , y ) ) . The ith hybrid, denoted H~(x, y), is defined by the following process:
c h o o s e a r a n d o m s t r i n g r
h o ~ [ x , y , r, e]
h 1 ~ ( Pt ( xl ) , V ' ( x l , h o ) )
h 2 . . . . ( P 2 ( x 2 ) , V ' ( x 2 , h i ) )
h i ~. - ( P i ( x i ) , V ' ( x i , h ~ - l ) )
h i + l ' - M [ , t ' ( x ~ + l , h , )
. , .
h h *-- Mkv,(Xk, h k - l )
m ~ m i r a 2 9 9 9 ms
O U T P U T ( [ x , y , r, m-I).
As before, each hi is of the form Ix, h H, ri, mr]. The extreme hybrids, H o and Hk,
correspond t o Mv . ( X , y ) and ( P ( x ) , V* ( x , y ) ) , respectively. Clearly, if we can c-
distinguish between the extreme hybrids, t hen a const ant c' and t wo adj acent
hybri ds which can be c' -distinguished, say Hi-1 and Hi, must exist. It is not har d to
see t hat , for sufficienty large n, c ' is approxi mat el y equal to c.
14 O. Goldreich and Y. Oren
L e t p r e f ~ ( x , y ) b e t h e p r o b a b i l i t y d i s t r i b u t i o n d e f i n e d b y t h e p r o c e s s
c h o o s e a r a n d o m s t r i n g r
h o ~ - [ x , y , r , e ]
h 1 , . - ( P l ( x l ) , V ' ( x 1, h o ) )
h 2 , . - ( P 2 ( x z ) , V' ( x 2 , h i ) )
o , .
hi-1 ' - ( Pi - l ( x i - 1 ) , V ' ( x H , h i - ~) )
O U T P U T ( h ~ - I ) .
L e t h b e a s t r i n g wh i c h m a y o c c u r wi t h n o n z e r o p r o b a b i l i t y i n e i t h e r o f t h e
d i s t r i b u t i o n s M ~ , , ( x i , h i - l ) a n d ( P i ( x i ) , V ' ( x i , h i - l ) ) , wh e r e h i - 1 i s a s t r i n g a s s i g n e d
n o n z e r o p r o b a b i l i t y b y p r e f ~ ( x , y ) . An y s u c h s t r i n g h wi l l c o n t a i n ml , m2 . . . . . m i a n d
x, y, a n d r. F o r s t r i n g s h o f t hi s t y p e we d e f i n e s u f f i ( h ) t o b e t h e p r o b a b i l i t y
d i s t r i b u t i o n g e n e r a t e d b y r u n n i n g
hi + 1 ~ - M ~ + , l ( X i + l , h )
hi+ 2 ~-- M ~ + 2 ( x i + 2 , hi +l )
h~ , - M ~,(x~, hR-1)
m 4- ml m2 . . . mR
O U T P U T ( I x , y , r , m] ) .
The di s t r i but i on pref~(x, y) is act ual l y a di s t r i but i on on all t he possi bl e auxi l i ar y
i nput s t o t he i t h st age, gi ven t ha t t he i ni t i al i nput is x and t he initial auxi l i ar y i nput is
t he st r i ng y. The di st r i but i on s u ~ can be r egar ded as an o p e r a t o r whi ch on i nput a
st age i hi s t or y appl i es t he r emai ni ng k - i s i mul at i on stages. I f t he i nput t o suffi c ome s
f r om M~,(x~, h H ) , t hen t he effect of s u ~ will c or r e s pond t o a st r i ng comi ng f r om
H H ( x , y). I f t he i nput comes f r om (P~(x~), V'(x~, h ~ _ l ) ) , t hen t he effect of suff~ will
c or r e s pond t o a st r i ng c omi ng f r om H ~ ( x , y). Ou r a i m is t o s how t ha t i f (x, y) ar e
such t ha t A c-di st i ngui shes bet ween H o ( x , y) a nd H~(x, y), t hen s ome i a nd s ome
h* exist such t ha t t he A ~~ we cons t r uct while c' - di st i ngui sh bet ween M~,(x~, h*) a nd
(P~(x~), V'(x~, h * ) ) . A "~ will act ual l y act i vat e t he s u ~ o p e r a t o r on its i nput text, h, t o
obt a i n a t ext in a f or ma t sui t abl e f or A, a nd t hen "l et A do t he di st i ngui shi ng. "
We us e t h e f o l l o wi n g n o t a t i o n a l s h o r t h a n d s :
P R i [ h ] = P r o b { p r e f i ( x , y ) = h } .
S u f f i ( M [ h ] ) = s u f f i ( M i v , ( x , , h)).
s u f f i ( P [ h ] ) = s u f f i ( ( e i ( x i ) , V ' ( x i , h ) ) ).
Re c a l l t h a t pa ~ d e n o t e s t h e p r o b a b i l i t y t h a t a l g o r i t h m A o u t p u t s 1 o n i n p u t o f a n
e l e me n t c h o s e n a c c o r d i n g t o t h e p r o b a b i l i t y d i s t r i b u t i o n D. T h e f o l l o wi n g r e l a t i o n -
s h i p h o l d s :
pH,-,t=.y) = ~ , P R i [ h - I . pAUffi(Mtlq).
h
The pr oba bi l i t y pnA'-~t~'Y) is wr i t t en a b o v e as a wei ght ed aver age ove r all t he possi bl e
h's, o f t he pr oba bi l i t y t ha t A out put s 1 on i nput a n el ement chosen accor di ng t o
suff~(M[h]). The wei ght is assi gned by t he pr oba bi l i t y o f h t o be a n i - 1 st age hi st or y.
Definitions and Properties of Zero-Knowledge Pr oof Systems 15
Similarly:
p n a ' t x ' ~ = ~ P R , [ h ] " p ~ . f f , te th l).
h
It was assumed that the values pff,_~tx.y) and p~,tx,y) differ c'-nonnegligibly. Since both
are weighted averages over the same probability space, there must be some element h*
for which there will be a c'-nonnegligible difference between p~u$Iauth*l) and p~sJ',teth'l).
Since p ] , _ , t x , y) _ p ~ , t ~ , y ) > 1 / i x l C ' , some h* exists for which
1
p ~ f f , t u t h ' l ) _ p ~ , f f , O'th*l) > I x l ~ "
We concl ude t hat , for every (x, y) for which H o ( x , y ) and H k ( x , y ) can be c-
distinguished, ( x i , Y i ) exists such t hat (Pi(xi), V ' ( x i , Y i ) ) and M [ , , ( x i , Y i ) can be
c' -distinguished. The auxiliary i nput Yi will be the string h* correspondi ng to x and
y. On i nput a text T = [ x i , Y i , r i , m i ] chosen either according t o ( P i ( x i ) , V ' ( x i , Y i ) )
or to M ~ . , ( x i , y ~ ) , the test A ") extracts m~, m2, . . . , mH, x, y, r (which are cont ai ned
in T since t hey were cont ai ned in Yi = h*) and mi from T. It t hen runs
h i + l ~. _ AAi+lt- T)
~,.t V, ~.X.i+l,
hi+2 '-- M[,+, 2(xi+~, hi+l)
. . .
h k " -- M ~ , , ( X k , h k - 1 )
m , - - m i r a 2 9 9 9 m k
O U T P U T ( [ x , y , r , m])
to obt ai n a text T' = Ix, y, r, m]. The test A ~ t hen runs A on T' and out put s the
out put of A.
By our const ruct i on it is clear t hat A ~ will c' -distinguish between
( P i ( x i ) , V ' ( x i , Y i ) ) and M ~ , ( x i , Y i ) . This cont radi ct s the fact the M~,, is a "good"
si mul at or for (Pi, V' ). []
We concl ude t hat { M v . ( x , y ) } x ; y is pol ynomi al l y indistinguishable from
{ ( P ( x ) , V * ( x , y ) ) } x ; y and the t heorem follows. []
R e m a r k 3 . 9 . The assumpt i on t hat k, the number of protocols, is const ant was
required in order t o argue t hat if rio and I l k can be distinguished for infinitely many
pairs (x, y), t hen some i exists such t hat HH and Hi can also be distinguished
infinitely many times, t hus cont radi ct i ng the assumpt i on t hat M~v, is a good simula-
tor. Observe, however, t hat in the case where a single prot ocol ( P, V) is iterated,
it is no l onger essential to assume t hat k is a const ant . Clearly, we coul d no longer
claim t hat , for some i, the di st ri but i ons HH and Hi can be distinguished infinitely
many times. However, distinguishing any two adj acent hybri ds Hi-1 and Hi means
in every case distinguishing My. from ( P, V' ), cont rary t o the assumpt i on t hat Me,
is a good si mul at or for ( P, V' ). Therefore the Sequential Composi t i on Theorem
also holds in this case. Mor e generally, the Sequential Composi t i on Theorem hol ds
for nonconst ant k whenever, in each of the k stages, one of a finite set of prot ocol s
is run.
16 o. Goldreich and Y. Oren
Re mar k 3.10. An anal ogous Sequential Composi t i on Theorem can be proved for
the bl ackbox-si mul at i on zero-knowledge definition.
4. Essential Properties of Zero-Knowledge Proofs
In this section we show t hat certain properties are essential to zero-knowledge pr oof
systems. We do so by demonst rat i ng the t ri vi al i t y of zero-knowledge pr oof systems
lacking these properties. By a class of interactive pr oof systems we mean, for
example, all pr oof systems in which the verifier is deterministic, all pr oof systems
in which onl y one message is sent, and so on. Let us first discuss the meani ng of
triviality in the context.
The complexity class BPP encompasses our not i on of efficient comput at i on.
Recall t hat a l anguage L is in BPP if a probabilistic pol ynomi al -t i me machi ne M
exists such that, for every const ant c > 0 and large enough x,
if x e L Pr o b ( M( x ) = A CC) > 1 - I x l - c ( Compl et eness condition),
if x L Prob(M(x) = R E J) > 1 - I x l - c ( Soundness condition).
Since V can recognize by itself any language in BPP, it follows t hat any l anguage
in BPP has a trivial zero-knowledge pr oof system: one in which the verifier checks
by itself if x ~ L or not. Accordingly, we consider any class of zero-knowledge
interactive proofs trivial if pr oof systems of this class can be zero-knowledge onl y
for languages in BPP.
4.1. General Fr ame wor k o f Tri val i t y Proof s
Basically, our pr oof met hod is the following: to prove the trivially of some class C,
we assume t hat some language L has a zero-knowledge pr oof system of class C. By
the definition of zero-knowledge, a si mul at or M v, which generates hi st ory descrip-
tions of the i nt eract i on of V with the proper P (in some cases we consider the
si mul at or with respect to some cheating verifier V*, t hat is My . ) , exists. We build
a BPP machi ne for L, t hat uses My ( My. ) .
Let H = l-x, r, m] be a hi st ory description (H = Ix, y, r, m] in the case of auxiliary
input), where x is the common i nput (y is the auxiliary input), r is the r andom input,
and m is the sequence of messages sent in the protocol. String m is of the form
(~o, fll . . . . . ~k) where the ~'s are the prover messages and the fl's are the verifier
messages (m will be of the form (ill, ~q . . . . . ~k) if, in the protocol, V "speaks" first).
We denot e by V*(x, r, ~o . . . . . ~i-~) the deterministic pol ynomi al -t i me comput a-
tion t hat a verifier V* uses to determine fli (in the case of auxiliary input, fli =
V*(x, y, r, 0t o . . . . . ~-1)). Similarly, P( x, fll . . . . . fir) denotes the probabilistic compu-
t at i on used by P t o det ermi ne ~t. The comput at i on used by the honest verifier, V,
to determine whet her t o accept or t o reject is denot ed by p(x, r, ~ . . . . . ~k)"
Def'mition. A history description (or "conversation") H = Ix, r, m] (H = Ix, y, r, m]
in the case of auxiliary input) is legal wi t h respect to a verifier V* if the messages
cont ai ned in m satisfy the following requirement:
Vi, 1 < i < k, fl: = V*(x, r, ~o . . . . . ct~-t)-
Definitions and Properties of Zero-Knowledge Proof Systems 17
(In the case of auxiliary input, fli = V*(x, y, r, ~ o , . . . , ~-1)). For convenience, we
simply say "H is legal" when the identity of V* is clear from the context. H is
accepting if it is legal with respect to V and if
p(x, r, ~o, . . . , ~ ) = ACC.
Accepting conversations are only defined with respect to II".
Recall that the texts produced by My on input x e L must be polynomially
indistinguishable from the texts of real interaction between V and P. Therefore, and
since a real conversation between P and V on x ~ L will be with very high probability
legal and accepting, it follows that My must also produce legal and accepting
conversations with very high probability for x ~ L, and do so within polynomial
time. Otherwise a distinguisher which simply outputs 1 if the given conversation is
accepting will clearly distinguish between real iteractions and simulation texts. The
definition(s) of zero-knowledge require nothing of My in the case x r L. The result
of running Mr. on x r L may be one of the following:
(1) Mr may run for t oo long.
(2) Mr may produce a nonaccepting (though perhaps legal) conversation.
(3) My may produce an accepting conversation.
The third case is indeed possible: in all protocols demonstrated to be zero-
knowledge (e.g., [ GMR1] and [ GMWl ] ) the simulator presented in the proof
generates accepting conversations regardless of whether x is in the language or not.
In fact, if this case were not possible, then, for any language which has a zero-
knowledge proof system, we could easily build a BPP machine: the machine would
run Mr on x and accept if and only if My produces an accepting conservation.
We conclude that a BPP machine which runs Mr can "safely" reject if either case
1 or case 2 occurs, because they are guaranteed to occur with negligible probability
for x e L. The hard case to handle is the third case. In the proofs t hroughout
this section, for each instance we use the special structure of the specific class of
interactive proofs under consideration to handle this case.
While using Mr ( Mr. ) in the proofs that follow we usually claim that some
property, existing in the texts of real interaction on x e L, must also exist with very
high probability in the texts produced by the simulator on input x e L. (For
example, a property such as "the text constitutes an accepting conversation.") If the
protocol is perfect or almost-perfect zero-knowledge, this claim follows immedi-
ately. However, if the two probability distributions are "only" polynomiaUy indis-
tinguishable (following [AH1], we refer to this case as computational zero-knowl-
edge), the proof may become more involved. In each case we first present a proof
for perfect zero-knowledge, and then adapt it to computational zero-knowledge.
Each formal proof is preceded by an intuitive discussion of the main ideas underly-
ing it.
Remark 4.1. In the proofs that follow, the BPP machines built arc actually shown
to satisfy the requirements of BPP for all but perhaps a f i ni t e set of x's. Clearly,
any such machine can be transformed into a "true" BPP machine.
18 O. Goldreich and Y. Oren
4.2. Zero-Knowledge Proofs Which Never Err and Zero-Knowledoe
Proofs with Deterministic Verifiers
M. Blum proposed the concept of "Las Vegas" interactive proofs. Informally, these
are interactive proof systems that never err, that is, never cause V to accept when
x ~ L. In I-GMS] these protocols are referred to as "interactive proofs with perfect
soundness." In this section we show that no protocol of this type can be zero-
knowledge, even with respect to the [ GMR1] definition, unless the language is in
RP. A formal definition of "Las Vegas Interactive Proofs" can be obtained from the
definition of general interactive proofs simply by replacing the soundness condition
with: "whenever x r L, and for every program P* run by the prover, either V rejects
or the protocol does not terminate."
Theorem 4.1. Let L be a lanffuage f or which a zero-knowledffe Las Ve#as interactive
proof system exists. Then L E RP.
Proof. The idea is to show that in this case accepting conversations simply do not
exist for x r L, while (as always), for x e L, the simulator My will produce accepting
conversations with very high probability. Let us first recall the definition of random
polynomial time: a language L is in RP if a probabilistic polynomial-time algorithm
M exists such that
on input x e L machine M accepts with probability > 1/2 (completeness),
on input x $ L machine M always rejects (soundness).
Construction of the RP Machine. Since L has a Las Vegas zero-knowledge proof
system, a probabilistic polynomial-time machine My that simulates the membership
proofs of P and V exists. Let Q([xl) denote an upper bound for the running time of
My on input x ~ L (where Q is some polynomial). The random polynomial-time
machine we build, M, uses My.
On input x, machine M runs My on x, maintaining a step count. If My runs more
than Q(Ixl) steps, or does not produce an accepting conversation, M rejects. Other-
wise (if the conversation produced by My is accepting) M accepts.
Soundness of M.
Claim 4.1.1. On input x ~ L, machine M v cannot possibly generate an accepting
conversation.
Proof. Assume it could, that is, there exists a random string r and a set of prover
messages such that V running with random string r and receiving the appropriate
messages accepts on x. Then the conversation could occur in a real interaction with
nonzero probability, violating the conditions of Las Vegas protocols. []
Not e that this claim follows only from the fact that accepting conversations
cannot exist for x $ L, and not from the fact that the conversation was generated
by My. Therefore it is valid regardless of the "quality" of the texts produced by M v.
Definitions and Properties of Zero-Knowledge Proof Systems 19
It is clear that M will never accept on x ~ L, and therefore the soundness condition
is established.
Completeness of M. The completeness property of interactive proofs requires that
conversations on x E L be accepting with very high probability. The same is clearly
true of the conversations produced by My in the case of perfect zero-knowledge.
Adapting the argument to computational zero-knowledge is simple in this case:
note that p, the predicate used by V to decide whether to accept or reject, must be
computable in polynomial time. Consequently, if My does not produce accepting
conversations on x e L with very high probability, then p will distinguish the texts
of the simulator from those of real interaction. [ ]
We conclude that the error probability on x 8 L instances, existing in all known
zero-knowledge proofs, is inevitable and essential to the nontriviality of these proof
systems. Another essential property of nontrivial zero-knowledge proofs is the
randomness of the verifier. We prove this by demonstrating that any language which
has a zero-knowledge interactive proof in which the verifier is deterministic, has a
zero-knowledge Las Vegas interactive proof.
Lemma 4.1.1. Let (P, V> be a (zero-knowledge) interactive proof system for a
language L, in which the verifier is deterministic. Then L has a (zero-knowledge) Las
Vegas interactive proof.
Proof. We show that if <P, V) is not itself Las Vegas, then either it can be slightly
modified to become Las Vegas, or it cannot constitute an interactive proof system
for L. Suppose the protocol is not Las Vegas. Then there exists a prover P* and a
set of x # L such that V, when interacting with P* on such an x accepts with nonzero
probability. If this set is finite, then the protocol can be modified in the following
way to become Las Vegas: on input x, the verifier first checks if x belongs to the
"problematic" set, and if it does, V rejects immediately. Otherwise the original
protocol is carried out. Clearly, the modified protocol is Las Vegas. If the original
protocol was zero-knowledge, then the modified protocol will also be, since with
respect to x ~ L bot h protocols are the same (recall that the definitions of zero-
knowledge require nothing if x r L). We now show that the "problematic" set must
be finite: assun~e it is not, and an infinite sequence Seq of x r L exists such that V,
when interacting with P* on x e Seq accepts with nonzero probability. Since V is
determinstic, it follows that, for every x ~ Seq, a sequence of prover messages exists
that cause V to accept (that is, V will accept with probability 1 when receiving this
sequence of messages). Clearly, some/ ~ exists that, for every x ~ Seq, can find this
sequence and always cause V to accept. One such /~ is a machine that given x
simply tries out every possible set of messages to see on which of them, if any, V
accepts./~ can check this easily as the computation of V is completely determined
by x and by the prover messages, and does not depend on some hidden random
string. Therefore the protocol cannot be an interactive proof system for L. []
The following theorem is an immediate corollary of Theorem 4.1 and Lcmma 4.1.1:
20 O. Goldreich and Y. Oren
Theorem 4.2. Let L be any language and assume that L has a zero-knowledge
interactive proof in which the verifier is determinstic. Then L e RP.
4.3. One-Step Zero-Knowledge Proofs
One-step interactive proof systems do exist and contain NP proof systems as a
special case. However, NP-like proof systems give out a large amount of knowledge,
much of which is not essential for the proof. It was pointed out in [GMW1] that a
one-step protocol cannot be zero-knowledge if it constitutes an interactive proof
system for a language not in BPP. Here we present a formal proof of this statement.
The proof holds even under the original [GMR1] definition of zero-knowledge.
Theorem 4.3. Let L be a language for which there exists a one-step zero-knowledge
interactive proof system. Then L e BPP.
ProoL As before, we use My, the simulator for the honest verifier E The idea is
to simulate the process of the interactive proof by ensuring that the message
generated by the simulator "on behalf" of the prover is not based on prior knowl-
edge of the verifier's random string. V's decision on whether to accept or reject is
obtained by evaluating a determinstic polynomial-time predicate p(x, at, r), where
x is the (common) input to <P, V>, 9 is the prover's message to V, and r is V's
random string. Ifx e L, then some ~ exists such that, for most r's, the predicate must
evaluate to ACC. In cases where x r L, for every 9 there may be a only few random
strings r that cause p to evaluate to ACC, but the simulator may be such that on
x ~ L it always generates conversations in which p evaluates to ACC, using these
few existing strings. (Recall that the definition of zero-knowledge requires nothing
of the simulator in case x r L, and therefore this kind of behavior is possible). For
that purpose we substitute the random string r produced by the simulator with a
truly randomly chosen r'. In this way we simulate not the text but the process of
the interactive proof, retaining its desired soundness property.
Construction of the BPP Machine. Following is a description of M, the BPP
machine for L:
On input x, machine M runs Mv on x, maintaining a step count. If
Mv runs too long or does not produce an accepting conversation, M
rejects. Otherwise, if I-x, r, ~] is an accepting conversation, where r is V's
random string and ~ is the prover's message, M discards r, chooses a
new, random string r', and outputs p(x, r', ~).
Soundness of M. We claim that if x r L and r' is randomly chosen, then p(x, r', ~)
will almost certainly evaluate to RE J, regardless of the value of ~. Otherwise, if it
evaluates to ACC with nonnegligible probability for an infinite number of x r L,
then the soundness condition of interactive proofs is violated.
Completeness of M. In the case of perfect zero-knowledge, the completeness of M
follows directly from the completeness condition of interactive proofs. If x ~ L, then
Definitions and Properties of Zero-Knowledge Proof Systems 21
the prover is guaranteed to produce (with high probability) an ~ that will cause V
to accept for nearly all random strings r. The ~'s produced by the simulator will
have the same property.
The following lemma adapts the proof to computational zero-knowledge.
Let l,(n) be the length of the random string used by V when interacting on input
of length n.
L e mma 4.3.1. Let { ( P(x), V(x) ) }~ and { Mv(x) }~ be polynomially indistinguishable
and let ~(x) be the string output by M v as the "prover message" when running on
input x. Then, f or all but perhaps a f i ni t e set of x ~ L with very high probability,
p(x, r, ~(x)) = ACC when x ~ L, i f r ~ R{0, 1} I'tlxl).
Proof. In a manner similar to the proof of Theorem 4.1, we use p to distinguish the
text of simulation from those of real interaction. More formally: assume a constant
c > 0 and an infinite sequence Seq of x e L exists for which the u produced by
running Mv(x) causes p(x, r, ~) to evaluate to REJ with c-nonnegligible probability,
where r ~ R{0, 1} l'~lxD.
Consider the following distinguisher, A: on input H = Ix, r, ~], the algorithm
chooses r' ~ R{0, 1} ~r~lxD and computes p(x, r', ~). It then outputs 1 if the result is
ACC and 0 otherwise. If H is a description of a real conversation, then it follows
from the completeness property of interactive proofs that A will out put 1 with very
high probability. We assume that if H is a simulation text, then A will out put 0 with
c-nonnegligible probability. Therefore A will c-distinguish between { (P(x), V(x))}~
and {Mv(x)}~, and the two distribution ensembles cannot be polynomially
indistinguishable. []
The theorem follows.
[]
4.4. Two-Step Auxi l i ary-Input Zero-Knowl edge Proofs
We proceed to show that no two-step protocol can be auxiliary-input zero-
knowledge in a nontrivial manner. Not e that while one-step protocols cannot be
(nontriviaUy) zero-knowledge even with respect to the prespecified verifier V, two-
step protocols may be zero-knowledge (in a nontrivial manner) with respect to the
prespecified verifier. In fact, such protocols (i.e., which are zero-knowledge with
respect to V) are known for languages believed not to be in BPP (e.g., Quadratic
nonresiduosity [ GMR1] and graph nonisomorphism [GMW1]). Consequently, in
order to prove our result we have to make use of the full power of the definition of
zero-knowledge, specifically the requirement that, for all V *'s, a simulator My.
exists. To prove an adapting lemma for this case we need to assume a stronger
definition of polynomial indistinguishability, one in which the distinguishers are
nonuniform (polynomial-time machines). Let us present this definition:
De f i ni t i o n (Nonuniform Polynomial Indistinguishability). For every algorithm A
which has an auxiliary input tape, let PA~)'" denote the probability that A out put s
1 on input an clement chosen according to the probability distribution D(x, y)
22 O. Goidreieh and Y. Oren
while having string z as its auxiliary input. Denote by Dora the domain from
which the pairs x, y are chosen. The distribution ensembles {D(x, Y)}x,y~aom and
{D'(x, Y)}x;y~Dom are nonuni f orml y pol ynomi al l y indistinguishable if, for every prob-
abilistic algorithm (with auxiliary input) A which runs in time polynomial in the
length of its input, and, for every constant c > 0, there exists No such that, for every
x, Ix[ > No, for every y such that (x, y) 6 Dom, and every z,
IP~t~ "" - P f f ~ " l < Ixl -c.
We refer to the definition of computational auxiliary-input zero-knowledge
obtained when using the above definition of polynomial indistinguishability as
"nonuniform computational auxiliary-input zero-knowledge."
Re mar k 4.2. If we apply this definition of polynomial indistinguishability to
blackbox-simulation zero-knowledge, the relationship demonstrated in Section 3
still holds. Also, the proof of the Composition Theorem for the auxiliary-input
definition (presented in Section 3) can be carried out almost unaltered when using
the above definition of polynomial indistinguishability.
We begin by an informal discussion: Two-step protocols can in general be viewed
as ones in which the verifier generates questions which the prover can answer with
nonnegligible probability if and only if x e L. When V follows the protocol, it
"knows" the answer to its questions (and will therefore gain no knowledge from the
answers), but this is no longer guaranteed for arbitrary V*'s. The proof presented
in this subsection makes use of this observation to demonstrate the triviality of
two-step auxiliary-input protocols. It seems that the same reasoning should apply
to the original [GMR1] definition. However, in view of the result in [AH2]
discussed in the introduction (relativized two-step [GMR1] zero-knowledge is
not contained in relativized BPP), it is clear that the argument presented in this
subsection will not extend to the [GMR1] definition, as it relativizes. In spite of
that, it can be shown I-O1] that the two-step protocols mentioned above (for
quadratic nonresiduosity and graph nonisomorphism) cannot be [GMRl-l-zero-
knowledge unless these languages are in BPP. Both known two-step protocols
mentioned above were modified by letting the verifier first "prove" to the prover
that it "knows" the answers to its queries, resulting in protocols with more rounds
which are zero-knowledge (with respect to any verifier) [GMR1], [ GMWl ] .
Returning to auxiliary-input zero-knowledge, we intend to prove:
Theorem 4. 4. L e t L be a l anguage f o r whi ch a t wo- st ep perf ect or nonuni f orml y
comput at i onal auxi l i ar y i nput zero- knowl edge p r o o f s ys t em exi st s. Then L E BPP.
Proof. Let (P, V) be the two-step proof system for L. Without loss of generality,
we can describe (P, V) in the following way:
V: computes fl = V( x, r), where r is V's random string.
V ~ P: fl.
P: computes a = P( x , fl).
P ~ V : ~ .
V: computes p( x, r, a) ~ { ACC, R E J } and stops.
Definitions and Properties of Zero-Knowledge Proof Systems 23
The const ruct i on of the BPP machi ne in this case will run al ong the same general
lines as in the one-step case, i.e., M will si mul at e the process of the interactive pr oof
rat her t han merely its text. In a real i nt eract i on P must answer the "quest i on"
wi t hout havi ng access t o the r andom string r used t o compute/~. The prover' s ability
t o provide, under these conditions, an answer ~ for which p( x, r, ~) = A C C is consid-
ered sufficient evidence t hat x ~ L. The completeness propert y of interactive proofs
guarant ees t hat the prover will be able t o come up with such an 9 for al most any
= V( x, r), if x e L. The soundness condi t i on of interactive proofs ensures t hat no
prover could generate from ~ = V( x, r) an ~ such t hat p( x, r, ~) = A C C for any but
a negligible fract i on of the r's. Not e t hat the prover is expected t o generate such an
given onl y ~ = V( x, r), whereas this ~ is tested against r itself. As in our pr oof we
i nt end t o substitute the si mul at or for the prover as a means of generat i ng ~, it is
essential t hat the r andom string r remai n hiddle from the simulator. Otherwise we
coul d not rely on the soundness of the underl yi ng interactive proof. Asking the
si mul at or to "answer" our "quest i on" ~ wi t hout giving away out secret r is achieved
using the auxiliary i nput to the verifier.
Construction o f t he B P P Machi ne. Consi der a verifier V* t hat , given a string fl* as
its auxiliary input, set ~ =/ ~* (and sends ~ to P) instead of choosi ng a r andom r
and comput i ng fl = V( x, r). Provi ded t hat the length of 8" is pol ynomi al in the
length of x, a verifier V* as described above is clearly a pol ynomi al -t i me machine,
for which a si mul at or My . is guarant eed. Machi ne My . , given as i nput x ~ L and
any auxiliary i nput fl*, simulates the i nt eract i on between P and V*.
Using My , we now build M, the BPP machi ne for L. The idea is t o generate a
meassage fl which is based on a t rul y r andom string r, and t hen use My . t o obt ai n
the prover message ~ correspondi ng t o this ~, wi t hout giving Me . access to r.
Machi ne M operates as follows: On i nput x, machi ne M performs the following
actions:
(1) Chooses a r andom string r and comput es 8" = V(x, r).
(2) Runs Mr . ( X, ~ff*). If My . produces a legal conservat i on [x,/~*, r' , (/~*, g)] (r'
is the r andom string generat ed by the si mul at or t o emul at e V*'s r andom i nput
in a real interaction), discard r' and got o (3). Otherwise reject.
(3) Out put s p( x, r, ~).
Soundness o f M. Not e t hat as far as V (or its simulated version) is concerned,
we are i mi t at i ng exactly the process of the interactive proof: a r andom string r is
chosen and a message ~ = V( x, r) comput ed. This message is sent t o some ot her
machine, which returns a message a. Then p(x, r, ~) is used t o det ermi ne whet her
to accept or reject. All we have done is substitute the si mul at or for the prover
as a means of generat i ng the message a. Therefore the soundness of M follows
directly from the soundness condi t i on of interactive proofs: if x r L and My .
coul d generate an ~t for which p( x, r, ~) = A C C with nonnegligible probability, t hen
a prover P* using M v , coul d do the same, violating the soundness of the underl yi ng
interactive proof. It is clear therefore t hat M will reject any x r L with very high
probability.
24 o. Goldreich and Y. Oren
Co mp l e t e n e s s o f M . I f x e L, t hen P, whe n i nt er act i ng wi t h t he pr especi f i ed V, is
g u a r a n t e e d t o be a bl e t o gener at e an " a ns we r " ~t s uch t ha t p ( x , r, ~t) = A C C f or
a l mo s t a n y r a n d o m st r i ng r. Su p p o s e n o w t ha t P i nt er act s wi t h V*, a n d t ha t V*
has as auxi l i ar y i nput a st r i ng fl s uch t ha t fl = V ( x , r) f or s o me r a n d o ml y c hos e n r.
Si nce r is r a n d o ml y c hos e n a n d fl is c o mp u t e d a c c or di ng t o t he pr ot oc ol , a p r o v e r
P has n o wa y of k n o wi n g t ha t it is i nt er act i ng wi t h a ma c hi ne ot he r t ha n V, a nd will
t her ef or e be ha ve exact l y as whe n i nt er act i ng wi t h V, t ha t is, will a t t e mp t t o ge ne r a t e
an 9 s uch t ha t p ( x , r, Qt) = A C C . The s i mul a t or i n t he case of per f ect auxi l i ar y- i nput
z e r o- knowl e dge ge ne r a t e s t he s a me di s t r i but i on as P, a n d will t her ef or e al s o gener -
at e a s ui t abl e ~t. The c ompl e t e ne s s c o n d i t i o n of i nt er act i ve pr oof s c a n t her ef or e be
us ed her e t o es t abl i s h t he c ompl e t e ne s s of M. The f ol l owi ng a da pt i ng l e mma will
s h o w t ha t t hi s is t r ue even f or n o n u n i f o r m c o mp u t a t i o n a l z e r o- knowl e dge .
Le t l,(n) be t he l engt h of t he r a n d o m st ri ng us ed b y V whe n i nt er act i ng o n i nput
of l engt h n.
Lemma 4.4.1. I f { ( P( x) , V*(x, Y))}x,y a n d {Mr. (X, Y)}x,y a r e n o n u n i f o r ml y p o l y n o -
mi a l l y i n d i s t i n g u i s h a b l e , t hen, f o r al l b u t p e r h a p s a f i n i t e s e t o f x e L , i f f l * = V ( x , r)
f o r r ~ R{O, 1 }t~lxl~ a n d ~ i s o b t a i n e d f r o m t h e o u t p u t o f Mv.(X, fl*), t h e n w i t h v e r y h i g h
p r o b a b i l i t y p ( x , r, ~) = A C C .
Pr oof . A hi s t or y des cr i pt i on H, or i gi nat i ng ei t her f r om { ( P( x) , V*(x, Y)>}x~y o r
f r om { Mv . ( X , Y)}x;y, will be of t he f or m n = [x, fl*, r' , (fl*, ct)], wher e fl* is t he
auxi l i ar y i nput t o V* (used as t he verifier' s first message) a nd r ' is V*' s r a n d o m
string. Ob s e r v e t hat r ' a l mos t cer t ai nl y is n o t t he r a n d o m st r i ng r us e d t o c o mp u t e
fl*, a nd is act ual l y i gnor e d b y V*.
As s t a t e d earl i er, t he a ge ne r a t e d by t he p r o v e r is g u a r a n t e e d b y t he c ompl e t e ne s s
c ondi t i on of i nt er act i ve pr oof s t o ha ve t he f ol l owi ng pr ope r t y: ~ will c a us e p ( x , r, ~)
t o e va l ua t e t o A C C wi t h ver y hi gh pr oba bi l i t y, p r o v i d e d t ha t r is t he r a n d o m st r i ng
us ed t o ge ne r a t e t he fl*. I f t hi s p r o p e r t y doe s n o t hol d f or t he ~t's o b t a i n e d f r om t he
o u t p u t o f Mv . ( X , fl*), t hen a di s t i ngui s her t est i ng f or t hi s p r o p e r t y s houl d be abl e
t o di st i ngui sh { ( P ( x ) , V* ( x , y)>}x;y f r om {Mvo( X, y)}x~y. Ho we v e r , gi ven onl y H, t he
di s t i ngui s her has no i dea whi ch r a n d o m st r i ng r was us e d t o cr eat e fl* a n d t her e-
f or e has n o wa y t o pe r f or m t he r equi r ed test. We use t he auxi l i ar y i nput t o t he
di st i ngui sher , z, as a me a ns t o s uppl y t he di s t i ngui s her wi t h t he " t r ue " r a n d o m st r i ng
c o r r e s p o n d i n g t o t he c onve r s a t i on on i t s ma i n i nput .
As s ume a c o n s t a n t c > 0 a nd an i nfi ni t e s equence S e q of x ~ L exi st s f or whi ch
t he ct p r o d u c e d b y r unni ng M r . ( X , fl*), wher e fl* = V ( x , r) a n d r ~ R{0, 1 }t,(lxl~, caus es
p ( x , r, ~t) t o e va l ua t e t o R E J wi t h c- nonnegl i gi bl e pr oba bi l i t y.
De n o t e b y pMc(x, r) t he p r o b a b i l i t y t ha t p ( x , r, or) e va l ua t e s t o A C C whe r e fl* =
V ( x , r) a nd ~t is o b t a i n e d b y r unni ng M r . ( X , fl*). Si mi l arl y, e
p,~c(x, r) de not e s t he
p r o b a b i l i t y t ha t p ( x , r, ~t) e va l ua t e s t o A C C wher e fl* = V ( x , r) a nd ~ is o b t a i n e d
b y r unni ng ( P( x ) , V* ( x , f l *) ) .
Le t p~c( x) be def i ned by
1 M
Definitions and Properties of Zero-Knowledge Proof Systems 25
and pC, co(x) by
1
P
p o , c ( x ) = Z ~ " p ~ ( x , r).
By our assumpt i on some c > 0 exists such t hat , for every x ~ Seq,
1
p~(x) - p~ >_ - -
i x l r
It follows t hat , for every x ~ Seq, some r exists such t hat
1
P
- p o c , ( x , r ) >_ ixlr
p , ~ c ( x , r ) u
Consi der the following distinguisher A: on i nput a conversat i on Ix, fl*, r' , (fl*, ct)]
and auxiliary i nput r, A comput es p( x, r, ct) and out put s 1 if the comput at i on results
in ACC.
Clearly, for every x ~ Seq, some r exists and fl* = V( x, r) such t hat A (running
with auxiliary i nput r) will c-distinguish between Mv. ( X, [3*) and (P(x), V*(x, [3")).
We concl ude t hat {Mv. ( X, Y)}x;y and {(P(x), V*(x, Y))}x;y are not nonuni f or ml y
pol ynomi aUy indistinguishable. []
The t heorem follows.
[]
4.5. Auxi l i ar y- I nput Zer o- Knowl edge Pr o o f Syst ems with Deterministic Provers
In this subsection we show t hat any l anguage which has an auxi l i ary-i nput zero-
knowl edge pr oof system in which the prover is deterministic belongs t o BPP. The
pr oof generalizes the pr oof met hod (but not the results) of the one-step and two-step
cases. As in those cases, we i nt end t o si mul at e the process of the interactive proof.
Our pr oof relativizes, and t hus in view of [AH2] will not ext end to [ GMR1]
zero-knowledge.
Theorem 4.5. Le t L be any language. I f L has an auxi l i ary-i nput zero-knowl edge
pr oof syst em in which t he prover is deterministic, then L ~ BPP.
Proof. If P is deterministic, t hen the following holds: the entire conversat i on
between P and V is fully det ermi ned by x and by r, the verifier's r andom string.
Fur t her mor e, P' s i t h message 0t i depends onl y on x and on [31 . . . . , fli. We exploit
this propert y in our proof. As in the one-step and two-step cases, we imitate V's
view of the interactive proof, using the si mul at or t o generate the prover messages.
We begin by choosi ng a r andom string r, and const ruct the unique conversat i on
correspondi ng to r and x round-by-round. At first, we use the si mul at or t o generate
~o (and ignore the rest of the text). Once we have ~o, we can comput e fll as V would,
using the r andom string r. We now run the si mul at or again, this time "forcing" the
verifier t o use the comput ed fll as its first message. This is achieved by placing [31
on the verifier's auxiliary input. Since the prover is deterministic (and the si mul at or
must also be "deterministic in some sense" as we shall see) we can be sure t hat the
26 O. Goldreich and Y. Oren
same 0t o will be comput ed for t he new conversat i on, and t herefore t he fll we
comput ed will be a legal verifier message in t he new conver sat i on (t hat is, a string
r exists such t hat fll = V(x, r, ~o))- Fr om t he new conver sat i on we obt ai n ~1, and
so on. We t hus r econst r uct t he ent i re conversat i on, while not revealing r t o the
si mul at or t hr oughout t he process. Once we have all t he pr over messages, we use p
t o deci de whet her t o accept or reject. It is easy t o see t hat this met hod woul d not
work if t he pr over were not deterministic. Consi der, for example, a t hree-st ep pr ot o-
col: we coul d first r un t he si mul at or t o obt ai n (some) ~t o. We coul d t hen comput e a
suitable fll and "force" t he verifier t o use it as its message. However , in the new
conver sat i on we woul d pr obabl y have a compl et el y different ~o (because P is not
det ermi ni st i c and may have mor e t han one possible ~o) and t he comput ed fl~ woul d
no l onger be a legal message in t hat conversat i on. As a result, we coul d not use
t he new conver sat i on t o obt ai n a meani ngful ~q.
Construction o f t he B P P Machi ne. Consi der a "verifier" V* in t he auxi l i ary i nput
model , which when havi ng a string [fl*, fl~' . . . . , p*] on its auxi l i ary i nput uses fl*,
fl~', . . . , fl* as its i first messages t o t he prover, and t hen comput es t he rest of its
messages in an ar bi t r ar y manner. Since t he pr ot ocol is auxi l i ary-i nput zero-knowl -
edge, a probabi l i st i c pol ynomi al - t i me machi ne My . exists which simulates t he
i nt er act i on of V* and P. We use My , t o build a BPP machi ne, denot ed M, for t he
l anguage L: On i nput x, machi ne M proceeds as follows:
Choose r andom r.
Run Mv. ( X ) with empt y auxi l i ary i nput (or simply My( x) , t he si mul at or
with respect t o t he prespecified verifier V) t o obt ai n ~o (discard the rest of
t he text).
For i : = l t o k do
Comput e fli "- V(x, r, ~o . . . . . ~i-1).
Run Mv . with auxi l i ary i nput [fl~, f12 . . . . . fl~] t o obt ai n ~ (which is
our "guess" for P( x, fit . . . . . fl~)). Di scard t he rest of t he text.
enddo
out put p( x, r, ~t o . . . . . ~k)
Soundness o f M. As was t he case for t he one-st ep and t wo-st ep proofs, in this case
we i mi t at e exact l y t he process of t he i nt eract i ve pr oof as far as V is concerned, onl y
subst i t ut i ng t he si mul at or for the pr over as a means of generat i ng ~o . . . . . ~k. The
si mul at or comput es ~ti at stage i while havi ng no knowl edge of t he r andom string
used t o comput e fl~ . . . . . fl~, precisely t he condi t i ons under which P must comput e
~t i in a real i nt eract i on. It follows t hat Mv. ' S ability t o generat e, under these
condi t i ons, a set of messages ~o . . . . . 0tk for which g( x, r, 0to . . . . . ~tk) eval uat es t o A C C
with nonnegl i gi bl e pr obabi l i t y implies t he ability of some pr over P* t o do t he same
in a real i nt eract i on. The soundness of M t herefore follows from t he soundness of
the underl yi ng i nt eract i ve proof. Not e t hat t he soundness condi t i on does not
depend in any way on t he "zero-knowl edge-ness" of t he prot ocol .
Completeness o f M. Consi der an i nt er act i on on i nput x. Let fl~ . . . . . ~ be t he first
i verifier messages of t he uni que conver sat i on cor r espondi ng t o x and t o some
Definitions and Properties of Zero-Knowledge Proof Systems 27
r a n d o m st r i ng r. The p r o v e r P, whe n i nt er act i ng o n x wi t h a veri fi er t ha t us es
fll . . . . . fit as i t s first i messages, will o u t p u t t he mes s ages ~t o . . . . . ~t t c o r r e s p o n d i n g t o x
a n d r. Thi s is t r ue i n pa r t i c ul a r f or t he pr e vi ous l y de s c r i be d veri fi er V*. No t unt i l
it r ecei ves t he mes s age flt+l c a n P ( per haps ) real i ze it is i nt er act i ng wi t h a c he a t e r
V* a n d n o t wi t h t he we l l - be ha ve d E The r e f or e al l i t s mes s ages u p t o t ha t p o i n t will
be as speci fi ed b y t he pr ot oc ol . I n t he cas e o f per f ect z e r o- knowl e dge , t he t ext s o f
Mr 9 will ha ve t he s a me pr ope r t y. I n par t i cul ar , at r o u n d i t he mes s age ~t o b t a i n e d
f r om t he s i mul a t i on t ext will be t he uni que P(x, fll . . . . . fit) c o r r e s p o n d i n g t o x a n d
t he r a n d o m st r i ng r chos en. I n all, t he s e que nc e ~o . . . . . ~k o f p r o v e r mes s ages
ge ne r a t e d by M will be t he uni que s e que nc e c o r r e s p o n d i n g t o x a n d r, a nd t her ef or e
t he c ompl e t e ne s s of M f ol l ows f r om t he c ompl e t e ne s s of ( P , V) .
We n o w p r o c e e d t o a d a p t t he a r g u me n t t o c o mp u t a t i o n a l z e r o- knowl e dge . We
ne e d t o p r o v e t hat , at r o u n d i, t he mes s ages 0t o . . . . . at ge ne r a t e d b y My , o n i nput
x a nd auxi l i ar y i nput [fl~ . . . . . f t ] ar e wi t h ver y hi gh p r o b a b i l i t y P(x), P(x, flit), . . . .
P(x, f~ . . . . . ft). We fi rst a ddr e s s t he f ol l owi ng ques t i on:
Si ngl e Element Question. Le t {n~' }~a be a di s t r i but i on e ns e mbl e havi ng t he
f ol l owi ng pr ope r t y: f or ever y l ar ge e n o u g h x t he pr oba bi l i t y di s t r i but i on n~ assi gns
hi gh p r o b a b i l i t y t o o n e el ement , d e n o t e d trx (in o u r case, t he di s t r i but i on c r e a t e d
b y t he p r o v e r is t ot a l l y det er mi ni st i c, t ha t is, assi gns p r o b a b i l i t y 1 t o s o me t ext try).
Le t {n[ }x~o be a di s t r i but i on e ns e mbl e whi ch is p o l y n o mi a l l y i ndi s t i ngui s habl e
f r om {rc~'}x~o. Mu s t {n~}~ ha ve essent i al l y t he s a me p r o p e r t y (i.e., f or ever y l ar ge
e n o u g h x, t he di s t r i but i on n~ assi gns hi gh pr oba bi l i t y t o try)?
Bef or e a t t e mp t i n g t o a n s we r t hi s ques t i on, l et us e xa mi ne mo r e cl os el y t he n o t i o n
of p o l y n o mi a l i ndi s t i ngui s habi l i t y. I n t he def i ni t i on of p o l y n o mi a l i ndi st i ngui sh-
abi l i t y us e d t h r o u g h o u t t he paper , t wo di s t r i but i on e ns e mbl e s {n~}~ a n d {~z[}~,
cl ai med t o be p o l y n o mi a l l y i ndi s t i ngui s habl e, mu s t sat i sfy t he f ol l owi ng condi t i on:
a n y p o l y n o mi a l - t i me pr oba bi l i s t i c al gor i t hm, o n i nput a si ngl e st r i ng s a mpl e d f r om
{~z~'}x, mu s t b e h a v e a p p r o x ma t e l y t he s a me as whe n gi ven a st r i ng s a mpl e d f r om
{Tt]}~. Anot he r , pos s i bl y st ri ct er, def i ni t i on is t h e fol l owi ng: a n y p o l y n o mi a l - t i me
al gor i t hm, o n i nput a sequence ( of c o n s t a n t o r p o l y n o mi a l size) o f st ri ngs s a mpl e d
f r om { ~ } x , mu s t b e h a v e a p p r o x i ma t e l y t he s a me as when gi ven a s e que nc e o f
st r i ngs s a mpl e d f r om {n[}~. We refer t o t he first ver s i on of t he def i ni t i on as
single-sample p o l y n o mi a l i ndi st i ngui shabi l i t y, a nd t o t he s e c ond as multiple-sample
p o l y n o mi a l i ndi st i ngui shabi l i t y.
Mul t i pl e - s a mpl e p o l y n o mi a l i ndi s t i ngui s habi l i t y be a r s r el evance t o o u r di scus-
s i on d u e t o t he f ol l owi ng fact: whe n usi ng t he mul t i pl e - s a mpl e def i ni t i on a pos i t i ve
a n s we r t o t he si ngl e el ement q u e s t i o n p o s e d ear l i er c a n be easi l y pr ove d, p r o v i d e d
t ha t {n~}~ c a n be s a mpl e d i n p o l y n o mi a l t i me. The f ol l owi ng t wo cl ai ms d e mo n -
s t r a t e this.
Claim 4.5.1. Let {n~'}x assign hioh probability (say _>3/4) to ax f or every laroe
enouoh x and let {n~'}x and {rc~}x be multiple-sample polynomially indistinguishable.
Then {n[}~ must, f or every laroe enouoh x, assion very hioh probability (say > 3/5)
to exactly one strino, denoted tr'~.
28 O. Goldreich and Y. Oren
Proof. Assume to the contrary that no string appears in n[ with high probability
(i.e., higher than 3/5). Consider the following two-sample distinguisher A: on input
two strings, s~ and s2, algorithm A outputs 1 if s~ = s2 and 0 otherwise. If s~, s2
were sampled from {n~'}~, then s~ = s2 with very high probability (namely, > (3/4)2).
On the other hand, if sl, s2 were sampled from {n[}~, then sl = s2 with too
low probability (namely, 13/25 < 9/16). Therefore A will distinguish {~'}~ from
[ ]
The above claim guarantees that {n[}x assigns very high probability to a single
string. We now show that this string must be o~ (single-sample polynomial
indistinguishability suffices to prove the following claim).
Claim 4.5.2. Let {n~'}~D be a distribution ensemble such that, Yx ~ D, the distribu-
tion n~ assigns probability at least 89 + 8 to one string, denoted ox. Let {rr~}~a be a
distribution ensemble such that, Yx ~ D, the distribution ~ assigns probability at least
1 r
+ e to one string, denoted ax. I f {n~'}~ and {n[}~ are polynomially indistinguishable
and {n[}x can be sampled in polynomial time, then, f or all but f i ni t el y many x ~ D,
string a~ equals strino a' .
Proof. If otherwise, consider the following distinguisher A: on input a string s,
algorithm A samples ~ to obtain, with overwhelmingly high probability, string a;,
(which by hypothesis is different from ax). (The number of sample points is polyno-
mial in 1/e.) The algorithm outputs 1 if s = a" and 0 otherwise. If s comes from hi ,
then with probability > 89 + ~ we have s = a' . If, on the other hand, s comes from
~ , then with probability > 89 + 8 we have s = ax and hence (assuming a'x # ax)
s ~ a" (with probability > 89 + 8). Therefore A will distinguish {n~ }~ from {n~}~. []
All that remains in order to answer the single element question for single-sample
polynomial indistinguishability is to show, if we can, that single-sample polynomial
indistinguishability is equivalent to multiple-sample polynomial indistinguishabil-
ity. However, can we? Polynomial indistinguishability was originally discussed in
the context of probabilistic encryption [ GM] and pseudorandom generators [Y].
In these cases the distributions of both the ensembles which are assumed to be
polynomially indistinguishable can be sampled in polynomial time. This fact can
be used to prove that in these contexts single-sample polynomial indistinguish-
ability (the usual definition) and multiple-sample polynomial indistinguishability
are equivalent (intuitively, becase the distinguisher can generate additional samples
by itself).1 The same proof cannot be applied, however, in general and in particular
in the context of zero-knowledge, because in this case one of the distribution
ensembles, mainly ( P, V) , cannot be sampled in polynomial time.
We return to our original question. Since we cannot demonstrate the equivalence
single-sample polynomial indistinguishability to multiple-sample polynomial indis-
tinguishability, we must adopt a different approach. We now demonstrate that
1 In [ GGM] Goldreich e t al . define multiple-sample polynomial indistinguishabifity and prove its
equivalence to single-sample polynomial indistinguishability in the context ofpseudorandom generators.
Definitions and Properties of Zero-Knowledge Proof Systems 29
even under single-sample pol ynomi al indistinguishability, {Tt[}~ must assign very
high probabi l i t y t o tT~ (the string assigned high probabi l i t y by g]'). For any distribu-
t i on g and string s, we denot e by it(s) the probabi l i t y assigned by ~ to s.
Single Element Lemma. Let e <_ 89 Let {lt~}~ D and {l t [ }~ a be polynomially
indistinguishable distribution ensembles such that ~ and ~ are probability distribu-
tions over strinfs of length polynomial in Ix[. Assume that, f or every laroe enough x,
some strino, denoted tT~, exists such that ~ assions to tTx probability >_ 1 - e. Assume
further that {~z~}~ a can be sampled in polynomial time ( thouoh { ~ } ~ D may not be).
Then ~( a~) > 1 - 2e f or all but f i ni t el y many x.
Proof. Assume an infinite sequence Seq of x' s exists such t hat g[ assigns Gx
probabi l i t y at most 1 - 2e.
For any x ~ Seq there must be one or more strings s such t hat ~[(s) > 0 (a~ may
or may not be one of them). These strings can be arranged in lexicographical order.
For any two strings sl , s2, we write sl < s2 to mean t hat sa precedes s2 in lexico-
graphical order, s~ _< s2 means sa < s2 or sx = s2.
Let P~- be defined by
P ; = {sl~}s~_r It~(s)
and P+ by
Z
{sis _<ox}
Example. Let ax = 100 and ~ assign probabi l i t y 1/5 to each of the following
strings: 00, 01, 000, 100, 1001. Then P~- = 3/5 and P+ = 4/5. If (~x = 100 and) ~
assigns probabi l i t y 1/4 t o each of the strings 00, 01,000, 1001, t hen P~- = P] = 3/4.
For any x ~ Seq, we have three possible cases (not necessarily distinct):
(1) P+ < 0.8.
(2) P ; > 0.2.
(3) P+ _ 0.8 and Px- < 0.2.
Denot e by S t, 1 < i _ 3, the subsequence of Seq such t hat x ~ Si if case i holds for
x. Clearly, at least one of the subsequences must be infinite. We now show how t o
handl e each of the correspondi ng cases.
Case (1). Assume S~ is infinite. Let us first prove the following claim:
Cl ai m 4.5.3. Let ~ be any probability distribution on strings. A k-experiment on
will consist of sampling k times the distribution ~. Denote by si, i <_ k, the result of
the ith sampling in the k-experiment. Let P~ denote the probability that the sample si
is larger or equal to all of the samples (i.e. Pi = Prob(Vj, si >_ s~)). Then P1 >- 1/k.
P r o o f . For reasons of symmet ry, Vi, j _< k, Pi = Pj. Since in every k-experiment
there must be at least one maxi mal value, it follows t hat ~i kl Pi _ 1, and therefore,
Vi < k, P~ > 1/k. []
30 o . Goldreich and Y. Oren
C o n s i d e r n o w t h e f o l l o wi n g d i s t i n g u i s h e r , A: o n i n p u t a s t r i n g s, t h e d i s t i n g u i s h e r
A f i r s t s a mp l e s n~ f o r k - 1 t i me s (k is a c o n s t a n t t o b e d e t e r mi n e d l at er ) . I t t h e n
o u t p u t s 1 i f s is g r e a t e r t h a n o r e q u a l t o e a c h o f t h e k - 1 s a mp l e d s t r i ngs . S u p p o s e
s wa s s a mp l e d f r o m n~. We c a n vi e w t h e wh o l e p r o c e s s a s a k - e x p e r i me n t o n ~ , i n
wh i c h s i s t h e f i r st s a mpl e . By t h e a b o v e c l a i m, t h e p r o b a b i l i t y t h a t A o u t p u t s 1 i n
t hi s c a s e is g r e a t e r t h a n o r e q u a l t o 1/k. O n t h e o t h e r h a n d , i f s wa s s a mp l e d f r o m
rt~' ( i n wh i c h c a s e s = tr x wi t h p r o b a b i l i t y > 1 - e ) , t h e n ( f or e v e r y x ~ $1) t h e
p r o b a b i l i t y o f a s i ngl e s a mp l e b e i n g s ma l l e r t h a n o r e q u a l t o s is l ess t h a n
( 1 - e ) - 0. 8 + e < 0. 9 ( t he f i r s t t e r m i s f o r t h e c a s e s = trx). T h e p r o b a b i l i t y t h a t al l
k - 1 s a mp l e s wi l l b e s ma l l e r t h a n o r e q u a l t o s, i s t h u s l ess t h a n 0. 9 k-1. A s u i t a b l e
c h o i c e o f k ( s a y k = 50) yi e l ds 0. 9 k-~ < 1/(2k). Cl e a r l y , f o r a n y x ~ $1, a l g o r i t h m A
wi l l d i s t i n g u i s h b e t we e n ~r~' a n d n~, a n d t h e r e f o r e t h e d i s t r i b u t i o n e n s e mb l e s c a n n o t
be p o l y n o mi a l l y i n d i s t i n g u i s h a b l e .
Cas e (2). As s u me $2 is i nf i ni t e. Th i s c a s e i s s y mme t r i c t o t h e p r e v i o u s cas e, s i nce
i f we r e v e r s e t h e l e x i c o g r a p h i c a l o r d e r we o b t a i n P~+ < 0. 8. I t c a n t h e r e f o r e b e
h a n d l e d i n t h e s a me wa y.
Cas e (3). As s u me $3 is i nf i ni t e. I n t hi s c a s e r e v e r s i n g t h e l e x i c o g r a p h i c a l o r d e r wi l l
st i l l l e a ve s us i n t h e s a me cas e. Ob s e r v e , h o we v e r , t h a t i f P~+ > 0. 8 a n d P~- < 0. 2, i t
mu s t be t h a t lr~(trx) > 0.6. I n s u c h a c a s e we c a n f i nd tr~ wi t h s uf f i ci ent c o n f i d e n c e
b y s a mp l i n g rr~ a p o l y n o mi a l n u mb e r o f t i mes . C o n s i d e r a d i s t i n g u i s h e r A whi c h,
o n i n p u t a s t r i n g s, s a mp l e s n~ e n o u g h t i me s t o p i c k o u t , wi t h v e r y h i g h p r o b a b i l i t y
( s a y > 1 - e/3), a s t r i n g s ' f o r wh i c h rr~(s' ) > 0. 6, a n d t h e n o u t p u t s 1 i f s = s' . We
h a v e Pr o b ( s ' = a~) > 1 - # 3 . F o r a n y x, x ~ S3, i f s wa s s a mp l e d f r o m n~', t h e n
Prob~7(s = s ' ) > 1 - e - # 3 . We s t a r t e d o u t t h e p r o o f b y a s s u mi n g t h a t , f o r a n y
x ~ Se q ( a n d t h e r e f o r e f o r a n y x e $3), n~(a~) < 1 - 2e a n d h e n c e P r o b ~ ( s = s ' ) <
1 - 2e + # 3 . Cl e a r l y , A wi l l d i s t i n g u i s h b e t we e n {zr~'}~ ~ o a n d {rr~ }~ ~ o ( wi t h g a p # 3 ) .
T h e l e mma f ol l ows . [ ]
We n o w r e t u r n t o o u r o r i g i n a l g o a l o f a d a p t i n g t h e c o mp l e t e n e s s a s s e r t i o n o f M
t o t h e c a s e o f c o mp u t a t i o n a l z e r o - k n o wl e d g e . T h e c o r r e s p o n d i n g a d a p t i n g l e mma
is a n e a s y c o n s e q u e n c e o f t h e Si ngl e E l e me n t L e mma .
L e m m a 4. 5. 1. L e t D be t he s et o f al l pai r s ( x, y) f o r whi ch x ~ L and y = [ fll . . . . . fli],
such t hat , f o r s ome r andom s t r i ng r,
fll = V( x , r, [0t o = P ( x ) ] ) ,
f12 = V( x , r, [0c o = P( x ) , ot x = P( x , i l l ) ] ) ,
fli = V( x , r, [ ao = P( x ) , oq = P( x , i l l ) . . . . . ~q-1 = P( x , f i t , f12 . . . . . f l i - l ) ] ) .
I f t he di s t r i but i on ens embl es { Mv . ( X, Y)}(x,y)~o and {(P(x), V*(x, Y) 5 } t x , ~ o ar e
p o l y n o mi a l l y i ndi s t i ngui s habl e, t he n i n t he t e x t s pr oduc e d b y M y . on i nput x and y
wi t h ver y hi gh pr obabi l i t y,
Vj <_ i, ctj = P( x , i l l , f12 . . . . . fl~).
Definitions and Properties of Zero-Knowledge Proof Systems 31
Proof. For every j < i, let n] x'y) be the distribution of the first j + 1 prover
messages in P' s interaction with V* on input x and auxiliary input y = [fix . . . . . flj]
(note that this distribution depends solely on x and y and not on V*'s random
string). Let rc~ x'y) be the distribution of the first j + 1 "prover messages" produced
by My* on input x and y. Clearly, if { (P(x), V*(x, Y))}~x,y~D and {Mv,(X, Y)}~[Link]~o
are polynomially indistinguishable, then so are t i J~.y)~D and {n~x'Y~}~.yj~ D. The
ensemble {n~ x'y)}~x,y)~ o clearly can be sampled in polynomial time, and n] ~' y~ assigns
one string (namely, [P(x), P(x,/~1) . . . . . P(x, ~ , . . . , / ~ j ) ] ) probability 1 for any
(x, y) e D. We can thus apply the Single Element Lemma.
We conclude that, at round i, machine My , will produce, with very high probabil-
ity, the messages P(x) . . . . . P(x, ~ . . . . . ~i) corresponding to x and the string r used
to compute/~1 . . . . . /~i. []
The theorem follows. []
Remark 4.3. The fact that single-sample and multiple-sample polynomial indis-
tinguishability may not be equivalent in the context of zero-knowledge raises the
following questions, which deserve further investigation: can single-sample and
multiple-sample polynomial indistinguishability be proved equivalent or strictly
different in the context of zero-knowledge (i.e., when one ensemble cannot be
sampled in polynomial time)? If they are different, which should be used in a
"correct" cryptographic definition of zero-knowledge? Observe that the two defini-
tions are equivalent if the distinguisher is allowed to have auxiliary input, as in the
definition of "nonuniform" polynomial indistinguishability presented in the previ-
ous subsection.
4.6. A Remark on Extension to Zero-Knowl edge Arguments
The results of the pevious subsections extend to the zero-knowledge argurhents
introduced in [BCC]. In these protocols it is guaranteed that no efficient way of
fooling the verifier to accept false statements exists. This is a relaxion of the
soundness condition in interactive proofs where it is required that no way of fooling
the verifier (to accept false statements) exists. In the extensions we use exactly the
same constructions of BPP machines, and the same reasoning for the completeness
condition (i.e. that th~ machine accepts, with high probability, inputs in the lan-
guage). For the soundness of the BPP machine (i.e., showing that it rejects, with high
probability, inputs not in the language) we use a slightly more careful reasoning.
Recall that the soundness of the BPP machine is proved by relying on the soundness
of the protocol. In fact, in all cases we have shown that a violation of the soundness
of the BPP machine yields violation of the soundness condition for interactive
proofs. This, in turn, was done by incorporating the "cheating BPP machine" inside
of a "cheating prover." Hence, the "cheating prover" constructed in all cases is
indeed efficient and thus contradicts the soundness condition of zero-knowledge
arguments as well.
32 O. Goldreich and Y. Oren
Acknowledgments
We woul d like to thank Shi mon Even for maki ng useful comment s on the paper.
The concept of Las Vegas interactive proofs was raised by Manual Bl um and
communi cat ed through Silvio Micali. The questi on of triviality of proof systems
with deterministic provers was raised by Shi mon Even.
[AH1]
[AH2]
[B]
[BCC]
[FS]
IF]
[ GGM]
[ GK]
[GMS]
[GMW1]
[GMW2]
[GM]
[GMR1]
[GMR2]
[GS]
ElY]
[O1]
[ 02]
[S]
[TW]
IV]
References
Aiello, W., and J. Hastad, Perfect Zero-Knowledge Languages Can Be Recognized in Two
Rounds, Proc. 28th FOCS, 1987, pp. 439-448.
Aiello, W., and J. Hastad, Relativized Perfect Zero-Knowledge Is Not BPP, Inform. and
Comput., Vol. 93, 1992, pp. 223-240.
Babai, L., Trading Group Theory for Randomness, Proc. 17th STOC, 1985, pp. 421-429.
Brassard, G., D. Chaum, and C. Crepeau, Minimum Disclosure Proofs of Knowledge,
J. Comput. System Sci., Vol. 37, No. 2, Oct. 1988, pp. 156-189.
Feige, U., and A. Shamir, Personal communication.
Fortnow, L., The Complexity of Perfect Zero-Knowledge, Proc. 19th STOC, 1987,
pp. 204-209.
Goldreich, O., S. Goldwasser, and S. Micali, How To Construct Random Functions, J. Assoc.
Comput. Mach., Vol. 33, No. 4, 1986, pp. 792-807.
Goldreich, O., and H. Krawczyk, On the Composition of Zero-Knowledge Proof Systems,
Proc. 17th ICALP, Lecture Notes in Computer Science, Vol. 443, Springer-Verlag, Berlin,
1990, pp. 268-282.
Goldreich, O., Y. Mansour, and M. Sipser, Interactive Proof Systems: Provers that Never
Fail and Random Selection, Proc 28th FOCS, 1987, pp. 449-461.
Goldreich, O., S. Micali, and A. Wigderson, Proofs that Yield Nothing but their Validity and
a Methodology of Cryptographic Protocol Design, Proc. 27th FOCS, 1986, pp. 174-187.
Goldreich, O., S. Micali, and A. Wigderson, How to Play any Mental Game or a Complete-
ness Theorem for Protocols with Honest Majority, Proc. 19th STOC, 1987, pp. 218-229.
Goldwasser, S., and S. Micali, Probabilistic Encryption, J. Comput. System Sci., Vol. 28,
No. 2, 1984, pp. 270-299.
Goldwasser, S., S. Micali, and C. Rackoff, Knowledge Complexity of Interactive Proofs, Proc.
17th STOC, 1985, pp. 291-304.
Goldwasser, S., S. Mieali, and C. Rackoff, The Knowledge Complexity of Interactive Proof
Systems, SI AM J. Comput., Vol. 18, No. 1, 1989, pp. 186-208.
Goldwasser, S., and M. Sipser, Arthur Merlin Games Versus Interactive Proof Systems, Proc.
18th STOC, 1986, pp. 59-68.
Impagliazzo, R., and Yung, M., Direct Minimum-Knowledge Computations, Advances
in Cryptology--Crypto 87 (proceedings), Lecture Notes in Computer Science, Vol. 293,
Springer-Verlag, Berlin, 1987, pp. 40-51.
Oren, Y., Properties of Zero-Knowledge Proofs, [Link]. Thesis, Computer Science Depart-
ment, Technion, Haifa, Nov. 1987 (in Hebrew).
Oren, Y., On the Cunning Power of Cheating Verifiers: Some Observations about Zero-
Knowledge Proofs, Proc. 28th FOCS, 1987, pp. 462-471.
A. Shamir, IP = PSPACE, Proc. 31st FOCS, 1990, pp. 11-15.
Tompa, M., and H. Woll, Random Self-Reducibility and Zero-Knowledge Interactive Proofs
of Possession of Information, Proc. 28th FOCS, 1987, pp. 472-482.
Yao, A. C., Theory and Applications of Trapdoor Functions, Proc. 23rd FOCS, 1982,
pp. 80-91.