Efficient Zero-Knowledge Proofs for Commitments from Learning with Errors over Rings
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
- PDF / 352,319 Bytes
- 21 Pages / 439.37 x 666.142 pts Page_size
- 6 Downloads / 207 Views
2
ENS, CNRS, INRIA, and PSL, Paris, France [email protected] AIT Austrian Institute of Technology GmbH, Vienna, Austria [email protected] 3 ENS, INRIA, Paris, France [email protected] 4 IST Austria, Klosterneuburg, Austria [email protected]
Abstract. We extend a commitment scheme based on the learning with errors over rings (RLWE) problem, and present efficient companion zeroknowledge proofs of knowledge. Our scheme maps elements from the ring (or equivalently, n elements from Fq ) to a small constant number of ring elements. We then construct Σ-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(M n 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 Σ-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).
Keywords: Commitment schemes Knowledge Proofs of Knowledge
1
·
Ring learning with errors
·
Zero-
Introduction
Commitment schemes are among the most widely used cryptographic primitives. They allow one party, the committer, to commit to a message m to another This work was done while the second author was at IBM Research – Zurich. This work was partly funded by the ERC Grants 321310–PERCY and 259668–PSPC, and by the French ANR-13-JS02-0003 JCJC Project CLE. c Springer International Publishing Switzerland 2015 G. Pernul et al. (Eds.): ESORICS 2015, Part I, LNCS 9326, pp. 305–325, 2015. DOI: 10.1007/978-3-319-24174-6 16
306
F. Benhamouda et al.
party. At a later point in time, the committer may reveal m by opening the commitment c. The scheme is said to be secure if it is binding and hiding. The former property says that the committer cannot open c to a message different from m, and the latter ensures that only knowing c gives no information about m to the receiver. In higher-level protocols, commitments are often used to link different building blocks, e.g., encryption-, signature-, and revocation schemes in constructions of group signatures or anonymous credentials [CKL+14]. In such situations, it is often necessary to prove properties of a message m contained in a commitment, without revealing any additional information about m. This is done via so-called zero-knowledge proofs of knowledge (ZK-PoK). These are two-party protocols which allow a prover to convince a verifier that it knows some secret piece of information, without revealing anything else than what is already revealed by the claim itself [GMR85]. As the efficiency of ZK-PoKs of commitments directly affects the efficiency of many higher-level sys
Data Loading...
