CryptoDB

Paper: Practical Sublinear Proofs for R1CS from Lattices

Authors: Ngoc Khanh Nguyen , IBM Research Europe and ETH Zurich Gregor Seiler , IBM Research Europe Search ePrint Search Google Slides CRYPTO 2022 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.
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
}