3
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\begingroup$ Should there be a "such that" in "algorithm $S$ for every"? $\:$ Of course we allow any $\hspace{1.19 in}$ other cheating-verifier to have access to $O$, since we give everything access to $O$. $\hspace{1.26 in}$ $\endgroup$
    – user6973
    Sep 12, 2013 at 5:25
  • $\begingroup$ @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$? $\endgroup$
    – Marcos Villagra
    Sep 12, 2013 at 5:53
  • $\begingroup$ Having the oracle be "no-cheaters-allowed" would permit protocols to work by having the verifier use the oracle access to authenticate itself to the prover. $\;\;\;$ Additionally, one would have to ask which, if any, of $\:P,S,D\:$ have access to the oracle. $\;\;\;$ (That reminds me: your definition does not account for auxiliary input.) $\;\;\;\;\;\;$ $\endgroup$
    – user6973
    Sep 12, 2013 at 6:02
  • $\begingroup$ First, you're correct, I'm not considering auxiliary-input. Second, what is P,S,D? $\endgroup$
    – Marcos Villagra
    Sep 12, 2013 at 6:12
  • $\begingroup$ prover,simulator,distinguisher $\;$ $\endgroup$
    – user6973
    Sep 12, 2013 at 6:14

1 Answer 1

Reset to default
1
$\begingroup$

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.

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ Hi Sadeq, thank you very much for your very clear example! $\endgroup$
    – Marcos Villagra
    Sep 13, 2013 at 1:30
  • $\begingroup$ @MarcosVillagra: Hi. I'm happy it was useful for you :) $\endgroup$
    – Sadeq Dousti
    Sep 13, 2013 at 5:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.