Whether one-way functions (OWF) exist is arguably the most important
problem in Cryptography, and beyond. While lots of candidate
constructions of one-way functions are known, and recently also
problems whose average-case hardness characterize the existence of
OWFs have been demonstrated, the question of
whether there exists some \emph{worst-case hard problem} that characterizes
the existence of one-way functions has remained open since their
introduction in 1976.

In this work, we present the first ``OWF-complete'' promise
problem---a promise problem whose worst-case hardness w.r.t. \BPP
(resp. \Ppoly) is \emph{equivalent} to the existence of OWFs secure
against \PPT (resp. \nuPPT) algorithms. The problem is a
variant of the Minimum Time-bounded Kolmogorov Complexity
problem (\mktp[s] with a threshold s), where we condition on
instances having small ``computational depth''.

We furthermore show that depending on the choice of the
threshold s, this problem characterizes either ``standard''
(polynomially-hard) OWFs, or quasi polynomially- or
subexponentially-hard OWFs. Additionally, when the threshold is
sufficiently small (e.g., 2^{O(\sqrt{n})} or \poly\log n) then
\emph{sublinear} hardness of this problem suffices to characterize
quasi-polynomial/sub-exponential OWFs.

While our constructions are black-box, our analysis is \emph{non-
black box}; we additionally demonstrate that fully black-box constructions
of OWF from the worst-case hardness of this problem are impossible.
We finally show that, under Rudich's conjecture, and standard derandomization
assumptions, our problem is not inside \coAM; as such, it
yields the first candidate problem believed to be outside of \AM \cap \coAM,
or even {\bf SZK}, whose worst case hardness implies the existence of OWFs.

Whether one-way functions (OWF) exist is arguably the most important
problem in Cryptography, and beyond. While lots of candidate
constructions of one-way functions are known, and recently also
problems whose average-case hardness characterize the existence of
OWFs have been demonstrated, the question of
whether there exists some \emph{worst-case hard problem} that characterizes
the existence of one-way functions has remained open since their
introduction in 1976.

In this work, we present the first ``OWF-complete'' promise
problem---a promise problem whose worst-case hardness w.r.t. \BPP
(resp. \Ppoly) is \emph{equivalent} to the existence of OWFs secure
against \PPT (resp. \nuPPT) algorithms. The problem is a
variant of the Minimum Time-bounded Kolmogorov Complexity
problem (\mktp[s] with a threshold s), where we condition on
instances having small ``computational depth''.

We furthermore show that depending on the choice of the
threshold s, this problem characterizes either ``standard''
(polynomially-hard) OWFs, or quasi polynomially- or
subexponentially-hard OWFs. Additionally, when the threshold is
sufficiently small (e.g., 2^{O(\sqrt{n})} or \poly\log n) then
\emph{sublinear} hardness of this problem suffices to characterize
quasi-polynomial/sub-exponential OWFs.

While our constructions are black-box, our analysis is \emph{non-
black box}; we additionally demonstrate that fully black-box constructions
of OWF from the worst-case hardness of this problem are impossible.
We finally show that, under Rudich's conjecture, and standard derandomization
assumptions, our problem is not inside \coAM; as such, it
yields the first candidate problem believed to be outside of \AM \cap \coAM,
or even {\bf SZK}, whose worst case hardness implies the existence of OWFs.