The Knowledge-of-Exponent Assumptions and 3-Round Zero-Knowledge Protocols
Lecture notes in computer sciencePublished 1 January 2004
Mihir Bellare, Adriana Palacio
Citations235
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 it is possible to “falsify” assumptions like KEA2 that, due to their nature and quantifier-structure, do not lend themselves easily to "efficient falsification" (Naor [15]).
Abstract
Hada and Tanaka [11,12] showed the existence of 3-round, negligible-error zero-knowledge arguments for NP based on a pair of non-standard assumptions, here called KEA1 and KEA2. In this paper we show that KEA2 is false. This renders vacuous the results of [11,12]. We recover these results, however, under a suitably modified new assumption called KEA3. What we believe is most interesting is that we show that it is possible to "falsify" assumptions like KEA2 that, due to their nature and quantifier-structure, do not lend themselves easily to "efficient falsification" (Naor [15]).
Keywords
Computer Science
Lecture notes in computer scienceHow To Prove Yourself: Practical Solutions to Identification and Signature Problems
3,870 Citations2007Amos Fiat, Adi Shamir
Simple identification and signature schemes which enable any user to prove his identity and the authenticity of his messages to any other user without shared or public keys are described.
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.
Lecture notes in computer scienceAdvances in Cryptology — CRYPTO’ 99
2,625 Citations1999Michael J. Wiener
A sophisticated variant of Desmedt-Odlyzko's method where the attacker obtains the signatures of m1, mτ−1 and exhibits the signature of an mτ which was never submitted to the signer is presented.
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.
How to go beyond the black-box simulation barrier
484 Citations2001Boaz Barak
It is presented the first constructions of non-black-box simulators, and assuming the existence of collision resistent hash functions, a new zero-knowledge argument system for NP that satisfies the following properties.
SIAM Journal on ComputingOn the Composition of Zero-Knowledge Proof Systems
425 Citations1996Oded Goldreich, Hugo Krawczyk
Lecture notes in computer scienceTowards Practical Public Key Systems Secure Against Chosen Ciphertext attacks
352 Citations2007Ivan Damgård
Two efficient constructions aimed at making public key systems secure against chosen ciphertext attacks are presented and a connection between such public-key systems and efficient identification schemes is pointed out.
Lecture notes in computer scienceOn Cryptographic Assumptions and Challenges
349 Citations2003Moni Naor
This work proposes several open problems regarding cryptographic tasks that currently do not have a good challenge of that sort by creating a challenge to their validity by classifying computational assumptions based on the complexity of falsifying them.
Lecture notes in computer scienceNon-Interactive Oblivious Transfer and Applications
293 Citations2007Mihir Bellare, Silvio Micali
This work shows how to implement oblivious transfer without interaction, through the medium of a public file, so that an application can get non-interactive zero knowledge proofs via the same public file.
Lecture notes in computer scienceOn the existence of 3-round zero-knowledge protocols
177 Citations1998Satoshi Hada, Toshiaki Tanaka
This paper constructs a 3-round zero-knowledge protocol for any NP language based on a novel computational assumption related to the Diffie-Hellman problem and achieves a weaker notion of zero- Knowledge: auxiliary-input non-uniform zero- knowledge.
Journal of CryptologyA Note on Negligible Functions
70 Citations2002Bellare
It is argued that the issue that really arises is what it might mean for a collection of functions to be ``negligible,'' and two such notions are considered, and it is said that any cryptographic primitive has a specific associated ``security level.
DSpace@MIT (Massachusetts Institute of Technology)On the Existence of 3-Round Zero-Knowledge Proofs
11 Citations2002Matthew Lepinski
A nonblack-box simulatable 3-round zero-knowledge proof system for NP is presented, which is secure even when the prover has unbounded computational resources, and a proof of knowledge framework is provided in which to view this type of non-standard assumption.
Lecture notes in computer scienceOn the Discrepancy between Serial and Parallel of Zero-Knowledge Protocols
9 Citations2007Kouichi Sakurai, Toshiya Itoh
This paper investigates the discrepancy between a serial version and a parallel version of zero-knowledge protocols, and clarifies the information “leaked” in the parallel version, which is not zero- knowledge unlike the case of the serial version.