One-Way Functions and Boundary Hardness of Randomized Time-Bounded Kolmogorov Complexity

We revisit the question of whether worst-case hardness of the time-bounded Kolmogorov complexity problem, MINKᵖᵒˡʸ - that is, determining whether a string is "structured" (i.e., K^t(x) < n-1) or "random" (i.e., Kᵖᵒˡʸ⁽ᵗ⁾ ≥ n-1) - suffices to imply the existence of one-way functions (OWF). Liu-Pass (CRYPTO'25) recently showed that worst-case hardness of a boundary version of MINKᵖᵒˡʸ - where, roughly speaking, the goal is to decide whether given an instance x, (a) x is K^poly-random (i.e., Kᵖᵒˡʸ⁽ᵗ⁾(x) ≥ n-1), or just close to K^poly-random (i.e., Kᵗ(x) < n-1 but Kᵖᵒˡʸ⁽ᵗ⁾ > n - log n) - characterizes OWF, but with either of the following caveats (1) considering a non-standard notion of probabilistic K^t, as opposed to the standard notion of K^t, or (2) assuming somewhat strong, and non-standard, derandomization assumptions. In this paper, we present an alternative method for establishing their result which enables significantly weakening the caveats. First, we show that boundary hardness of the more standard randomized K^t problem suffices (where randomized K^t(x) is defined just like K^t(x) except that the program generating the string x may be randomized). As a consequence of this result, we can provide a characterization also in terms of just "plain" K^t under the most standard derandomization assumption (used to derandomize just BPP into P) - namely E ̸ ⊆ ioSIZE[2ᵒ⁽ⁿ⁾]. Our proof relies on language compression schemes of Goldberg-Sipser (STOC'85); using the same technique, we also present the the first worst-case to average-case reduction for the exact MINKᵖᵒˡʸ problem (under the same standard derandomization assumption), improving upon Hirahara’s celebrated results (STOC'18, STOC'21) that only applied to a gap version of the MINKᵖᵒˡʸ problem, referred to as GapMINKᵖᵒˡʸ, where the goal is to decide whether K^t(x) ≤ n-O(log n)) or Kᵖᵒˡʸ⁽ᵗ⁾(x) ≥ n-1 and under the same derandomization assumption.