Paper 2021/977

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

Yuval Ishai, Hang Su, and David J. Wu

Abstract

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.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Major revision.ACM Conference on Computer and Communications Security (CCS) 2021
DOI
10.1145/3460120.3484572
Keywords
lattice-based SNARKszkSNARKssuccinct argumentslinear PCP
Contact author(s)
yuvali @ cs technion ac il
hs2nu @ virginia edu
dwu4 @ cs utexas edu
History
2021-09-03: revised
2021-07-22: received
See all versions
Short URL
https://ia.cr/2021/977
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/977,
      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{https://eprint.iacr.org/2021/977}},
      url = {https://eprint.iacr.org/2021/977}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.