Paper 2023/1606

Efficient Lattice-based Sublinear Arguments for R1CS without Aborts

Abstract

We propose a new lattice-based sublinear argument for R1CS that not only achieves efficiency in concrete proof size but also demonstrates practical performance in both proof generation and verification. To reduce the proof size, we employ a new encoding method for large prime fields, resulting in a compact proof for R1CS over such fields. We also devise a new proof technique that randomizes the input message. This results in fast proof generation performance, eliminating rejection sampling from the proving procedure. Compared to Ligero (CCS 2017), a hash-based post-quantum SNARK, our proof system yields a comparable proof size and proof generation performance, and excels in verification performance by an order of magnitude.