**Cryptography from Sublinear-Time Average-Case Hardness of Time-Bounded Kolmogorov Complexity**

*Yanyi Liu and Rafael Pass*

**Abstract: **Let $\mktp[s]$ be the set of strings $x$ such that $K^t(x) \leq s(|x|)$, where $K^t(x)$ denotes the $t$-bounded Kolmogorov complexity of the truthtable described by $x$. Our main theorem shows that for an appropriate notion of mild average-case hardness, for every $\varepsilon>0$, polynomial $t(n) \geq (1+\varepsilon)n$, and every ``nice'' class $\F$ of super-polynomial functions, the following are equivalent:
- the existence of some function $T \in \F$ such that $T$-hard one-way functions (OWF) exists (with non-uniform security);
- the existence of some function $T \in \F$ such that $\mktp[T^{-1}]$ is mildly average-case hard with respect to sublinear-time non-uniform algorithms (with running-time $n^{\delta}$ for some $0<\delta<1$).
For instance, existence of subexponentially-hard (resp. quasi-polynomially-hard) OWFs is equivalent to mild average-case hardness of $\mktp[\poly\log n]$ (resp. $\mktp[2^{O(\sqrt{\log n})})]$) w.r.t. sublinear-time non-uniform algorithms.

We additionally note that if we want to deduce $T$-hard OWFs where security holds w.r.t. uniform $T$-time probabilistic attackers (i.e., uniformly-secure OWFs), it suffices to assume sublinear time hardness of $\mktp$ w.r.t. uniform probabilistic sublinear-time attackers. We complement this result by proving lower bounds that come surprisingly close to what is required to unconditionally deduce the existence of (uniformly-secure) OWFs: $\mktp[\poly\log n]$ is worst-case hard w.r.t. uniform probabilistic sublinear-time algorithms, and $\mktp[n-\log n]$ is mildly average-case hard for all $O(t(n)/n^3)$-time deterministic algorithms.

**Category / Keywords: **foundations / one-way functions, Kolmogorov complexity, average-case complexity

**Original Publication**** (with minor differences): **On https://eccc.weizmann.ac.il/. In STOC 2021.
**DOI: **10.1145/3406325.3451121

**Date: **received 19 Apr 2021

**Contact author: **yl2866 at cornell edu,rafael@cs cornell edu

**Available format(s): **PDF | BibTeX Citation

**Version: **20210423:122203 (All versions of this report)

**Short URL: **ia.cr/2021/517

[ Cryptology ePrint archive ]