Circular-secure FHE ⇒ NIZK argument for NP

CRS model · via Fiat–Shamir · CCH+19

Statement

If there is a circular-secure FHE scheme, every language in $\mathbf{NP}$ has an adaptively sound NIZK argument in the common reference string model — CCH+19. Circular security is assumed only at the standard level, negligible advantage for polynomial-time adversaries. The construction applies the Fiat–Shamir transform to a trapdoor $\Sigma$-protocol, with a hash family built from the FHE scheme that is correlation intractable for the protocol’s bad-challenge function — CCH+19.

Notes

• The same paper obtains NIZK arguments for $\mathbf{NP}$ in the common reference string model from almost-optimal hardness of search LWE against polynomial-time adversaries in place of circular-secure FHE — CCH+19.
• LWE with polynomial modulus-to-noise ratio alone also gives NIZK for $\mathbf{NP}$ (LWE ⇒ NIZK) — PS19.