Paper 2021/535

On the Possibility of Basing Cryptography on $$

Yanyi Liu and Rafael Pass

Abstract

Liu and Pass (FOCS'20) recently demonstrated an equivalence between the existence of one-way functions (OWFs) and mild average-case hardness of the time-bounded Kolmogorov complexity problem. In this work, we establish a similar equivalence but to a different form of time-bounded Kolmogorov Complexity---namely, Levin's notion of Kolmogorov Complexity---whose hardness is closely related to the problem of whether $$. In more detail, let $$ denote the Levin-Kolmogorov Complexity of the string $$; that is, $$, where $$ is a universal Turing machine, and $$ denotes the output of the program $$ after $$ steps, and let $$ denote the language of pairs $$ having the property that $$. We demonstrate that: - $$ (i.e., $$ is infinitely-often \emph{two-sided error} mildly average-case hard) iff infinititely-often OWFs exist. - $$ (i.e., $$ is infinitely-often \emph{errorless} mildly average-case hard) iff $$. Thus, the only ``gap'' towards getting (infinitely-often) OWFs from the assumption that $$ is the seemingly ``minor'' technical gap between two-sided error and errorless average-case hardness of the $$ problem. As a corollary of this result, we additionally demonstrate that any reduction from errorless to two-sided error average-case hardness for $$ implies (unconditionally) that $$. We finally consider other alternative notions of Kolmogorov complexity---including space-bounded Kolmogorov complexity and conditional Kolmogorov complexity---and show how average-case hardness of problems related to them characterize log-space computable OWFs, or OWFs in $$.