question about concurrent ZK paper by Prabhakaran & Sahai 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?
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.

-Manoj