Is it easier to check that the solution to a problem is correct than the solution to the problem?
The question – known as the “NP vs. P” problem – is the deepest fundamental problem in computer science and cryptography, which lies at the heart of whether any data on the Internet can be truly private.
In the unlikely event that P = NP, all encryption schemes and methods of keeping our data private online would be insecure. But even if P is not equal to NP, and even if someone manages to prove it, we still do not know how to get an encryption scheme that is really secure.
Rafael Pass, professor of computer science at Cornell Tech and Cornell Ann S. Bowers College of Computing and Information Science, and co-author Yanyi Liu, a doctoral student in computer science, have offered a one-of-a-kind solution.
Their work is detailed in “On the Possibility of Cryptography Based on EXP ≠ BPP”, which won the Best Paper award at CRYPTO ’21 and will be presented at the conference on 17 August.
The question posed in the title of the paper deals with the idea of chance, a prickly computer science, and mathematical questions. The EXP versus BPP problem – though not as popular as the “NP versus P” problem – is another long-standing problem, and the cause for even more embarrassment in this area, according to Pass.
“The question is essentially, can coincidence exponentially accelerate calculations?” Tha Pass. “It is clearly believed that this is impossible. We would not think that just tossing a few random coins will allow us to speed up our calculations exponentially. That would be madness, but people have not yet been able to prove it. “
If calculations can be exponentially accelerated using randomness, then all encryption schemes can be broken. The so-called “brutal” attacks, in which all possible keys are counted, can now be effectively implemented.
Pass and Liu address the question of whether simply assuming that EXP is not equal to BPP – that calculations cannot be exponentially accelerated using randomness – is enough to obtain unbreakable encryption schemes. For this, Pass and Liu review a link between the Kolmogorov-encrypted schemes and time-limited complexity they created last year.
The complexity of the time-limited Kolmogorov string (x) is the length of the shortest program that can output x at a given time. But the new work considers another notion of Kolmogorov complexity: the calculation of the “Levin-Kolmogorov complexity” of a string (x). Problem: Given x, find the “most efficient” program that prints x, where “efficiency” is the sum of the program length and the logarithm of the program’s running time.
Their work shows that unbreakable encryption is possible if and only if there is no efficient algorithm that can calculate the Levin-Kolmogorov Complexity for most arrays without making many mistakes.
“So to get an unbreakable encryption,” Pass said, “we just have to show that no efficient algorithm can solve this particular problem.”
While they are unable to prove that such an algorithm does not exist, they show that assuming EXP is not equal to BPP, there is no efficient “error-free” algorithm (an algorithm that either produces the correct answer or says “I do not know”) for determining the Levin-Kolmogorov Complexity of a large fraction of random strings.
“He doesn’t have to fix it for all the wires – he can give up sometimes,” Pass said. “But when you give an answer, it always has to be the right one.”
In other words, erroneous algorithms do well in tests where you are rewarded based on the number of questions you get right, while error-free algorithms do well in tests where you are penalized for wrong questions.
Their results conclude that the Levin-Kolmogorov Complexity problem is central to understanding both the EXP versus BPP problem and the problem of whether there are unbreakable encryption schemes.
“This problem holds the key to some of the most important questions in computer science,” Pass said. “This specific problem is fundamental and we really need to understand the gap between error-free algorithms and algorithms that can err.”
The authors show that if the gap can be closed – a “if” giant in computer science – then you have not only proved that unbreakable cryptography exists if EXP is not equal to BPP, but in fact you have also proved that POE is not equal to P.
This work was supported by grants from the National Science Foundation, the Air Force Scientific Research Office, the JP Morgan Faculty Award, and the Defense Advanced Research Projects Agency.