Low-noise LPN + DDH ⇒ NIZK argument for NP

CRS model · via Fiat–Shamir · BKM20

Statement

If low-noise LPN is hard and DDH holds, every language in $\mathbf{NP}$ has a computational NIZK argument in the common random string model, with adaptive soundness and adaptive zero knowledge — BKM20. More generally, low-noise LPN and any rate-1 trapdoor hash function for constant-degree functions with an enhanced correctness property, which all existing constructions satisfy, suffice; DDH enters through the rate-1 trapdoor hash of DGI+19 — BKM20.

Notes

• The same construction gives NIZK arguments from low-noise LPN together with QR or DCR, through the trapdoor hash functions of DGI+19 (QR ⇒ TDH, DCR ⇒ TDH) — BKM20.
• Low-noise LPN alone gives trapdoor hash functions only with slightly sublinear compression, not rate 1 (Low-noise LPN ⇒ TDH), and they do not appear efficient enough for this route to correlation intractability — AMR25.