Paper 2021/977

Shorter and Faster Post-Quantum Designated-Verifier zkSNARKs from Lattices

Yuval Ishai, Hang Su, and David J. Wu


Zero-knowledge succinct arguments of knowledge (zkSNARKs) enable efficient privacy-preserving proofs of membership for general NP languages. Our focus in this work is on post-quantum zkSNARKs, with a focus on minimizing proof size. Currently, there is a $1000\times$ 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. With our construction, after an initial preprocessing step, a proof for an NP relation of size $2^{20}$ is just over 16 KB. Our proofs are $10.3\times$ shorter than previous post-quantum zkSNARKs for general NP languages. Compared to previous lattice-based zkSNARKs (also in the designated-verifier preprocessing model), we obtain a $42\times$ reduction in proof size and a $60\times$ reduction in the prover's running time, all while achieving a much higher level of soundness. Compared to the shortest pre-quantum zkSNARKs by Groth (Eurocrypt 2016), the proof size in our lattice-based construction is $131\times$ longer, but both the prover and the verifier are faster (by $1.2\times$ and $2.8\times$, respectively). Our construction follows the general blueprint of Bitansky et al. (TCC 2013) and Boneh et al. (Eurocrypt 2017) of combining a linear probabilistically checkable proof (linear PCP) together with a linear-only vector encryption scheme. We develop a concretely-efficient lattice-based instantiation of this compiler by considering quadratic extension fields of moderate characteristic and using linear-only vector encryption over rank-2 module lattices.

Available format(s)
Publication info
Published elsewhere. Major revision.ACM Conference on Computer and Communications Security (CCS) 2021
lattice-based SNARKszkSNARKssuccinct argumentslinear PCP
Contact author(s)
yuvali @ cs technion ac il
hs2nu @ virginia edu
dwu4 @ cs utexas edu
2021-09-03: revised
2021-07-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yuval Ishai and Hang Su and David J.  Wu},
      title = {Shorter and Faster Post-Quantum Designated-Verifier zkSNARKs from Lattices},
      howpublished = {Cryptology ePrint Archive, Paper 2021/977},
      year = {2021},
      doi = {10.1145/3460120.3484572},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.