Christopher Peikert: Noninteractive Zero Knowledge for NP from Learning With Errors


Christopher Peikert, University of Michigan (Ann Arbor)


Vinod Vaikuntanathan and Yael Kalai

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

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.

Time permitting, we will also discuss some ongoing work on improving the efficiency of NIZKs from LWE.