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

Friday, October 18, 2019 - 10:30am to 12:00pm

Location:

Hewlett, G882

Speaker:

Christopher J Peikert, University of Michigan (Ann Arbor)

Seminar group:

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.

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