Has anything been done on the modification of the zero knowledge condition
where the distinguisher has access to the witness used by the prover and
the random bits used by the algorithm that generated the auxiliary input?

(Or is that, in fact, how the zero knowledge condition is usually defined?)

This seems like it would be important for using ZK protocols as pieces of larger protocols,
since whether or not an adversary succeeds could depend on that information.

  • 1
    $\begingroup$ Why don’t you just consider the witness and the random bits (I do not know what you mean by the latter, but whatever it is) also as part of the auxiliary input? Then I think that this is the same as the usual definition of zero-knowledge. $\endgroup$ Mar 1, 2012 at 13:44
  • $\begingroup$ Because then the simulator would have access to the witness used, so the simulator could just run an interaction between the cheating verifier and the prover. $\:$ ("random bits" = independent $\{0,1\}$-valued random variables with the uniform distribution) $\;\;$ $\endgroup$
    – user6973
    Mar 1, 2012 at 20:51

1 Answer 1


Regarding the prover's witness, the standard zero-knowledge (ZK) definitions already imply that ZK holds even if the distinguisher is given this witness.

I'm not sure what you mean by "the random bits used by the algorithm that generated the auxiliary input". Please clarify.

  • $\begingroup$ (My understanding of the standard definition is that) The cheating prover and the distinguisher are both given the output of an arbitrary algorithm whose input was the instance to be proven; that output is the "auxiliary input". $\:$ In particular, (my understanding is that) the random bits used by that algorithm are normally not available to the distinguisher. $\;\;$ $\endgroup$
    – user6973
    Mar 22, 2012 at 17:33
  • $\begingroup$ The standard notion of zero knowledge is <em>auxiliary-input</em> zero knowledge, which is preserved even if the distinguisher is given <em>any</em> auxiliary input (in particular the random bits used to generate the instance to be proven). $\endgroup$
    – user6584
    Apr 24, 2012 at 0:46

Your Answer

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