Subgroup decision ⇒ BARG for NP

CRS model · WW22

Statement

If the subgroup decision assumption holds in composite-order bilinear groups, $\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.

Notes

• In prime-order pairing groups, the $k$-Lin assumption for any $k\ge 1$ gives one as well (Bilinear pairing + k-Lin ⇒ BARG for NP) — WW22.