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

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,

1. The simulator can see what values parties query the oracle on.
2. 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.

• I think you might mean "exhaustive" instead of "exhausting". – Dave Clarke Sep 20 '10 at 15:56
• I beg to differ. I meant I found a way for "exhausting" the simulator of ZK protocols... There's no such thing as "exhaustive" simulator. – M.S. Dousti Sep 20 '10 at 16:51
• My bad. I read exhausting as an adjective, not a verb. – Dave Clarke Sep 20 '10 at 17:51

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.

• Does the same hold for "universal simulation" ZK? After all, black-box ZK is a type of universal-simulation ZK, whose running time is fixed before $V*$ is determined. (However, non-black-box ZK is a type of universal-simulation ZK, in which S can look at the "guts" of V*) – M.S. Dousti Sep 22 '10 at 6:18
• Please see the edited question for some references. – M.S. Dousti Sep 23 '10 at 12:34
• For a universal (non-black-box) simulator, one must allow running time polynomial in the running time of $V^{*}$ since otherwise the simulator doesn't have time to invoke $V^{*}$. But generally the point I was making is that "black-box zero knowledge" is not a canonical definition but rather a tool, and that tool can be used differently in the context of positive or negative results to make the results more meaningful. – Boaz Barak Sep 23 '10 at 17:31
• I delayed replying to your comment since I wanted to read more. In particular, I read Yung and Zhao's paper (cited above), and noted that they used black-box ZK in the RO model for a positive result, while you said "it doesn't make sense to say that a random-oracle model simulator is 'black-box'." Is their result philosophically problematic, or should we relax the definition of black-box? – M.S. Dousti Sep 26 '10 at 20:33

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.

• Thank for the answer David. Regardless of the ability of the simulator to program the RO, it should be able to "monitor" them. So, every oracle query from V* wastes M's time by at least time. Your big idea is to change the model to "let the simulator run in time polynomial in |x| and the number of RO queries issued by V*." That is not the standard model, but I see it as a reasonable solution. Yet I think the "giants" in the community must acknowledge the authenticity of such model first... – M.S. Dousti Sep 20 '10 at 15:43
• Can you cite a source that precisely defines "the standard model"? (That term is often used as a synonym for "no random oracles or other such modifications are present in the model of computation," but I don't think that this is what you meant.) My expectation is that I have sketched the definition of what would be considered standard, and if not, then we can figure that out without any "giants" actively certifying our reasoning. – David Cash Sep 20 '10 at 16:48
• Sure, by "standard model" I meant the "standard definition" of ZK under the RO model. You may refer to Rafael Pass's paper (cited in the question), or his MSc thesis (titled "Alternative Variants of Zero-Knowledge Proofs"), or Wee's paper in AsiaCrypt 2009 ("Zero Knowledge in the Random Oracle Model, Revisited"). None of them defined "black-box" ZK in the RO model (they all mentioned auxiliary input ZK), though none referred to "run in time polynomial in |x| and the number of RO queries made by V*". Hence, I think you are putting forward a new definition (Google it!) – M.S. Dousti Sep 20 '10 at 17:17
• Please see the edited question for some references. – M.S. Dousti Sep 23 '10 at 12:33