Paper 2023/1858

A Novel Power-Sum PRG with Applications to Lattice-Based zkSNARKs

Charanjit S Jutla, IBM T. J. Watson Research Center
Eamonn W. Postlethwaite, CWI Amsterdam
Arnab Roy, Mysten Labs

zkSNARK is a cryptographic primitive that allows a prover to prove to a resource constrained verifier, that it has indeed performed a specified non-deterministic computation correctly, while hiding private witnesses. In this work we focus on lattice based zkSNARK, as this serves two important design goals. Firstly, we get post-quantum zkSNARK schemes with $O(\log (\mbox{Circuit size}))$ sized proofs (without random oracles) and secondly, the easy verifier circuit allows further bootstrapping by arbitrary (zk)SNARK schemes that offer additional or complementary properties. However, this goal comes with considerable challenges. The only known lattice-based bilinear maps are obtained using multi-linear maps of Garg, Gentry, and Halevi 2013 (GGH13), which have undergone considerable cryptanalytic attacks, in particular annihilation attacks. In this work, we propose a (level-2) GGH13-encoding based zkSNARK which we show to be secure in the weak-multilinear map model of Miles-Sahai-Zhandry assuming a novel pseudo-random generator (PRG). We argue that the new PRG assumption is plausible based on the well-studied Newton's identity on power-sum polynomials, as well as an analysis of hardness of computing Grobner bases for these polynomials. The particular PRG is designed for efficient implementation of the zkSNARK. Technically, we leverage the 2-linear instantiation of the GGH13 graded encoding scheme to provide us with an analogue of bilinear maps and adapt the Groth16 (Groth, Eurocrypt 2016) protocol, although with considerable technical advances in design and proof. The protocol is non-interactive in the CRS model.

Available format(s)
Cryptographic protocols
Publication info
zero-knowledgesuccinct proofweak multilinear modellinear interactive proofsGrobner basisNewton's Identity
Contact author(s)
csjutla @ us ibm com
eamonn postlethwaite @ cwi nl
arnabr @ gmail com
2023-12-06: approved
2023-12-04: received
See all versions
Short URL
Creative Commons Attribution-ShareAlike


      author = {Charanjit S Jutla and Eamonn W. Postlethwaite and Arnab Roy},
      title = {A Novel Power-Sum PRG with Applications to Lattice-Based zkSNARKs},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1858},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.