Skip to Main content Skip to Navigation
Conference papers

Lattice-Based Zero-Knowledge Arguments for Integer Relations

Benoît Libert 1, 2 San Ling 3 Khoa Nguyen 3 Huaxiong Wang 3 
Abstract : We provide lattice-based protocols allowing to prove relations among committed integers. While the most general zero-knowledge proof techniques can handle arithmetic circuits in the lattice setting, adapting them to prove statements over the integers is non-trivial, at least if we want to handle exponentially large integers while working with a polynomial-size modulus q. For a polynomial L, we provide zero-knowledge arguments allowing a prover to convince a verifier that committed L-bit bitstrings x, y and z are the binary representations of integers X, Y and Z satisfying Z = X + Y over Z. The complexity of our arguments is only linear in L. Using them, we construct arguments allowing to prove inequalities X < Z among committed integers, as well as arguments showing that a committed X belongs to a public interval [α, β], where α and β can be arbitrarily large. Our range arguments have logarithmic cost (i.e., linear in L) in the maximal range magnitude. Using these tools, we obtain zero-knowledge arguments showing that a committed element X does not belong to a public set S using O(n · log |S|) bits of communication, where n is the security parameter. We finally give a protocol allowing to argue that committed L-bit integers X, Y and Z satisfy multiplicative relations Z = XY over the integers, with communication cost subquadratic in L. To this end, we use our protocol for integer addition to prove the correct recursive execution of Karatsuba's multiplication algorithm. The security of our protocols relies on standard lattice assumptions with polynomial modulus and polynomial approximation factor.
Document type :
Conference papers
Complete list of metadata

Cited literature [62 references]  Display  Hide  Download
Contributor : Benoit Libert Connect in order to contact the contributor
Submitted on : Sunday, November 4, 2018 - 1:51:00 PM
Last modification on : Monday, May 16, 2022 - 4:58:02 PM
Long-term archiving on: : Tuesday, February 5, 2019 - 12:21:24 PM


Files produced by the author(s)




Benoît Libert, San Ling, Khoa Nguyen, Huaxiong Wang. Lattice-Based Zero-Knowledge Arguments for Integer Relations. CRYPTO 2018 - Annual International Cryptology Conference, Aug 2018, Santa Barbara, United States. pp.700-732, ⟨10.1007/978-3-319-96881-0_24⟩. ⟨hal-01911886⟩



Record views


Files downloads