Now our understanding of our search for meaning is starting to come together. We abhor randomness and love patterns. We are biologically programmed to find some patterns that explain what they see. But we can never be certain that the pattern we’ve identified is the right one. Even if we could somehow be assured that we haven’t made a mistake, and we are exhibiting a computer-like perfection, there may always still be a deeper truth to unearth. This tension helps drive our love of literature, theater, and the cinema. When we read a novel, or watch a play, the author or director is presenting us with a sequence of events that has a common theme, pattern, or moral. Literature, plays, and the cinema offer us a delightful escape from the usual unintelligible, meaningless chaos that we find in the real world around us. Really good literature goes further, and leaves us with the possibility of many interpretations. We come face to face with the incomputability of the Kolmogorov complexity.
Since time-bounded Kolmogorov complexity is computable, a natural next question is how hard it is to compute. And this is the question that Liu and Pass proved holds the key to whether one-way functions exist. Suppose you’ve set your sights on a less lofty goal than calculating the exact time-bounded Kolmogorov complexity of every possible string — suppose you’re content to calculate it approximately, and just for most strings. If there’s an efficient way to do this, then true 1-way functions cannot exist. In that case, all our candidate 1-way functions would be instantly breakable, not just in theory but in practice. “Bye-bye to cryptography”.
Conversely, if calculating the approximate time-bounded Kolmogorov complexity is too hard to solve efficiently for many strings, then true 1-way functions must exist. If that’s the case, their paper even provides a specific way to make one. The 1-way function that they describe in their paper is too complicated to use in real-world applications, but in cryptography, practical constructions often quickly follow a theoretical breakthrough. And if their function can be made practical, it should be used in preference to the candidate 1-way functions based on multiplication and other mathematical operations.
Gregor J. Rothfuss 