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?
