Summary: A recent breakthrough of Y. Liu and R. Pass [in: Proc. 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 1243–1254, 2020. doi:10.1109/FOCS46700.2020.00118] shows that one-way functions exist if and only if the (polynomial-)time-bounded Kolmogorov complexity, \(K^t\), 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 KT complexity is bounded-error average-case hard if and only if there exist one-way functions in constant parallel time (i.e. NC\(^0\)). This result crucially relies on the idea of randomized encodings. Previously, a seminal work of textit{B. Applebaum} et al. [SIAM J. Comput. 36, No. 4, 845–888 (2006; Zbl 1126.94014); FOCS’04] used the same idea to show that NC\(^0\)-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 NC\(^1\)-versions and logspace-versions of \(K^t\) complexity, and the KT 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 KT complexity and a variant of \(K^t\) complexity.

–

We prove tight connections between the hardness of \(K^t\) 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 \(K^t\) and KT. We show that a Strong Perebor Hypothesis for \(K^t\) implies the existence of (weak) one-way functions of near-optimal hardness \(2^{n-o(n)}\). 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 MCSP 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 MCSP over a natural distribution.

–

Finally, we study the average-case hardness of MKtP. We show that it characterizes cryptographic pseudorandomness in one natural regime of parameters, and complexity-theoretic pseudorandomness in another natural regime.

For the entire collection see [Zbl 1465.68023].