Paper 2021/535

On the Possibility of Basing Cryptography on $\EXP \neq \BPP$

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 $\EXP \neq \BPP$. In more detail, let $Kt(x)$ denote the Levin-Kolmogorov Complexity of the string $x$; that is, $Kt(x) = \min_{\desc \in \bitset^*, t \in \N}\{|\desc| + \lceil \log t \rceil: U(\desc, 1^t) = x\}$, where $U$ is a universal Turing machine, and $U(\desc,1^t)$ denotes the output of the program $\Pi$ after $t$ steps, and let $\mktp$ denote the language of pairs $(x,k)$ having the property that $Kt(x) \leq k$. We demonstrate that: - $\mktp \notin \HeurpBPP$ (i.e., $\mktp$ is infinitely-often \emph{two-sided error} mildly average-case hard) iff infinititely-often OWFs exist. - $\mktp \notin \AvgpBPP$ (i.e., $\mktp$ is infinitely-often \emph{errorless} mildly average-case hard) iff $\EXP \neq \BPP$. Thus, the only ``gap'' towards getting (infinitely-often) OWFs from the assumption that $\EXP \neq \BPP$ is the seemingly ``minor'' technical gap between two-sided error and errorless average-case hardness of the $\mktp$ problem. As a corollary of this result, we additionally demonstrate that any reduction from errorless to two-sided error average-case hardness for $\mktp$ implies (unconditionally) that $\NP \neq \P$. 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 $\NC^0$.