Cryptology ePrint Archive: Report 2021/977

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

Yuval Ishai and 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 candidates. 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. Finally, compared to the shortest pre-quantum zkSNARKs by Groth (Eurocrypt 2016), the proof size in our lattice-based construction is $131\times$ longer, but the prover's running time is $1.2\times$ faster.

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.

Category / Keywords: implementation / lattice-based SNARKs, zkSNARKs, succinct arguments, linear PCP

Original Publication (with major differences): ACM Conference on Computer and Communications Security (CCS) 2021

Date: received 21 Jul 2021

Contact author: yuvali at cs technion ac il, hs2nu at virginia edu, dwu4 at cs utexas edu

Available format(s): PDF | BibTeX Citation

Version: 20210722:092332 (All versions of this report)

Short URL: ia.cr/2021/977


[ Cryptology ePrint archive ]