Quantum Computers Will Break the Encryption that Protects the Internet (economist.com) 166
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.
So what? (Score:5, Funny)
If you're not guilty, you have nothing to hide.
And unbreakable encryption only serves the Bad Guys (tm).
Or so we're told...
Re:So what? (Score:5, Insightful)
And yet absolutely every person I've ever heard make this statement was fully clothed when they made it.
People have things to hide not because there is anything wrong with them, but because they are private. Full stop.
Re: So what? (Score:1)
You do realize that there are practical reasons for wearing clothes, right?
Re: So what? (Score:1)
Most things can be stored in your colon. Pockets are overrated.
Re: (Score:1)
Re: (Score:3)
You do realize that's not a parallel, right?
The reasons to encrypt your data are all about information hiding and non-repudiation. The reasons to wear clothing include that, and temperature modulation, shelter from elements, carrying capacity upgrades, and sanitation. And on a less practical level, self-expression (you could argue encryption as self-expression, but that's usually cyphers that humans can decode).
The analogy is just a terrible one. We already know why "if you're not guilty, you have nothin
Re: (Score:2)
Re: (Score:1)
Re: (Score:2)
Have you never been hot and realized you would be more comfortable without a shirt, but couldn't take it off due to the setting? The analogy fits, but it is confusing due to the other reasons for clothing which are not about privacy or modesty.
Re: (Score:2)
And yet absolutely every person I've ever heard make this statement was fully clothed when they made it.
People have things to hide not because there is anything wrong with them, but because they are private. Full stop.
Bad metaphor dude ... Slashdot has taught me that that anti-nudity thing is just an American hangup, from our bad old puritan days
Re: (Score:2)
Is the only reason that you poop with the door closed is to hide your poop?
Really?
Here's the difference: with poop, 99.99% of the time you don't actually care if somebody *wants* to deal with your poo, you just know that they almost certainly don't.
With encryption, you do care if somebody wants to deal with your contents, even though in most cases they probably don't.
It's completely different. Why don't we use normal analogies? The surprise you intend to keep for a loved one until their birthday?
Re:So what? (Score:5, Informative)
People have things to hide not because there is anything wrong with them, but because they are private. Full stop.
What basic psychology I ever learned said precisely this, that it's normal, natural, and healthy for people to want privacy, and to 'share' when it's their choice. This is a fact despite what so-called 'social media' corporations have been trying to indoctrinate people with over the last 20 years or so.
Re: (Score:2)
What basic psychology I ever learned said precisely this...
Basic psychology is also clear that men want one style of job and women another, but that won't stop the tirade of 'tech hates women' and 'diversity'.
Re: (Score:2)
Basic psychology is also clear that men want one style of job and women another
Okay, I'll bite: post links to credible, academic and/or science-based studies, preferably peer-reviewed, that back that statement up.
Re: (Score:2)
Re: (Score:2)
Nobody has any "right" to privacy beyond the fact that they might want it, and one may have the delusion that anything that a person wants is something that they somehow also have a right to have.
My point, above, is only that people who have not necessarily done anything wrong still desire privacy, and it is simply a matter of being humanely decent to eachother that compels every one of us to respect it. Man-made laws in excess of this which impose restrictions on what people are allowed to do which mig
Re: (Score:3)
Governments encrypt everything, so they would know best.
Re: (Score:2)
The Economist "predicts" what everyone believes (Score:2, Informative)
There is no other value to their analyses. Their track record shows that. The magazine is a nicely packaged nothing.
Perhaps we need a better infrastructure. (Score:2)
Encryption of TCP/IP traffic was always a kludge workaround to the internet problem.
Re: (Score:2)
Of course what they refuse to acknowl
Re: (Score:1)
No, they will not (Score:5, Insightful)
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.
Re: (Score:1)
Also, we will have poisoned ourselves with micro plastics way before this is an issue.
Re: (Score:1)
First, even if QCs ever work for reasonably sized problems, it will take a long, long time for them to get there.
TIL 5 years is a long time.
Ah yes the old progress is linear trope (Score:2)
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
Re: (Score:2)
Quantum computing has failed to perform for something like 40 years now. Any other technology this abysmally bad has just been scrapped. But somehow there are a lot of really clueless people that think this is magic and will suddenly scale and whatnot. There is absolutely no indication for that and a ton of indications to the contrary.
Re: (Score:2)
Nuclear fusion?
Re: (Score:1)
My own favorite example of start and stop progress is aeronautics. As a kid, I remember seeing a Twilight Zone episode in which a World War I fighter pilot flew his plane into a cloud and came out in the present (which at the time the episode was made was the late 50s or maybe early 60s). So there was this scene of a World War I Biplane fighter taxing past Boeing B-52 stratofrotresses and other aircraft representing 30-40 years of progress in aviation, and the contrast was stark and amazing to my youthful
Re: (Score:2)
Nice example! Technologies do plateau, the question is where. For classical computing we are pretty much there now. But we had a fed decades of rapid progress before and these things are very powerful and useful. For Quantum Computers, it looks like they pretty much plateaued as well or are about too, bit at a scale were they are pretty useless and a modern pocket calculator can beat them easily.
Re: (Score:2)
The belief that quantum computers will deliver complex results in an instant is like believing that you can add numbers of arbitrary precision with a slide rule. Theoretically possible, but only if a certain physical model was a complete description of the real world, which we know for sure it is not.
Re: (Score:2)
Exactly. Incidentally, the slide-rule example is limited pretty much by noise and measurement precision. The same is true for classical digital computers (at some scale and speed you are losing bits and digital computations become infeasible) and the huge success for classical computers comes from them having dealt very effectively with noise. It looks now like noise is the bane of QCs as well, but at a scale where they have not yet scaled to any useful size as classical computers hang that bar very high.
Re: (Score:2)
You are comparing apples and oranges. Nuclear fusion has at least two observable instances where it works large-scale: 1. The sun 2. Hydrogen bombs. Nothing like that exists for QC.
Re: (Score:2)
Any other technology this abysmally bad has just been scrapped.
Low hanging fruits. We first developed the easy technologies, in which the S curve had a short slow R&D start, then a relatively steep exponential growth curve, and a slowly developing plateau. Alongside that we stumbled upon classic computation, which had (emphasis on had) the most insanely steep exponential growth of all technologies developed before and probably will never be matched again. That one has now matured and plateaued too. So now we're entering the realm of hard to develop technologies tha
Re: (Score:2)
Plus, the amount of money put into one specific research topic should not be just based on media hypes. There are plenty of research fields that promise much sooner life-improving progress than the hypothetical quantum computers.
Re: (Score:2)
Indeed. And that is just my point. QC is a crapshot at this time. It may at some time be valuable, it is not today and will not be for a long time. That does not mean stop all research, but that does certainly mean do not prioritize it and do not put major emphasis in decision making on what it may or may not eventually deliver. Now, it is possible that at some future time some other tech becomes available that makes higher-intensity research into QCs a good idea, but at the moment this is not the case and
Re: (Score:2)
Risk analysis (for cryptographically protected data and communications) would say:
risk (real soon) = Medium or High because = probability=low x impact=ginormous (for now).
Also, I can see a group of natural philosophers sitting around 600 years ago in a drinking establishment (I drink therefore I am) listening to someone in a wooden armchair griping "You people have been yammering on about figuring out how things work for 2000 years now, and I
Re: (Score:2)
I disagree. After 40 years of failure, the probability("real soon") is at worst "low" but realistically "very low". And the impact is not "ginormous", but rather "moderate". That makes risk = low ... very low.
Even most encryption is not threatened. A working, scaling QC is nowhere near as magic as people believe. These things are useless except for a few tasks and even for them (factorization) they may have huge constants in their run-times.
Re: (Score:2)
My understanding was that grover's search and schorr's alg both dont have such bad constants. Thats why people have already been able to run toy examples to even though we've only built QCs with very limited number of qubits so far.
They have constants in real life that allows you to run toy examples in a matter of weeks or worse. Sure, the one good run was much faster, but do the researchers list how many bad ones they had and how much time that took? Also, you may get additional complexity from the real-world set-up. That would not show up in the toy examples or the theory, but it may well show up in practice.
A practical example is that when you run out of memory for a hash-table, you suddenly have to put it in SSD, then disk, then t
Re: No, they will not (Score:2)
https://www.google.co.uk/amp/s... [google.co.uk]
IBM begs to differ. And IBM doesn't beg very often.
Re: (Score:2)
Well, you haven't been reading their financial statements then.
Re: (Score:2)
IBM is desperate for relevancy these days. They are on their knees.
Re: (Score:2)
There are classes of secrets for which "decades" is a reasonable threat model. Communications can be an example. If I'm recording everything you send NOW, are you sure there's nothing in there that won't be a problem for you in 20, 30 years? Consider some person is going to be present of the US in 20, 30 years.
If you're on the Nation State side of this, recording everything you can and decrypting later is a totally legitimate strategy, as SOMEONE will be the leader of $otherCountry then, and having all thei
Re: (Score:2)
Consider some person is going to be present of the US in 20, 30 years.
Decryption: The inaugural unwrapping of the new US present.
Re: (Score:2)
I should be concerned over a QC that can factor 100 bit numbers? My RSA key is 2048 bit. No reason for concern at all.
Re: (Score:2)
Re: (Score:3)
That's probably not true. Quantum computers are more difficult to make the more qubits you need to stick together. In a conventional computer the "difficulty" of a computation is dominated by the number of operations. In a quantum computer it tends to be dominated by the number of qubits that are required.
Re: (Score:2)
True, but it's still a fixed cost for any given quantum computer and amortizes over a large number of operations that can be done by that computer.
And I'd suggest that this principle is only true today, while there are actual real inviolable reasons why factoring large numbers is hard for any conventional computer (unless P
Re: (Score:2)
"And I'd suggest that this principle is only true today"
Unlikely. It's fairly easy to make a qubit. It's fairly easy, but not trivial, to put a bunch of them on a chip. It's hard to put a bunch of them on a chip, have them highly coupled, and have them maintain coherence long enough to do something useful. And it gets harder rapidly the more you want to have, due to real physical limitations.
Re: (Score:2)
Indeed. This tech has scaled sub-linear for 4 decades now. It is very likely it will only get worse at larger sizes. It may well hit a wall at sizes far below what is needed to threaten modern encryption and it will certainly not get there anytime soon. These are not classical computing scaling factors were you got a factor of 16 in just 8 years for a long time.
Re: (Score:2)
So? If it is high-order polynomial, things stay secure. You can do public-key crypto with, say , effort n in in one direction and n^4 in the other. Requiring NP is just convenient and if you can get it, go for it. But it is not required at all.
Re: (Score:2)
And you just outed yourself as utterly clueless. There are no "rounds" in RSA. You are thinking of a Feistel-construction or the like, which is something completely different. Incidentally, I am in the know but you would not even understand what that means.
Re: (Score:2)
You have no clue what you are talking about. Due to fundamental physical limitations, QCs will never scale the way digital computers did for a long time.
Oh No!!! (Score:1)
Will this break all the foundational DRM on which all our good stuff depends?!?!?
Fusion power vs Quantum computing (Score:1)
Quantum computing is a good way to fleece investors, but that is about it.
No it will not (Score:1, Interesting)
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
Re: No it will not (Score:2)
Nobody has broken RSA.
Re: (Score:1)
Quantum proof algorithm? (Score:2)
Re: (Score:2)
Many of our existing algorithms, AES, ECDH, and others scale to the 2^(N-K) for N bits used in their keys with classical computers in terms of the operations to break them and that K is very small compared to the 64, 128, or 256-bits. Some of the proposed quantum attacks reduce these states by about the square root causing it to become 2^(N/2) operations. 2^32 states isn't that many for a classical computer to evaluate so 64-bit keys could reasonably break. 256-bit keys are reduced to 2^128 operations which
Re: (Score:3)
Lots of cryptographic algorithms are fine, or may just need longer codes. The hardest ones to replace are public-keys, where I think the front runners are lattice or error correction based (see NTRU and McEliece).
The other possibility is public key encryption dies, and we have to build some wacky network of symmetric encryption trust rings or something.
Re: (Score:2)
There are several:
https://en.wikipedia.org/wiki/... [wikipedia.org]
No worries (Score:1)
https://csrc.nist.gov/Projects/Post-Quantum-Cryptography
Don't panic, citizen.
Re: No worries (Score:3)
https://www.safecrypto.eu/pqcl... [safecrypto.eu]
Sounds like an ad for (Score:2)
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.
Re: (Score:2)
Bitcoin mining involves doing SHA256 hashes, that's not something you can do faster with a quantum computer.
Re: (Score:2)
Re: (Score:2)
sure, if you don't have the slightest clue what quantum computing actually is.
All it does is search a space of all possible states at once. Each real qubit added doubles the search space (power) of your computer.
QC is great for some problems that can be expressed as search problems. It doesn't do much otherwise.
That botnet can theoretically hash out stuff yes, but you aren't pooling that processing power, you are distributing it which causes it's own bottlenecks and headaches.
A quantum computer (they DO exist) can hash out faster than any of those combined.
Even if you assume RSA smashing quantum computers exist there is still no evidence they could put much of a dent in 'hashing out'.
the technology that QC can eventually provide us will literally remove the need for encryption. Unless you are at point A or point B, there's nothing to encrypt, listen to or steal. Spooky action at a distance is a real thing and it's spooky as fuck but potentially will change our entire techno-ecosphere for the better.
"spooky action at a distance" decides outcomes rather than conducts information. It can't be used to conduct information.
Problem with quantum en
Re: (Score:2)
-On the other hand, QC may make mining bitcoins much more economical.-
Isn't the expense of mining the only intrinsic value bitcoin has? If mining cryptocurrencies is economical then inflation in those currencies will make them valuless.
Re: (Score:2)
No, it's the other way around. The value of bitcoin determines how much effort people will put in mining.
The word "intrinsic" is misleading. Nothing has intrinsic value. Value always depends on context.
Re: (Score:2)
No, BTC's value proposition is in the hard-limited number of coins and in the ability to verify ownership via the blockchain. Also, like any other currency its value is in the collective actions of those who support it.
Re: (Score:2)
If Bitcoins suddenly became easier to mine, they'd just have to increase difficulty. It's not like there's a static amount of work to be done, and this will do it faster (which is good, as otherwise Bitcoins would rapidly lose value as computing improved). If they couldn't adjust the difficulty enough to compensate, the system would need major change.
But it would likely actually collapse for a different reason: QC could make spending other people's Bitcoins very easy - and thus make all of them worthless.
This again...? (Score:2)
How often can we rehash the same thing?
We've been saying this for how long now?
Re: This again...? (Score:2)
Hashes must repeat, limited outputs. if
And if... (Score:2)
That breaks RSA (Score:2)
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... [safecrypto.eu]
Phishing scams break the internet (Score:4, Insightful)
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.
Re: (Score:2)
Quantum safe is a NSA conspiracy (Score:2)
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.
Already been done (Score:2)
They made a movie about it [imdb.com]. 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.
It's why the summary is false (Score:2)
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
Only broken for a while (Score:3)
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.
Quantum computers are useless (Score:2)
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.
Finds the period of a function - doesn't factor (Score:2)
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 differen
Remember when you thought privacy existed? (Score:1)
Future Algorithms - difficulties today (Score:2)
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
Real quantum computers do not yet exist (Score:2)
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.
Communication via Entanglement makes this obsolete (Score:2)
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.
Re:Second article this year Iâ(TM)ve seen abo (Score:4, Funny)
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.
Re: (Score:1)
Really? A problem that required billions of dollars and millions of man-hours to fix worldwide wasn't a big deal?
Re: Y2K (Score:2)
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 wide
Re: So what (Score:5, Informative)
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).
Re: (Score:3, Informative)
How is quantum-resistant crypto research going? (Score:2)
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.
Re:How is quantum-resistant crypto research going? (Score:5, Informative)
In general. parent is saying ECC is still probably safe
The problem with ECC is the damn NSA. Fifteen or so years ago the NSA strongly endorsed moving to ECC to get ahead of the risk of quantum computing. Sadly, the specifics they suggested were poison: what the proposed was weak in a way the NSA knew about, but they hoped no one else would ever figure out. There's a lingering distrust for ECC as a result, perhaps unfairly.
And there's no good reason to choose ECC for "post-quantum" crypto when there are good alternatives [wikipedia.org]
Re: (Score:2)
ECC is not post-quantum, it relies on the discrete log problem for which there are good QC algorithms.
https://en.wikipedia.org/wiki/... [wikipedia.org]
Check it out. Supersingular isogeny Diffieâ"Hellman key exchange uses ECC operatins, but is post-quantum and not patented.
Re: (Score:2)
... quantum computer cryptanalysis would also destroy all existing blockchain implementations and cryptocurrencies.
I fail to see the problem.
Re: (Score:1)
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.
Re: Yeah but.... (Score:2)
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.
Re: (Score:2)
utterly amazing how well that movie aged, isn't it?