Caltech Logo

TCS+ Talk

Wednesday, May 1, 2019
10:00am to 11:00am
Add to Cal
Annenberg 322
Noninteractive Zero Knowledge for NP from Learning With Errors
Chris Peikert, University of Michigan,

Abstract: 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 Learning With Errors (LWE) problem, and thereby on worst-case lattice problems. Our proof system instantiates a framework developed in a series of recent works 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 ad-hoc LWE variants) or, more recently, on the existence of circularly secure fully homomorphic encryption. However, none of these assumptions are known to be implied by 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 LWE (with small polynomial approximation factors). 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.

(This is joint work with Sina Shiehian. Paper: )

For more information, please contact Bonnie Leung by email at