In a paper titled "On Deniability in the Common Reference String and Random Oracle Model," Rafael Pass writes:
We note that when proving security according to the standard zero-knowledge definition in the RO [Random Oracle] model, the simulator has two advantages over a plain model simulator, namely,
- The simulator can see what values parties query the oracle on.
- The simulator can answer these queries in whatever way it chooses as long as the answers "look" OK.
The first technique, namely the ability to "monitor" queries to the RO, is very common in all papers referring to the concept of zero-knowledge in the RO model.
Now, consider the definition of black-box zero-knowledge (PPT stands for probabilistic, polynomial-time Turing machine):
$\exists$ a PPT simulator $S$, such that $\forall$ (possibly cheating) PPT verifier $V^*$, $\forall$ common input $x\in L$, and $\forall$ randomness $r$, the following are indistinguishable:
- the view of $V^*$ while interacting with the prover $P$ on input $x$ and using randomness $r$;
- the output of $S$ on inputs $x$ and $r$, when $S$ is given black-box access to $V^*$.
Here, I want to exhibit a cheating verifier $V'$, whose job is to exhaust any simulator which tries to monitor RO queries:
Let $S$ be the simulator guaranteed by the existential quantifier in the definition of black-box zero-knowledge, and let $q(|x|)$ be a polynomial which upper-bounds the running time of $S$ on input $x$. Assume that $S$ tries to monitor the queries of $V^*$ to the RO.
Now, consider a cheating $V'$, which first queries the RO for $q(|x|)+1$ times (on arbitrary inputs of its choice), and then acts arbitrarily maliciously.
Obviously, $V'$ exhausts the simulator $S$. A simple way for $S$ is to reject such malicious behavior, yet that way, a distinguisher can easily distinguish the real interaction from the simulated one. (Since in the real interaction, the prover $P$ cannot monitor $V'$'s queries, and thus won't reject based on the mere fact that $V'$ is querying too much.)
What is the workaround for the above problem?
A good source for studying ZK in the RO model is:
Martin Gagné, A Study of the Random Oracle Model, Ph.D. Thesis, University of California, Davis, 2008, 109 pages. Available on ProQuest: http://gradworks.umi.com/33/36/3336254.html
Particularly, it gives definitions of black-box ZK in the RO Model in section 3.3 (page 20), attributed to Yung and Zhao: