Concurrent Zero Knowledge Proofs with Logarithmic Round-Complexity

Page numbers are from the paper itself, and not the pdf.

From page 3,

"An interactive proof system is said to be black-box (computational) zero
knowledge if there is a probabilistic polynomial time oracle machine $S$ such that
for any probabilistic polynomial time verifier $V^*$ and for all $\:x \in L\:$, the distribution
of the output produced by $S^{V^*}$ on input $x$ is computationally indistinguishable
from the view of the verifier at the end of the interaction $(P,V)(x)$."

I assume they mean $\:\left(P,V^*\right)(x)\:$ at the end, otherwise this
just defines Honest Verifier Computational Zero Knowledge.

From page 7,

"If the simulator does not abort till all the sessions are over (or the
verifier terminates), it outputs the view of the verifier at that point."

From the third paragraph on page 8,

"If the depth counter indicates that we are just one level above the leaves, then the
simulator has to wait for the next two preamble messages, i.e., it has to move through
the two leaves, and then return. For this the simulator keeps modifying the current view
by letting the (modified) prover and the verifier run, until two preamble messages arrive."

It seems to me like this can't work, since the prover's message
at that stage is just a statistically binding commitment.

Let $\: p: \omega \to \omega \:$ be a polynomial that bounds the number of oracle queries $S$ makes when $V^*$ only requests one proof. $\:$ Suppose the statistically binding commitment scheme being used
is such that it is easy to compute a predicate which commitments have a probability of approximately $\: \frac1{2\cdot p(k)} \:$ of satisfying (for example, Naor commitments or commitment from an injective pseudo-random generator). $\:$ Have the cheating verifier $V_1$ request only one proof and then behave like the honest verifier except that, at one level above the leaves, it will terminate
if the prover's commitment does not satisfy the predicate. $\;\;$ The probability of $\:\left(P,V_1\right)(x)\:$ succeeding is obviously approximately $\: \frac1{2\cdot p(k)} \:$, $\:$ whereas by the union bound, but by the
union bound and the independence of the simulator's, the probability that $S^{V_1}$ outputs a
succeeding view is not non-negligibly more than $\: \frac1{4\cdot p(k)} \:$. $\;\;$ This means that for sufficiently
large $k$, the probability of $\:\left(P,V_1\right)(x)\:$ succeeding will be more than $\: \frac1{5\cdot p(k)} \:$ greater than
the probability $S^{V_1}$ has of outputting a succeeding view. $\;\;$ That means the distribution
of $S^{V_1}$ is computationally distinguishable from the distribution of $\:\left(P,V_1\right)(x)\:$.

Is this an error in the paper? $\:$ If no, what am I missing?


1 Answer 1


I'm one of the authors. Someone pointed me to this question. Based on a quick reading, here's an attempt at answering your concern.

What may not be very clear from this version of the description of the simulator (this was the first time I was describing a simulator, and admittedly it reads a bit too much like machine language) is that the view output by the simulator, after all the pushing and popping of the stack, corresponds to only the traversal through edges labeled with L1 and R1. So even if the verifier aborts somewhere else, it just get popped off, and the simulator continues.

I'd recommend the FOCS proceedings version (or a slightly expanded version that is available from my homepage) over this e-print version. In terms of the description in the proceedings version, the simulator's output corresponds to the "main thread" of the simulation, and doesn't include any aborts that may happen in the look-ahead blocks. (Just looking at the paper: see Figure 3 for an illustration.)

Hope that helps.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.