Name
Title | ||
|---|---|---|
Efficient Zero-Knowledge Proofs for Commitments from Learning With Errors over Rings. |
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/978-3-319-24174-6_16 | ESORICS |
Keywords | DocType | Volume |
Commitment schemes, Ring learning with errors, ZeroKnowledge Proofs of Knowledge | Conference | 9326 |
ISSN | Citations | PageRank |
0302-9743 | 11 | 0.50 |
References | Authors | |
25 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Fabrice Benhamouda | 1 | 240 | 15.59 |
| Stephan Krenn | 2 | 378 | 21.46 |
| Vadim Lyubashevsky | 3 | 1174 | 59.91 |
| Krzysztof Pietrzak | 4 | 1513 | 72.60 |