Computational Complexity and Knowledge Complexity.
We study the computational complexity of languages which have interactive proofs of logarithmic knowledge complexity.  We show that all such languages can be recognized in ${\cal BPP}^{\cal NP}$.  Prior to this work, for languages with greater-than-zero knowledge complexity only trivial computational complexity bounds were known. In the course of our proof, we relate statistical knowledge complexity to perfect knowledge complexity; specifically, we show that, for the honest verifier, these hierarchies coincide up to a logarithmic additive term.
Introduction
The notion of knowledge-complexity was introduced in the seminal paper of Goldwasser
Micali and Rackoff [GMR-85, GMR-89]. Knowledge-complexity (KC) is intended to measure
the computational advantage gained by interaction. Satisfactory formulations of knowledge-
complexity, for the case that it is not zero, have recently appeared in [GP-91]. A natural
suggestion, made by Goldwasser, Micali and Rackoff, is to classify languages according to
the knowledge-complexity of their interactive-proofs [GMR-89]. We feel that it is worthwhile
to give this suggestion a fair try.
The lowest level of the knowledge-complexity hierarchy is the class of languages having
interactive proofs of knowledge-complexity zero, better known as zero-knowledge. Actually,
there are three hierarchies extending the three standard definitions of zero-knowledge; namely
An extended abstract of this paper appeared in the 26th ACM Symposium on Theory of Computing
(STOC 94), held in Montreal, Quebec, Canada, May 23-25, 1994.
y Department of Applied Mathematics and Computer Science, Weizmann Institute of Science, Rehovot,
Israel. E-mail: oded@wisdom.weizmann.ac.il. Supported by grant no. 92-00226 from the United States
Israel Binational Science Foundation, Jerusalem, Israel.
z Computer Science Division, University of California at Berkeley, and International Computer Science
Institute, Berkeley, CA 94720. E-mail: rafail@cs.Berkeley.EDU. Supported by an NSF Postdoctoral
Fellowship and ICSI.
x Computer Science Department, Technion - Israel Institute of Technology, Haifa 32000, Israel. E-mail:
erez@cs.technion.ac.il.
perfect, statistical and computational. Let us denote the corresponding hierarchies by PKC(\Delta),
SKC(\Delta), and CKC(\Delta). Assuming the existence of one-way functions, the third hierarchy
collapses, namely differently,
the zero level of computational knowledge-complexity extends to the maximum possible.
Anyhow, in the rest of this paper we will be only interested in the other two hierarchies.
Previous works have provided information only concerning the zero level of these hierar-
chies. Fortnow has pioneered the attempts to investigate the computational complexity of
(perfect/statistical) zero-knowledge [F-89], and was followed by Aiello and Hastad [AH-87].
Their results can be summarized by the following theorem that bounds the computational
complexity of languages having zero-knowledge proofs.
Theorem [F-89, AH-87]:
co-AM
Hence, languages having statistical zero-knowledge must lie in the second level of the
polynomial-time hierarchy. Needless to say that function k
and in particular for k j 0.
On the other hand, if we allow polynomial amount of knowledge to be revealed, then every
language in IP can be proven.
Theorem [LFKN-90, Sh-90]:
As indicated in [GP-91], the first equality is a property of an adequate definition (of knowledge
complexity) rather than a result.
In this paper we study the class of languages that have interactive-proofs with logarithmic
knowledge-complexity. In particular, we bound the computational complexity of such
languages, showing that they can be recognized by probabilistic polynomial-time machines
with access to an NP oracle.
Main Theorem:
We recall that BPP NP is contained in the third level of the polynomial-time hierarchy
(PH). It is believed that PH is a proper subset of PSPACE. Thus, assuming PH ae
PSPACE, our result yields the first proof that there exist languages in PSPACE which
cannot be proven by an interactive-proof that yields O(log n) bits of knowledge. In other
words, there exist languages which do have interactive proofs but only interactive proofs
with super-logarithmic knowledge-complexity.
Prior to our work, there was no solid indication 1 that would contradict the possibility
that all languages in PSPACE have interactive-proofs which yield only one bit of knowledge.
Alas, if one had been willing to assume that all languages in PSPACE have interactive proofs of logarithmically
many rounds, an assumption that we consider unreasonable, then the result in [BP-92] would
have yielded a proof that PSPACE is not contained in SKC(1), provided (again) that PH ae PSPACE .
The only attempt to bound the computational complexity of languages having interactive
proofs of low knowledge-complexity was done by Bellare and Petrank. Yet, their work
refers only to languages having interactive proofs that are both of few rounds and of low
knowledge complexity [BP-92]. Specifically, they showed that if a language L has a r(n)-round
interactive-proof of knowledge-complexity O( log n
then the language can be recognized in
BPP NP .
Our proof of the Main Theorem consists of two parts. In the first part, we show that the
procedure described by Bellare and Petrank [BP-92] suffices for recognizing languages having
interactive proofs of logarithmic perfect knowledge complexity. To this end, we use a more
careful analysis than the one used in [BP-92]. In the second part of our proof we transform
interactive proofs of statistical knowledge complexity k(n) into interactive proofs of perfect
knowledge complexity k(n)+log n. This transformation refers only to knowledge-complexity
with respect to the honest verifier, but this suffices since the first part of our proof applies
to the knowledge-complexity with respect to the honest verifier. Yet, the transformation is
interesting for its own sake, and a few words are in place.
The question of whether statistical zero-knowledge equals perfect zero-knowledge is one
of the better known open problems in this area. The question has been open also for the
case of zero-knowledge with respect to the honest verifier. We show that for every poly-time
computable function k : N7!N (and in particular for k j
This result may be considered an indication that these two hierarchies may collide.
Techniques Used
As stated above, the first part of our proof consists of presenting a more careful analysis of
an existing procedure, namely the procedure suggested by Bellare and Petrank in [BP-92].
Their procedure, in turn, is a culmination of two sequences of works discussed bellow.
The first sequence originates in Fortnow's definition of a simulator-based prover [F-89].
Fortnow [F-89], and consequently Aiello and Hastad [AH-87], used the simulator-based prover
in order to infer, by way of contradiction, bounds on the sizes of specific sets. A more
explicit usage of the simulator-based prover was introduced by Bellare, Micali and Ostrovsky
specifically, they have suggested to use a PSPACE-implementation of the
simulator-based prover, instead of using the original prover (of unbounded complexity) witnessing
the existence of a zero-knowledge interactive proof system. (Thus, they obtained
a bound on the complexity of provers required for zero-knowledge proof systems.) Ostrovsky
[Ost-91] suggested to use an implementation of the interaction between the verifier
and the simulation-based prover as a procedure for deciding the language. Furthermore,
assuming that one-way functions do not exist, he used "universal extrapolation" procedures
of [ILu-90, ILe-90] to approximate the behavior of the simulator-based prover. (Thus, assuming
that one-way function do not exists, he presented an efficient procedure that decides
languages in SKC(0) and inferred that one-way functions are essential to the non-triviality
of statistical zero-knowledge). Bellare and Petrank distilled the decision procedure from the
context of one-way functions, showing that the simulator-based prover can be implemented
using a perfect universal extrapolator (also known as a "uniform generation" procedure)
[BP-92]. The error in the implementation is directly related to the deviation of the uniform
generation procedure.
The second sequence of works deals with the two related problems of approximating the
size of sets and uniformly generating elements in them. These problems were related by
Jerrum et. al. [JVV-86]. Procedures for approximating the size of sets were invented by
Sipser [Si-83] and Stockmeyer [St-83], and further improved in [GS-89, AH-87], all using the
"hashing paradigm". The same hashing technique, is the basis of the "universal extrapo-
lation" procedures of [ILu-90, ILe-90]. However, the output of these procedures deviates
from the objective (i.e., uniform distribution on the target set) by a non-negligible amount
(i.e., 1=poly(T ) when running for time T ). On the other hand, Jerrum et. al. have also
pointed out that (perfect) uniform generation can be done by a BPP \Sigma P
Bellare and Petrank combined the hashing-based approximation methods with the ideas of
[JVV-86] to obtain a BPP NP -procedure for uniform generation with exponentially vanishing
error probability [BP-92]. Actually, if the procedure is allowed to halt with no output
with constant (or exponentially vanishing) probability, then its output distribution is exactly
uniform on the target set.
Motivation for studying KC
In addition to the self-evident fundamental appeal of knowledge complexity, we wish to point
out some practical motivation for considering knowledge-complexity greater than zero. In
particular, cryptographic protocols that release a small (i.e., logarithmic) amount of knowledge
may be of practical value, especially if they are only applied once or if one can obtain
sub-additive bounds on the knowledge complexity of their repeated executions. Note that
typically, a (single application of a) sub-protocol leaking logarithmically many bits (of knowl-
edge) does not compromise the security of the entire protocol. The reason being that these
(logarithmically many) bits can be guessed with non-negligible probability, which in turn
means that any attack due to the "leaked bits" can be simulated with non-negligible probability
without them.
But why use low knowledge-complexity protocols when one can use zero-knowledge ones
(see, [GMW-86, GMW-87])? The reason is that the non-zero-knowledge protocols may be
more efficient and/or may require weaker computational assumptions (see, for example,
[OVY-91]).
Remarks
A remark concerning two definitions. Throughout the paper, SKC(k(\Delta)) and PKC(k(\Delta))
denote the classes of knowledge-complexity with respect to the honest verifier. Note that the
Main Theorem is only strengthen by this, whereas the transformation (mentioned above) is
indeed weaker. Furthermore, by an interactive proof we mean one in which the error probability
is negligible (i.e., smaller than any polynomial fraction). A few words of justification
appear in Section 2.
A remark concerning Fortnow's paper [F-89]. In course of this research, we found out
that the proof that SKC(0) ' co-AM as it appears in [F-89] is not correct. In particular,
there is a flaw in the AM-protocol presented in [F-89] for the complement language (see


Appendix

A). However, the paper of Aiello and Hastad provides all the necessary machinery
for proving Fortnow's result as well [AH-87, H-94]. Needless to say that the basic approach
presented by Fortnow (i.e., looking at the "simulator-based prover") is valid and has inspired
all subsequent works (e.g., [AH-87, BMO-90, Ost-91, BP-92, OW-93]) as well as the current
one.
Preliminaries
Let us state some of the definitions and conventions we use in the paper. Throughout this
paper we use n to denote the length of the input x. A function f called
negligible if for every polynomial p and all sufficiently large n's
p(n) .
2.1 Interactive proofs
Let us recall the concept of interactive proofs, presented by [GMR-89]. For formal definitions
and motivating discussions the reader is referred to [GMR-89]. A protocol between a
(computationally unbounded) prover P and a (probabilistic polynomial-time) verifier V constitutes
an interactive proof for a language L if there exists a negligible function ffl
such that
1. Completeness: If x 2 L then
2. Soundness: If x 62 L then for any prover P
Remark: Usually, the definition of interactive proofs is robust in the sense that setting the
error probability to be bounded away from 1does not change their expressive power, since
the error probability can be reduced by repetitions. However, this standard procedure is not
applicable when knowledge-complexity is measured, since (even sequential) repetitions may
increase the knowledge-complexity. The question is, thus, what is the right definition. The
definition used above is quite standard and natural; it is certainly less arbitrary then setting
the error to be some favorite constant (e.g., 1) or function (e.g., 2 \Gamman ). Yet, our techniques
yield non-trivial results also in case one defines interactive proofs with non-negligible error
probability (e.g., constant error probability). For example, languages having interactive
proofs with error probability 1=4 and perfect knowledge complexity 1 are also in BPP NP .
For more details see Appendix B. Also note that we have allowed two-sided error probability;
this strengthens our main result but weakens the statistical to perfect transformation 2 .
Suppose you had a transformation for the one-sided case. Then, given a two-sided interactive proof
of some statistical knowledge complexity you could have transformed it to a one-sided error proof of the
same knowledge complexity (cf., [GMS-87]). Applying the transformation for the one-sided case would have
yielded an even better result.
2.2 Knowledge Complexity
Throughout the rest of the paper, we refer to knowledge-complexity with respect to the honest
verifier; namely, the ability to simulate the (honest) verifier's view of its interaction with the
prover. (In the stronger definition, one considers the ability to simulate the point of view of
any efficient verifier while interacting with the prover.)
We let denote the random variable that represents V 's view of the interaction
with P on common input x. The view contains the verifier's random tape as well as the
sequence of messages exchanged between the parties.
We begin by briefly recalling the definitions of perfect and statistical zero-knowledge. A
perfect zero-knowledge (resp., statistical zero-knowledge) over a language L
if there is a probabilistic polynomial time simulator M such that for every x 2 L the random
variable M(x) is distributed identically to the statistical difference between
M(x) and (P; V )(x) is a negligible function in jxj).
Next, we present the definitions of perfect (resp., statistical) knowledge-complexity which
we use in the sequel. These definitions extend the definition of perfect (resp., statistical) zero-
knowledge, in the sense that knowledge-complexity zero is exactly zero-knowledge. Actually,
there are two alternative formulations of knowledge-complexity, called the oracle version and
the fraction version. These formulations coincide at the zero level and differ by at most an
additive constant otherwise [GP-91]. For further intuition and motivation see [GP-91]. It
will be convenient to use both definitions in this paper 3 .
By the oracle formulation, the knowledge-complexity of a protocol is the number
of oracle (bit) queries that are needed to simulate the protocol efficiently.
Definition 2.1 (knowledge complexity - oracle version): Let k: N ! N. We say that an
interactive proof language L has perfect (resp., statistical) knowledge complexity
k(n) in the oracle sense if there exists a probabilistic polynomial time oracle machine M and
an oracle A such that:
1. On input x 2 L, machine M queries the oracle A for at most k(jxj) bits.
2. For each x 2 L, machine M A produces an output with probability at least 1, and given
that M A halts with an output, M A (x) is identically distributed (resp., statistically close)
to
In the fraction formulation, the simulator is not given any explicit help. Instead, one
measures the density of the largest subspace of simulator's executions (i.e., coins) which is
identical (resp., close) to the
Definition 2.2 (knowledge complexity - fraction version): Let ae: N ! (0; 1]. We say that an
interactive proof language L has perfect (resp., statistical) knowledge-complexity
log 2
(1=ae(n)) in the fraction sense if there exists a probabilistic polynomial-time machine M
with the following "good subspace" property. For any x 2 L there is a subset of M's possible
random tapes S x , such that:
3 The analysis of the [BP-92] procedure is easier when using the fraction version, whereas the transformation
from statistical to perfect is easier when using the oracle version.
1. The set S x contains at least a ae(jxj) fraction of the set of all possible coin tosses of M(x).
2. Conditioned on the event that M(x)'s coins fall in S x , the random variable M(x) is
identically distributed (resp., statistically close) to )(x). Namely, for the perfect
case this means that for every -
c
where M(x;!) denotes the output of the simulator M on input x and coin tosses sequence
!.
As mentioned above, these two measures are almost equal.
Theorem [GP-91]: The fraction measure and the oracle measure are equal up to an additive
constant.
Since none of our results is sensitive to a difference of an additive constant in the measure, we
ignore this difference in the subsequent definition as well as in the statement of our results.
Definition 2.3 (knowledge complexity classes):
languages having interactive proofs of perfect knowledge complexity k(\Delta).
languages having interactive proofs of statistical knowledge complexity k(\Delta).
2.3 The simulation based prover
An important ingredient in our proof is the notion of a simulation based prover, introduced
by Fortnow [F-89]. Consider a simulator M that outputs conversations of an interaction
between a prover P and a verifier V . We define a new prover P   , called the simulation based
prover, which selects its messages according to the conditional probabilities induced by the
simulation. Namely, on a partial history h of a conversation, P   outputs a message ff with
probability
denotes the distribution induced by M on t-long prefixes of conversations. (Here,
the length of a prefix means the number of messages in it.)
It is important to note that the behavior of P   is not necessarily close to the behavior
of the original prover P . Specifically, if the knowledge complexity is greater than 0 and
we consider the simulator guaranteed by the fraction definition, then P   and P might have
quite a different behavior. Our main objective will be to show that even in this case P   still
behaves in a manner from which we can benefit.
3 The Perfect Case
In this section we prove that the Main Theorem holds for the special case of perfect knowledge
complexity. Combining this result with the transformation (Theorem 2) of the subsequent
section, we get the Main Theorem.
Theorem 1 PKC(O(log n)) ' BPP NP
Our proof follows the procedure suggested in [BP-92], which in turn follows the approach
of [F-89, BMO-90, Ost-91] while introducing a new uniform generation procedure which
builds on ideas of [Si-83, St-83, GS-89, JVV-86] (see introduction).
Suppose that is an interactive proof of perfect knowledge complexity
O(log n) for the languages L, and let M be the simulator guaranteed by the fraction formulation
(i.e., Definition 2.2). We consider the conversations of the original verifier V with
the simulation-based-prover P   (see definition in Section 2.3). We are going to show that
the probability that the interaction (P  accepting is negligible if x 62 L and greater
than a polynomial fraction if x 2 L. Our proof differs from [BP-92] in the analysis of the
case x 2 L (and thus we get a stronger result although we use the same procedure). This
separation between the cases x 62 L and x 2 L can be amplified by sequential repetitions of
the protocol (P  remains to observe that we can sample the (P
in probabilistic polynomial-time having access to an NP oracle. This observation originates
from [BP-92] and is justified as follows. Clearly, V 's part of the interaction can be produced
in polynomial-time. Also, by the uniform generation procedure of [BP-92] we can implement
by a probabilistic polynomial time machine that has access to an NP oracle. Actually,
the implementation may fail with negligible probability, but this does not matter. Thus, it
remains only to prove the following lemma.
Lemma 3.1
1. If x 2 L then the probability that (P  outputs an accepting conversation is at least2
2. If x 62 L then the probability that (P  outputs an accepting conversation is negligible.
Remark: In [BP-92], a weaker lemma is proven. Specifically, they show that the probability
that (P  output an accepting conversation (on x 2 L) is related to 2 \Gammak \Deltat , where t is the
number of rounds in the protocol. Note that in our proof t could be an arbitrary polynomial
number of rounds.
proof: The second part of the lemma follows from the soundness property as before. We
thus concentrate on the first part. We fix an arbitrary x 2 L for the rest of the proof and
allow ourselves not to mention it in the sequel discussion and notation. Let
q be the number of coin tosses made by M . We denote
q the set of all possible
coin tosses, and by S the "good subspace" of M (i.e., S has density 2 \Gammak
in\Omega and for ! chosen
uniformly in S the simulator outputs exactly the distribution of the interaction
Consider the conversations that are output by the simulator on ! 2 S. The probability
to get such a conversation when the simulator is run on ! uniformly selected in \Omega\Gamma is at
least 2 \Gammak . We claim that the probability to get these conversations in the interaction (P
is also at least 2 \Gammak . This is not obvious, since the distribution produced by (P
not be identical to the distribution produced by M on a uniformly selected ! 2 \Omega\Gamma Nor is
it necessarily identical to the distribution produced by M on a uniformly selected ! 2 S.
However, the prover's moves in (P  are distributed as in the case that the simulator
selects ! uniformly in \Omega\Gamma whereas the verifier's moves (in (P  are distributed as in the
case that the simulator selects ! uniformly in S. Thus, it should not be too surprising that
the above claim can be proven.
However, we need more than the above claim: It is not enough that the (P  conversations
have an origin in S, they must be accepting as well. (Note that this is not obvious
since M simulates an interactive proof that may have two-sided error.) Again, the density
of the accepting conversations in the "good subspace" of M is high (i.e.,
need to show that this is the case also for the (P  Actually, we will show
that the probability than an (P  conversation is accepting and "has an origin" in S is at
least
Let us begin the formal argument with some notations. For each possible history of the
interaction, h, we define subsets of the random tapes of the simulator (i.e., subsets of \Omega\Gamma
as
h is the set of !
2\Omega which cause the simulator to output a conversation with
prefix h. S h is the subset of !'s
in\Omega h which are also in S. A h is the set of !'s in S h which
are also accepting.
Thus, letting M t (!) denote the t-message long prefix output by the simulator M on coins
!, we get
A h
Let C be a random variable representing the (P  be an indicator so
that the conversation -
c is accepting and Our aim is to prove
that . Note that
-c
-c
The above expression is exactly the expectation value of jAc j
. Thus, we need to show that:
where the expectation is over the possible conversations - c as produced by the interaction
Once Equation (1) is proven, we are done. Denote the empty history by -. To
prove Equation (1) it suffices to prove that
since using jA - j
The proof of Equation (2) is by induction on the number of rounds. Namely, for each round
i, we show that the expected value of jA h j
over all possible histories h of i rounds (i.e.,
length i) is greater or equal to the expected value of this expression over all histories h 0 of
rounds. In order to show the induction step we consider two cases:
1. the current step is by the prover (i.e., P   ); and
2. the current step is by the verifier (i.e., V ).
In both cases we show, for any history h,
where the expectation is over the possible current moves m, given history h, as produced by
the interaction (P
Technical Claim
The following technical claim is used for deriving the inequalities in both cases.
positive reals. Then,
Proof: The Cauchy-Schwartz Inequality asserts:
a i!
Setting a i
can do this since y i is positive) and b i
a i
, and rearranging the terms,
we get the desired inequality. 2
Prover Step - denoted ff
Given history h, the prover P   sends ff as its next message with probability
. Thus,
ff
ff
The inequality is justified by using the Technical Claim and noting that
and
Verifier Step - denoted fi
By the perfectness of the simulation, when restricted to the good subspace S, we know that
given history h, the verifier V sends fi as its next message with probability jS hffifi j
. Thus,
The inequality is justified by using the Technical Claim and noting that
and
j\Omega h j.
Having proven Equation (3) for both cases, Equation (2) follows and so does the lemma. 2
4 The Transformation
In this section we show how to transform statistical knowledge complexity into perfect knowledge
complexity, incurring only a logarithmic additive term. This transformation combined
with Theorem 1 yields the Main Theorem.
Theorem 2 For every (poly-time computable) k : N 7! N,
We stress again that these knowledge complexity classes refer to the honest verifier and that
we don't know whether such a result holds for the analogous knowledge complexity classes
referring to arbitrary (poly-time) verifiers.
proof: Here we use the oracle formulation of knowledge complexity (see Definition 2.1). We
start with an overview of the proof. Suppose we are given a simulator M which produces
output that is statistically close to the real prover-verifier interaction. We change both the
interactive proof and its simulation so that they produce exactly the same distribution space.
We will take advantage of the fact that the prover in the interactive proof and the oracle that
"assists" the simulator are both infinitely powerful. Thus, the modification to the prover's
program and the augmentation to the oracle need not be efficiently computable. We stress
that the modification to the simulator itself will be efficiently computable. Also, we maintain
the original verifier (of the interactive proof), and thus the resulting interactive proof is still
sound. Furthermore, the resulting interaction will be statistically close to the original one
(on any x 2 L) and therefore the completeness property of the original interactive proof is
maintained (although the error probability here may increase by a negligible amount).
Preliminaries
be the guaranteed interactive proof. Without loss of gener-
ality, we may assume that all messages are of length 1. This message-length convention is
merely a matter of encoding.
Recall that Definition 2.1 only guarantees that the simulator produces output with probability
- 1. Yet, employing Proposition 3.8 in [GP-91], we get that there exists an oracle
machine M , that after asking k(n) log log n queries, always produces an output so that
the output is statistically close to the interaction of (P; V ). Let A denote the associated or-
acle, and let be the simulation-based prover and verifier 4 induced
by M 0 (i.e.,
In the rest of the presentation, we fix a generic input x 2 L and omit it from the notation.
notations: Let [A; B] i be a random variable representing the i-message (i-bit) long prefix of
the interaction between A and B (the common input x is implicit in the notation). We denote
by A(h) the random variable representing the message sent by A after interaction-history
h. Thus, if the i th message is sent by A, we can write [A; B]
Y we denote the fact that the random variables X and Y are statistically close.
Using these notations we may write for every h 2 f0; 1g i and oe 2 f0; 1g:
and similarly,
4.1 The distribution induced by (P statistically close to the distributions induced
by both M
proof: By definition, the distributions produced by M are statistically
close. Thus, we have
s
We prove that [P statistically close to [P by induction on the length of the
interaction. Assuming that [P
s
we wish to prove it for i + 1. We distinguish
two cases. In case the i st move is by the prover, we get
s
(use the induction hypothesis for s
=). In case the i st move is by the verifier, we get
s
s
s
4 A simulator-based verifier is defined analogously to the simulator-based prover. It is a fictitious entity
which does not necessarily coincide with V .
where the first s
is justified by the induction hypothesis and the two others by Eq. (4).
We stress that since the induction hypothesis is used only once in the induction step, the
statistical distance is linear in the number of induction steps (rather than exponential). 2
Motivating discussion: Note that the statistical difference between the interaction (P
the simulation M due solely to the difference between the proper verifier (i.e.,
and the verifier induced by the simulator (i.e., V 0 ). This difference is due to V 0 putting
too much probability weight on certain moves and thus also too little weight on their sibling
messages (recall that a message in the interaction contains one bit). In what follows we deal
with two cases.
The first case is when this difference between the behavior of V 0 (induced by M 0 ) and
the behavior of the verifier V is "more than tiny". This case receives most of our attention.
We are going to use the oracle in order to move weight from a verifier message fi that gets
too much weight (after a history h) to its sibling message fi \Phi 1 that gets too little weight
(after the history h) in the simulation. Specifically, when the new simulator M 00 invokes M 0
and comes up with a conversation that has h ffi fi as a prefix, the simulator M 00 (with the
help of the oracle) will output (a different) conversation with the prefix h ffi (fi \Phi 1) instead
of outputting the original conversation. The simulator M 00 will do this with probability that
exactly compensates for the difference between V 0 and V . This leaves one problem. How
does the new simulator M 00 come up with a conversation that has a prefix h ffi (fi \Phi 1)? The
cost of letting the oracle supply the rest of the conversation (after the known prefix hffi(fi \Phi1))
is too high. We adopt a "brutal" solution in which we truncate all conversations that have
as a prefix. The truncation takes place both in the interaction (P
stops the conversation after fi \Phi 1 (with a special STOP message) and in the simulation
where the oracle recognizes cases in which the simulator M 00 should output a truncated
conversation. These changes make M 00 and V behave exactly the same on messages for
which the difference between V 0 and V is more than tiny. Naturally, V immediately rejects
when P 00 stops the interaction abruptly, so we have to make sure that this change does not
foil the ability of P 00 to convince V on an input x 2 L. It turns out that these truncations
happen with negligible probability since such truncation is needed only when the difference
between V and V 0 is more than tiny. Thus, P 00 convinces V on x 2 L almost with the same
probability as P 0 does.
The second possible case is that the difference between the behavior of V and V 0 is tiny.
In this case, looking at a full conversation -
c, we get that the tiny differences sum up to a
small difference between the probability of -
c in the distributions of M 0 and in the distribution
of We correct these differences by lowering the probabilities of all conversations in
the new simulator. The probability of each conversation is lowered so that its relative weight
(relatively to all other conversations) is equal to its relative weight in the interaction (P
Technically, this is done by M 00 not producing an output in certain cases that M 0 did produce
an output.
Technical remark: The oracle can be used to allow the simulator to toss bias coins when the
simulator does not "know" the bias. Suppose that the simulator needs to toss a coin so that
it comes-up head with probability N
and both N and m are integers. The
simulator supplies the oracle with a uniformly chosen r 2 f0; 1g m and the oracle answers
head if r is among the first N strings in f0; 1g m and tail otherwise. A similar procedure
is applicable for implementing a lottery with more than two a-priori known values. Using
this procedure, we can get extremely good approximations of probability spaces at a cost
related to an a-priori known upper bound on the size of the support (i.e., the oracle answer
is logarithmic in the size of the support).
O(t)
where t is the number of rounds in the interaction
ffl Let h be a partial history of the interaction and fi be a possible next move by the verifier.
We say that fi is weak with respect to h if
ffl A conversation - with respect to
it is i-good. (Note that a conversation can be i-weak only if the i th move is a verifier
move.)
ffl A conversation -
it is i-weak but j-good for every
A conversation - i-co-critical if the conversation obtained from - c, by
complementing (only) the i th bit, is i-critical. (Note that a conversation can be i-critical
only for a single i, yet it may be i-co-critical for many i's.)
ffl A conversation is weak if it is i-weak for some i, otherwise it is good.
conversations with negligible probability.
proof: Recall that [P
and that the same holds also for prefixes of the conver-
sations. Namely, for any 1 - i - t, [P
s
us define a prefix h 2 f0; 1g i of
a conversation to be bad if either
or
ffl'
The claim follows by combining two facts.
Fact 4.3 The probability that (P outputs a conversation with a bad prefix is negligible.
to be the set of bad prefixes of length i. By the statistical closeness of
we get that
for some negligible fraction fl. On the other hand, \Delta can be bounded from bellow by
which by definition of B i is at least
Thus,
and the fact follows. 2
Fact 4.4 If a conversation -
contains a bad prefix.
proof: Suppose that fi is a bad prefix then
we are done. Otherwise it holds that
Using the fact that fi is weak with respect to h, we get
which implies that h ffi fi is a bad prefix of - c. 2
Combining Facts 4.3 and 4.4, Claim 4.2 follows. 2
conversation. Then, the probability that - c is
output by M 0 is at least (1 \Gamma ffl) dt=2e \Delta Prob([P
is i-good for every
proof: To see that this is the case, we write the probabilities step by step conditioned on
the history so far. We note that the prover's steps happen with equal probabilities in both
sides of the inequality, and therefore can be reduced. Since the relevant verifier's steps are
not weak, we get the mentioned inequality. The actual proof proceeds by induction on k \Gamma l.
Clearly, the claim holds. We note that if k \Gamma l = 1 the claim also holds since
step k in the conversation is either a prover step or a k-good verifier step.
To show the induction step we use the induction hypothesis for 2. Namely,
include one prover message and one verifier message. Assume, without
loss of generality, that the prover step is k \Gamma 1. Since P 0 is the simulator based prover, we
get
Since step k of the verifier is good, we also have:
Combining Equations 5, 6, and 7, the induction step follows and we are done. 2
Dealing with weak conversations
We start by modifying the prover P 0 , resulting in a modified prover, denoted P 00 , that stops
once it gets a verifier message which is weak with respect to the current history; otherwise,
Namely,
Definition (modified prover - P 00
STOP if fi is weak with respect to
We assume that the verifier V stops and rejects immediately upon receiving an illegal message
from the prover (and in particular upon receiving this STOP message).
Next, we modify the simulator so that it outputs either good conversations or truncated
conversations which are originally i-critical. Jumping ahead, we stress that such truncated
i-critical conversations will be generated from both i-critical and i-co-critical conversations.
The modified simulator, denoted M 00 , proceeds as follows 5 . First, it invokes M 0 and obtains
a conversation - queries the augmented oracle on -
c. The oracle answers
probabilistically and its answers are of the form (i; oe), where i 2 f1; :::; tg and oe 2 f0; 1g.
The probability distribution will be specified below, at this point we only wish to remark
that the oracle only returns pairs (i; oe) for which one of the following three conditions holds
1. -
c is good, is good and is not i-co-critical for any i's then the oracle
always answers this way);
2. -
c is i-critical and
3. -
c is i-co-critical and oe = 1.
Finally, the new simulator (M 00 ) halts outputting which in case
not a prefix of -
c. Note that i may be smaller than t, in which case M 00 outputs a truncated
conversation which is always i-critical; otherwise, M 00 outputs a non-truncated conversation.
Note that this oracle message contains at most 1 log t bits where t is the length of the
interaction between P 0 and V . It remains to specify the oracle's answer distribution.
Let us start by considering two special cases. In the first case, the conversation generated
by M 0 is i-critical, for some i, but is not j-co-critical for any j ! i. In this case the oracle
always answers (i; 0) and consequently the simulator always outputs the i-bit long prefix.
However, this prefix is still being output with too low probability. This will be corrected by
the second case hereby described. In this ("second") case, the conversation - c generated by M 0
is good and i-co-critical for a single i. This means that the i-bit long prefix is given too much
probability weight whereas the prefix obtained by complimenting the i th bit gets too little
weight. To correct this, the oracle outputs (i; 1) with probability q and (t;
q will be specified. What happens is that the M 00 will output the "i-complimented prefix"
with higher probability than with which it has appeared in M 0 . The value of q is determined
as follows. Denote
Then, setting q so that
allows the simulator to output
the prefix with the right probability.
5 We stress that P 00 is not necessarily the simulator-based prover of M 00 .
In the general case, the conversation generated by M 0 may be i-co-critical for many
i's as well as j-critical for some (single) j. In case it is j-critical, it can be i-co-critical
only for us consider the sequence of indices, (i 1 ; :::; i l ), for which the generated
conversation is critical or co-critical (i.e., the conversation is i k -co-critical for all k ! l and
is either i l -critical or i l -co-critical). We consider two cases. In both cases the q k 's are set as
in the above example; namely, q
\Phi 1) and
\Phi 1).
1. The generated conversation, -
-co-critical for every k ! l and is i l -
critical. In this case, the distribution of the oracle answers is as follows. For every
l, the pair (i k ; 1) is returned with probability (
the pair
appears with probability
We stress that no other pair appears in this
distribution. 6
2. The generated conversation, -
-co-critical for every k - l. In this case,
the distribution of the oracle answers is as follows. For every k - l, the pair (i
is returned with probability (
the pair (t; 0) appears with
probability
appears in this distribution.
1. [P
2. Each conversation of (P )-conversation or a truncated (i.e.,
critical) one, is output by M 00 with probability that is at least a 3fraction of
the probability that it appears in [P
proof: The weak conversations are negligible in the output distribution of (P
4.2). The only difference between [P originates from a different behavior
of P 00 on weak conversations, specifically P 00 truncates them while P 0 does not. Yet,
the distribution on the good conversations remains unchanged. Therefore the distribution
of [P statistically close to the distribution of [P and we are done with Part (1).
For Part (2) let us start with an intuitive discussion which may help reading through the
formal proof that follows. First, we recall that the behavior of the simulation M 0 in prover
steps is identical to the behavior of the interaction (P steps. This follows
simply from the fact that P 0 is the simulation based prover of M 0 . We will show that this
property still holds for the new interaction (P and the new simulation M 00 . We will do
this by noting two different cases. In one case, the prover step is conducted by P 00 exactly
as it is done by P 0 and then M 00 behaves exactly as M 0 . The second possible case is that the
prover step contains the special message STOP. We shall note that this occurs with exactly
the same probability in the distribution (P in the distribution of M 00 .
Next, we consider the verifier steps. In the construction of M 00 and P 00 we considered the
behavior of M 0 and V on verifier steps and made changes when these differences were not
"tiny". We called a message fi weak with respect to a history h, if the simulator assigns the
message fi (after outputting h) a probability which is smaller by a factor of more than
from the probability that the verifier V outputs the message fi on history h. We did not
6 Indeed the reader can easily verify that these probabilities sum up to 1.
make changes in messages whose difference in weight (between the simulation M 0 and the
interaction were smaller than that. In the proof, we consider two cases. First, the
message fi is weak with respect to the history h. Clearly, the sibling message fi \Phi 1 is getting
too much weight in the simulation M 0 . So in the definition of M 00 we made adjustments to
move weight from the prefix h ffi (fi \Phi 1) to the prefix h ffi fi. We will show that this transfer
of weight exactly cancels the difference between the behavior of V and the behavior of M 0 .
Namely, the weak messages (and their siblings) are assigned exactly the same probability
both in M 00 and by V . Thus, we show that when a weak step is involved, the behavior of
and the behavior of M 00 are exactly equivalent. It remains to deal with messages for
which the difference between the conditional behavior of V and M 0 is "tiny" and was not
considered so far. In this case, M 00 behaves like M 0 . However, since the difference is so tiny,
we get that even if we accumulate the differences throughout the conversation, they sum up
to at most the multiplicative factor 3=4 stated in the claim.
Let us begin the formal proof by writing again the probability that (P 00
c as
the product of the conditional probabilities of the t steps. Namely,
Y
We do the same for the probability that M 00 outputs a conversation
c. We will show by induction that each step of any conversation is produced by M 00 with at
least times the probability of the same step in the (P )-interaction. Once we have
shown this, we are done. Clearly this claim holds for the null prefix. To prove the induction
step, we consider the two possibilities for the party making the st step.
st step is by the prover: Consider the conditional behavior of M 00 given the history so
far. We will show that this behavior is identical to the behavior of P 00 on the same partial
history.
A delicate point to note here is that we may talk about the behavior of M 00 on a prefix
only if this prefix appears with positive probability in the output distribution [M 00
However, by the induction hypothesis any prefix that is output by [P appears with
positive probability in [M 00
We partition the analysis into two cases.
1. First, we consider the case in which the last message of the verifier is weak with respect
to the history that precedes it. Namely, and fi is weak with respect to h 0 . In
this case, both in the interaction (P in the simulation M 00 , the next message of
the prover is set to STOP with probability 1. Namely,
2. The other possible case is that the last message of the verifier is not weak with respect
to its preceding history. In this case, the simulator M 00 behaves like M 0 and the prover
(Note that the changes in critical and co-critical steps apply only to
verifier steps.) Thus,
To summarize, the conditional behavior of M 00 in the prover steps and the conditional
behavior of P 00 are exactly equal.
st step is by the verifier: Again, we consider the conditional behavior of M 00 given the
history so far. Let us recall the second modification applied to M 0 when deriving M 00 . This
modification changes the conditional probability of the verifier steps in the distribution of M 0
in order to add weight to steps having low probability in the simulation. We note that this
modification is made only in critical or co-critical steps of the verifier. Consider a history h i
which might appear in the interaction (P possible response fi of V to h i . Again,
by the induction hypothesis, h i has a positive probability to be output by the simulation
M 00 and therefore we may consider the conditional behavior of M 00 on this history h i . There
are three cases to be considered, corresponding to whether either fi or fi \Phi 1 or none is weak
with respect to h i .
We start with the simplest case in which neither fi nor fi \Phi 1 is weak (w.r.t. h i ). In this
case, the behavior of M 00 is identical to the behavior of M 0 since the oracle never sends the
message (i in this case. However, by the fact that fi is not weak, we get that
and we are done with this simple case.
We now turn to the case in which fi is weak (w.r.t. h i ). In this case, given that M 00 has
produced the prefix h i , it produces h i ffifi whenever M 0 produces the prefix h i ffifi. Furthermore,
with conditional probability q (as defined above), M 00 produces the prefix h i ffi fi also in case
produces the prefix h i ffi (fi \Phi 1). As above, we define
is the simulation (M 0 ) based verifier, we may also write
Also, recall that q was defined as p\Gammap 0
using these notations:
Using Equation (8), we get
Finally, we turn to the case in which fi \Phi 1 is weak (w.r.t. h i ). Again, this means that fi is
co-critical in - c. Given that M 00 has produced the prefix h i , it produces h i ffi fi only when M 0
produces the prefix h i ffi fi, and furthermore, M 00 does so only with probability
q is again as defined above). We denote p and p 0 , with respect to the critical message fi \Phi 1.
Namely,
Thus, recalling that
This completes the proof of Claim 4.6. 2
Lowering the probability of some simulator outputs
After handling the differences between M 0 and (P which are not tiny, we make the last
modification, in which we deal with tiny differences. We do that by lowering the probability
that the simulator outputs a conversation, in case it outputs this conversation more frequently
than it appears in (P 00 ; V ). The modified simulator, denoted M 000 , runs M 00 to obtain a
conversation - c. (Note that M 00 always produces output.) Using the further-augmented
oracle, M 000 outputs -
c with probability
c
Note that p - c - 1 holds due to Part 2 of Claim 4.6.
1. M 000 produces output with probability 3;
2. The output distribution of M 000 (i.e., in case it has output) is identical to the distribution
proof: The probability that M 000 produces an output is exactly:
As for part (2), we note that the probability that a conversation -
c is output by M 000 is exactly4
the simulator halts with an output with probability exactly 3,
we get that given that M 000 halts with an output, it outputs -
c with probability exactly
and we are done. 2
An important point not explicitly addressed so far is whether all the modifications applied to
the simulator preserve its ability to be implemented by a probabilistic polynomial-time with
bounded access to an oracle. Clearly, this is the case with respect to M 00 (at the expense of
additional
regarding the last modification there
is a subtle points which needs to be addressed. Specifically, we need to verify that the
definition of M 000 is implementable; namely, that M 000 can (with help of an augmented oracle)
"sieve" conversations with exactly the desired probability. Note that the method presented
above (in the "technical remark") may yield exponentially small deviation from the desired
probability. This will get very close to a perfect simulation, but yet will not achieve it.
To this end, we modify the "sieving process" suggested in the technical remark to deal
with the specific case we have here. But first we modify P 00 so that it makes its random
choices (in case it has any) by flipping a polynomial number of unbiased coins. 7 This rounding
does change a bit the behavior of P 00 , but the deviation can be made so small that the above
assertions (specifically Claim 4.6) still hold.
Consider the specific sieving probability we need here.
c=d
, where
a
d
observation is that c is the number
of coin tosses which lead M 00 to output -
c (i.e., using the notation of the previous section,
j). Observing that b is the size of probability space for [P using the above
modification to P 00 , we rewrite p - c as 3ad
c
are some
non-negative integers.
We now note, that the oracle can allow the simulator to sieve conversations with probability
e
c
in the following way. M 000 sends to the oracle the
random tape ! that it has tossed for M 00 , and the oracle sieves only e out of the possible c
random tapes which lead M 00 to output - c. The general case of p -
c2 f is deal by writing
c
To implement this sieve, M 000 supplies
the oracle with a uniformly chosen f-bit long string (in addition to !). The oracle sieves out
q random-tapes (of M 00 ) as before, and uses the extra bits in order to decide on the sieve in
case ! equals a specific (different) random-tape.
Combining Claims 4.1, 4.6 (part 1), and 4.7, we conclude that (P 00 is an interactive proof
system of perfect knowledge complexity O(log n) for L. This completes the proof of
Theorem 2.
7 The implementation of P 00 was not discussed explicitly. It is possible that P 00 uses an infinite number
of coin tosses to select its next message (either 0 or 1). However, an infinite number of coin tosses is not
really needed since rounding the probabilities so that a polynomial number of coins suffices, causes only
exponentially small rounding errors.
Concluding Remarks
We consider our main result as a very first step towards a classification of languages according
to the knowledge complexity of their interactive proof systems. Indeed there is much to be
known. Below we first mention two questions which do not seem too ambitious. The first
is to try to provide evidence that NP-complete languages cannot be proven within low
(say logarithmic or even constant) knowledge complexity. A possible avenue for proving this
conjecture is to show that languages having logarithmic knowledge complexity are in co-AM,
rather than in BPP NP (recall that NP is unlikely to be in co-AM - see also [BHZ-87]). The
second suggestion is to try to provide indications that there are languages in PSPACE which
do not have interactive proofs of linear (rather than logarithmic) knowledge complexity. The
reader can easily envision more moderate and more ambitious challenges in this direction.
Another interesting question is whether all levels greater then zero of the knowledge-
complexity hierarchy contain strictly more languages than previous levels, or if some partial
collapse occurs. For example, it is open whether constant or even logarithmic knowledge
complexity classes do not collapse to the zero level.
Regarding our transformation of statistical knowledge complexity into perfect knowledge
complexity (i.e., Theorem 2), a few interesting questions arise. Firstly, can the cost of the
transformation be reduced to bellow O(log n) bits of knowledge? A result for the special
case of statistical zero-knowledge will be almost as interesting. Secondly, can one present an
analogous transformation that preserves one-sided error probability of the interactive proof?
(Note that our transformation introduces a negligible error probability into the completeness
condition.) Finally, can one present an analogous transformation that applies to knowledge
complexity with respect to arbitrary verifiers? (Our transformation applies only to knowledge
complexity with respect to the honest verifier.)
6

Acknowledgement

We thank Leonard Shulman for providing us with a simpler proof of Claim 3.2.



--R


The (True) Complexity of Statistical Zero-Knowledge
Making Zero-Knowledge Provers Efficient


The Complexity of Perfect Zero-Knowledge
Interactive Proof Systems: Provers that never Fail and Random Selection.
"Proofs that Yield Nothing But their Validity and a Methodology of Cryptographic Protocol Design"
"How to Play any Mental Game or a Completeness Theorems for Protocols of Honest Majority"
Quantifying Knowledge Complexity.
The Knowledge Complexity of Interactive Proofs.
The Knowledge Complexity of Interactive Proofs.
Public Coins in Interactive Proof Systems


Better Ways to Generate Hard NP Instances than Picking Uniformly at Random
Direct Minimum-Knowledge computations
Random Generation of Combinatorial Structures from a Uniform Distribution.
Algebraic Methods for Interactive Proof Systems.


Fair Games Against an All-Powerful Adversary

A Complexity Theoretic Approach to Randomness.
The Complexity of Approximate Counting.
--TR

--CTR
Amos Beimel , Paz Carmi , Kobbi Nissim , Enav Weinreb, Private approximation of search problems, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
Oded Goldreich , Salil Vadhan , Avi Wigderson, On interactive proofs with a laconic prover, Computational Complexity, v.11 n.1/2, p.1-53, January
Amit Sahai , Salil Vadhan, A complete problem for statistical zero knowledge, Journal of the ACM (JACM), v.50 n.2, p.196-249, March
knowledge complexity;interactive proofs;randomness;cryptography;complexity classes;zero knowledge