Slashdot Mirror
Quantum Computers Will Break the Encryption that Protects the Internet (economist.com)
An anonymous reader shares a report: Factorising numbers into their constituent primes may sound esoteric, but the one-way nature of the problem -- and of some other, closely related mathematical tasks -- is the foundation on which much modern encryption rests. Such encryption has plenty of uses. It defends state secrets, and the corporate sort. It protects financial flows and medical records. And it makes the $2trn e-commerce industry possible. Nobody, however, is certain that the foundation of all this is sound. Though mathematicians have found no quick way to solve the prime-factors problem, neither have they proved that there isn't one. In theory, any of the world's millions of professional or amateur mathematicians could have a stroke of inspiration tomorrow and publish a formula that unravels internet cryptography -- and most internet commerce with it.
In fact, something like this has already happened. In 1994 Peter Shor, a mathematician then working at Bell Laboratories, in America, came up with a quick and efficient way to find a number's prime factors. The only catch was that for large numbers his method -- dubbed Shor's algorithm -- needs a quantum computer to work. Quantum computers rely on the famous weirdness of quantum mechanics to perform certain sorts of calculation far faster than any conceivable classical machine. Their fundamental unit is the "qubit", a quantum analogue of the ones and zeros that classical machines manipulate. By exploiting the quantum-mechanical phenomena of superposition and entanglement, quantum computers can perform some forms of mathematics -- though only some -- far faster than any conceivable classical machine, no matter how beefy.
In fact, something like this has already happened. In 1994 Peter Shor, a mathematician then working at Bell Laboratories, in America, came up with a quick and efficient way to find a number's prime factors. The only catch was that for large numbers his method -- dubbed Shor's algorithm -- needs a quantum computer to work. Quantum computers rely on the famous weirdness of quantum mechanics to perform certain sorts of calculation far faster than any conceivable classical machine. Their fundamental unit is the "qubit", a quantum analogue of the ones and zeros that classical machines manipulate. By exploiting the quantum-mechanical phenomena of superposition and entanglement, quantum computers can perform some forms of mathematics -- though only some -- far faster than any conceivable classical machine, no matter how beefy.
If you're not guilty, you have nothing to hide.
And unbreakable encryption only serves the Bad Guys (tm).
Or so we're told...
Check your premises.
First, even if QCs ever work for reasonably sized problems, it will take a long, long time for them to get there. If the last 30 years are any indication, they scale decidedly sub-linear with time. And second, nobody knows whether they scale at all or are limited to low qbit numbers.
Any panic over this is a few decades premature.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
Will this break all the foundational DRM on which all our good stuff depends?!?!?
Quantum computing is a good way to fleece investors, but that is about it.
The encryption is ALREADY broken, we don't have to wait for quantum machines to get there
Additionally speed is not the ONLY factor in security/encryption. complexity is also a key factor, but if people would get rid of ridiculous ideas like "public CA's" and force everyone to perform private and variable key exchanges provided by the site itself on first visit we can rapidly increase security. [this is just one simplified example and to save time not a complete answer, so don't get your undies in a wad]
As long as you require an encryption system that relies on a 3rd party institution as part of its key exchange it will never be secure, Quantum hacking or not.
Real security is hard and requires some inconveniences.
I seem to remember having read about a recent cryptographic algorithm that could withstand a quantum computer. Anyone remembers more detail?
https://csrc.nist.gov/Projects/Post-Quantum-Cryptography
Don't panic, citizen.
the company offering quantum encryption.
If QC is the latest, greatest thing that is coming "Real Soon Now" you should ignore botnets with hundreds of thousands of systems, which exist now.
On the other hand, QC may make mining bitcoins much more economical.
https://www.forbes.com/sites/forbestechcouncil/2018/04/18/worse-than-y2k-quantum-computing-and-the-end-of-privacy/
This is worse than y2k
If it is 10x worse than y2k, then it will still be no problem at all.
I'm a good cook. I'm a fantastic eater. - Steven Brust
How often can we rehash the same thing?
We've been saying this for how long now?
I tend to rant.
...your encryption method does not use prime numbers to work?
Religion: The greatest weapon of mass destruction of all time
The trouble is that with the quantum algorithms finding the key becomes the same order of difficulty as deciding the message if you know the key. Before decryption was O(N) and cracking was O(2^N), so you can increase the key size until you get the right trade-off of ease of use and security. If they are the same order then there may not be a key size that has a reasonable ease of use and security trade-off.
That said, this generally only applies to RSA. If you're using elliptic curve cryptography it discrete logarithms then you are probably still safe (since we haven't yet figured out how to get qubits to perform analogous operations without collapsing).
Really? A problem that required billions of dollars and millions of man-hours to fix worldwide wasn't a big deal?
Which has been on the decline on the Internet for a while. Factorising large numbers won't help with elliptic curve, Rijndael or any other post-quantum crypto.
For the latest:
https://www.safecrypto.eu/pqcl...
It's a small world and it smells funny; I'd buy another if it wasn't for the money; Take back what I paid (SoM)
No, because you can conceive of a very large scale parallel computer, such as the one the EFF built.
Quantum attacks are parallel attacks, so a large enough parallel computer can mimic them.
It's a small world and it smells funny; I'd buy another if it wasn't for the money; Take back what I paid (SoM)
Hell, we even see news items that the NSA contractors are USB'ing data around, dropping passwords, and using their hotmail accounts at work etc. Front door breaks are for academics, interesting mathematically, but not useful day to day.
There is no other value to their analyses. Their track record shows that. The magazine is a nicely packaged nothing.
Agreed. The article is essentially the same rehash of, "tomorrow's computers will break today's encryption just like today's computers broke yesterday's encryption." Nothing to see here; we already know that tomorrow's encryption will be reinvented.
Let's make like a bird... and get the flock outta here.
Always prudent to make sure security stacks are sufficiently configurable to enable rapid phase out of broken technology as it becomes necessary. It's great to work on quantum safe key exchange and new ciphers just in case.
What is foolish and wasteful is switching to something else from a position of fear of what can't be ruled out when no affirmative evidence to support such fears exists. At that point you are no better off hiring keyboard mashing monkeys to set policy.
could have a stroke of inspiration tomorrow and publish a formula that unravels internet cryptography
They made a movie about it. The problem is the "deep state" has hidden it from the public, just like they've hidden those aliens who helped us in World War II.
We will bankrupt ourselves in the vain search for absolute security. -- Dwight D. Eisenhower
In general. parent is saying ECC is still probably safe, but can anyone reference or summarize other work in this?
I know Vitalik Butarin was concerned about it and investigating, a few years ago, because apart from existing e-commerce and secure surfing etc this, quantum computer cryptanalysis would also destroy all existing blockchain implementations and cryptocurrencies.
Where are we going and why are we in a handbasket?
Encryption is a force multiplier.
1) They'll make fast computers that are so cheap that everyone can use them (or time-share them or whatever), and therefore be resistant to quantum-computer-speed brute-force.
2) They'll make fast computers that are so expensive only the the most powerful can crack encryption, and only selectively at that. But it's probably easier for the CIA and NSA to get around encryption other ways. I just kind of assume that they've got their fingers into most everything.
3) Something in between.
We live in a magical age where the poorest of poor can utilize services (that are so cheap they're free) which the most powerful of the powerful cannot thwart. They are secure in their person and papers. Despite a warrant. And that really rankles the powerful. They're typically not big fans of not having power over people. If they make a fundamentally faster computer, it'll crack the encryption of today. But it WON'T crack the encryption of tomorrow, because they'll simply use the faster computing technology. (or from factoring to ellipse curves). The transition period is where cyberpunk novels are written.
Technological progress is definitely not linear in general.
It builds on itself and thus sometimes has a geometric or exponential progress.
Often times, advances in multiple areas can combine to make a new revolutionary solution that was impractical before.
e.g. Theoretical advances + materials research can lead to practical quantum computing, or maybe high temperature superconductivity etc,
which then can be a foundation for a whole new layer of practical revolutionary and unpredicted technologies.
It tends to have breakthroughs, tipping points etc, in other words, punctuated equilibrium.
So don't count on progress in quantum computing staying slow and incremental.
Where are we going and why are we in a handbasket?
Encryption of TCP/IP traffic was always a kludge workaround to the internet problem.
If something is so important that you feel the need to post it on the internet... It probably isn't that important.
The armchair wise-asses laughed at how lame Y2K was.
Their pea-brains didn't understand that it was no big deal precisely because a lot of planning, time, and effort went into technical fixes and technology replacements to avoid the impacts of the problem.
A lot of computing-related problems are still pretty binary. Either they'll happen, or if fixed, they won't. It can be all or nothing easily. E.g. a patch for a critical and easy to exploit OS security hole. Could be a laughable hype, if discovered and widely patched in time, or could be a widespread disaster.
Where are we going and why are we in a handbasket?
The results of the computation depends on the observer
And it is a QA nightmare, none of the computations are repeatable.
All the memory states of a quantum computers can be 1 or 0 till you read it your would not know. Once you read it the memory is destroyed.
sed -e 's/Chuck Norris/Rajnikant/g' joke > fact
For RSA you don't actually have to factor the large composite number, you need to just know the period of the messages, which is what Shor's algorithm does.
In RSA you choose two large prime numbers p and q, and then publish n=(p*q) and e. e is a smallish usually prime number. Your private key is a number d such that e*d is congruent to 1 module (p-1)(q-1). (p-1)(q-1) is the number of coprime numbers to (p*q). Given a number M less than n that is coprime to n, if you raise that number to every different power less than (p-1)(q-1) and take the modulus n, you will get every coprime number of n. When you raise M to (p-1)(q-1) and take the modulus you will get 1 and when you raise it to (p-1)(q-1)+1 you will get M again.
(p-1)(q-1) is the number of coprimes to n and also the period of any M being raised to a power modulo n. In classical computing you would likely find p and q by factoring n and then calculate (p-1)(q-1). However, Shor's algorithm actually gives you the period. (You could then find p and q though)
You can argue about encryption algorithms and faster computers, but the real issue is time. Anything that traverses the wire becomes part of a permanent record. They copy and store every single bit, knowing that they cannot crack your encryption today, but in the future it will become trivial. So at best you're talking about mitigation. Everything you've ever said or done will have to live up to the impossible moral standard of the world communist courts of the not so distant future. There will be no deviation from the hive mind of public opinion which you will be happy to oblige.
We can sign things with just a hashing function. For key agreement and other fun things there are other problems that it appears a quantum computer can't solve. https://en.wikipedia.org/wiki/...
However, there are a number of problems:
1 - If the NSA records the handshake of your conversation today, they will be able to read your messages in the future when/if they build a quantum computer. I find this point very frustrating. So many people think they are safe as long as they adopt something before a quantum computer is built.
2 - Adoption is going to be very slow. Other than Supersingular elliptic curve isogeny, none of the other proposals are drop in replacements for what we do today. So the protocols will have to change.
3 - Performance and bandwidth - some of the new algorithms have similar computation requirements but many are more expensive, some require significantly more RAM and almost all require huge message sizes. Most of my work is with ZigBee and 21 byte ECC point representations are fine. 1K messages are going to be really hard. 30K will be impossible. The bandwidth will take nearly an hour, many $1 systems won't even have that much memory. Hell the power consumption to be awake to receive the message will kill some devices.
Wrong. There are also efficient quantum algorithms to compute discrete logs and elliptic curve discrete logs (which is generally what elliptic curve cryptography is based on). Lattice based crypto and symmetric key systems might well be safe, but quantum computers basically break all commonly used public key cryptography protocols.
and it may be decades before they do.
IBM's 5 qbit machine is coherent for 50 microseconds. It is not big enough to solve any useful problems. D-Wave isn't any faster than an ordinary computer and using quantum "annealing" it is limited in the kinds of problems it can solve.
If someone created a 4096 GPG key it would most likely be good for their lifetime.
Running with Linux for over 20 years!
The summary says:
Anyone smart enough to solve this problem is smart enough to do something other than publish the proof. Patriots will probably get a large payday for delivering it to their local intelligence service. Black hats can sell it on the dark web. White hats would warn about an impending publication and let everyone crash move to a new system first.
Your ad here. Ask me how!
utterly amazing how well that movie aged, isn't it?
Quantum physics allows us to entangle bits (really qubits) and separate them by great distances. We can create a totally secure "quantum net" that allows instantaneous communication between one set of entangled bits and another set of entangled bits.
Yeah, you physicists are going to say something about "information passing", "speed of light limits", yada, yada yada. That is fine in theory, but in practice 99% of all social media post have no real information.