Cryptology ePrint Archive: Report 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).
Category / Keywords: cryptographic protocols / Commitment Schemes, Ring Learning with Errors, Zero-Knowledge Proofs of Knowledge
Date: received 28 Oct 2014, last revised 28 Oct 2014
Contact author: skr at zurich ibm com
Available format(s): PDF | BibTeX Citation
Version: 20141030:133732 (All versions of this report)
Short URL: ia.cr/2014/889
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]