Sub-exponential DDH ⇒ NIZK argument for NP

CRS model · via Fiat–Shamir · JJ21 · security loss: requires sub-exponentially small DDH advantage against polynomial-time adversaries

Statement

If DDH is sub-exponentially hard for some group generator (no pairing is needed), every $\mathbf{NP}$ language has a NIZK argument in the common reference string model with adaptive soundness and computational zero knowledge — JJ21. The proof needs DDH hardness only against polynomial-time adversaries, with sub-exponentially small advantage. It instantiates Fiat–Shamir with a correlation-intractable hash family for constant-depth threshold circuits, built from a new tool, interactive trapdoor hashing protocols — JJ21.

Notes

• The main construction of the same paper is a NIZK argument in the common random string model with adaptive multi-theorem statistical zero knowledge and only non-adaptive soundness; relaxing zero knowledge to computational is what gives adaptive soundness — JJ21.
• The paper also gives zap arguments for $\mathbf{NP}$ under the same assumption. Their soundness is computational, so they are not zaps in the Dwork–Naor sense, which are proofs — JJ21.
• In groups with a symmetric bilinear pairing, NIZK proofs for $\mathbf{NP}$ follow from DLIN: DLIN ⇒ NIZK — GOS06b.