https://scholar.google.com/scholar?cluster=14678868687868063...
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.
P !== NP is a theory that has never been proven, so it very well could happen in reality.
This is one of those things that keeps me awake, like Carrington events [2].
To rephrase if this is not the case - what value does solving P = NP provide?
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).
> 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.
* P != NP. In practical terms, nothing changes.
* 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.
P means you don't have to try every single possible answer.
But lots of algorithms fit that description while still being impractically slow. Keys might still be uncrackable.
It would be fun fodder for a sequel, but I feel like it'd come across as histrionic disaster-porn.
But how would the movie end?
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."
"just". So how do you do the key exchange?
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.
Apparently, some cesium based list of numbers, again, was 20 years ago.
Point is, it was a one time pad...
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?
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)
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.
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.
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 :-)
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?
In the end, as the world burns, I will helpfully explain how I was right.