Cryptology ePrint Archive: Report 2000/045

Efficient Zero-Knowledge Proofs of Knowledge Without Intractability Assumptions

Ronald Cramer and Ivan Damg{\aa}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, $q$-one-way group homomorphisms. None of our results rely on intractability assumptions.

Category / Keywords: foundations / zero knowledge

Publication Info: Preliminary version appeared in PKC 2000

Date: received 11 Sep 2000

Contact author: philmac at lucent com

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20000912:174538 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]