Hardness of KT Characterizes Parallel Cryptography
Hanlin Ren and Rahul Santhanam
Abstract
A recent breakthrough of Liu and Pass (FOCS'20) shows that one-way functions exist if and only if the (polynomial-)time-bounded Kolmogorov complexity, , is bounded-error hard on average to compute. In this paper, we strengthen this result and extend it to other complexity measures:
* We show, perhaps surprisingly, that the complexity is bounded-error average-case hard if and only if there exist one-way functions in *constant parallel time* (i.e., ). This result crucially relies on the idea of *randomized encodings*. Previously, a seminal work of Applebaum, Ishai, and Kushilevitz (FOCS'04; SICOMP'06) used the same idea to show that -computable one-way functions exist if and only if logspace-computable one-way functions exist.
* Inspired by the above result, we present randomized average-case reductions among the -versions and logspace-versions of complexity, and the complexity. Our reductions preserve both bounded-error average-case hardness and zero-error average-case hardness. To the best of our knowledge, this is the first reduction between the complexity and a variant of complexity.
* We prove tight connections between the hardness of complexity and the hardness of (the hardest) one-way functions. In analogy with the Exponential-Time Hypothesis and its variants, we define and motivate the *Perebor Hypotheses* for complexity measures such as and . We show that a Strong Perebor Hypothesis for implies the existence of (weak) one-way functions of near-optimal hardness . To the best of our knowledge, this is the first construction of one-way functions of near-optimal hardness based on a natural complexity assumption about a search problem.
* We show that a Weak Perebor Hypothesis for implies the existence of one-way functions, and establish a partial converse. This is the first unconditional construction of one-way functions from the hardness of over a natural distribution.
* Finally, we study the average-case hardness of . We show that it characterizes cryptographic pseudorandomness in one natural regime of parameters, and complexity-theoretic pseudorandomness in another natural regime.