Paper 2016/538

How to prove knowledge of small secrets

Carsten Baum, Ivan Damgård, Kasper Larsen, and Michael Nielsen


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.

Available format(s)
Cryptographic protocols
Publication info
Published by the IACR in CRYPTO 2016
Proofs of Plaintext KnowledgeLattice-based EncryptionHomomorphic HashingInteger Commitments
Contact author(s)
cbaum @ cs au dk
2016-05-31: received
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.