Revision #1 Authors: Yanyi Liu, Rafael Pass

Accepted on: 5th September 2023 10:50

Downloads: 185

Keywords:

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.