TY - JOUR
T1 - Amortized Efficient zk-SNARK from Linear-Only RLWE Encodings
AU - Chung, Heewon
AU - Kim, Dongwoo
AU - Kim, Jeong Han
AU - Kim, Jiseung
N1 - Publisher Copyright:
© 2023 KICS.
PY - 2023/6
Y1 - 2023/6
N2 - 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.
AB - 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.
KW - Post-quantum cryptography
KW - RLWE
KW - SNARK
KW - zero-knowledge proofs
UR - http://www.scopus.com/inward/record.url?scp=85182563715&partnerID=8YFLogxK
U2 - 10.23919/JCN.2023.000012
DO - 10.23919/JCN.2023.000012
M3 - Article
AN - SCOPUS:85182563715
SN - 1229-2370
VL - 25
SP - 271
EP - 284
JO - Journal of Communications and Networks
JF - Journal of Communications and Networks
IS - 3
ER -