Practical Sublinear Proofs for R1CS from Lattices

Abstract

We propose a practical sublinear lattice-based zero-knowledge proof system for Rank-1 Constraint Satisfaction (R1CS). The proof size asymptotically scales with the square root of the witness size and concretely becomes 2-3 times smaller than Ligero (ACM CCS 2017), which also exhibits square root scaling, for more than 224 constraints.