The fundamental theorem of Goldreich, Micali, and Wigderson (J. ACM 1991) shows that the existence of a one-way function is sufficient for constructing computational zero knowledge ($\mathrm{CZK}$) proofs for all languages in $\mathrm{NP}$. We prove its converse, thereby establishing characterizations of one-way functions based on the worst-case complexities of zero knowledge. Specifically, we prove that the following are equivalent:

- A one-way function exists.
- $\mathrm{NP} \subseteq \mathrm{CZK}$ and $\mathrm{NP}$ is hard in the worst case.
- $\mathrm{CZK}$ is hard in the worst case and the problem $\mathrm{GapMCSP}$ of approximating circuit complexity is in $\mathrm{CZK}$.

The characterization above also holds for statistical and computational zero-knowledge argument systems. We further extend this characterization to a proof system with knowledge complexity $O(\log n)$. In particular, we show that the existence of a one-way function is characterized by the worst-case hardness of $\mathrm{CZK}$ if $\mathrm{GapMCSP}$ has a proof system with knowledge complexity $O(\log n)$. We complement this result by showing that $\mathrm{NP}$ admits an interactive proof system with knowledge complexity $\omega(\log n)$ under the existence of an exponentially hard auxiliary-input one-way function (which is a weaker primitive than an exponentially hard one-way function). We also characterize the existence of a robustly-often nonuniformly computable one-way function by the nondeterministic hardness of $\mathrm{CZK}$ under the weak assumption that $\mathrm{PSPACE} \not\subseteq \mathrm{AM}$.

We present two applications of our results. First, we simplify the proof of the recent characterization of a one-way function by $\mathrm{NP}$-hardness of a meta-computational problem and the worst-case hardness of $\mathrm{NP}$ given by Hirahara (STOC'23). Second, we show that if $\mathrm{NP}$ has a laconic zero-knowledge argument system, then there exists a public-key encryption scheme whose security can be based on the worst-case hardness of $\mathrm{NP}$. This improves previous results which assume the existence of an indistinguishable obfuscation.