Research Article
Batch Lattice-Based Designated-Verifier ZK-SNARKs for R1CS
@INPROCEEDINGS{10.1007/978-3-031-64948-6_17, author={Xi Lin and Han Xia and Yongqiang Li and Mingsheng Wang}, title={Batch Lattice-Based Designated-Verifier ZK-SNARKs for R1CS}, proceedings={Security and Privacy in Communication Networks. 19th EAI International Conference, SecureComm 2023, Hong Kong, China, October 19-21, 2023, Proceedings, Part I}, proceedings_a={SECURECOMM}, year={2024}, month={10}, keywords={ZK-SNARKs Post-quantum Succinct argument}, doi={10.1007/978-3-031-64948-6_17} }- Xi Lin
Han Xia
Yongqiang Li
Mingsheng Wang
Year: 2024
Batch Lattice-Based Designated-Verifier ZK-SNARKs for R1CS
SECURECOMM
Springer
DOI: 10.1007/978-3-031-64948-6_17
Abstract
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({\mathbb {F}}{p^n})for any primep. Then, we apply our batch SNARK schemes for R1CS in({\mathbb {F}}{2^n})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(2^{10})to(2^{14})).
To exemplify the efficiency, we present some practical examples. Initially, we integrate a rank-1 constraint system in({\mathbb {F}}_{2^8})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.
