TY - GEN
T1 - Batch Lattice-Based Designated-Verifier ZK-SNARKs for R1CS
AU - Lin, Xi
AU - Xia, Han
AU - Li, Yongqiang
AU - Wang, Mingsheng
N1 - Publisher Copyright:
© ICST Institute for Computer Sciences, Social Informatics and Telecommunications Engineering 2025.
PY - 2023
Y1 - 2023
N2 - Zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARK) is a crucial cryptographic tool to achieve privacy protection and has drawn considerable attention for its appealing applications, e.g., anonymous transactions, confidential smart contracts, and scalable consensus mechanisms. Compared with the pre-quantum case, the practicability of this primitive in the post-quantum setting is still unsatisfactory, especially for the space complexity. In this work, we generalize the LPCP-based SNARK schemes for general cyclotomic rings and propose a tighter bound in the noise analysis for non-power-of-two cyclotomic rings using the powerful basis. Secondly, we introduce the first batch SNARK scheme for rank-1 constraint system (R1CS) in Fpn for any prime p. Then, we apply our batch SNARK schemes for R1CS in F2n and implement it. Using the batch technique, we can process multiple relations at the same time, thereby yielding nice amortized results. The amortized proof size is around 3KB for moderate-size circuits (the circuit size ranges from 210 to 214). To exemplify the efficiency, we present some practical examples. Initially, we integrate a rank-1 constraint system in F28 for the AES algorithm, which is 3.95x smaller than xJsnark (Kosba et al., 2018) in terms of the number of constraints. Subsequently, we proceed to instantiate our batch SNARK scheme for AES, MiMC, and LowMC.
AB - Zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARK) is a crucial cryptographic tool to achieve privacy protection and has drawn considerable attention for its appealing applications, e.g., anonymous transactions, confidential smart contracts, and scalable consensus mechanisms. Compared with the pre-quantum case, the practicability of this primitive in the post-quantum setting is still unsatisfactory, especially for the space complexity. In this work, we generalize the LPCP-based SNARK schemes for general cyclotomic rings and propose a tighter bound in the noise analysis for non-power-of-two cyclotomic rings using the powerful basis. Secondly, we introduce the first batch SNARK scheme for rank-1 constraint system (R1CS) in Fpn for any prime p. Then, we apply our batch SNARK schemes for R1CS in F2n and implement it. Using the batch technique, we can process multiple relations at the same time, thereby yielding nice amortized results. The amortized proof size is around 3KB for moderate-size circuits (the circuit size ranges from 210 to 214). To exemplify the efficiency, we present some practical examples. Initially, we integrate a rank-1 constraint system in F28 for the AES algorithm, which is 3.95x smaller than xJsnark (Kosba et al., 2018) in terms of the number of constraints. Subsequently, we proceed to instantiate our batch SNARK scheme for AES, MiMC, and LowMC.
KW - Post-quantum
KW - Succinct argument
KW - ZK-SNARKs
UR - https://www.scopus.com/pages/publications/85207582653
U2 - 10.1007/978-3-031-64948-6_17
DO - 10.1007/978-3-031-64948-6_17
M3 - Conference Proceeding
AN - SCOPUS:85207582653
SN - 9783031649479
T3 - Lecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering, LNICST
SP - 329
EP - 349
BT - Security and Privacy in Communication Networks - 19th EAI International Conference, SecureComm 2023, Proceedings
A2 - Duan, Haixin
A2 - Debbabi, Mourad
A2 - de Carné de Carnavalet, Xavier
A2 - Luo, Xiapu
A2 - Au, Man Ho Allen
A2 - Du, Xiaojiang
PB - Springer Science and Business Media Deutschland GmbH
T2 - 19th EAI International Conference on Security and Privacy in Communication Networks, SecureComm 2023
Y2 - 19 October 2023 through 21 October 2023
ER -