Paper 2000/045
Efficient Zero-Knowledge Proofs of Knowledge Without Intractability Assumptions
Ronald Cramer, Ivan Damgård, and Philip MacKenzie
Abstract
We initiate the investigation of the class of relations
that admit extremely efficient perfect zero knowledge
proofs of knowledge: constant number of rounds, communication
linear in the length of the statement and the witness, and
negligible knowledge error. In its most general incarnation,
our result says that for relations that have a particular
three-move honest-verifier zero-knowledge (HVZK) proof of knowledge,
and which admit a particular three-move HVZK proof of knowledge for
an associated commitment relation, perfect zero knowledge
(against a general verifier) can be achieved essentially for free,
even when proving statements on several instances combined
under under monotone function composition. In addition,
perfect zero-knowledge is achieved with an optimal 4-moves.
Instantiations of our main protocol lead to efficient perfect
ZK proofs of knowledge of discrete logarithms and RSA-roots,
or more generally,
Metadata
- Available format(s)
-
PDF PS
- Category
- Foundations
- Publication info
- Published elsewhere. Preliminary version appeared in PKC 2000
- Keywords
- zero knowledge
- Contact author(s)
- philmac @ lucent com
- History
- 2000-09-12: received
- Short URL
- https://ia.cr/2000/045
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2000/045, author = {Ronald Cramer and Ivan Damgård and Philip MacKenzie}, title = {Efficient Zero-Knowledge Proofs of Knowledge Without Intractability Assumptions}, howpublished = {Cryptology {ePrint} Archive, Paper 2000/045}, year = {2000}, url = {https://eprint.iacr.org/2000/045} }