CryptoDB
Practical Sublinear Proofs for R1CS from Lattices
| Authors: |
|
|---|---|
| Download: | |
| 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
}