Paper 2014/934

Efficient Generic Zero-Knowledge Proofs from Commitments

Samuel Ranellucci, Alain Tapp, and Rasmus Winther Zakarias

Abstract

Even though Zero-knowledge has existed for more than 30 years, few generic constructions for Zero-knowledge exist. In this paper we present a new kind of commitment scheme on which we build a novel and efficient Zero-knowledge protocol for circuit satisfiability. We can prove knowledge of the AES-key which map a particular plaintext to a particular ciphertext in less than 4 seconds with a soundness error of $2^{-40}$. Our protocol only requires a number of commitments proportional to the security parameter with a small constant (roughly 5).

Note: Corrections from various sources has been addressed, links to implementation has been added with performance graphs and data. Also instructions on how to reproduce our results are included.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
Zero-knowledgecommitments
Contact author(s)
rwl @ cs au dk
History
2015-10-05: revised
2014-11-14: received
See all versions
Short URL
https://ia.cr/2014/934
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/934,
      author = {Samuel Ranellucci and Alain Tapp and Rasmus Winther Zakarias},
      title = {Efficient Generic Zero-Knowledge Proofs from Commitments},
      howpublished = {Cryptology ePrint Archive, Paper 2014/934},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/934}},
      url = {https://eprint.iacr.org/2014/934}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.