Proofs that yield nothing but their validity and a methodology of cryptographic protocol design
Published 1 October 1986
Oded Goldreich, Silvio Micali, Avi Wigderson
Citations544
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
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.
Abstract
In this paper we demonstrate the generality and wide applicability of zero-knowledge proofs, a notion introduced by Goldwasser, Micali and Rackoff. These are probabilistic and interactive proofs that, for the members x of a language L, efficiently demonstrate membership in the language without conveying any additional knowledge. So far, zero-knowledge proofs were known only for some number theoretic languages in NP ∩ Co-NP.
Keywords
Computer Science
Communications of the ACMHow to share a secret
13,453 Citations1979Adi Shamir
This technique enables the construction of robust key management schemes for cryptographic systems that can function securely and reliably even when misfortunes destroy half the pieces and security breaches expose all but one of the remaining pieces.
Reducibility among Combinatorial Problems
10,823 Citations1972Richard M. Karp
The Design and Analysis of Computer Algorithms
9,456 Citations1974Alfred V. Aho, John E. Hopcroft
This text introduces the basic data structures and programming techniques often used in efficient algorithms, and covers use of lists, push-down stacks, queues, trees, and graphs.
The complexity of theorem-proving procedures
6,107 Citations1971Stephen Cook
It is shown that any recognition problem solved by a polynomial time-bounded nondeterministic Turing machine can be “reduced” to the problem of determining whether a given propositional formula is a tautology.
How to generate and exchange secrets
3,712 Citations1986Andrew Chi-Chih Yao
It is shown how two parties A and B can interactively generate a random integer N = p¿q such that its secret, i.e., the prime factors, is hidden from either party individually but is recoverable jointly if desired.
Journal of Computer and System SciencesProbabilistic encryption
2,554 Citations1984Shafi Goldwasser, Silvio Micali
It is proved that extracting any information about the cleartext from the cyphertext is hard on the average for an adversary with polynomially bounded computational resources.
Theory and application of trapdoor functions
1,020 Citations1982Andrew Chi-Chih Yao
A new information theory is introduced and the concept of trapdoor functions is studied and applications of such functions in cryptography, pseudorandom number generation, and abstract complexity theory are examined.
Theory and application of trapdoor functions
938 Citations1982Andrew Chi-Chih Yao
Trading group theory for randomness
772 Citations1985László Babai
The aim of this paper is to replace most of the (proven and unproven) group theory of [BS] by elementary combinatorial arguments and defines a new hierarchy of complexity classes “just above NP</italic””, introducing Arthur vs. Merlin games and proving that it consists precisely of those languages which belong to NP.
Bounded-width polynomial-size branching programs recognize exactly those languages in <i>NC</i><sup>1</sup>
683 Citations1986David A. Mix Barrington
The method of proof is extended to investigate the complexity of the word problem for a fixed permutation group and show that polynomial size circuits of width 4 also recognize exactly nonuniform NC 1.
A robust and verifiable cryptographically secure election scheme
409 Citations1985Josh Cohen, Michael J. Fischer
A cryptographic scheme for holding a secure secret ballot election in which all communication is public is described, which introduces a new form of "interactive proof" by which one participant gives passive observers high confidence that certain claims are true without releasing related private information.
Journal of Computer and System SciencesBounded-width polynomial-size branching programs recognize exactly those languages in NC1
407 Citations1989David A. Mix Barrington
Lecture notes in computer scienceDemonstrating Possession of a Discrete Logarithm Without Revealing it
111 Citations1987David Chaum, Jan‐Hendrik Evertse +2 more
Techniques are presented that allow A to convince B that she knows a solution to the Discrete Log Problem without revealing anything about x to B, and it is proved that these protocols secure under a formal model which is of interest in its own right.
Non-transitive transfer of confidence: A perfect zero-knowledge interactive protocol for SAT and beyond
106 Citations1986Gilles Brassard, Claude Crépeau
A perfect zero-knowledge interactive proof is a protocol by which Alice can convince Bob of the truth of some theorem in a way that yields no information as to how the proof might proceed (in the sense of Shannon's information theory).
Lecture notes in computer scienceZero-Knowledge Simulation of Boolean Circuits
72 Citations2007Gilles Brassard, Claude Crépeau
A zero-knowledge interactive proof is a protocol by which Alice can convince a polynomially-bounded Bob of the truth of some theorem without giving him any hint as to how the proof might proceed.
Lecture notes in computer scienceDemonstrating that a Public Predicate can be Satisfied Without Revealing Any Information About How
60 Citations2007David Chaum
The problem solved here may be defined in the following way: Both parties y and z agree on a Boolean expression called a predicate; y claims to know a secret value satisfymg the predicate; z wants very high certainty that y does have such a value; while y is willing to demonstrate possession of the secret satisfying value, y is unwilling to reveal the secret value to z.
Flipping Coins In Many Pockets (Byzantine Agreement On Uniformly Random Values)
31 Citations2005Arndt Bröder, Danny Dolev
It is shown that no (probabilistic) protocol can achieve agreement on a fair coin in fewer phases then necessary for Byzantine agreement, and hence the "pre-dealt" nature of the random sequence required for Rabin's algorithm is crucial.