Paper 2016/538
How to prove knowledge of small secrets
Carsten Baum, Ivan Damgård, 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.
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- Published by the IACR in CRYPTO 2016
- Keywords
- Proofs of Plaintext KnowledgeLattice-based EncryptionHomomorphic HashingInteger Commitments
- Contact author(s)
- cbaum @ cs au dk
- History
- 2016-05-31: received
- Short URL
- https://ia.cr/2016/538
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2016/538, author = {Carsten Baum and Ivan Damgård and Kasper Larsen and Michael Nielsen}, title = {How to prove knowledge of small secrets}, howpublished = {Cryptology {ePrint} Archive, Paper 2016/538}, year = {2016}, url = {https://eprint.iacr.org/2016/538} }