Paper 2023/1086

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

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. $$ (resp. $$) is \emph{equivalent} to the existence of OWFs secure against $$ (resp. $$) algorithms. The problem is a variant of the Minimum Time-bounded Kolmogorov Complexity problem ($$ with a threshold $$), where we condition on instances having small ``computational depth''. We furthermore show that depending on the choice of the threshold $$, this problem characterizes either ``standard'' (polynomially-hard) OWFs, or quasi polynomially- or subexponentially-hard OWFs. Additionally, when the threshold is sufficiently small (e.g., $$ or $$) 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 $$; as such, it yields the first candidate problem believed to be outside of $$, or even $$, whose worst case hardness implies the existence of OWFs.