<p>Regarding your reference request, I remember the following paper off the top of my head:</p>

<p>Willaim Aiello and Johan Hastad. 1991. Relativized perfect zero knowledge is not BPP. <em>Inf. Comput.</em> 93, 2 (August 1991), 223-240. <a href="http://dx.doi.org/10.1016/0890-5401%2891%2990024-V" rel="nofollow">http://dx.doi.org/10.1016/0890-5401(91)90024-V</a>.</p>

<p>Now, to answer your question: Consider any NP-complete language $L$, let $G$ be a generator for a public-key encryption scheme, and define $O$ as a decryption oracle for this encryption system. Finally, let $(P,V)$ be a protocol for proving membership in $L$. </p>

<p>Based on $(P,V)$, define the following modified protocol $(P',V')$: In the beginning of the protocol, $P$ uses $G$ and generates a public key pair $(pk,sk)$, and sends $pk$ to $V'$. Moreover, any message exchanged in $(P,V)$ in encrypted using $pk$ in $(P',V')$.</p>

<p>The prover can find the decrypted messages using $sk$, and the <strong>honest</strong> verifier $V'$ can use the oracle $O$ to find the decrpted messages. However, no other verifier $V^*$ can follow the protocol if we disallow their access to $O$. Therefore, the protocol is ZK for any cheating verifier!</p>

<p>In general, I think the definition should allow any verifier to access $O$, to prevent "twisted" protocols such as the one described above. The same holds for the distinguisher and simulator. However, I believe the prover need not necessarily have access to $O$.</p>

CC BY-SA 3.0
2013-09-13T01:30:43.240Z
Hi Sadeq, thank you very much for your very clear example!
Marcos Villagra
CC BY-SA 3.0
2013-09-13T05:28:32.687Z
@MarcosVillagra: Hi. I'm happy it was useful for you :)
Sadeq Dousti
CC BY-SA 3.0
2013-09-12T16:04:15.867Z
2013-09-12T16:42:37.833Z
2013-09-12T16:42:37.833Z
Sadeq Dousti
<p>An $IP$ system $(P,V)$ is zero-knowledge (ZK) for some language $L$ if for every probabilistic polynomial-time verifer $V^*$ there exists a probabilistic polynomial-time algorithm $S$ for every $x\in L$ such that the output distribution of $(P,V^*)(x)$ and $S(x)$ are "close". Close means that the probability distribution of their outputs are either "equal" (perfect ZK), "statistically close" (statistical ZK), or "computationally indistinguishable" (computational ZK).</p>

<p>My question is,</p>

<blockquote>
  <p>if we allow the honest-verifier $V$ to have access to oracle $O$, do we have to allow any other cheating-verifier $V^*$ to also have access to $O$? Or, do we just simply consider all cheating-verifiers without access to any oracle?</p>
</blockquote>

<p>My main problem is that, intuitively, the complexity classes for ZK might be very different depending on if we allow the cheating-verifiers such oracle access.</p>

<p>I cannot find any reference regarding relativized classes of ZK. If anyone could direct me to any reference I will really appreciate it. I'm aware of the Random Oracle model (RO), where all parties, even malicious ones, have access to a random oracle. But the goals, motivation, and applications of RO are not the ones I'm interested. I'm interested in relativization results in the Baker-Gill-Solovay sense.</p>

CC BY-SA 3.0
2013-09-12T05:53:28.187Z
@RickyDemer, yes for your question. Now regarding my question, clearly we can just define that cheating-verifiers does not have any access to the oracle. So, what you say is that the only "interesting" or "make-sense" definition of zero-knowledge must be that cheating-verifiers have access to the $O$? Or, do you mean that, if we don't allow cheating-verifiers oracle access, then that means thatthis definition is equivalent to the definition that does allow access to $O$?
Marcos Villagra
CC BY-SA 3.0
2013-09-12T06:12:00.890Z
First, you're correct, I'm not considering auxiliary-input. Second, what is P,S,D?
Marcos Villagra
<cc.complexity-theory><cr.crypto-security><zero-knowledge>
How to properly define a zero-knowledge proof system with oracle access
Marcos Villagra
# How to properly define a zero-knowledge proof system with oracle access

(Asked by: username_0 on 2013-09-12)

An $IP$ system $(P,V)$ is zero-knowledge (ZK) for some language $L$ if for every probabilistic polynomial-time verifer $V^\*$ there exists a probabilistic polynomial-time algorithm $S$ for every $x\in L$ such that the output distribution of $(P,V^\*)(x)$ and $S(x)$ are "close". Close means that the probability distribution of their outputs are either "equal" (perfect ZK), "statistically close" (statistical ZK), or "computationally indistinguishable" (computational ZK).

My question is,

> if we allow the honest-verifier $V$ to have access to oracle $O$, do we have to allow any other cheating-verifier $V^\*$ to also have access to $O$? Or, do we just simply consider all cheating-verifiers without access to any oracle?

My main problem is that, intuitively, the complexity classes for ZK might be very different depending on if we allow the cheating-verifiers such oracle access.

I cannot find any reference regarding relativized classes of ZK. If anyone could direct me to any reference I will really appreciate it. I'm aware of the Random Oracle model (RO), where all parties, even malicious ones, have access to a random oracle. But the goals, motivation, and applications of RO are not the ones I'm interested. I'm interested in relativization results in the Baker-Gill-Solovay sense.

**Tags:** cc.complexity-theory, cr.crypto-security, zero-knowledge
> **Comments:**
> **username_0**: @RickyDemer, yes for your question. Now regarding my question, clearly we can just define that cheating-verifiers does not have any access to the oracle. So, what you say is that the only "interesting" or "make-sense" definition of zero-knowledge must be that cheating-verifiers have access to the $O$? Or, do you mean that, if we don't allow cheating-verifiers oracle access, then that means thatthis definition is equivalent to the definition that does allow access to $O$?  
> **username_0**: First, you're correct, I'm not considering auxiliary-input. Second, what is P,S,D?  

---

## 1 answers

### Answer by username_1 on 2013-09-12. Score: 1 | Accepted answer

Regarding your reference request, I remember the following paper off the top of my head:

Willaim Aiello and Johan Hastad. 1991. Relativized perfect zero knowledge is not BPP. *Inf. Comput.* 93, 2 (August 1991), 223-240. [http://dx.doi.org/10.1016/0890-5401(91)90024-V](http://dx.doi.org/10.1016/0890-5401%2891%2990024-V).

Now, to answer your question: Consider any NP-complete language $L$, let $G$ be a generator for a public-key encryption scheme, and define $O$ as a decryption oracle for this encryption system. Finally, let $(P,V)$ be a protocol for proving membership in $L$.

Based on $(P,V)$, define the following modified protocol $(P',V')$: In the beginning of the protocol, $P$ uses $G$ and generates a public key pair $(pk,sk)$, and sends $pk$ to $V'$. Moreover, any message exchanged in $(P,V)$ in encrypted using $pk$ in $(P',V')$.

The prover can find the decrypted messages using $sk$, and the **honest** verifier $V'$ can use the oracle $O$ to find the decrpted messages. However, no other verifier $V^\*$ can follow the protocol if we disallow their access to $O$. Therefore, the protocol is ZK for any cheating verifier!

In general, I think the definition should allow any verifier to access $O$, to prevent "twisted" protocols such as the one described above. The same holds for the distinguisher and simulator. However, I believe the prover need not necessarily have access to $O$.

> **Comments:**
> **username_0**: Hi Sadeq, thank you very much for your very clear example!  
> **username_1**: @MarcosVillagra: Hi. I'm happy it was useful for you :)  

---

