Witness indistinguishable and witness hiding protocols
Published 1 January 1990Open access
Uriel Feige, Adi Shamir
Citations526
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 work proves two central results: Unlike zero knowledge protocols, witness indistinguishablity is preserved under arbi t rary composition of protocols, including parallel execution, and any witness indistinguishable protocol for this s ta tement is also.
Abstract
A two party protocol in which party A uses one of several secret witnesses to an NP assertion is witness indistinguishable if party B cannot tell which witness A is actually using. The protocol is witness hiding if by the end of the protocol B cannot compute any new witness which he did not know before the protocol began. Witness hiding is a natural security requirement, and can replace zero knowledge in many cryptographic protocols.
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.
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).
Journal of Computer and System SciencesMinimum disclosure proofs of knowledge
956 Citations1988Gilles Brassard, David Chaum +1 more
This paper unifies and extends models and techniques previously put forward by the authors, and compares some independent related work.
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.
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.
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*.
Lecture notes in computer scienceNon-Interactive Zero-Knowledge Proof Systems
162 Citations1988Alfredo De Santis, Silvio Micali +1 more
The result is strengthened by showing that Non-Interactive Zero-Knowledge Proof Systems exist based on the weaker and well-known assumption that quadratic residuosity is hard.
Lecture notes in computer scienceNew Paradigms for Digital Signatures and Message Authentication Based on Non-Interactive Zero Knowledge Proofs
148 Citations2007Mihir Bellare, Shafi Goldwasser
Noninteractive zero knowledge proofs in a network which have the property that anyone in the network can individually check correctness while the proof is zero knowledge to any sufficiently small coalition are shown.
Lecture notes in computer scienceEverything in NP can be argued in perfect zero-knowledge in a bounded number of rounds
41 Citations2007Gilles Brassard, Claude Crépeau +1 more
The first perfect zero-knowledge protocol that offers arbitrarily high security for any statement in NP with a constant number of rounds is given (under a suitable cryptographic assumption).
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 scienceOn Generating Solved Instances of Computational Problems
21 Citations1990Martı́n Abadi, Eric Allender +3 more
This work considers the efficient generation of solved instances of computational problems and considers invulnerable generators, which are defined as programs that produce instance-witness pairs according to a distribution under which any polynomial-time adversary fails to find a witness that x ∈ S.