[Resource Topic] 2000/045: Efficient Zero-Knowledge Proofs of Knowledge Without Intractability Assumptions

Welcome to the resource topic for 2000/045

Efficient Zero-Knowledge Proofs of Knowledge Without Intractability Assumptions

Authors: Ronald Cramer, Ivan Damgård, Philip MacKenzie


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.

ePrint: https://eprint.iacr.org/2000/045

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .