CryptoDB
On the Possibility of Basing Cryptography on $\EXP \neq \BPP$
| Authors: |
|
|---|---|
| Download: |
|
| Conference: | CRYPTO 2021 |
| Award: | Best Paper |
| Abstract: | Liu and Pass (FOCS'20) recently demonstrated an equivalence between the existence of one-way functions 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 let $\mktp$ denote the language of pairs $(x,k)$ having the property that $Kt(x) \leq k$. We demonstrate that: - $\mktp$ is \emph{two-sided error} mildly average-case hard (i.e., $\mktp \notin \HeurpBPP$) iff infinititely-often one-way functions exist. - $\mktp$ is \emph{errorless} mildly average-case hard (i.e., $\mktp \notin \AvgpBPP$) iff $\EXP \neq \BPP$. Thus, the only ``gap'' towards getting (infinitely-often) one-way functions 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 one-way functions, or one-way functions in $\NC^0$. |
Video from CRYPTO 2021
BibTeX
@inproceedings{crypto-2021-31170,
title={On the Possibility of Basing Cryptography on $\EXP \neq \BPP$},
publisher={Springer-Verlag},
doi={10.1007/978-3-030-84242-0_2},
author={Yanyi Liu and Rafael Pass},
year=2021
}