Paper 2019/158

Noninteractive Zero Knowledge for NP from (Plain) Learning With Errors

Chris Peikert and Sina Shiehian


We finally close the long-standing problem of constructing a noninteractive zero-knowledge (NIZK) proof system for any NP language with security based on the plain Learning With Errors (LWE) problem, and thereby on worst-case lattice problems. Our proof system instantiates the framework recently developed by Canetti et al. [EUROCRYPT'18], Holmgren and Lombardi [FOCS'18], and Canetti et al. [STOC'19] for soundly applying the Fiat--Shamir transform using a hash function family that is correlation intractable for a suitable class of relations. Previously, such hash families were based either on ``exotic'' assumptions (e.g., indistinguishability obfuscation or optimal hardness of certain LWE variants) or, more recently, on the existence of circularly secure fully homomorphic encryption (FHE). However, none of these assumptions are known to be implied by plain LWE or worst-case hardness. Our main technical contribution is a hash family that is correlation intractable for arbitrary size-$S$ circuits, for any polynomially bounded $S$, based on plain LWE (with small polynomial approximation factors). The construction combines two novel ingredients: a correlation-intractable hash family for log-depth circuits based on LWE (or even the potentially harder Short Integer Solution problem), and a ``bootstrapping'' transform that uses (leveled) FHE to promote correlation intractability for the FHE decryption circuit to arbitrary (bounded) circuits. Our construction can be instantiated in two possible ``modes,'' yielding a NIZK that is either computationally sound and statistically zero knowledge in the common random string model, or vice-versa in the common reference string model.

Note: Refined statement of final open problem.

Available format(s)
Publication info
Published by the IACR in CRYPTO 2019
noninteractive zero knowledgecorrelation intractabilitylearning with errorslattices
Contact author(s)
cpeikert @ alum mit edu
shiayan @ umich edu
2019-06-06: last of 3 revisions
2019-02-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Chris Peikert and Sina Shiehian},
      title = {Noninteractive Zero Knowledge for NP from (Plain) Learning With Errors},
      howpublished = {Cryptology ePrint Archive, Paper 2019/158},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.