Paper 2021/517

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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Minor revision. On https://eccc.weizmann.ac.il/. In STOC 2021.
DOI
10.1145/3406325.3451121
Keywords
one-way functionsKolmogorov complexityaverage-case complexity
Contact author(s)
yl2866 @ cornell edu
rafael @ cs cornell edu
History
2021-04-23: received
Short URL
https://ia.cr/2021/517
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/517,
      author = {Yanyi Liu and Rafael Pass},
      title = {Cryptography from Sublinear-Time Average-Case Hardness of Time-Bounded Kolmogorov Complexity},
      howpublished = {Cryptology ePrint Archive, Paper 2021/517},
      year = {2021},
      doi = {10.1145/3406325.3451121},
      note = {\url{https://eprint.iacr.org/2021/517}},
      url = {https://eprint.iacr.org/2021/517}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.