However, the Kolmogorov complexity has a significant disadvantage: it cannot be calculated. That is, there is no algorithm that can calculate the complexity of every possible sequence. Fortunately, there is a weaker version of the idea that is quite predictable. The “time-limited” Kolmogorov complexity does not necessarily specify the shortest program that produces a string, but it does specify the shortest that is efficient. Because the shortest algorithm could possibly need millions of years to find the description of a sequence. Such cases are excluded in the weakened version.
One can thus determine the time-limited Kolmogorov complexity for any sequence of numbers. Now the question typical of computer science arises: how easy is it to calculate the complexity? As Liu and Pass found, this is the key to proving the existence of one-way functions.
In fact, the task does not have to be quite so rigorous: it suffices to deal with the time-limited complexity by approximation (one does not demand exact precision) – and one only wants to determine it for most strings. If there is an efficient way to do this, then no true one-way functions exist, as Liu and Pass have shown. And all candidates for irreversible functions would be quickly crackable not only in theory but also in practice. With this, there could be no secure cryptography.
According to Pass and Liu, however, in the opposite scenario, true one-way functions exist: when it is impossible to efficiently compute the approximate time-limited Kolmogorov complexity for many sequences of numbers. In this case, the two computer scientists even provide instructions on how to create an irreversible mapping. In its current form, however, it would be too complicated to be used in real applications. But as Ishai points out, a theoretical breakthrough in cryptography is often followed by practical constructions. Therefore, according to Ishai, the complex derivation of the one-way function of Liu and Pass is not a fundamental constraint.
If the two computer scientists’ approach can actually be simplified, it should be preferred to functions based on multiplication and other mathematical operations. Because with the latter it is not guaranteed that they are really irreversible.
The paper by Pass and Liu has triggered a veritable flood of research at the interface between cryptography and complexity theory. Although both disciplines have the same goal, they approach the question from different points of view, explains the complexity theorist Rahul Santhanam from the University of Oxford. Cryptography is fast-moving and pragmatic, complexity theory is rather slow and conservative.
Each area offers a fresh perspective on the other: cryptographers have good reason to believe that one-way functions exist; at the same time, there is some evidence for complexity theorists that the time-limited Kolmogorov complexity is difficult to determine. With the new results from Liu and Pass, the two hypotheses now support each other. Nonetheless, experts continue to investigate whether there are other “key problems” besides Kolmogorov complexity that could account for irreversible functions. This would perhaps bring you a little closer to the dream of absolutely secure communication.
In which cryptographic world do we live?
In 1995, the computer scientist Russell Impagliazzo from the University of California, San Diego, dealt with the different cryptographic possibilities that a world can offer. To summarize his findings, Impagliazzo described five universes, which he imaginatively named Algorithmica, Heuristica, Pessiland, Minicrypt, and Cryptomania. In them, mathematical problems have different degrees of difficulty and scope of application, which are suitable for encryption methods. Every single universe described could be the world we live in. Which one we actually inhabit is still unclear.
Algorithmica
In this world, all arithmetic tasks are simple, which makes cryptography impossible. This means that the set of problems with efficient solutions – referred to as “P” in computer science – not only contains the previously known tasks that we can calculate quickly. Rather, P in this universe also includes all NP problems; those are the ones whose results are easy to verify if someone supplies them. Among other things, this category includes tasks that are currently difficult to solve.
At first glance, P and NP appear very different: Although the solution to an efficiently solvable problem can be verified quickly (P is therefore part of NP), the reverse is not always the case. An example of this is packing a suitcase. If someone else fills it, it’s easy to make sure everything fits. You just have to check if something has been forgotten. So this is an NP problem. But packing the bag yourself is much more difficult, especially if you have a lot to store: you may have to try numerous arrangements before it works. It is not currently clear whether there is an efficient algorithm that can do this for all possible combinations of items and suitcases. So we don’t know if the problem is in P.
In Algorithmica, P and NP are the same, that is, they contain the same problems. If that were actually the case, a veritable gold mine would have been discovered. Because it would follow that there are fast algorithms that solve difficult problems like packing suitcases and many other complex examples from NP. That would make numerous applications easier – but for cryptographers it would be a disaster. Because another element of NP is the decryption of cryptographic processes: If someone claims to have cracked an encrypted message, one can easily check whether the decrypted text matches the original.
The prevailing notion in computer science is that P and NP are different for the simple reason that there are so many problems in NP that, despite years of tedious effort, cannot be solved efficiently. So far, no one has been able to prove or disprove this. In fact, “P versus NP” has been considered the most famous question in theoretical computer science for more than five decades. It is one of the seven Millennium Problems for which the Clay Mathematics Institute offered a $1 million reward in 2000. “However, apart from the constant failure of the brightest minds, there is no evidence that ‘P versus NP’ is difficult to crack,” says Yuval Ishai of the Technion in Haifa, Israel.
heuristics
In this world there are NP problems that are not easy to solve, that is, in general P ≠ NP. Nevertheless, most problems from NP can be calculated efficiently, at least on average. For example, in Heuristica, there might be a fast suitcase-packing algorithm that almost always works. The calculation rule would only fail for a few combinations of containers and objects. Such efficient and usually successful algorithms are commonly referred to as “heuristics”, from which the name of the universe is derived.
From a cryptographic point of view, there is not much difference to Algorithmica. If you think up an encryption method in Heuristica, there is a fast decryption method that can handle almost any message. This renders cryptography useless for practical purposes in this scenario.
Pessilland
In fact, this world is the worst of all possible options from a computational point of view. Because in Pessiland some problems in NP are of average difficulty, but they do not allow one-way functions that are necessary for cryptography.
These are mathematical mappings that are easy to execute (this is how you create encryption), but cannot be reversed (decrypted). Computer scientists have shown that secure encryption requires one-way functions.
In this universe, any efficient algorithm fails not just occasionally—as in Heuristica—but almost always. On the other hand, you cannot construct functions to hide secret information from the averagely difficult tasks. “We definitely don’t want to live in Pessiland,” says Eric Allender of Rutgers University. “Here you have all the disadvantages of high complexity, but none of the advantages of it, such as cryptography.”
minicrypt
In that world, some NP problems are of average difficulty, while some lend themselves to creating the most fundamental building block of cryptography: a one-way function. This enables cryptographic procedures with secret keys; digital signatures that ensure an individual’s identity; and pseudo-random number generators.
“The existence of one-way functions is undoubtedly the most important problem in cryptography,” says Rafael Pass of Cornell University. “If we don’t have them, all these things can be broken.”
Cryptomania
The universe in this scenario offers enough complexity to enable all applications in Minicrypt – and even more advanced cryptographic protocols. Cryptomania can also be used to encrypt using public key methods (which allow encrypted messages to be sent without knowing the secret key), which are essential in the digital age.
According to Yuval Ishai, most computer scientists are convinced that cryptography exists at least partially in our world. So we most likely live in Cryptomania or Minicrypt. However, definitive proof is still a long way off. Because for that you would have to exclude the other three worlds – and just to eliminate Algorithmica, you have to solve the “P versus NP” problem, which theoretical computer science has been grappling with unsuccessfully for decades.
However, in 2020, Rafael Pass and his graduate student Yanyi Liu found a new approach to explore the possible cryptographic universes. They were able to show that the time-limited Kolmogorov complexity clearly separates worlds with and without cryptography.
If the above complexity is easy to calculate on average, according to Liu and Pass, there is no such thing as secure encryption. So in this case we are in Algorithmica, Heuristica or Pessiland. On the other hand, if the task is difficult to solve on average, one-way functions can be constructed – we would then at least be in Minicrypt and possibly even in Cryptomania.
Another effort could use the new results to completely rule out Pessiland – the worst of all worlds. This would require proving that the average simplicity of the time-limited Kolmogorov complexity carries over to all other problems in NP. Then only four possible universes remained: those in which cryptography is possible (Minicrypt and Cryptomania), and those in which every problem in NP is easy on average (Algorithmica and Heuristica).
Computer scientists would also like to get rid of heuristics. Because if the time-limited Kolmogorov complexity is average easy, then every NP problem would always be easy to solve in Heuristica—not just on average.
So if both worlds could be eliminated, we would either be living in Algorithmica, where everything is always simple, or there would be enough complexity to allow at least basic cryptography.
SOURCE: Impagliazzo, R.: A personal view of average-case complexity. Proceedings of Structure in Complexity Theory. 10th Annual IEEE Conference, 1995