P=NP: The Ticking Bomb of Cyber Security, or Another false alarm?
If it is difficult for us, is it also difficult for God? That’s what cyber security is built on
Bitcoin, Etherium, blockchain, eCommerce, and the public cyber square in general are founded on a silent cryptographic hope that P ≠ NP. It’s the number one mathematical challenge of cyber security. It has been attacked relentlessly, for decades, and it is still standing.
Unlike Fermat’s last theorem which is so easy to present (alas, took hundreds of years to solve), the P=NP question is hiding in a mathematical swamp that most of us don’t dare to wade into. Even the meaning of P — “polynomial difficulty”, and NP: “non-deterministic polynomial” are so thick and muddy. Here is a clean version: A teacher explains to you a difficult concept, a profound, and intricate idea. You attack it mentally, think about it, and finally understand it. Now you ask yourself: “Could I have invented it, originated it, thought about it on my own?”
Some say, if I could understand something, if I am smart enough to grasp it — I should be smart enough to have invented it, thought about it myself. Others say, hey — many people come to understand Darwin’s evolution, it does not mean they could have come up with this theory on their own.
If you subscribe to the first option you believe that P=NP. If you think like the latter then you claim, as most mathematicians do, that P ≠ NP. Computationaly speaking: if you can easily verify that a given solution is the right one, could you also find that solution with comparable ease? The venerable RSA security algorithm is based on the hope that while it is difficult to find x, and y in the equation: x * y = 10963136449, it is easy to verify that x= 104729 and y=104681, are indeed a solution. Bitcoin hinges on the hope that despite the ease in which a hash can be verified, it is hopelessly hard to find it in the first place. Is it?
The situation is skewed towards the bad guys. If it turns out that P ≠ NP then hacking is not vanquished, not by a long shot. But if P=NP then cyber security is in real trouble.
Recent techniques involving mathematical symmetry seem to suggest that at least some such problems known as ‘one way function’ may be mapped into a super-symmetric language where finding and verifying are mutually reversible, computationally speaking.
This question is deeper than mathematical formalities. Cyber security today is based on defensive walls constructed of mathematical challenges that are too difficult for us to solve. The P v. NP question is an arrogant attempt, some say, to claim that if it is hard for us, it is also hard for God, and for any mathematician smarter than we are. Unfortunately, mathematicians live inside their imagination horizon, and what is beyond that horizon is beyond their reach. All that is needed for our adversaries to defeat us in the coming cyber war, is to see further, enjoy a more distant mathematical horizon. And one such mathematician may be enough. You don’t need a brigade! Not very reassuring, I know, that is why so many security mavens paper over this peril — the ticking cyber security bomb.
Not sooner but later, not at once, but gradually and grudgingly, we will come to realize that mathematical intractability (the technical name) is too far stretched to base our cyber well being on. And then we will turn to the resource that will save the day, and keep our cyber life happy. This resource is randomness. We have just recently developed the technology to manfucture large amounts of high quality random bits, and this is a game changer. Next article: how randomness defeats smarts. For Geeks: “BitFlip: A Randomness Rich Cipher” Popov, Samid: https://eprint.iacr.org/2017/366