I'm confused about the definitions of black-box zero knowledge and non-black-box zero knowledge. I have searched and found explanations but still a bit confused about it. From the context, their definition (with auxiliary input) of black-box zero knowledge proof system between the prover $P$ and (malicious) verifier $V^*$ can be described as follows:

$\{\langle P(\omega), V^*(z)(x)\rangle\}_{(x,\omega) \in R, z \in \{0,1\}^{p(|x|)}}$

and $\{S^{V^*(z,x,\cdot)}(x)\}_{(x,\omega) \in R, z \in \{0,1\}^{p(|x|)}}$

are (perfectly/statistically/computationally) indistinguishable, Where $S$ is a simulator which has access to a oracle function $V^*(z,x,\cdot)$

In my opinion, the only difference between the definition of non-black-box zero knowledge and the definition of black-box zero knowledge is that non-black-box zero knowledge allows that for all $V^*$ there exists unbounded simulator $S$, is this correct?

  • $\begingroup$ The way I remember it, nobody allows for unbounded simulator. It is common to require an efficient probabilistic algorithm, producing a transcript in expected polynomial time. $\endgroup$ Mar 17 '17 at 19:47

The difference is to do with the quantifiers on the simulator. Non black-box zero-knowledge says that for all verifiers, there exists a simulator that can simulate a proof of all statements (i.e. there can be one simulator per verifier). Black-box zero knowledge says that there exists a simulator that can simulate a proof of all statements over all verifiers (i.e. there is one simulator total). Therefore, black-box zero-knowledge is the stronger definition of security.

Reference: Lysyanskaya, 2002 (page 31) https://dspace.mit.edu/handle/1721.1/29271

  • $\begingroup$ To complement this answer, and older paper by Goldreich, Micali, Wigderson: Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems introducing two definitions of simulator. $\endgroup$ Sep 19 '17 at 20:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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