No BBZK for AM(3)
Theorem: A language has a constant-round Arthur-Merlin interactive proof which is black-box simulation zero-knowledge if and only if . (This post is for AM(3))
Protocol
Consider an Arthur-Merlin protocol for a language consisting of three rounds. Denote by the input for the protocol, and by the length of this input.
The first message in the interaction is sent by the prover. We denote it by The second round is for which sends a string The third (and last) message is from and we denote it by
The predicate computed by the verifier in order to accept or reject the input is denoted by and we consider it, for convenience, as a deterministic function We will also assume, without loss of generality, the existence of a polynomial such that
Simulation Process
Let this three-round Arthur-Merlin protocol be black-box simulation zero-knowledge. Denote by the guaranteed probabilistic expected polynomial-time black-box simulator which given access to the black-box simulates The process of simulation consists of several "tries" or calls to the interacting verifier ("the black-box"). In each such call the simulator feeds the arguments for . These arguments are the input (which may be different from the "true" input ), the random coins for , and a string representing the message sent by the prover In our case, it suffices for our results to consider a simulator that is just able to simulate conversations with deterministic (non-uniform) verifiers. In particular, this simulator does not care about feeding the black-box with random coins. This simplifies our proof by avoiding any reference to these random coins for and strengthen our result (since it holds even under the sole existence of this weak kind of simulator).
After completing its tries the simulator outputs a conversation .
Simulator as a Subroutine
Our goal is to present a BPP algorithm for the language The idea is to use the simulator in order to distinguish between inputs in and outside For that, we use the simulator itself as a subroutine of the algorithm. We do not make any assumption on the internal behaviour of this simulator, but just use the following observation. The behavior of the simulator , interacting with a verifier is completely determined by the input , the random tape used by and the strings output by (in response to the arguments fed by the simulator during its tries). Therefore, in order to operate we just need to feed it with an input a tape of random coins, and a sequence of responses to its messages
Fix an input of length a string (of length where is a polynomial bounding the number of random coins used by on inputs of length ) and (arbitrary) strings each of length Activate on input with its random tape containing For each and tried by respond with a message from the above list according to the following rule. (This rule depends on the strings but not on ). To the first presented by respond with For subsequent 's check whether the same string was presented before by If so, respond with same as in that case, if it is the first time this is presented then respond with the first unused in the list. That is, if is the -th different string presented by then we respond with . We denote the -th different by Clearly, is uniquely determined by and the strings i.e., there exists a deterministic function such that We denote by the conversation output by the simulator when activated with these parameters (notice that strings always suffice for answering all tries of ) . By our convention on the simulator there exists such that and .
Definition: M-good
We say that a vector is M-good if is an accepting conversation for the (honest) verifier . Namely, if and We say that is (or -good for shortness) if it is -good and ,
The main property of M-good strings is stated in the following Lemma.
Lemma
Let be a 3 -round Arthur-Merlin protocol for a language Suppose is black-box simulation zero-knowledge, and let be a black-box simulator as above. Then,
For strings outside only a negligible portion of the vectors are -good. For strings in there exists a non-negligible portion of the vectors that are -good. (This non-negligible portion is at least one half of the completeness probability of the protocol , i.e. the probability that convinces to accept ).
BPP Algorithm
By Lemma we get the following BPP algorithm for the language . On input :
select at random a vector accept if and only if is -good.
The complexity of this algorithm is as the complexity of testing for -goodness. The later is polynomial-time since it involves running the simulator which is polynomial-time, and evaluating the predicate which is also polynomial-time computable. The success probability of the algorithm is given by Lemma .
Proof of Lemma
Part 1
Assume that the portion of -good vectors for 's not in is not negligible. This means that there exist infinitely many for which the portion of -good vectors is non-negligible.
For each such there exists an index for which a non-negligible fraction of the vectors are -good (since there are only polynomially many possible values for ).
Thus, there exists a non-negligible number of prefixes each with a non-negligible number of good continuations (i.e., such that are good). Let be such a prefix, and let For each -good continuation machine outputs a conversation for which In particular, there exists a non-negligible number of for which this happens.
In other words, for each as above there exists a string for which the set is of non-negligible size among all possible strings
Consider now a ("cheating") prover that sends this as its first message. If responds with the prover sends the corresponding that convinces to accept. Since selects its messages at random, then the probability of being convinced by the above prover is (at least) as the relative size of i.e. non-negligible.
Concluding, we have shown the existence of a prover that for infinitely many 's outside , convinces to accept with non-negligible probability. This contradicts the soundness condition of the protocol , and this part of the Lemma follows.
Part 2
We show that for strings in a non-negligible portion of the vectors are -good.
We do it by considering the behavior of the simulator when receiving "random like" responses from the verifier. This behaviour is analyzed by introducing a particular family of "cheating" verifiers, each of them associated to a different hash function from a a family of -wise independent hash functions. The -wise independence (where is the bound on the number of simulator's tries) achieves the necessary randomness from the verifiers responses.
Let and let denote its length. Consider a family of hash functions which map -bit strings into -bit strings, such that the locations assigned to the strings by a randomly selected hash function are uniformly distributed and -wise independent. (Recall that is the length of messages and in the Arthur-Merlin protocol for while is the bound on the number of 's tries).
We observe that such functions can be described by a string of length i.e. polynomial in .
For each hash function we associate a (deterministic non-uniform) verifier which responds to the prover's message with the string has wired in the description of ). Consider the simulation of conversations by the simulator Fixing an input a random tape for and a function the whole simulation is determined. In particular, this (uniquely) defines a sequence of 's tried by the simulator, and the corresponding responses of We denote by the different values of in these tries. In case that , we complete this sequence to by adding strings in some canonical way, such that the resultant are all different. Let and define
Part 2 of the lemma follows from the following two claims.
Claim 1: For there is a non-negligible portion of the pairs for which the vector is -good.
Claim 2: For all strings and , and for chosen with uniform probability from , the vector is uniformly distributed over the set
Claim 2 states that for any the value of is uniformly distributed over all possible vectors On the other hand, by Claim a non-negligible portion of are -good, and then we get that a non-negligible portion of the vectors are -good.
The Lemma follows.