News for hackers. Stuff that matters.
Re:The existence of true one-way functions depends on Kolmog... by pishpash on Friday April 08, 2022 @03:48AM (#30954397)
Has this paper actually found anything meaningful or just engaged in sophistry? So instead of using a Turing machine to compute the Kolmogorov complexity where you face the halting problem and uncomputability, they use a time-bounded Turing machine to compute the time-bounded Kolmogorov complexity where you face the hardness of one-way functions.

Yes, constructing a one-way function out of a computation of Kolmogorov complexity is interesting, but frankly it would appear that it is the possible existence of one-way functions (i.e. hard computations) that is more fundamental, just like the uncomputability of the halting problem is more fundamental, not the wrapper that is Kolmogorov complexity.

There are no comments on this comment yet.