Slashdot Mirror
IBM Warns Quantum Computing Will Break Encryption (zdnet.com)
Long-time Slashdot reader CrtxReavr shares a report from ZDNet:
Quantum computers will be able to instantly break the encryption of sensitive data protected by today's strongest security, warns the head of IBM Research. This could happen in a little more than five years because of advances in quantum computer technologies. "Anyone that wants to make sure that their data is protected for longer than 10 years should move to alternate forms of encryption now," said Arvind Krishna, director of IBM Research... Quantum computers can solve some types of problems near-instantaneously compared with billions of years of processing using conventional computers... Advances in novel materials and in low-temperature physics have led to many breakthroughs in the quantum computing field in recent years, and large commercial quantum computer systems will soon be viable and available within five years...
In addition to solving tough computing problems, quantum computers could save huge amounts of energy, as server farms proliferate and applications such as bitcoin grow in their compute needs. Each computation takes just a few watts, yet it could take several server farms to accomplish if it were run on conventional systems.
The original submission raises another possibility. "What I wonder is, if encryption can be 'instantly broken,' does this also mean that remaining crypto-coins can be instantly discovered?"
In addition to solving tough computing problems, quantum computers could save huge amounts of energy, as server farms proliferate and applications such as bitcoin grow in their compute needs. Each computation takes just a few watts, yet it could take several server farms to accomplish if it were run on conventional systems.
The original submission raises another possibility. "What I wonder is, if encryption can be 'instantly broken,' does this also mean that remaining crypto-coins can be instantly discovered?"
Wasn't elliptic curve cryptography supposed to be resistant to quantum computers?
What a strange and verbose way of saying "you're right, quantum computing will break HTTPS".
Hashes are actually one of the best ways to stay QC-safe.
At the moment, we use our existing encryption algorithms to generate hashes. Instead, most of the quantum-safe encryption algorithms use hashes to build themselves.
The reason is quite simple if I can use an analogy. It's not 100% accurate, but good enough to make most people understand.
First - a hash.
You take an input, you generate a "mini-mash" of it - you jumble it up and cut bits out in a predictable manner until you get something that is absolutely tiny but built from that original input.
The same input will give the same hash every time, because you do the same thing every time. Yet millions of different inputs might give you that same mini-mash (because they are much fewer hashes than there are data-sets, so by chance they overlap sometimes - a hash collision) but that hardly matters in real life because the chances of those other inputs being valid Microsoft Word files, or containing the same secrets as your files are infinitesimally small.
Quantum-computers attacking conventional encryption works like this:
- you "build a circuit" that performs the same encryption that was used (e.g. AES, ECC, etc.).
- you plug in the ANSWER (the encrypted text) into the end of it.
- by some magic of physics, it instantaneously determines the only possible inputs that could have ever formed that answer. Thus, it works out the SECRET INPUT (i.e. the keys) that was originally used to encrypt it - all in one "tick".
As such, QC defeats traditional encryption entirely. Every encrypted text/web session is one tick away from compromise with zero effort required and only tiny amounts of time expended.
But when you apply that technique to hashes, there may not be only one possible input. In fact there may be an infinity of inputs that give the same hash (because the input can be any size, right? So the mini-mash of a entire novel could the same as the mini-mash of "123" or the same as the mini-mash of a dataset as large as the universe).
As such, the QC can't determine the answer - it gets all the answers and doesn't know which one's right. To know which one was right, you'd have to check them all... and you're now back from "working out the answer instantaneously" to "checking all the possible combinations one at a time".
So instead you can build QC-safe encryption by using hashes upon hashes upon hashes upon hashes. Now any possible inputs a quantum computer may determine is lost in an infinity of other inputs... and it's no longer as simple as "just give us the only input that looks like a Word file" - you have to check them all.
As such, hashes are the basis of much more security, based on their "unknown but potentially infinite amount of data" turned into "a small set of characters" property.
Crypto-currencies use hashes a lot (Bitcoin is/was basically built upon "keep hashing different things on the end of this string until you get a hash of 0 out of it") and so may be the last thing to fall to QC.
In the same way that QC turns cryptanalysis on its head, to solve the problem of QC we turn hashes and encryption on their heads.
Yes, quantum computers will eventually allow people to crack the private keys for most cryptocurrency wallets. However, some projects are already working to address this. The best example is Quantum Resistant Ledger (QRL), which is redesigned from the ground up to use quantum proof crypto algorithms. Look it up, they have a lot of info on exactly HOW quantum computers will affect cryptocurrencies, and other related data.
Probably wrong on the details
But that's slightly different than dead wrong.
It does emphasize what we all sort of know. Encryption that is good enough today will probably be not good enough in a few -- five, ten, fifteen -- years. Which suggests that all your email and metadata that you and others have stashed in encrypted stores may be decodable if you (and they) keep the stores around too long.
And it doesn't matter what technology makes the data readable. Quantum computing, brute force, some clever algorithm, some flaw in common encryption algorithms or the software implementing them. Your secrets may not remain secret.
That's probably not a good thing.
You can't see ANYTHING from a car, You've got to get out of the goddamned contraption and walk...Edward Abbey
This could theoretically be the biggest breakthrough in computing since transistors, and this person is wondering about how it's going to affect Monopoly money? Jesus.
Yes, because the computer farms doing blockchain proof of work are devastating for the environment. If blockchain dies, there's a much better chance of there still being a habitable world for my grandchildren. The sort of person heavily into cryptocurrencies tends to be the sort of person who either doesn't believe humans have any impact on climate change or has wet dreams about helping cause widespread devastation, so it needs something external to kill them.
Quidnam Latine loqui modo coepi?
More accurate would be be "if an ideal (perfect) quantum computer existed, with enough cubits, it could break some types of encryption in a reasonable time".
Ideal quantum computers don't exist, and never will. An open question how near actual, physical quantum computers will get to this theoretical perfect machine. It's kinda like doing physics approximations and starting with "ignoring air resistance and friction ...". Well yes, if there were no friction we could build machines that do a lot of things which can't actually be done, because in the real world there is friction.
In a universe that only exists in textbooks, a universe of ideal machines, ideal quantum computers could factor numbers in polynomial time. Not instantly, but it wouldn't take a billion years like it would with classical computers.
Some of the cryptographic algorithms we use today get their strength from the difficulty of factoring certain types of large numbers. Those algorithms would need to be replaced if quantum computers developed sufficiently.
Already, we deprecate cryptographic algorithms every couple of years. Part of my job is checking https, ipsec, and other systems to see that they are configured to use strong algorithms. I have to update our list of currently accepted algorithms a couple times per year. The designers of these protocols were smart in that the designed the protocols to support any algorithm you want. For example, TLS defines that "key exchange" messages should be exchanged, but doesn't define what type of key exchange. It could be RSA key exchange, it could be Diffie-Hellman, it could be elliptic curve Diffie-Hellman, or supersingular elliptic curve Diffie-Hellman. TLS (aka SSL) doesn't know or care. Classical Diffie-Hellman can be replaced with supersingular DH without changing anything about TLS.