Doubly enhanced certified TDP ⇒ NIZK

Fully-black-box reduction · CRS model · FLS90, GR13 · security loss: polynomial: zero knowledge reduces to hard-core-bit unpredictability through a hybrid over the unrevealed hidden bits and the proved theorems; soundness is statistical

Statement

A family of doubly enhanced, certified trapdoor permutations (indices are recognizably permutations) yields a NIZK proof system for every language in $\mathbf{NP}$ in the common reference string model: soundness is statistical, zero-knowledge is computational, and one reference string serves polynomially many theorems — FLS90. The hidden-bits compilation uses the double enhancement, and double enhancement suffices for it — GR13.

Sketch

FLS90 give an unconditional NIZK for Hamiltonicity in the hidden-bits model and compile it: the prover samples $(f,\mathsf{td})\leftarrow \mathsf{Gen}(1^{\lambda })$ and sends $f$, the reference string is read as images $y_1,\dots ,y_m$ under $f$, hidden bit $i$ is $b(\mathsf{Invert}(\mathsf{td},y_i))$ for a hard-core predicate $b$, and the prover reveals a bit by publishing its preimage while unrevealed bits stay unpredictable to the verifier. One string serves polynomially many theorems by proving ”$x\in L$ or the trailing block of the string is in the image of a $\mathsf{PRG}$”; the simulator plants a pseudorandom block and uses its seed as the witness.

Notes

• For families over $\{0,1{\}}^n$ the certified-permutation hypothesis can be dropped: the prover certifies the index with a NIZK proof that it describes an (almost) permutation — BY96.
• Doubly enhanced families still leave the FLS90 instantiation unsound for adversarially chosen indices whose domain is not recognizable; certifiable injectivity closes the gap and suffices for the FLS paradigm even for trapdoor functions — CL18.
• BFM88 introduced NIZK, from a number-theoretic assumption; NIZK for $\mathbf{NP}$ from trapdoor permutations is FLS90.