Efficient Zero-Knowledge Proofs for Commitments from Learning with Errors over Rings
Fabrice Benhamouda, Stephan Krenn, Vadim Lyubashevsky, Krzysztof Pietrzak · Lecture notes in computer science · 2015
We extend a commitment scheme based on the learning with errors over rings ( $$\mathsf{RLWE}$$ ) problem, and present efficient companion zero-knowledge proofs of knowledge. Our scheme maps elements from the ring (or equivalently, n elements from $$\mathbb F_q$$ ) to a small constant number of ring elements. We then construct $$\varSigma $$ -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 $$\mathcal {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 $$\varSigma $$ -protocols for LWE-related languages only achieved a noticeable or even constant knowledge error (thus requiring many repetitions of the protocol), or relied on “smudging” out the error (which necessitates working over large fields, resulting in poor efficiency).