Average-case-hard SZK ⇒ OWF

Standard model · Ost91 · security loss: polynomial

Statement

If SZK is hard on average, that is, some promise problem $\Pi \in \mathbf{SZK}$ and PPT sampler $D$ over ${\Pi }_Y\cup {\Pi }_N$ satisfy ${\mathrm{Pr}}_{x\leftarrow D(1^n)}[\mathcal{A}(x)=\Pi (x)]\le 1/2+\mathrm{negl}(n)$ for all efficient $\mathcal{A}$, then one-way functions exist — Ost91.

Sketch

The candidate one-way function maps the coins of $D$ and of the simulator, together with a round index $i$, to the instance $x$ and the first $i$ messages of the simulated transcript on $x$. If no one-way function exists, it can be inverted with nearly uniform preimages — IL89 — so an efficient prover can extend partial conversations with the honest verifier as the simulator would. The verifier then accepts on yes-instances by statistical zero knowledge and rejects on no-instances by soundness, which decides $\Pi$ on most $x\leftarrow D(1^n)$ and contradicts its hardness.

Notes

• From worst-case hardness alone, $\mathbf{SZK}⊈\mathbf{BPP}$, auxiliary-input one-way functions exist, and the argument extends to computational zero knowledge (CZK ⊄ BPP ⇒ Auxiliary-input OWF) — OW93.