Removing Interaction from Zero-Knowledge Proofs

Alfredo De Santis, Silvio Micali and Giuseppe Persiano
Additional contact information
Alfredo De Santis: IBM T. J. Watson Research Center
Silvio Micali: Laboratory for Computer Science, MIT
Giuseppe Persiano: Harvard University, Aiken Comp. Lab.

A chapter in Sequences, 1990, pp 377-393 from Springer

Abstract: Abstract 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.

Keywords: Encryption Scheme; Proof System; Random String; Jacobi Symbol; Quadratic Residue Modulo (search for similar items in EconPapers)
Date: 1990
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4612-3352-7_30

Ordering information: This item can be ordered from
http://www.springer.com/9781461233527

DOI: 10.1007/978-1-4612-3352-7_30

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().