<p>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.</p>

<p>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.</p>

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

CC BY-SA 2.5
2010-09-20T15:43:48.400Z
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...
Sadeq Dousti
CC BY-SA 2.5
2010-09-20T16:48:10.780Z
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
CC BY-SA 2.5
2010-09-20T17:17:42.940Z
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!)
Sadeq Dousti
CC BY-SA 2.5
2010-09-23T12:33:46.510Z
Please see the edited question for some references.
Sadeq Dousti
CC BY-SA 2.5
2010-09-20T15:25:06.153Z
2010-09-20T15:25:06.153Z
David Cash
<p>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:</p>

<p>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".</p>

<p>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.</p>

CC BY-SA 2.5
2010-09-22T06:18:57.950Z
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*)
Sadeq Dousti
CC BY-SA 2.5
2010-09-23T12:34:25.127Z
Please see the edited question for some references.
Sadeq Dousti
CC BY-SA 2.5
2010-09-23T17:31:01.890Z
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
CC BY-SA 2.5
2010-09-26T20:33:45.347Z
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?
Sadeq Dousti
CC BY-SA 2.5
2010-09-22T05:26:00.773Z
2010-09-22T05:26:00.773Z
Boaz Barak
<p>In a paper titled &quot;On Deniability in the Common Reference String and Random Oracle Model,&quot; Rafael Pass writes:</p>
<blockquote>
<p>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,</p>
<ol>
</blockquote>
<li>The simulator can see what values parties query the oracle on.
<li>The simulator can answer these queries in whatever way it chooses as long as the answers "look" OK.
</ol>
<p>The first technique, namely the ability to &quot;monitor&quot; queries to the RO, is very common in all papers referring to the concept of zero-knowledge in the RO model.</p>
<p>Now, consider the definition of <strong>black-box</strong> zero-knowledge (<strong>PPT</strong> stands for <em>probabilistic, polynomial-time Turing machine</em>):</p>
<p><span class="math-container">$\exists$</span> a PPT simulator <span class="math-container">$S$</span>, such that <span class="math-container">$\forall$</span> (possibly cheating) PPT verifier <span class="math-container">$V^*$</span>, <span class="math-container">$\forall$</span> common input <span class="math-container">$x\in L$</span>, and <span class="math-container">$\forall$</span> randomness <span class="math-container">$r$</span>, the following are indistinguishable:</p>
<ul>
<li>the view of <span class="math-container">$V^*$</span> while interacting with the prover <span class="math-container">$P$</span> on input <span class="math-container">$x$</span> and using randomness <span class="math-container">$r$</span>;
<li>the output of <span class="math-container">$S$</span> on inputs <span class="math-container">$x$</span> and <span class="math-container">$r$</span>, when <span class="math-container">$S$</span> is given black-box access to <span class="math-container">$V^*$</span>.
</ul>
<p>Here, I want to exhibit a cheating verifier <span class="math-container">$V'$</span>, whose job is to exhaust any simulator which tries to monitor RO queries:</p>
<p>Let <span class="math-container">$S$</span> be the simulator guaranteed by the existential quantifier in the definition of black-box zero-knowledge, and let <span class="math-container">$q(|x|)$</span> be a polynomial which upper-bounds the running time of <span class="math-container">$S$</span> on input <span class="math-container">$x$</span>. Assume that <span class="math-container">$S$</span> tries to monitor the queries of <span class="math-container">$V^*$</span> to the RO.</p>
<p>Now, consider a cheating <span class="math-container">$V'$</span>, which first queries the RO for <span class="math-container">$q(|x|)+1$</span> times (on arbitrary inputs of its choice), and then acts arbitrarily maliciously.</p>
<p>Obviously, <span class="math-container">$V'$</span> exhausts the simulator <span class="math-container">$S$</span>. A simple way for <span class="math-container">$S$</span> 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 <span class="math-container">$P$</span> cannot monitor <span class="math-container">$V'$</span>'s queries, and thus won't reject based on the mere fact that <span class="math-container">$V'$</span> is querying too much.)</p>
<blockquote>
<p>What is the workaround for the above problem?</p>
</blockquote>
<h2>Edit:</h2>
<p>A good source for studying ZK in the RO model is:</p>
<p>Martin Gagné, A Study of the Random Oracle Model, Ph.D. Thesis, <em>University of California, Davis</em>, 2008, 109 pages. Available on ProQuest: <a href="http://gradworks.umi.com/33/36/3336254.html" rel="nofollow noreferrer">http://gradworks.umi.com/33/36/3336254.html</a></p>
<p>Particularly, it gives definitions of black-box ZK in the RO Model in section 3.3 (page 20), attributed to Yung and Zhao:</p>
<p><a href="https://doi.org/10.1007%2F11681878_2?from=SL" rel="nofollow noreferrer">Moti Yung and Yunlei Zhao. Interactive Zero-Knowledge with Restricted Random Oracles.  In <em>Theory of Cryptography - TCC 2006</em>, LNCS 3876, pp. 21-40, 2006.</a></p>

CC BY-SA 2.5
2010-09-20T15:56:19.100Z
I think you might mean "exhaustive" instead of "exhausting".
Dave Clarke
CC BY-SA 2.5
2010-09-20T16:51:20.763Z
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.
Sadeq Dousti
CC BY-SA 2.5
2010-09-20T17:51:30.793Z
My bad. I read exhausting as an adjective, not a verb.
Dave Clarke
<cc.complexity-theory><cr.crypto-security><oracles><black-box>
Exhausting Simulator of Zero-Knowledge Protocols in the Random Oracle Model
Sadeq Dousti
# Exhausting Simulator of Zero-Knowledge Protocols in the Random Oracle Model

(Asked by: username_0 on 2010-09-19)

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.](https://doi.org/10.1007%2F11681878_2?from=SL)

**Tags:** cc.complexity-theory, cr.crypto-security, oracles, black-box

> **Comments:**
> **username_1**: I think you might mean "exhaustive" instead of "exhausting".  
> **username_0**: 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.  
> **username_1**: My bad. I read exhausting as an adjective, not a verb.  

---

## 2 answers

### Answer by username_3 on 2010-09-22. Score: 10 | Accepted answer

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.

> **Comments:**
> **username_0**: 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*)  
> **username_0**: Please see the edited question for some references.  
> **username_3**: 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.  
> **username_0**: 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?  

---

### Answer by username_2 on 2010-09-20. Score: 4

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.

> **Comments:**
> **username_0**: 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...  
> **username_2**: 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.  
> **username_0**: 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!)  
> **username_0**: Please see the edited question for some references.  

---

