Will technology security implode? A discussion on P vs NP.
We log into bank accounts without any concern. We send emails with confidence that our data is protected. And we share personal texts, all over internet communication that we trust is secure. But what if it was proved the cryptographic protocols protecting these communications can be hacked efficiently?
P vs NP is a foundational question in theoretical computer science. The answer to this problem has immense implications. It may redefine problems computers can or cannot solve. It may strengthen our cryptographic systems - or cripple them entirely.
You might be wondering: what do P and NP even stand for? And how can society be relying on things we do not know are secure? If intrigued, keep reading - we’ll get into this and more below.
What is P? And NP?
Algorithms can be classified as efficient or inefficient. P and NP provide more formal definitions around these concepts. P represents the class of problems that a computer can solve efficiently, while NP represents the class of problems that a computer can verify efficiently.
Verifying differs from solving a problem in that we receive additional information when we verify a problem. This additional information is a proposed solution which we verify is in fact a valid solution to the problem at hand. P=NP investigates whether or not this additional information differentiates problems we can solve efficiently from those we cannot.
What does it mean for P to equal NP?
If P=NP, then any problem that can be verified efficiently can also be solved efficiently. This classification is visualized below.
Although this may not seem very groundbreaking, the solution to whether P=NP will have immense societal impact. One area that will be significantly impacted is public-key cryptography.
How does P=NP affect cryptographic systems?
Many cryptographic protocols rely on problems that can be verified efficiently, with the assumption that they cannot be efficiently solved for. If P=NP, then algorithms exist that can efficiently solve the problems used to protect some cryptographic protocols. It is just a matter of finding the algorithm.
There exists a group of problems that we know are in NP, but we have not yet proved or disproved are in P. Public-key cryptography relies on the assumption that these problems cannot be solved for efficiently.
We will take a look at the implications of P=NP for one of the most widely used cryptographic protocols today: RSA.
In the case of RSA, it relies on the difficulty of large integer factorization. The large integer factorization problem is whether a and b can be found given some c where c=a*b. Note that a, b, and c are all integers.
We can walk through some examples to make the difficulty of this problem more clear. Given c=27, we can conclude that a possible solution is a=9 and b=3. But what about c=851? It is a little more difficult to see a=23 and b=37. And for c=61423? Well, I think we would need to break out a pen and paper.
Currently, we do not have an efficient algorithm to find a and b given c. Therefore we cannot concretely say large integer factorization is or is not in the class P.
However, the problem is in the class NP. Given a, b and c, we are able to efficiently verify a*b=c by computing a*b and comparing it to c. In the prior example, given a=23, b=37 and c=61423, we can easily verify 23*37 does in fact equal 61423.
RSA is just one example of a commonly used security protocol that relies on a problem in NP, and may or may not be in P.
Conclusion
So what are the repercussions if P=NP? Ultimately, much of our digital security would crumble. Internet communications that are currently considered secure could be intercepted and efficiently decoded by adversaries. Public-key cryptography relies on the assumption that P does not equal NP, a pretty steep bet to take when many theoretical computer scientists and mathematicians suspect they may in fact be equal.
Curious to investigate this further? Here are some resources you may find interesting: