Cryptography Reference
In-Depth Information
Barak's results (cf. (8) and also (9)) call for the re-evaluation of
many common beliefs. Most concretely, they say that results regard-
ing black-box simulators do not reflect inherent limitations of zero-
knowledge (but rather an inherent limitation of a natural way of demon-
strating the zero-knowledge property). Most abstractly, they say that
there are meaningful ways of using a program other than merely invok-
ing it as a black-box. Does this mean that a method was found to
“reverse engineer” programs or to “understand” them? We believe that
the answer is negative. Barak (8) is using the adversary's program in
a significant way (i.e., more significant than just invoking it), without
“understanding” it.
The key idea underlying Barak's protocol (8) is to have the prover
prove that either the original NP-assertion is valid or that he (i.e.,
the prover) “knows the verifier's residual strategy” (in the sense that
it can predict the next verifier message). Indeed, in a real interaction
(with the honest verifier), it is infeasible for the prover to predict the
next verifier message, and so computational-soundness of the protocol
follows. However, a simulator that is given the code of the verifier's
strategy (and not merely oracle access to that code), can produce a valid
proof of the disjunction by properly executing the sub-protocol using its
knowledge of an NP-witness for the second disjunctive. The simulation
is computationally indistinguishable from the real execution, provided
that one cannot distinguish an execution of the sub-protocol in which
one NP-witness (i.e., an NP-witness for the original assertion) is used
from an execution in which the second NP-witness (i.e., an NP-witness
for the auxiliary assertion) is used. That is, the sub-protocol should be a
witness indistinguishable
argument system, and the entire construction
uses the
FLS technique
(described in Section 4.4.3). We warn the reader
that the actual implementation of the above idea requires overcoming
several technical diculties (cf. (8; 11)).
copies. However, even preservation of security under an a priori bounded number of
executions goes beyond the impossibility results of (71; 40) (which refers to black-box
simulations).
