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.

Comments

So what?

[forkfail]

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?

[mark-t]

If you're not guilty, you have nothing to hide.

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?

[mwvdlee]

Governments encrypt everything, so they would know best.

Re:So what?

[Rick Schumann]

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: So what?

[Your.Master]

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 nothing to hide" is a troublesome statement and it's not really similar to why people wear clothing.

No, they will not

[gweihir]

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:No, they will not

[ceoyoyo]

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:Second article this year Iâ(TM)ve seen abo

[nitehawk214]

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: So what

[Anonymous Coward]

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).

Phishing scams break the internet

[edi_guy]

Really...people are still worried about the front door attacks? Not too long ago, my employer w/ >10,000 employees hired a company to send out fake phish emails to see who would take the bait and click. Over 15% of the people clicked on the bogus link. Extrapolating, would indicate that there are 1,500 times from one single email, that a bad guy could pwn our Fortune 500 company. Probably already does.

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: No worries

[jd]

https://www.safecrypto.eu/pqcl...

Re: So what

[thechemic]

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.

Only broken for a while

[HeckRuler]

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.

Re:Quantum proof algorithm?

[JMZero]

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:How is quantum-resistant crypto research going?

[lgw]

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