I'm surprised nobody has written a thriller yet where a new mathematical algorithm is found (maybe something to do with primes?), all encryption suddenly collapses, and with that we go into a psuedo-apocalypse where nobody is sure whether anything is authentic anymore. Banks can't share cash, ID systems are useless, we've still got electricity but no functioning internet, hardware root of trust is shattered...
A classic paper that explores what happens if various scenarios come to pass. Would be worth exploring some of the updated versions and fictionalizing them.
"Summer Wars"[1] features breaking keys as a plot element, with a passing mention of Shor's Algorithm. The rest of the movie is mostly unrelated to math. Good movie though.
As someone who is only vaguely familiar with the P = NP problem, can someone explain to me if proving P=NP automatically solves the numerous problems that can then be “quickly computed” or does it simply prove there is an existence of an algorithm for each problem?
To rephrase if this is not the case - what value does solving P = NP provide?
* Nonconstructive case. The resulting algorithm looks something like some primality test algorithms (which I'll describe): essentially, if a number n is composite, then there is some (X + a)^n = X^n + a in Z/nZ (X is a polynomial here). If you test "enough" a's, then you can prove whether n is prime or composite. A nonconstructive case would mean we have a proof that you only need to test poly(lg n) a's to confirm truth, without necessarily telling which a's you have to test. In this world, there is no practical change to problems--the proof doesn't yield an effective algorithm to actually solve any NP-complete problem.
* Combinatorial algorithm for an NP-complete problem. The good example here is what has been done to prove L = SL. The result is "technically" in L, but the factors in the algorithm run very quickly into "more than the number of atoms in the universe" phase. The goal is to find a memory-less algorithm (can't use a visit stack) that can prove a path between two points in an undirected graph, and it turns out that you can transform the graph into another one that will guarantee that you will visit every node in a certain amount of time. The found result has a new graph that replaces every node with more nodes than exist atoms in the universe, so it technically meets the requirements but is completely and totally impractical. Sometimes people handwave this possibility by saying that once an algorithm is found, people will find better results, but this result hasn't been improved on in close to two decades.
* "Simple" algorithm for an NP-complete problem. This is the result that really, really changes things. Once you get a simple algorithm for one NP-complete problem, you can generally find analogous ways to get simple algorithms for other NP-complete problems. However, the research done to date does suggest that this is perhaps the least likely solution: looking at the "hard" instances of SAT problems, it does seem that there is a certain complexity that is at best reducible via some sort of combinatorical nightmare construction rather than the kinds of decompositions that yields "simple" algorithms.
It's only required to prove an algorithm that solves an NP-complete problem exists, not find it.
Even if that algorithm exists and was found, it could be that such an algorithm is O(n^123456789), which would not break RSA in any practical sense, though it would be mathematically asymptotically faster than O(2^n).
If P == NP, then it could be possible that a proof would show that an algorithm must exist without providing such an algorithm. But that approach wouldn't be necessary, actually showing an algorithm would of course also be a proof.
> To rephrase if this is not the case - what value does solving P = NP provide?
P vs NP is a question of enormous practical interest. But it's also a very interesting question of pure mathematics. A proof that P != NP, or a proof of P == NP that didn't provide an algorithm would still be a huge deal in the math and computer science world.
Think about cryptography for a second…. In cryptography you need a problem that if you know the key is fast to decode but if you don’t is really slow… like you would have to search all the possibilities one by one. Such problems are (basically…) called NP. P are all the algorithms that are fast on computers. If P = NP than any problem you could use for cryptography could be decoded fast
It's been a little while - but I think it's because NP problems can be converted into each other, so if you can solve one of them in P you can solve all of them in P.
Some have speculated though that P doesn't necessarily have to be a short period of time. If P == NP, but P takes hundreds of years to compute, we may survive.
The Carrington event page was fascinating to read. Telegraph operators held an entire conversation without power! It is fairly unsettling though. I wonder if there are contingency plans that include thoroughly shielded or non-electronic communications equipment.
It took me a surprisingly long time to realize that I was reading fiction. The example SHA sums even do work, it's just that they only start with 40 bits set to 0 (expect to require 10^12 operations to generate each randomly - about a second on an ANTMiner) instead of 88 0 bits (multiple weeks of the full Bitcoin network to generate each randomly)
One of the neater bits of world building/subplots in the book "A fire upon the deep" is their ship is a freighter with a cargo full of one time pad keys. that is, the encryption you would revert to in a world where factorization is easy.
Symmetric encryption should still be unbreakable even against quantum computers or any advances in prime numbers. Given we currently trust CAs they could switch to something like Kerberos.
Cloudflare and Meta team up to invent a proprietary crypto algorithm that fixes everything but routes all traffic through their servers, centralizing the internet completely. All speech is controlled and monitored by this new entity, which receives a national security letter thereby merging it with the US government for all intents and purposes, but, like, you know, for our safety.
Nobody notices or cares what has happened, and critics are met with "well it dOesN'T mATteR because they aren't using the information for anything bad."
In the worst possible case we just switch to the one time pad encryption, which makes things inconvenient but literally can't be cracked by any computer or algorithm(tldr: the length of the key is as long as the length of the message, so a message can decode into anything and you can't tell whether the text you decoded is the right one or not). So a scenario where literally no encryption is available seems far fetched.
Yes, we simply change to one time pad encryption and ... distribute pre-share keys to every user on earth for every service that modern civilization relies on? The failure of RSA in a significant way would mean the end of modern commerce, military balance of power, and the sharing of information. It would be a history-altering event in the best case and devolve into existential war in the worst case. OTPs would do exactly zero to prevent any of that.
>>OTPs would do exactly zero to prevent any of that.
So if it was literally the only remaining unbroken type of encryption on the planet, it would have no effect? How so, exactly? We would just go with no encryption whatsoever rather than bear the inconvenience of distributing OTP keys?
Not really. The failure of RSA would necessitate a rapid shift to, probably, lattice key exchange. It would be a fire drill, but it would be greater by degree and perhaps not by kind than previous fire drills we've run.
Isn't the problem with one time pads distributing the pad? Like, you would have to walk to a bank and have them hand you a piece of paper... and tellers could read the paper before handing it to you. So basically so ineffective in practice as to be unusable?
The distribution part have gotten a lot easier.
I would be very possible for banks to give all their customers USB devices with a few GByte of one time pads and keep a copy of those same GBytes in their own systems.
And most banks still have brick-and-mortar stores where customers could come and identify themselves and collect their one time pad.
And a GByte of keypads would cover your banking need for a long time.
The problem is more that it works for some one-to-many relationsships such as banks, but not many-to-many relationships, such as emails, websites, etc. There have to be second or third parties.
On the hand, a lot of people seems to log in everywhere with Google Sign In or similar anyway.
And we could instead all have Google or Amazon devices with GBytes of one time pads. And that could be used to set up symmetric encryption, which should be more resistant to quantum computer attacks.
The only drawback is that we would have to trust the third party and everyone who could compromise the third party and every government that could put pressure on the third party :-)
Quantum Key Distribution. You can prove that the key hasn't been intercepted. But since that means you need a direct point to point connection with no routers, switches, hubs, amplifiers/repeaters etc., it only works for a tiny fraction of cases.
https://en.wikipedia.org/wiki/Quantum_key_distribution
Indeed, they're not one-time pads - they are symmetric authenticators where both sides hold the same seed, and iterate a PRNG or similarly iterable function every N units of time (say, 30 seconds), to give you the same new output, based on the same starting seed. Think stream cipher output, with an initialisation vector.
They are often called OTPs though (i.e. one-time passcodes), just to cause confusion.
The argument against OTP is that by securely distributing the key of the same length as your message, you ostensibly already have a secure messaging mechanism; why would you need the OTP?
Well no, that's not true - a bank could issue you with a one-time-pad long enough to encrypt the next 10000 messages with you, and use that over the years - they just need to tell you which line of the key is needed to decrypt your message. In that scenario you only need to guarantee security for the first time the key is distributed(for example a file sent to you when the account is opened).
You’d have to guarantee security every time a key is distributed, right? I guess practically it would look like going to the bank every few years… or maybe only once per account, you can fit a lot of bank statements in a couple gigabytes.
Actually this could be a nice service to offer now. We might worry that someday public key crypto will be broken, and we wouldn’t want all our old bank statements to become public at that point I guess.
I mean, years ago my local bank had an online banking system, where your PC had to dial-up their local server for any operations - and the authentication key was on a floppy. Which meant that yes, you needed to visit their branch once every year for a new key distributed on this physical medium.
Yes, it was inconvenient, but hardly an impossible thing to do. Banks manage to communicate the PIN for your card safely every time you open an account, I'm sure this could be done as well.
So now people have to keep a piece of paper around or somehow put it into some software and not lose access. You're right, it would work. In reality, people can't even be bothered to use a password manager or understand even the most simple of new security software, let alone even remember their password. That makes it completely intractable as a solution.
I mean, the scenario being discussed here is some kind of "world ending" situation where all known encryption is broken. So you either do it the way I described it, or you don't have any encryption whatsoever. I think under those conditions people would adjust. It isn't an alternative to our current arrangements.
Also: my bank access is done entirely through an app that obscures its internal implementation. It could already be using OTP and it wouldn't make any difference to me, nor would I be able to tell(my point is that the user wouldn't need to keep a piece of paper that they would need to type in anywhere - the internal implementation of tools we use every day would change, but most users wouldn't even notice)
I’m not clear on how we’d use a one-time-pad on a physical piece of paper (unless we want to do it like an old-timey spy novel character, using pencil and paper to combine the bits!)
Depends on the security of the service you want to use - I'd expect my bank or my email provider to send me my encryption keys by a recorded letter. Hacker news can probably email me their key instead.
Again, we're talking about some "world ending" scenario that OP mentioned - where all "normal" forms of encryption are already broken. If OTP is the only unbreakable encryption around, them I'm sure we'd find a way to distribute keys.
There's any number of less subtle and more important problems with this idea, but another problem you have here is that one-time pads only provide confidentiality, not integrity.
