Welcome to the resource topic for
**2023/1086**

**Title:**

On One-way Functions and the Worst-case Hardness of Time-Bounded Kolmogorov Complexity

**Authors:**
Yanyi Liu, Rafael Pass

**Abstract:**

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.

**ePrint:**
https://eprint.iacr.org/2023/1086

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .