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?Edit: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.htmlParticularly, it gives definitions of black-box ZK in the RO Model in section 3.3 (page 20), attributed to Yung and Zhao:Moti Yung and Yunlei Zhao. Interactive Zero-Knowledge with Restricted Random Oracles.  In Theory of Cryptography - TCC 2006, LNCS 3876, pp. 21-40, 2006.
Exhausting Simulator of Zero-Knowledge Protocols in the Random Oracle Model
cc.complexity theory;cr.crypto security;oracles;black box
There is a question of why one would want to define black-box ZK in the random oracle model. There are at least two reasons why people suggested the definition of black-box zero knowledge:1) For a positive result, when you say that a simulator is black-box zero knowledge it automatically gives you a nice bound on its running time (i.e., $poly(|x|) \cdot time(V*)$ as opposed to $poly(time(V*))$) and it also may be useful to know that the simulator doesn't look at the guts' of $V*$ and doesn't care if $V*$ is implemented using RAM, circuit, etc... While a random-oracle model simulator may be efficient, it's obviously not black-box, because it's supposed to somehow look at the execution of $V*$ and understand from it when $V*$ is evaluating a hash function. For this reason, there is a sense in which it doesn't make sense to say that a random-oracle model simulator is black-box.2) For a negative result, people use black-box simulator to capture a large class of proof techniques. In this case you can define black-box simulator also in the random oracle model and the definition that makes sense is what David said. In fact, for a negative result even not in the random oracle model, it's best if the result holds even if you allow the simulator $poly(time(V*))$ running time. Indeed, although it's not always stated, the negative results I'm aware of all have this property, since the cheating verifier $V*$ is typically a fixed polynomial algorithm that runs some pseudorandom functions, while the simulator can have any polynomial running time.