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.
• A publicly verifiable, completely non-interactive delegation scheme for all polynomial-time computations in the CRS model follows from an efficiently falsifiable decisional assumption on groups with bilinear maps, by first building a scheme with a CRS polynomial in the running time, following Paneth and Rothblum, and then bootstrapping it to a short CRS — KPY19.
• From $k$-Lin or subgroup decision in pairing groups, publicly verifiable non-interactive delegation for RAM programs has a CRS sublinear in the running time — WW22.