CryptoDB
Efficient Zero-Knowledge Proofs of Knowledge Without Intractability Assumptions
| Authors: | |
|---|---|
| Download: | |
| 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. |
BibTeX
@misc{eprint-2000-11389,
title={Efficient Zero-Knowledge Proofs of Knowledge Without Intractability Assumptions},
booktitle={IACR Eprint archive},
keywords={foundations / zero knowledge},
url={http://eprint.iacr.org/2000/045},
note={Preliminary version appeared in PKC 2000 philmac@lucent.com 11211 received 11 Sep 2000},
author={Ronald Cramer and Ivan Damgård and Philip MacKenzie},
year=2000
}