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 .