Average-case-hard CZK ⇒ OWF

Standard model · OW93

Statement

If CZK is hard on average, that is, a language $L$ with a computational zero-knowledge proof and a PPT sampler $D$ satisfy ${\mathrm{Pr}}_{x\leftarrow D(1^n)}[\mathcal{A}(x)=L(x)]\le 1/2+\mathrm{negl}(n)$ for all efficient $\mathcal{A}$, then one-way functions exist — OW93.

Notes

• Worst-case hardness, $\mathbf{CZK}⊈\mathbf{BPP}$, yields auxiliary-input one-way functions (CZK ⊄ BPP ⇒ Auxiliary-input OWF) — OW93.
• The statistical-zero-knowledge case predates OW93 (Average-case-hard SZK ⇒ OWF) — Ost91.