Amortized Efficient zk-SNARK from Linear-Only RLWE Encodings

Heewon Chung, Dongwoo Kim, Jeong Han Kim, Jiseung Kim

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

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 Zp[X]/(XN + 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 Zp[X]/(XN + 1) ≅ ZNp , the proposed scheme packs multiple messages from Zp, 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.

Original languageEnglish
Pages (from-to)271-284
Number of pages14
JournalJournal of Communications and Networks
Volume25
Issue number3
DOIs
StatePublished - Jun 2023

Keywords

  • Post-quantum cryptography
  • RLWE
  • SNARK
  • zero-knowledge proofs

Fingerprint

Dive into the research topics of 'Amortized Efficient zk-SNARK from Linear-Only RLWE Encodings'. Together they form a unique fingerprint.

Cite this