by Max Wolf
The question of whether a fundamentally unbreakable code exists in nature has always been central to cryptography. And until now, it is at the heart of all efforts to ensure the privacy of private information on the Internet.
Experts at Cornell Tech University have identified a problem that they believe is the key to understanding whether all of today’s encryption could be fundamentally violated. At the same time, these studies, important for the entire world of cryptography, were based on the conclusions of the genius Russian and Soviet mathematician Andrei Kolmogorov.
Rafael Pass, a professor of computer science at Cornell Tech, described the essence of his research: “If you can come up with an algorithm to solve Kolmogorov’s time-limited complexity problem, then you can crack all cryptocodes, all encryption schemes, all digital signatures. … However, if there is no effective algorithm for solving this problem, you can get a one-way function, and therefore get a completely secure encryption algorithm. ”
The whole research revolves around the fact that for millennia cryptography was considered a cycle: someone invented the code, that was effective until someone hacked it. In the 1970s, researchers looking for an increasingly perfect theory of cryptography introduced the concept of a one-way function – a simple but irreversible task or problem. As an example, we can cite a lighted match, which is easy to set fire to, but practically (without rearranging all its atoms to its original state) it is impossible to return to its original state.
“The idea was that the one-way function is the perfect starting point for understanding cryptography,” Pass said. “It’s very easy to encrypt a message. It remains to be done so that those who do not know the encryption key must do the impossible from a practical point of view – roughly speaking, restore an already lit match. ”
The starting point is good, but the problem is that researchers still haven’t been able to prove the existence of a one-way function. That is why, by the way, modern encryption is based not on a mathematical “lit match”, but on other, fundamentally hacked mechanisms.
Pass took the Kolmogorov complexity principle, described by mathematicians in the 1960s, as a possible natural basis for cryptography. The Kolmogorov complexity of a string of numbers is defined as the length (in binary alphabet) of the shortest computer program that can generate a string. According to Pass, his research not only shows that cryptography is fundamentally based on some basic principle, but also demonstrates a deep connection between two completely separate areas of mathematics and computer science – cryptography and algorithmic information theory.
The study was funded in part by the National Science Foundation and the United States Air Force’s Office of Scientific Research, and was based on programs carried out through National Intelligence research projects.
Open source
