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

Available format(s)
Category
Foundations
Publication info
Published elsewhere. Preliminary version appeared in PKC 2000
Keywords
zero knowledge
Contact author(s)
philmac @ lucent com
History
Short URL
https://ia.cr/2000/045

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},
note = {\url{https://eprint.iacr.org/2000/045}},
url = {https://eprint.iacr.org/2000/045}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.