Paper 2021/535

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

Yanyi Liu and Rafael Pass


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$.

Available format(s)
Publication info
Published elsewhere. Minor revision. On Submitted to Crypto'21
one-way functionsKolmogorov complexityaverage-case complexity
Contact author(s)
yl2866 @ cornell edu
rafael @ cs cornell edu
2021-04-23: received
Short URL
Creative Commons Attribution


      author = {Yanyi Liu and Rafael Pass},
      title = {On the Possibility of Basing Cryptography on $\EXP \neq \BPP$},
      howpublished = {Cryptology ePrint Archive, Paper 2021/535},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.