International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Practical Sublinear Proofs for R1CS from Lattices

Authors:
Ngoc Khanh Nguyen , IBM Research Europe and ETH Zurich
Gregor Seiler , IBM Research Europe
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2022
Abstract: We propose a practical sublinear-size zero-knowledge proof system for Rank-1 Constraint Satisfaction (R1CS) based on lattices. The proof size scales asymptotically with the square root of the witness size. Concretely, the size becomes 2-3 times smaller than Ligero (ACM CCS 2017), which also exhibits square root scaling, for large instances of R1CS. At the core lies an interactive variant of the Schwartz-Zippel Lemma that might be of independent interest.
Video from CRYPTO 2022
BibTeX
@inproceedings{crypto-2022-32247,
  title={Practical Sublinear Proofs for R1CS from Lattices},
  publisher={Springer-Verlag},
  author={Ngoc Khanh Nguyen and Gregor Seiler},
  year=2022
}