Paper 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)
- Category
- Cryptographic protocols
- Publication info
- A major revision of an IACR publication in CRYPTO 2022
- Keywords
- zero-knowledge proofs r1cs lattice-based cryptography
- Contact author(s)
-
nkn @ zurich ibm com
grs @ zurich ibm com - History
- 2022-08-17: approved
- 2022-08-12: received
- See all versions
- Short URL
- https://ia.cr/2022/1048
- License
-
CC BY
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} }