Quasi-polynomially hard LWE ⇒ Statistical zap arguments

Standard model · BLNWW25

Statement

If LWE with polynomial modulus-to-noise ratio is quasi-polynomially hard, every language in $\mathbf{NP}$ has a statistical zap argument: a two-message public-coin argument whose first message is a uniformly random string from the verifier, statistically witness-indistinguishable and computationally sound for statements fixed before that message — BLNWW25. The construction follows the hidden-bits paradigm; earlier zap arguments from lattice assumptions all relied on correlation-intractable hash functions — BLNWW25.

Notes

• The first statistical zap arguments are due to BFJKS20, from LWE with an explicit, efficiently computable bound on the adversary’s advantage, and concurrently GJJM20, from quasi-polynomially hard LWE, both through correlation-intractable Fiat–Shamir.