LWE with polynomial ratio ⇒ BARG for NP

CRS model · via Fiat–Shamir · CJJ21

Statement

If LWE with polynomial modulus-to-noise ratio is hard for polynomial-time adversaries, $\mathbf{NP}$ has a non-interactive batch argument in the CRS model: $k$ statements $x_1,\dots ,x_k$ of satisfiability for one circuit $C$ have a single proof of size $\mathrm{poly}(\lambda ,|C|,\log k)$, sound against efficient provers for statements fixed before the CRS is sampled — CJJ21. It is the first BARG for $\mathbf{NP}$ from LWE alone; it is somewhere extractable, and it is obtained by instantiating the Fiat–Shamir transform with correlation-intractable hashing for an interactive batch argument — CJJ21.

Notes

• The BARG is the main ingredient of the SNARG for deterministic computations in the same paper (LWE with polynomial ratio ⇒ SNARG for P) — CJJ21.