ECCC-Report TR21-055https://eccc.weizmann.ac.il/report/2021/055Comments and Revisions published for TR21-055en-usTue, 20 Apr 2021 14:36:21 +0300
Paper TR21-055
| Cryptography from Sublinear-Time Average-Case Hardness of Time-Bounded Kolmogorov Complexity |
Yanyi Liu,
Rafael Pass
https://eccc.weizmann.ac.il/report/2021/055Let $\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. \emph{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.Tue, 20 Apr 2021 14:36:21 +0300https://eccc.weizmann.ac.il/report/2021/055