Black-Box Computational Zero-Knowledge Proofs, Revisited: The Simulation-Extraction Paradigm.

Abstract

Abstract. The concept of zero-knowledge proofs has been around for about 25 years. It has been redefined over and over to suit the special security requirements of protocols and systems. Common among all definitions is the requirement of the existence of some efficient “device ” simulating the view of the verifier (or the transcript of the protocol), such that the simulation is indistinguishable from the reality. The definitions differ in many respects, including the type and power of the devices, the order of quantifiers, the type of indistinguishability, and so on. In this paper, we will scrutinize the definition of “black-box computational ” zero-knowledge, in which there exists one simulator for all verifiers, the simulator has black-box access to the verifier, and the quality of simulation is such that the real and simulated views cannot be distinguished by polynomial tests (computational indistinguisha-bility). Working in a theoretical model (the Random-Oracle Model), we show that the indistinguishability requirement is stated in a conceptually inappropriate way: Present definitions allow the knowledge of the verifier and distin-guisher to be independent, while the two entities are essentially coupled. Therefore, our main take on the problem will be conceptual and semantic, rather than literal. We formalize the concept by introducing a “knowledge ex-tractor ” into the model, which tries to extract the extra knowledge hard-coded into the distinguisher (if any), and then helps the simulator to construct the view of the verifier. The new paradigm is termed Simulation-Extraction