Black box simulation barrier (Part 1)

Cryptography 2019-05-08

I haven’t been writing posts since this semester. Yesterday I was surprised that this site was discovered by a fellow alumnus from Tsinghua University (See his blog: Gee Law). So I decided to spend some time continuing the topic I planned to write.

Enjoy reading!

The material from this post is mainly from Goldreich and Krawczyk 1996. Also note that some technical details are omitted.

The Barrier: AM $\cap$ bb-ZK $[k] =$ BPP

Recall that in the paper, the authors proved that,

The following condition hold for an IP $(P, V)$ for a language L if and only if L $\in$ BPP.

It is constant-round, i.e. the number of rounds of exchanging messages is bounded by a constant;
It is Arthur-Merlin, i.e. the verifier does not have hidden randomness from the prover;
It admits black-box simulation. That is to say, for any $V^*$ , there is a simulator $S^{V^*}$ which is an oracle machine that treats $V^*$ as a black-box, and that $S^{V^*}(x)$ produces a simulated view that is computationally indistinguishable from a real execution by $(P, V^*)(x)$ .

Last time we considered the almost-trivial case where there is only a single message from the prover. The existence of the simulator alogrithm itself gives us a way to find the appropriate proof in PPT time.

Today we will describe the 3 round case. (The proof is from section 6.1 and 6.2 from the paper.)

(Btw, after reading the paper more carefully, I realized that there are a lot of technical details that I missed. I will add them in whenever it is necessary. Comments will be appreciated.)

AM $\cap$ bb-ZK $[3] =$ BPP.

If there exists an IP $(P,V)$ with the above properties and, in particular has 3 rounds, for some language L. Then L $\in$ BPP.

By IP we mean, more specifically,

Completeness: If $x \in$ L, there is an honest prover which succeeds in convincing the verifier to accept with probability at least $1 -$ negl where negl is an negligible function;
Soundness: If $x \notin$ L, then for any prover, the probability of convincing the verifier is negligible;

(The probability above is over both the random coins by the prover and the verifier.)

The ZK protocol

We can illustrate any 3-round AM protocol $(P, V)$ for $x$ as follows. (Let $n = \lvert x \rvert$ .)

Prover sends a message $\alpha$ to Verifier.
Verifier sends random coins $\beta$ to prover. (We will assume $\lvert \alpha \rvert = \lvert \beta \rvert = l(n)$ by padding.)
Prover upon receiving $\beta$ , selects a message $\gamma$ (which depends on $(\alpha, \beta)$ ) to convince the verifier.

Finally the verifier locally runs a (possibly randomized) predicate $\rho_V(x, \alpha, \beta, \gamma)$ to determine if it should accept.

Let $M^{V^*}$ be the PPT simulator that, when fed in $x$ as the input, $R_M$ as the random coins used by the simulator, and $V^*$ as a black box, outputs a simulated transcript $(\alpha, \beta, \gamma)$ describing the interaction between $P$ and $V^*$ . Note that $M$ is capable of simulating the view of (non-uniform) deterministic $(V^*)$ verifiers and this property suffices for our proof.

The attack plan

The idea behind the reduction is similar to the 1-round case in its core, but is more technical due to interaction. We will use $M$ as a subroutine to generate some transcript, and we show that

If $x$ is in L, an accepting transcript with high probability is found;
Otherwise, with negligible probability will we find such an accepting transcript.

This will directly give us a BPP algorithm because after having such a transcript, we can use the predicate $\rho_V$ to decides $x$ .

How can we use $M$ to build a transcript?

Recall that the simulator might query the verifier $V^*$ in a blach box way by performing a sqeuence of trials on it: sending the first message $\alpha_i$ and receiving the corresponding random coins $\beta_i$ , and repeatedly for a total of $t$ rounds. And finally $M$ outputs a transcript $(x,\alpha,\beta,\gamma)$ .

Here is where AM comes into play : we simply feed in a freshly generated random coins to $M$ whenever requested. This way our algorithm runs in PPT time because $t$ is bounded by a polynomial. However there are some technical issues.

Using the simulator

The plan outlined in the previous section seems straightforward, but actually there are some complication to argue that the generated transcript have the desired property. (Because $M$ might exhibits undefined behavior when we give it too much garbage — who knows?)

Consistency of the random coins

To respond to the request made by $M$ , we should store a list of $\beta$ ’s and only give out a new random $\beta_j$ when a query $\alpha_j$ that is distinct from the previous queries has been made.

The reason is that we want our algorithm to be acting as a virtual deterministic verifier $V^*$ from the perspective of $M$ . As a deterministic verifier, the random coins sent $\beta$ is determined when given $\alpha$ , so we need to maintain the consistency, i.e. send the same $\beta$ , whenever the same $\alpha$ is given twice.

Appearance of final output in the sequence

We will assume that $M$ explicitly requests the generated $\alpha$ and receives $\beta$ in one of the trials (i.e. $(\alpha_i , \beta_i) = (\alpha, \beta)$ for some $i \in [t]$ ) before outputting $(x, \alpha, \beta, \gamma)$ as the simulated transcript.

Concrete discription of the BPP algorithm

Having the above assumption, the input to our BPP algorithm can be described as follows.

