Bilinear pairing + DLIN ⇒ Zaps (non-interactive)

Standard model · GOS06b

Statement

If the decisional linear assumption holds in prime-order symmetric bilinear groups whose description the verifier can check, every $\mathbf{NP}$ language has a non-interactive zap: a single-message witness-indistinguishable proof with no setup. For Circuit-SAT a proof for a circuit $C$ has $O(\lambda |C|)$ bits — GOS06b. A non-interactive zap is a zap whose prover ignores the verifier’s first message — folklore.

Notes

• Non-interactive zaps were known before only under a derandomization assumption, the existence of hitting-set generators against co-nondeterministic circuits (Barak, Ong and Vadhan) — GOS06b.
• Two-message zaps follow from NIZK proofs in the common random string model: NIZK ⇒ Zaps (Dwork–Naor) — DN00.
• The same paper gives NIZK proofs for $\mathbf{NP}$ in the common reference string model under DLIN: DLIN ⇒ NIZK — GOS06b.