Removing Interaction from Zero-Knowledge Proofs

Goldwasser, Micali, and Rackoff introduced the notion of a Zero-Knowledge Proof System for a particular communication model between the prover and the verifier: the Interactive Turing Machine model. Very recently different weaker communication models for Zero-Knowledge Proofs have been proposed to achieve Zero-Knowledge in a non-interactive scenario. Blum, Feldman, and Micali proved, under a specific complexity assumption, that it is possible for a prover to prove membership in any NP languages non-interactively and still in Zero-Knowledge, provided that the prover and the verifier share a random string. This model is called Non-Interactive Zero-Knowledge Proof System. Their work was subsequently improved by De Santis, Micali, and Persiano that proved the same result under a much weaker assumption. A different model has been proposed more recently by De Santis, Micali, and Persiano. They proved that the ability to interactively prove a randomly chosen theorem is enough for the prover to subsequently prove any smaller NP theorem, whose proof is discovered, non interactively and in Zero-Knowledge. This model is called Non- Interactive Zero-Knowledge Proof System with Preprocessing. Although the model is not as weak as the one introduced by Blum, Feldman, and Micali, they managed to base their protocol on a very weak assumption in cryptography, namely the existence of any secure encryption scheme. In this paper, we informally discuss the notions of Non-Interactive Zero-Knowledge Proof System and the Non-Interactive Zero-Knowledge Proof System with Preprocessing and we present new protocols, simpler that the previously proposed ones, for both models.