Exhausting Simulator of Zero-Knowledge Protocols in the Random Oracle Model

Question

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.html

Particularly, 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.

Answer 1

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.

Answer 2

Here is my take on the problem. I have not recently read any papers that deal with black-box zero-knowledge in the random oracle (RO) model, so I'm just guessing at what they mean and not at what is written there. The short answer (guess) is that BB-ZK in the RO model should let the simulator run in time polynomial in |x| and the number of RO queries issued by V*, the cheating verifier.

Let's try to justify that guess. An initial observation is that the term "black-box zero-knowledge proofs in the random oracle model" needs a closer look to properly define. Black-box simulators are defined to work with any oracle (i.e., the cheating verifier as a black-box), and their only interface is through the oracle input/output. If we just augment this model to give a RO to all parties (perhaps by allowing their circuits to have RO gates), then we get a model where the simulator cannot program the RO - on an oracle query, everything (including RO queries) just happens "inside" of the V* oracle, and then it returns its next message. If we want to allow RO programming, then we need to modify the interfaces: The simulator now gets an input/output oracle for V* and no random oracle. On each call to the V* oracle, instead of producing the next message, the oracle may instead produce the next query to the RO, and the simulator can give it the RO response by calling the oracle again. Now this allows RO programming, and we can also allow the simulator's running time to depend on the number of queries to the RO.

Any further exploration of the meaning of these definitions is left to the reader. I'm thinking syntacticly.