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, perfectly sound witness-indistinguishable proof with no setup. For Circuit-SAT a proof for a circuit $C$ has $O(\lambda |C|)$ bits — GOS06b.

Notes

• Non-interactive zaps were known before only under a derandomization assumption, the existence of hitting-set generators against co-nondeterministic circuits, which derandomizes two-message zaps (Zap + HSG ⇒ Non-interactive zaps (BOV)) — GOS06b, BOV03.
• A non-interactive zap is a zap whose prover ignores the verifier’s first message (Non-interactive zap ⇒ Zap) — folklore.
• 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.