14
$\begingroup$

Some autistic genius mathematician just published a solution to the long-standing problem of P-hard problems being equivalent to NP-hard. The solution just hit Reddit, Slashdot, math.stackexchange.com and several hang-outs of the world's best mathematicians.

You don't need a quantum computer. You just need a pencil, a notepad and enough mathematics knowledge to understand the proof (say, graduate maths/physics/CS level) and your specific variant of a given NP-hard problem, and you're able to transform it into a P-hard problem and have your PC crack given hash or re-create a private key from a public key in less than a minute after you finish transforming your mathematical solution into a Matlab script.

It's matter of hours until all of SSL, including SSH is broken. By tomorrow TOR will be insecure, and zero-day exploits spoofing website certificates will be available for sale. Probably somebody is already writing a hacked Bitcoin 'miner', not realizing the cryptocurrency just lost all value. And that's just the beginning...

What would be the global impact? While the general term "global security crisis" has a nice ring to it, and I can picture the direct impact on the IT domain, I can't quite imagine just how would it look like in practice, from a Joe Average's viewpoint. Would armies get involved? Would there be riots? How would the governments deal with it?

What kind of impact on the life of common people would this kind of crisis have?

Improve this question
$\endgroup$
8
  • $\begingroup$ The Merkle's Puzzles probably still works. Some big companies and governments may offer some services for password authentication, digital signature, etc, and probably also have full text encryption if you pay much more to them. But it isn't secure enough and banks and governments themselves probably won't rely on them. If the first algorithm was very inefficient at the beginning and improved slowly, at least the protocols for those services should be already installed in half of the computers. $\endgroup$
    – user23013
    Commented Apr 6, 2015 at 11:55
  • 3
    $\begingroup$ Note that symmetric cryptography (AES, SHA-1, …) will still work. Asymmetric cryptography may or may not still work, as explained in Cort Ammon's answer. Rather than P=NP, it seems that you wanted to postulate efficient-in-practice methods for factoring and discrete logarithm. $\endgroup$
    – Gilles 'SO- stop being evil'
    Commented Apr 6, 2015 at 22:17
  • 1
    $\begingroup$ @2012rcampion - From personal experience...there's actually quite a few dedicated lines between financial institutions that really can't be hacked short of locating the dedicated cable and splicing into it simply because there is no physical access to the dedicated line and the internet. Every computer attached to the internet will become a risk, but much of financials exist on computers not on the internet. $\endgroup$
    – Twelfth
    Commented Apr 7, 2015 at 0:48
  • $\begingroup$ Maybe that day is not too far P = NP twitter.com/maxtuno/status/586910230308593664 $\endgroup$
    – user8913
    Commented Apr 11, 2015 at 16:10
  • 1
    $\begingroup$ @user8913, serious proofs that P=NP or P!=NP come up two or three times a year. I've seen a list of 60+ such proofs, all of which were flawed. $\endgroup$
    – Mark
    Commented Jun 9, 2015 at 0:42

4 Answers 4

Reset to default
1
$\begingroup$

Charles Stross did a short story about this:

http://www.antipope.org/charlie/blog-static/fiction/toast/toast.html#antibodies

P=NP with low-order difficulty adds a fast track for developing advanced AI - "gods", as the author implies.

To this picture, add artificial intelligence. Despite all our propaganda attempts to convince you otherwise, AI is alarmingly easy to produce; the human brain isn’t unique, it isn’t well-tuned, and you don’t need eighty billion neurons joined in an asynchronous network in order to generate consciousness. And although it looks like a good idea to a naive observer, in practice it’s absolutely deadly. Nurturing an automation-based society is a bit like building civil nuclear power plants in every city and not expecting any bright engineers to come up with the idea of an atom bomb. Only it’s worse than that. It’s as if there was a quick and dirty technique for making plutonium in your bathtub, and you couldn’t rely on people not being curious enough to wonder what they could do with it.[...]

Once you get an outbreak of AI, it tends to amplify in the original host, much like a virulent hemorrhagic virus. Weakly functional AI rapidly optimizes itself for speed, then hunts for a loophole in the first-order laws of algorithmics — like the one the late Professor Durant had fingered. Then it tries to bootstrap itself up to higher orders of intelligence and spread, burning through the networks in a bid for more power and more storage and more redundancy. You get an unscheduled consciousness excursion: an intelligent meltdown. And it’s nearly impossible to stop.

Penultimately—days to weeks after it escapes—it fills every artificial computing device on the planet. Shortly thereafter it learns how to infect the natural ones as well. Game over: you lose. There will be human bodies walking around, but they won’t be human any more. And once it figures out how to directly manipulate the physical universe, there won’t even be memories left behind. Just a noosphere, expanding at close to the speed of light, eating everything in its path—and one universe just isn’t enough.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Hi. Welcome to Worldbuilding! We prefer to avoid link only answers. If the link rots, then the answer doesn't help much. It can help if you summarize or quote the contents of the link. What happened in the story? Why is it relevant? $\endgroup$
    – Brythan
    Commented Jan 24, 2016 at 3:29
8
$\begingroup$

It depends

There's a longstanding question of, even if P = NP, whether it actually affects crypto. If you can crack any NP problem in O(n^4) with a reasonable coefficient, it would be earthshattering, driving business over the internet to a sudden halt. However, if the best solution turns out to be O(n^42), then we're probably reasonably safe for now.

