QR ⇒ NIZK proofs with a common random string (Blum–De Santis–Micali–Persiano)

Fully-black-box reduction · CRS model · BFM88, BDMP91 · security loss: polynomial: soundness is statistical, and zero knowledge reduces to QR with a hybrid over the polynomially many repetitions

Statement

If QR is hard for Blum integers, every language in $\mathbf{NP}$ has a NIZK proof system with a uniformly random reference string: soundness is statistical, and zero knowledge is computational — BFM88, BDMP91. Soundness against provers that choose the statement after seeing the string follows from soundness for each fixed statement: repeating the proof on independent segments of the string drives the error for a fixed $x$ below $2^{-(|x|+\lambda )}$, a union bound over the statements of length $|x|$ leaves error at most $2^{-\lambda }$, and single-theorem zero knowledge survives the repetition by a hybrid argument — standard.

Sketch

The prover samples a Blum integer $N$, whose factorization it knows, and some $y\in {\mathrm{J}}_N\setminus {\mathrm{QR}}_N$, and proves unconditionally, in NIZK, that $N$ has exactly two distinct prime divisors and that $y$ is a quadratic non-residue — BDMP91. It reads the rest of the string as elements $x\in {\mathrm{J}}_N$, each carrying the hidden bit $[x\in {\mathrm{QR}}_N]$, which it opens with a square root of $x$ or of $xy$; these bits drive a proof for satisfiability. The simulator takes $y\in {\mathrm{QR}}_N$ instead, so that it can open every element either way, and QR hides the substitution.

Notes

• One reference string serves polynomially many theorems by the compiler of FLS90, which needs a PRG; QR gives one (QR ⇒ PRG) — BBS86.
• BDMP91 is the journal version of BFM88; the general-assumption counterpart, NIZK for $\mathbf{NP}$ from trapdoor permutations, is Doubly enhanced certified TDP ⇒ NIZK — FLS90.