Paper 2022/1048 Original: eprint.iacr.org/2022/1048 ↗
Practical Sublinear Proofs for R1CS from Lattices
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.
Metadata
- Available format(s)
PDF- Category
- Cryptographic protocols
- Publication info
- Preprint.
- History
- 2022-08-12: last updated
- 2022-08-12: published
- Short URL
- https://ia.cr/2022/1048
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2022/1048,
author = {Ngoc Khanh Nguyen and Gregor Seiler},
title = {Practical Sublinear Proofs for R1CS from Lattices},
howpublished = {Cryptology {ePrint} Archive, Paper 2022/1048},
year = {2022},
url = {https://eprint.iacr.org/2022/1048}
}