LWE ⇒ NIZK

CRS model · via Fiat–Shamir · PS19

Statement

If LWE is hard with polynomial modulus-to-noise ratio (plain LWE with small polynomial approximation factors, in the terms of PS19), every language in $\mathbf{NP}$ has a NIZK. The construction builds from LWE a hash family that is correlation intractable for all circuits of any fixed polynomial size and uses it to instantiate the Fiat–Shamir transform soundly. One mode is computationally sound (an argument) and statistically zero-knowledge in the common random string model; the other is statistically sound (a proof) and computationally zero-knowledge in the common reference string model — PS19.

Sketch

Apply Fiat–Shamir to a parallel-repeated commit-and-open $\Sigma$-protocol for an $\mathbf{NP}$-complete language. With a trapdoor for the commitments, the unique challenge on which a cheating prover could answer is an efficiently computable function of the first message, so a hash family that is correlation intractable for such functions makes the transform sound. PS19 build such families from LWE, from a correlation-intractable hash for log-depth functions and a bootstrapping step that uses leveled FHE — PS19.