Amortized Efficient zk-SNARK from Linear-Only RLWE Encodings

This paper addresses a new lattice-based designated zk-SNARK having the smallest proof size in the amortized sense, from the linear-only ring learning with the error (RLWE) encodings. We first generalize a quadratic arithmetic programming (QAP) over a finite field to a ring-variant over a polynomial ring Z_p[X]/(X^N + 1) with a power of two N. Then, we propose a zk-SNARK over this ring with a linear-only encoding assumption on RLWE encodings. From the ring isomorphism Z_p[X]/(X^N + 1) ≅ Z^N_p , the proposed scheme packs multiple messages from Z_p, resulting in much smaller amortized proof size compared to previous works. In addition, we present a refined analysis on the noise flooding technique based on the Hellinger divergence instead of the conventional statistical distance, which reduces the size of a proof. In particular, our proof size is 276.5 KB and the amortized proof size is only 156 bytes since our protocol allows to batch N proofs into a single proof. Therefore, we achieve the smallest amortized proof size in the category of lattice-based zk-SNARKs and comparable proof size in the (pre-quantum) zk-SNARKs category.