Paper 2014/889

Efficient Zero-Knowledge Proofs for Commitments from Learning With Errors over Rings

Fabrice Benhamouda, Stephan Krenn, Vadim Lyubashevsky, and Krzysztof Pietrzak

Abstract

We design an efficient commitment scheme, and companion zero-knowledge proofs of knowledge, based on the learning with errors over rings (RLWE) problem. In particular, for rings in which almost all elements have inverses, we construct a perfectly binding commitment scheme whose hiding property relies on the RLWE assumption. Our scheme maps elements from the ring (or equivalently, n elements from F_q) to a small constant number of ring elements. We then construct Sigma-protocols for proving, in a zero-knowledge manner, knowledge of the message contained in a commitment. We are able to further extend our basic protocol to allow us to prove additive and multiplicative relations among committed values. Our protocols have a communication complexity of O(Mn\log q) and achieve a negligible knowledge error in one run. Here M is the constant from a rejection sampling technique that we employ, and can be set close to 1 by adjusting other parameters. Previously known Sigma-protocols for LWE-related languages either relied on ``smudging'' out the error (which necessitates working over large fields, resulting in poor efficiency) or only achieved a noticeable or even constant knowledge error (thus requiring many repetitions of the protocol).

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
Commitment SchemesRing Learning with ErrorsZero-Knowledge Proofs of Knowledge
Contact author(s)
skr @ zurich ibm com
History
2014-10-30: received
Short URL
https://ia.cr/2014/889
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/889,
      author = {Fabrice Benhamouda and Stephan Krenn and Vadim Lyubashevsky and Krzysztof Pietrzak},
      title = {Efficient Zero-Knowledge Proofs for Commitments from Learning With Errors over Rings},
      howpublished = {Cryptology ePrint Archive, Paper 2014/889},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/889}},
      url = {https://eprint.iacr.org/2014/889}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.