Cryptology ePrint Archive: Report 2014/934

Efficient Generic Zero-Knowledge Proofs from Commitments

Samuel Ranellucci and 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).

Category / Keywords: cryptographic protocols / Zero-knowledge, commitments

Date: received 14 Nov 2014, last revised 5 Oct 2015

Contact author: rwl at cs au dk

Available format(s): PDF | BibTeX Citation

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.

Version: 20151005:113111 (All versions of this report)

Short URL: ia.cr/2014/934