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)
PDF
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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2016/538}},
      url = {https://eprint.iacr.org/2016/538}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.