Paper 2022/1048

Practical Sublinear Proofs for R1CS from Lattices

Ngoc Khanh Nguyen, IBM Research Europe, ETH Zurich
Gregor Seiler, IBM Research Europe
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
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.