LWE with polynomial ratio ⇒ SNARG for P

CRS model · via Fiat–Shamir · CJJ21 · security loss: polynomial

Statement

If LWE with polynomial modulus-to-noise ratio is hard for polynomial-time adversaries, every deterministic computation of $T$ steps has a publicly verifiable SNARG in the common random string model with adaptive soundness: the common random string and the proof have size $\mathrm{poly}(\lambda ,\log T)$, and verification takes time polylogarithmic in $T$ — CJJ21. The construction goes through the first non-interactive batch argument for NP from LWE alone (LWE with polynomial ratio ⇒ BARG for NP), obtained by instantiating the Fiat–Shamir transform with correlation-intractable hashing — CJJ21.

Notes

• Earlier SNARGs from standard assumptions covered only bounded-depth computations and needed sub-exponential hardness of LWE — JKKZ21.