Publications

Zero-knowledge succinct arguments of knowledge (zkSNARKs) enable efficient privacy-preserving proofs of membership for general \( \mathsf{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 \( \mathsf{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 \( \mathsf{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.