Bilinear pairing + k-Lin ⇒ BARG for NP

CRS model · WW22

Statement

If the $k$-Lin assumption holds in a prime-order pairing group for some $k\ge 1$, $\mathbf{NP}$ has a non-interactive batch argument in the CRS model: $m$ statements $x_1,\dots ,x_m$ of satisfiability for one Boolean circuit $C$ have a single proof of size $\mathrm{poly}(\lambda ,|C|,\log m)$, sound against efficient provers for statements fixed before the CRS is sampled — WW22. The construction verifies the batch directly, without correlation-intractable hashing or PCPs — WW22. As corollaries WW22 obtain a publicly verifiable non-interactive delegation scheme for RAM programs whose CRS is sublinear in the running time, and aggregate signatures with bounded aggregation, from standard bilinear assumptions — WW22.

Notes

• The CRS grows with the number $m$ of statements — WW22.
• The subgroup decision assumption in composite-order bilinear groups gives a BARG for $\mathbf{NP}$ as well (Subgroup decision ⇒ BARG for NP) — WW22.
• The first BARG for $\mathbf{NP}$ from LWE alone is LWE with polynomial ratio ⇒ BARG for NP, via correlation-intractable hashing — CJJ21.