Shorter and Faster Post-Quantum Designated-Verifier zkSNARK from Lattices 3738 views

Zero-knowledge succinct argument of knowledge (zkSNARK), a non-interactive zero-knowledge proof of knowledge protocol, enables efficient privacy-preserving proofs of memberships for general NP languages. Nowadays, zkSNARKs have become important build blocks in numerous applications, and a growing number of works have focused on optimizing different properties of the proof system. This work is focusing on minimizing concrete proof size for post-quantum zkSNARKs. At a high-level, our construction follows the blueprint of Bitansky et al. [BCIOP13] and Boneh et al. [BISW17] of combining a linear probabilistically checkable proof (linear PCP) together with a linear-only vector encryption scheme. We developed a concretely-efficient lattice-based instantiation by considering quadratic extension fields Fp2 with moderate characteristic and using linear-only vector encryption over rank-2 module lattice. To our knowledge, it is plausibly the first system that uses linear PCPs over extension fields. Moreover, applying linear-only encryption over extension fields reduces the lattice parameters, and thus improves the concrete efficiency of our lattice-based zkSNARK significantly. Before our work, there is a 1000x gap in the proof size between the best pre-quantum constructions and the best post-quantum ones. Here, we develop and implement new lattice-based zkSNARKs in the designated-verifier preprocessing model. After an initial preprocessing step, verifying an NP relation of size 2^20 requires a 16 KB proof, 68 s of prover time, and 1.2 ms of verifier time. Our proofs are 7.9x shorter than existing post-quantum candidates. Compared to previous lattice-based zkSNARKs (also in the designated-verifier preprocessing model), we obtain a 39.4x reduction in proof size and a 60.2x reduction in prover time, all while achieving a much higher level of soundness.

MS (Master of Science)

Applied Cryptography; Zero Knowledge Proof

English

2021-05-03