1970-01-01

(2026-04) Cryptographic Implications of Worst-Case Hardness of Time-Bounded Kolmogorov Complexity

[[Yanyi Liu]]
[[Noam Mazor]]
[[Rafael Pass]]

2026-04-06

Abstract

We consider the worst-case hardness of the gap version of the classic time-bounded Kolmogorov complexity problem— $Gap_pMK^tP[s_1,s_2]$ —where the goal is to determine whether for a given string x, $K^t(x) ≤s_1(n)$ or $K^{p(t)}(x) > s_2(n)$ , where $K^t(x)$ denotes the t-bounded Kolmogorov complexity of x. As shown by Hirahara (STOC’18), if $Gap_pMK^tP[s_1,s_2] \notin prBPP$ for every polynomial p, then (under appropriate derandomization assumption) $Gap_pMK^tP$ is errorless average-case hard with respect to BPP heuristics. The notion of errorless average-case hardness, however, is seemingly insufficient for cryptographic applications where one needs to consider average-case hardness against attacks that simply may err with some probability (i.e., two-sided error hardness).

In this work, we present several new consequences of the assumption that $Gap_pMK^tP[s_1,s_2]\notin P/poly$ for all polynomials p, for appropriate choices of $s_1$ , $s_2$ , and under appropriate (worst-case) derandomization assumptions. In particular, we show that this assumption implies:

The existence of an (inefficient-prover) zero-knowledge proof system for NP with a non-uniform simulator w.r.t. adversaries with a-priori bounded-length auxiliary-input.
The existence of a hard disjoint NP pair, defined as a promise problem $(Y,N)$ where both $Y,N\in NP$ ; this provides a barrier towards showing that $Gap_pMK^tP$ is NP-complete.

The above results are proven via first showing that the above assumption implies the existence of a so-called conditional PRG—roughly speaking, a cryptographic PRG where indistinguishability only needs to hold for some (potentially not efficiently sampleable) distribution over the seed to the PRG. (In fact, this notion of a PRG also almost directly implies average-case hardness of $Gap_pMK^tP$ , and as such, this provides a modular explanation to Hirahara’s results.) Finally, we show that for the results on conditional PRGs and Zero-knowledge Proofs, unconditional results can be obtained (that is, without making any derandomization assumptions), if considering an appropriate version of $Gap_pMK^tP$ concerning randomized $K^t$ .