Paper 2014/889
Efficient Zero-Knowledge Proofs for Commitments from Learning With Errors over Rings
Fabrice Benhamouda and Stephan Krenn and 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)
- 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
-
CC BY