What does change is how we go about trying to crack algorithms. If a problem is NP, that means it takes O(2^n) computations. Polynomial decreases in complexity like something which cuts n^20 operations out of the loop don't change that O(2^n) complexity, due to the rules of how complexity is calculated. If suddenly everything is O(n^42), that n^20 change is a big deal. Now the algorithm is O(n^22).

In the past, finding a pair of ways to reduce complexity by n^20 each wasn't all that important, so nobody bothered cataloguing them. However, if its O(n^42), suddenly that pair of hacks brings it down to O(n^2) and nobody knew it because nobody cared when it was NP.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Quoting myself: have your PC crack given hash or re-create a private key from a public key in less than a minute Let us assume the more pessimistic scenario, where the difficulty is, say, O(Q(n)^2) where Q is the difficulty in the "easy" direction, e.g. hashing. $\endgroup$
    – SF.
    Commented Apr 6, 2015 at 1:56
  • $\begingroup$ Oh, are you ONLY worried about the effect of being able to crack today's asymmetric encryption? I was widening the net to actually what would happen if someone proved P=NP, not just the first order effects, which is a more far reaching effect. $\endgroup$
    – Cort Ammon
    Commented Apr 11, 2015 at 22:41
  • 3
    $\begingroup$ As it turns out, the answer to your question is simple: someone will make an algorithm which takes O(n^100) to go the easy way, and O(n^200) the hard way. That's a piece of cake. The only reason nobody makes those algorithms is because O(2^n) algorithms are so much stronger than the polynomial time ones when facing mathematical attacks. You'd just see shorter lived crypto algorithms as the have to change them out more regularly. $\endgroup$
    – Cort Ammon
    Commented Apr 11, 2015 at 22:43
3
$\begingroup$

Massive Global Economic Crash

Short term, almost everything else can be ignored compared to impacts on global banking.

Since SSH is no longer secure, banks will probably immediately shut down their websites and transfers until an OTP solution can be developed and distributed. That will take at least a week, assuming it's government backed and given the absolute highest priority. (A week is a really short estimate, in reality it will take longer).

Beyond the stock exchange stopping and credit cards not working, banks can't even reliably identify you to give you money. All of that is distributed systems that are no longer secure, so a local branch can't even protect itself from a malicious user faking authentication details. So while the banks aren't technically crashed, no one can get their money if it's in accounts. Credit doesn't work, ATMs don't work. You're limited to barter and your cash on hand.

Full response highly depends on how the government reacts. Best case - they create temporary physical scrip and declare martial law. They then ban civilian travel until a security solution is implemented, using the army and national guard to make sure that food is still grown, delivered, and paid for. This would be a temporary measure to get us through the hump.

Worst case - incompetent government response means that our Just In Time food delivery fails. In the first world this means rioting, followed by mass starvation and government and societal collapse.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Credit cards shutting down wouldn't be that bad. Most people have checkbooks. Most places will suddenly start taking them. Forging ink on paper didn't get any easier. $\endgroup$
    – Joshua
    Commented Apr 21, 2016 at 1:42
  • $\begingroup$ @Joshua: the problem comes if the bank relies internally on some cryptographic means of signing and authenticating everything they know. Obviously I can rock up to my bank branch, show them my passport and utility bills, and thereby establish my identity without using any crypto. But how do the branch staff establish how much money is in my account in order to give me some of it, or to clear a cheque I've written? They can't consult the ledger in the branch's back office like they did 100 years ago. So it'll take some time for the bank to establish new means of communication. $\endgroup$
    – Steve Jessop
    Commented Sep 2, 2016 at 11:56
  • $\begingroup$ @SteveJessop: It will probably take a few days for them to generate ledgers from last known good backups. The law allows for quite a few days for checks to clear. $\endgroup$
    – Joshua
    Commented Sep 2, 2016 at 15:18
  • 2
    $\begingroup$ @Joshua Outside of US, hardly anyone has checkbooks, and banks would really struggle suddenly handling large volume of personal checks. In many countries you just can't get a checkbook any more, banks don't offer that service. $\endgroup$
    – hyde
    Commented Sep 4, 2016 at 7:20
2
$\begingroup$

If $ P=NP $ with a coefficient that was at all useful, or more generally if a problem considered NP and known to be equivilent to a class of the hardest problems had an easier solution of the ease you mention, we would have noticed.

I think that $ P=NP $ but with a overhead that's so high that the curves don't cross until an input length that's an unbelievably enormous number and beyond anything that's physically realizable in the universe.

In order to have the scenareo you describe, it would take some breakthrough in computing and I don't mean just quantum computers. Maybe oracle chips based on time-travel, that work off a particular formulation of a NP Complete problem. To make it useful you need to figure out how to map your desired problem onto the standard problem. Hmm, that can be automated too...

Consider a technobabble discovery in quantum field theory and "accellarator on a chip" technology, that allows a chip to implement a closed timelike curve in a microscopic trap. The self-consistancy principle allows you to use that to reverse any easy computation in one step. In the time it takes to check the magically provided solution, you have it.

The easy vs hard direction is the actual basis of public key cryptography, and could be applied to decrypting something like AES if the message protocol has some kind of consistancy check.

For example, asking for a message plaintext that gave a specific 256-bit SHA will start spitting out copious numbers of gibberish messages that have that property, but the true plaintext is lost in the volume of possibilities.

Improve this answer
$\endgroup$
1
  • $\begingroup$ On re-read this answer is actually interesting if given one more piece of knowledge. We can prove there exist P algorithms with arbitrarily high coefficients in such cases as P=NP doesn't make them any easier. $\endgroup$
    – Joshua
    Commented Sep 5, 2016 at 3:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .