International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Lattice-Based Zero-Knowledge Arguments for Integer Relations

Authors:
Benoît Libert
San Ling
Khoa Nguyen
Huaxiong Wang
Download:
DOI: 10.1007/978-3-319-96881-0_24 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2018
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 $$\mathbb {Z}$$. The complexity of our arguments is only linear in L. Using them, we construct arguments allowing to prove inequalities $$X
Video from CRYPTO 2018
BibTeX
@inproceedings{crypto-2018-28830,
  title={Lattice-Based Zero-Knowledge Arguments for Integer Relations},
  booktitle={Advances in Cryptology – CRYPTO 2018},
  series={Lecture Notes in Computer Science},
  publisher={Springer},
  volume={10992},
  pages={700-732},
  doi={10.1007/978-3-319-96881-0_24},
  author={Benoît Libert and San Ling and Khoa Nguyen and Huaxiong Wang},
  year=2018
}