Input: an instance $x$ to be decided.
Random coins: $R_M$ that will be fed to $M$ for simulation, and a series of random coins $\beta_1, \beta_2, \ldots, \beta_t$ used for responding to request made by $M$ .
Algorithm:
1. Fill random tape of $M$ by $R_M$ , run $M$ .
2. When a new $\alpha_i$ query is received from $M$ : feed into $M$ a new $\beta$ that is not used yet;
3. If $\alpha_j$ is already queried, reply the same $\beta_j$ that was used before.
4. When $M$ terminates, use $\rho_V$ on the outputted transcript $(x, \alpha, \beta, \gamma)$ and accept iff this test accepts.

Proof of correctness

Note that the generated transcript by $M$ is uniquely determined by the vector $(x, R_M, \beta_1, \beta_2, \ldots, \beta_t)$ . Call such a vector good if the resulting transcript is accepting, and call it $i$ -good if $(\alpha_i, \beta_i) = (\alpha, \beta)$ .

Then our goal is to show that a randomly selected vector has high probability of being good if $x \in L$ , while on the other hand a randomly selected vector has only negligible probability of being good if $x \notin L$ .

The case when $x \notin L$

Suppose on the contrary, for infinitely many $x \notin L$ , the fraction of good vectors is non-negligible. For each of such $x$ , there exists an $i_0$ such that the fraction of $i_0$ -good vector is non-negligible. (This can be seen because the set of all good vectors are partitioned into polynomially many classes, i.e. $i$ -good for $i = 1, 2, \ldots, t$ . So at least one of these classes contains a noticeable fraction.)

Specifically, for some $\alpha_{i_0}$ there are noticeable fraction of $\beta_{i_0}$ allowing the existence of $\gamma$ making an accepting transcript.

This contradicts to the soundness requirement. Because for infinitely many $x$ , a cheating prover can send some $\alpha_{i_0}$ as the first message, and with non-negligible probability the verifier replies a good $\beta$ which makes the final transcript accepting. (Note that we are dealing with interactive proofs, i.e. we allow a computationally unbounded prover who can find the string $\alpha_{i_0)}$ .)

The case when $x \in L$

We need to show that a noticeable fraction the vectors $(x, R_M, \beta_1, \beta_2, \ldots, \beta_t)$ are good. The strategy is as follows.

We first show that our replies to $M(x, R_M)$ will behave in an identical way as some cheating verifier $V^*_h$ (which is deterministic), so the outputted $(\alpha, \beta, \gamma)$ is close to a simulated transcript for $(P, V^*_h)$ (By computational zero-knowledge simulation of $M$ ).
The interaction between $P$ and $V^*_h$ is equivalent to an interaction between $P$ and $V$ .

Universal hash family

Recall that $t(n)$ is the running time bound of $M$ . In the following we will need a family of hash functions $H_n$ which maps $l(n)$ -bit strings to $l(n)$ -bit strings, such that for a random function $h \xleftarrow{R} H_n$ , we have

For any $\alpha$ , $h(\alpha)$ is uniformly random;
For any subset of $t(n)$ preimages, the respective images are $t(n)$ -independent.

Note that these functions can be described by a string $t(n)l(n)$ , i.e. polynomial in $n$ .

Constructing the (non-uniform) $V^*_h$

For any $h$ , the cheating verifier $V^*_h$ replies every query $\alpha$ by $h(\alpha)$ . By $t(n)$ -independence, the uniformly chosen vector $(x, R_M, \beta_1, \beta_2, \ldots, \beta_{t(n)})$ is equivalent to interacting with $V^*_h$ for some $h$ from $M$ ’s perspective.

Interaction between $V^*_h$ and $P$ is equivalent to $V$ with $P$

For any $\alpha$ from $P$ , the reply from $V^*_h$ , $\beta$ is uniformly random. So the behvaior of $V^*_h$ and an honest $V$ is equivalent. Therefore the probability of the transcript between $(P, V^*_h)$ eing accepted is 1-negl.

Putting the pieces together

The outputted transcript is (within a negligible difference) close to a real interaction between $(P, V^*_h)$ , but this transcript has probability 1-negl of accepting. Hence there is a noticeable fraction of good vectors.

Summary

To summarize, for $x \in$ L we have a noticeable fraction of good vectors and for $x \notin$ L we have negligible fraction of good vectors. So the proposed algorithm is a BPP algorithm for L.

The proof here is essentially the same from the paper in the reference, with some modification. After writing the post I saw on the slides by Alon Rosen that the use of universal hash can be replaced by PRFs, which might give a cleaner presentation.

I am not very certain (yet) if some modifications are indeed valid so please feel free to comment! And I will probably try to use the step-by-step approach of writing proofs next time:)

Hmpf.. I didn’t expect to be writing for so long. I will try to write about the case for constant round AM sometime later. It seems to be a long journey until I can finally share about the Boaz’s construction, which I am in fact not very familiar yet.

Reference:

Alon Rosen: Lower Bounds and Limitations on Zero Knowledge. (Day 2 of BIU school)

Oded Goldreich, Hugo Krawczyk 1996: On the Composition of Zero-Knowledge Proof Systems.