LWE ⇒ NIZK

CRS model · PS19

Statement

If plain LWE is hard with parameters corresponding to small polynomial approximation factors, 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.