CZK ⊄ BPP ⇒ Auxiliary-input OWF

Standard model · OW93

Statement

If CZK is hard in the worst case, that is, some language $L\notin \mathbf{BPP}$ has a computational zero-knowledge proof, then an auxiliary-input one-way function exists: a function $f(x,\cdot )$, efficiently computable given $x$, such that for all efficient $\mathcal{A}$ there are infinitely many $x$ on which $\mathcal{A}$ inverts $f(x,\cdot )$ on a uniform input with probability negligible in $|x|$ — OW93.

Notes

• The set of hard $x$ depends on $\mathcal{A}$; one set for all $\mathcal{A}$ gives a stronger notion — Vad06.
• Zero knowledge against the honest verifier suffices — OW93, GSV98; honest-verifier and general computational zero knowledge define the same class — Vad06.
• If the language is hard on average over a samplable distribution, a standard one-way function exists (Average-case-hard CZK ⇒ OWF) — OW93.
• For all of $\mathbf{NP}$ the auxiliary-input relaxation is unnecessary: a one-way function exists if and only if $\mathbf{NP}\subseteq \mathbf{CZK}$ and $\mathbf{NP}$ is hard in the worst case — HN24.