Subgroup decision ⇒ Perfect NIZK arguments for NP

CRS model · GOS06a

Statement

Assume the subgroup decision assumption in composite-order bilinear groups. Then every language in $\mathbf{NP}$ has a NIZK argument in the common reference string model with perfect zero knowledge, sound for false statements fixed before the reference string is sampled. It is the first perfect NIZK argument for $\mathbf{NP}$ — GOS06a.

Notes

• The arguments are adaptively sound only for statements restricted in advance, for example by an a-priori bound on their size. An adaptively sound perfect NIZK argument for $\mathbf{NP}$ with no such restriction follows from an extended knowledge-of-exponent assumption over bilinear groups, and the usual proof approach cannot give adaptively sound statistical NIZK arguments for $\mathbf{NP}$ unless $\mathbf{NP}\subseteq P/poly$ — AF07.
• The same paper gives the first UC-secure NIZK argument for $\mathbf{NP}$ against adaptive adversaries — GOS06a.
• Under the decisional linear assumption in prime-order bilinear groups, $\mathbf{NP}$ has NIZK proofs with perfect soundness (DLIN ⇒ NIZK) — GOS06b.