Efficient Zero-Knowledge Proofs of Knowledge Without Intractability Assumptions

Ronald Cramer; Ivan Damgård; Philip MacKenzie

Paper 2000/045 Original: eprint.iacr.org/2000/045 ↗

Efficient Zero-Knowledge Proofs of Knowledge Without Intractability Assumptions

Ronald Cramer

Ivan Damgård

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, $q$-one-way group homomorphisms. None of our results rely on intractability assumptions.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint.
History: 2000-09-12: last updated; 2000-09-12: published
Short URL: https://ia.cr/2000/045
License: https://creativecommons.org/licenses/by/4.0/

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}
}