Batch Lattice-Based Designated-Verifier ZK-SNARKs for R1CS
摘要
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 prime p. 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.