Time bounded Kolmogorov complexity and one way functions

Question

I recently read the following article https://www.quantamagazine.org/researchers-identify-master-problem-underlying-all-cryptography-20220406/ which links to https://arxiv.org/abs/2009.11514 that proves that the existence of one way functions is equivalent to the time-bounded Kolmogorov Complexity being impossible to compute in polynomial time for a certain fraction of inputs.

But it seems to me obvious that it is impossible to compute time bounded Kolmogorov complexity K without running (or at least checking) all programs of size less than K, of which there are an exponential number (since how else would one know that a program does not output a string x in t(x) time?) so it should always take exponential time to calculate time bounded Kolmogorov complexity. This would imply that one way functions exist according to the authors.

Clearly this was not obvious to the authors of the arxiv paper or the authors of Quanta since they didn’t mention it. My question why don’t people think this is obvious?

Answer 1

While intuitively it seems correct, in cryptography you can't assume anything about the particular algorithm an opponent runs. We don't know how to prove that there's no clever way to eliminate many of these programs and remain only with a polynomial number to check.

This is similar to the problem of $P = NP$. While intuitively it makes sense that $P \neq NP$ since you would have to enumerate all exponentially many certificates, we don't know how to prove there's no clever trick which would allow solving the problem in polynomial time.