Cryptology ePrint Archive: Report 2016/538
How to prove knowledge of small secrets
Carsten Baum and Ivan Damgård and Kasper Larsen and Michael Nielsen
Abstract: We propose a new zero-knowledge protocol applicable to additively homomorphic functions that map integer vectors to an Abelian group. The protocol demonstrates knowledge of a short preimage and achieves amortised efficiency comparable to the approach of Cramer and Damgård from Crypto 2010, but gives a much tighter bound on what we can extract from a dishonest prover. Towards achieving this result, we develop an analysis for bins-and-balls games that might be of independent interest. We also provide a general analysis of rewinding of a cut-and-choose protocol as well as a method to use Lyubachevsky's rejection sampling technique efficiently in an interactive protocol when many proofs are given simultaneously.
Our new protocol yields improved proofs of plaintext knowledge for (Ring-)LWE-based cryptosystems, where such general techniques were not known before. Moreover, they can be extended to prove preimages of homomorphic hash functions as well.
Category / Keywords: cryptographic protocols / Proofs of Plaintext Knowledge, Lattice-based Encryption, Homomorphic Hashing, Integer Commitments
Original Publication (in the same form): IACR-CRYPTO-2016
Date: received 31 May 2016
Contact author: cbaum at cs au dk
Available format(s): PDF | BibTeX Citation
Version: 20160531:151642 (All versions of this report)
Short URL: ia.cr/2016/538
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]