Communication efficient Zero-knowledge Proofs of knowledge
Lecture notes in computer sciencePublished 1 January 1992
Alfredo De Santis, Giuseppe Persiano
Citations20
SJR quartileQ2
SJR score0.35
SNIP0.55
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
It is shown that, after a constant-round preprocessing stage, it is possible to give any polynomial number of Non-Interactive Zero-Knowledge Proofs of Knowledge for any NP language.
Abstract
We show that, after a constant-round preprocessing stage, it is possible to give any polynomial number of Non-Interactive Zero-Knowledge Proofs of Knowledge for any NP language. Our proof-system is based on the sole assumption that one-way functions and Non-Interactive Zero-Knowledge Proof Systems of Language Membership exist.The new tool has applications to multi-party protocols. We present the first protocol for Electronic Cash with the following properties. It is provably secure under general complexity assumptions. Its security is based on the existence of one-way functions and Non-Interactive Zero-Knowledge Proof Systems. It does not require the presence of a trusted center; not even the Bank is required to be trusted by the users. Each transaction requires only constant rounds of interaction. Actually, most of the transactions requires just one round of interaction. Each transaction can be performed by only the users that are interested; that is, it is not necessary for all the users to take part in each single transaction to guarantee privacy and security. Moreover, the transcript of each transaction can be used to prove that the transaction has actually taken place and to prove eventual frauds committed.
Keywords
Computer Science
SIAM Journal on ComputingThe Knowledge Complexity of Interactive Proof Systems
3,186 Citations1989Shafi Goldwasser, Silvio Micali +1 more
A computational complexity theory of the “knowledge” contained in a proof is developed and examples of zero-knowledge proof systems are given for the languages of quadratic residuosity and 'quadratic nonresiduosity.
SIAM Journal on ComputingA Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks
2,776 Citations1988Shafi Goldwasser, Silvio Micali +1 more
A digital signature scheme based on the computational difficulty of integer factorization possesses the novel property of being robust against an adaptive chosen-message attack: an adversary who receives signatures for messages of his choice cannot later forge the signature of even a single additional message.
Journal of the ACMHow to construct random functions
2,111 Citations1986Oded Goldreich, Shafi Goldwasser +1 more
A constructive theory of randomness for functions, based on computational complexity, is developed, and a pseudorandom function generator is presented that has applications in cryptography, random constructions, and complexity theory.
Lecture notes in computer scienceUntraceable Electronic Cash
1,109 Citations1990David Chaum, Amos Fiat +1 more
An electronic cash protocol including the steps of using a one-way function f1 to generate an image f1 (x1) from a preimage x1 and receiving from the second party a note including a digital signature.
Journal of CryptologyZero-knowledge proofs of identity
1,034 Citations1988Uriel Feige, Amos Fiat +1 more
This paper defines the definition of unrestricted input zero- knowledge proofs of knowledge in which the prover demonstrates possession of knowledge without revealing any computational information whatsoever (not even the one bit revealed in zero-knowledge proofs of assertions).
Universal one-way hash functions and their cryptographic applications
964 Citations1989Moni Naor, Moti Yung
A Universal One-Way Hash Function family is defined, a new primitive which enables the compression of elements in the function domain and it is proved constructively that universal one- way hash functions exist if any 1-1 one-way functions exist.
Non-interactive zero-knowledge and its applications
864 Citations1988Manuel Blum, Paul Feldman +1 more
It is shown that interaction in any zero-knowledge proof can be replaced by sharing a common, short, random string, and this result is used to construct the first public-key cryptosystem secure against chosen ciphertext attack.
Pseudo-random generation from one-way functions
710 Citations1989Russell Impagliazzo, Leonid A. Levin +1 more
From one-way functions of type (1) or (2) it is shown how to construct pseudo-random generators secure against small circuits or fast algorithms, respectively, and vice-versa.
The round complexity of secure protocols
708 Citations1990Donald Beaver, Silvio Micali +1 more
It is shown that a rigorously-specified and extremely strong notion of secure function evaluation can be achieved by a protocol which requires only a fixed constant number of rounds of interaction, and this result assumes only the existence of a one-way function.
One-way functions are necessary and sufficient for secure signatures
692 Citations1990John Rompel
This paper is interested in signature schemes which are secure agMnst existential forgery under adaptive chosen message attacks, and the existence of trapdoor permutations can be shown to be necessary and sufficient for secure encryption schemes.
Proofs that yield nothing but their validity and a methodology of cryptographic protocol design
544 Citations1986Oded Goldreich, Silvio Micali +1 more
This paper demonstrates the generality and wide applicability of zero-knowledge proofs, a notion introduced by Goldwasser, Micali and Rackoff that efficiently demonstrate membership in the language without conveying any additional knowledge.
Lecture notes in computer scienceZero Knowledge Proofs of Knowledge in Two Rounds
293 Citations2007Uriel Feige, Adi Shamir
These protocols rely on two novel ideas: One for constructing commitment schemes, the other for constructing subprotocols which are not known to be zero knowledge, yet can be proven not to reveal useful information.
SIAM Journal on ComputingNoninteractive Zero-Knowledge
285 Citations1991Manuel Blum, Alfredo De Santis +2 more
If deciding quadratic residuosity (modulo composite integers whose factorization is not known) is computationally hard, it is shown that the NP-complete language of satisfiability also possesses noninteractive zero-knowledge proofs.
Non-cryptographic fault-tolerant computing in constant number of rounds of interaction
263 Citations1989Judit Bar‐Ilan, Donald Beaver
Any function can be evaluated in a constant number of rounds, using messages of size proportional to the size of a constant-depth, unbounded-fanin circuit describing the function, and a means to simulate unbounded fanin multiplicative (or AND) gates using constant rounds is provided.
Random self-reducibility and zero knowledge interactive proofs of possession of information
223 Citations1987Martin Tompa, Heather Woll
It is shown that any "random self-reducible" problem has a zero knowledge interactive proof of this sort, and new zeroknowledge interactive proofs are exhibited for "knowledge" of the factorization of an integer, nonmembership in cyclic subgroups of Zp*, and determining whether an element generates Zp*.
Multiple non-interactive zero knowledge proofs based on a single random string
177 Citations2002Uriel Feige, Dror Lapidot +1 more
The authors solve the two major open problems associated with noninteractive zero-knowledge proofs: how to enable polynomially many provers to prove in writing polynomial many theorems based on the basis of a single random string, and how to construct such proofs under general (rather than number-theoretic) assumptions.
Lecture notes in computer scienceDisposable Zero-Knowledge Authentications and Their Applications to Untraceable Electronic Cash
118 Citations2007Tatsuaki Okamoto, Kazuo Ohta
A new untraceable electronic cash scheme satisfying both untraceability and unreusablity is proposed, which overcomes the problems of the previous scheme proposed by Chaum, Fiat and Naor through its greater efficiency and provable security under reasonable cryptographic assumptions.
Pseudo-random generators under uniform assumptions
118 Citations1990Johan Håstad
The main result of this paper is to indeed prove that oneway functions in the uniform model imply uniformly secure generators.
Minimum resource zero knowledge proofs
70 Citations1989Joe Kilian, Silvio Micali +1 more
It is shown that after a preprocessing stage consisting of O(k) executions of oblivious transfer, any polynomial number of NP-theorems of any polysize can be proved noninteractively and in zero knowledge.
Lecture notes in computer scienceNon-Interactive Zero-Knowledge with Preprocessing
62 Citations1990Alfredo De Santis, Silvio Micali +1 more
It is proved that the existence of any secure probabilistic encryption scheme is enough for Non-Interactive Zero-Knowledge in a modified model and the ability to prove a randomly chosen theorem allows to subsequently prove noninteractively and in Zero- knowledge any smaller size theorem whose proof is discovered.
Lecture notes in computer scienceEverything in NP can be argued in perfect zero-knowledge in a bounded number of rounds
36 Citations1989Gilles Brassard, Claude Crépeau +1 more
This paper gives the first perfect zero-knowledge protocol that offers arbitrarily high security for any statement in NP with a constant number of rounds (under the assumption that it is infeasible to compute discrete logarithms modulo p even for someone who knows the factors of p−1, or more generally under the assumptions that one-way group homomorphisms exist).
Lecture notes in computer scienceCryptographic Applications of the Non-Interactive Metaproof and Many-prover Systems
26 Citations1991Alfredo De Santis, Moti Yung
A variety of cryptographic applications provided by the new tools are presented, including how the tools can be used to provide security mechanisms such as an "Oblivious Warden" which translates non-interactive proofs to random ones independently of the proof itself, and the notion of "Gradual opening of a zero-knowledge computation" which is first demonstrated to be correct using a non-Interactive proof, and then is opened gradually and fast.
Lecture notes in computer sciencePublic-Randomness in Public-Key Cryptography
16 Citations1991Alfredo De Santis, Giuseppe Persiano
This work considers the Diffie-Hellman Public-key model in which an additional short random string is shared by all users, which is very powerful as it supports simple non-interactive implementations of important cryptographic primitives.