Practical Sublinear Proofs for R1CS from Lattices

Ngoc Khanh Nguyen; Gregor Seiler

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: 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}
}