Welcome to the resource topic for 2021/517
Title:
Cryptography from Sublinear-Time Average-Case Hardness of Time-Bounded Kolmogorov Complexity
Authors: Yanyi Liu, 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.
ePrint: https://eprint.iacr.org/2021/517
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .