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.