Paper 2021/517

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

Yanyi Liu and Rafael Pass

Abstract

Let $$ be the set of strings $$ such that $$, where $$ denotes the $$-bounded Kolmogorov complexity of the truthtable described by $$. Our main theorem shows that for an appropriate notion of mild average-case hardness, for every $$, polynomial $$, and every ``nice'' class $$ of super-polynomial functions, the following are equivalent: - the existence of some function $$ such that $$-hard one-way functions (OWF) exists (with non-uniform security); - the existence of some function $$ such that $$ is mildly average-case hard with respect to sublinear-time non-uniform algorithms (with running-time $$ for some $$). For instance, existence of subexponentially-hard (resp. quasi-polynomially-hard) OWFs is equivalent to mild average-case hardness of $$ (resp. $$) w.r.t. sublinear-time non-uniform algorithms. We additionally note that if we want to deduce $$-hard OWFs where security holds w.r.t. uniform $$-time probabilistic attackers (i.e., uniformly-secure OWFs), it suffices to assume sublinear time hardness of $$ 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: $$ is worst-case hard w.r.t. uniform probabilistic sublinear-time algorithms, and $$ is mildly average-case hard for all $$-time deterministic algorithms.