After watching the latest Veritasium video about how Newton figured out a novel approach to solving PI which was dramatically simpler than the previous thousand-year old methods, I wonder if someone will come along and figure out a simple mathematical way to break these encryptions. That would be horrifying of course, but also really cool.
That video was one of the best videos on mathematics I have ever seen; the visualizations to aid in the explanation of Newton's "new" algorithm were absolutely top-notch. I'm not sure I could have followed it without them. With them, I feel like I know it well enough now to explain it to someone else.
The thing with applied cryptography is that everyone is expecting the attacks to get better over time, sometimes in big and inconvenient bursts. There are several strategies to mitigate this, including oversizing security margins by a certain amount (so that an innovation that improves an attack by an order of magnitude or two isn't an instantaneous shattering of your whole security model), and having what's sometimes termed "algorithm agility" (which has somewhat fallen out of favor recently due to having its own class of bugs due to the implementations around, say, an optional NONE pluggable cipher type).
As the other guy points out, we have a lot bigger problems than Bitcoin falling.
But it likely won't happen at all. Lots of work is being done on quantum proof cryptography[1]. IT systems and crypto can be upgraded to use it.
The real problem is going to be all the stashed encrypted data that US and China have stored on each other of a sensitive nature. The encryption on this information could be cracked by a quantum computer.
> The real problem is going to be all the stashed encrypted data that US and China have stored on each other of a sensitive nature
While there's no doubt they've stored lots of encrypted messages sent by each other, would it really be such a huge catastrophe if those messages were decrypted years after they were sent? Presumably neither side is sending the most sensitive information that has long-term value (like weapons designs) across a channel the other can read, encrypted or not. And the US and Chinese governments losing control of some of their secrets wouldn't necessarily be a net negative for the world anyway. Snowden "decrypted" some of the US's secrets and we are better off for it.
The bigger threat isn't both sides decrypting each other's stored messages, it's one side breaking the other's encryption without them knowing, like what happened with the Enigma in WWII.
Unfortunately the work being done on post quantum cryptography is mostly on the topic of symmetric key agreement (since that is what TLS needs), and cryptocurrencies need digital signature and/ zero knowledge proof systems. There is comparably much less work being done on solving those problems.
The community would fork the blockchain at some agree-upon moment, add a new encryption scheme, and carry on.
There would probably be some competing chains as different communities tried to be "the one". Things might settle down at some point as it's really a "winner takes all" market.
If you could easily break some basic widespread cryptographic primitives, you could mitm TLS and serve valid signature spoofed OS updates, basically giving you total control over the computers of just about any organization you like.
The first thing to target would be the network operators, so that you have the technical ability to observe and inject packets into connections from leaf nodes. Then, you could redirect those connections to yourself, proxy their TLS undetected, or serve replies that contain (valid signature) updates or malware.
This is one of the many reasons that a defense in depth strategy (that is, not solely/blindly trusting TLS or digital signatures to ensure that your computer doesn't run unauthorized code) is a good idea.
It is also probably another reason why so many state-level intel agencies target telecoms first and foremost.
The mathematics of Shor's algorithm have been known for decades. The challenge is in building the hardware, not in the math.
There are tens of billions of dollars worth of abandoned Bitcoins in addresses with exposed public keys. It would be trivial to get those if you can break ECDSA. Yes, there is much more outside of Bitcoin but I don't see why someone who had this capability wouldn't go after the easy targets first.
Yes, Shor's algorithm would be a feat of quantum computing hardware.
I was referring to if it was possible to break encryption using classical computers in polynomial time -- that would be a feat of mathematics, if it were even possible, and would likely have implications about P vs. NP.
