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.
So put other quantum computers to work finding even larger primes thus continuing the prime arms race that exists today
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.
New Headline: Quantum computers will create new protection to protect the internet.
Slashvertisement?
https://www.forbes.com/sites/forbestechcouncil/2018/04/18/worse-than-y2k-quantum-computing-and-the-end-of-privacy/
This is worse than y2k
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.
Olds for nerds
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.
AFAIK elliptical curve cryptography isn't as vulnerable to Quantum Computing as number factoring. Symmetric algorithms only need to double the key length from say 128 bits to 256 bits to gain the same level of protection, since a Quantum Computer only reduces the key space by the sqrt(2).
Also, we're still a LONG way away from having a quantum computer than can even factor very short prime numbers of say 4 digits, something you can do by hand. RSA relies on numbers that are hundreds of digits long.
So don't hold your breath about quantum computers that can solve these problems. We'll get their eventually, but it'll likely be decades before we do.
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
...can they do it far faster than any conceivable classical machine?
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
Nobody will post a more apt comment than my title alone.
There is nothing to worry about.
SIDH in Go for quantum-resistant TLS 1.3
It's the crappy mega corporations that we cannot necessarily trust with our security but even stinking Google has stepped up!
TSL is already moving to quantum algorithms. Microsoft have developed a version of Open VPN that is also quantum resistant.
Isn't this only an issue with public-key encryption? So RSA key exchange, etc?
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)
In another decade all the idiotic VCs will be wondering how they got taken again...
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.
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.
whatever you say
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?
On a wide spread , easily accessible to bad guys basis... sure.
Or something else will come along in classical computing.
It's not like TLS 1.0 was good enough to last forever. Our best encryption today will be obsoleted by SOMETHING... QC simply accelerates that timeline.
Next article, please.
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
Will? Who's Will?
Ok, so quantum computer will break all currently known encryption. That was expected eventually. BTW, thanks a fucking lot, quantums. You've ruined everything.
Solution: Use these quantum computers to encrypt the data, so only the NEXT breakthrough technology will be able to break it.
I read this thinking, "this is news? In 2018, on /., this is news??"
How long has /. been publishing stories on this subject? How long has this been known and accepted by the tech community? Ten years? Twenty?
In fact quantum logic has been developed, quantum algorithms, and primitive quantum computers. So no, this isn't news.
"Dog bites Man is not news. Man bites Dog, now that's news!"
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.
The article talks about quantum computers as if they actually exist. For a purpose such as implementing Shor's algorithm to factor a 512-bit number, they do not and are nowhere close to existing.
In fact, Shor's algorithm has *never* been implemented, on any scale, on any quantum device. Over a decade ago there were headlines about quantum computers factoring very small numbers (15, and later 21), but these toy computations did only the "easy" part (the logic) of Shor's algorithm. The hard, numerical part was replaced by a table lookup. A table of 21 entries was a challenge for a quantum device, but a table of 2^512 entries is not physically possible in our universe. In any case, allowing that much pre-computation, even a classical computer can "factor" a number in constant time.
Quantum computation is fascinating subject for mathematicians like Peter Shor to ponder, but whether it will ever be practically realized in hardware remains an open question.
It's sufficient evidence that noone actually working in the field did proofread that article.
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!
Just because "billions of dollars and millions of man-hours" was spent on it doesn't mean that is what was required
Consultant Fees all the way down
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.
Does "guilty" mean: "opposing government policy"?? Does it mean opposing irrational social mores ?? Are such possibilities part and parcel of "Guilt" ?
Has "guilt by association" been replaced by: "Guilt by Thinking?"
and what happens when the 'code' used by a brain is 'broken'? ... we are not far from that irreversible future!
There is no evidence that quantum computers work the way they say they do. None. After decades of research.
Normally that should exist before the decades of hype, not after.
This article is rife with false assumptions. The first assumption is that the only viable encryption method on the internet is public key encryption. Granted, public key encryption is the lazy man's preference, because it takes less work on the part of all parties to encrypt and decrypt messages. But this article exposes the weaknesses in public key encryption, and inevitably, public key encryption will be rendered obsolete.
The second false assumption is that quantum computers are so strong, that they can decrypt the most powerful encryption methods known to man today, such as one way hashes.
That assumption is dubious at best, because quantum computer advocates have yet to show how they can crack a seed that gives the permutations of 134217728 or larger on a 64 bit classical computer with 32 gigabytes or more of memory, where the message digest is encrypted back to back 128 or more times with unique seeds each time. The point is that such an encryption method is unwieldy if implemented all over the internet, because the management of so many seeds is a nightmare.
Nevertheless, quantum computer advocates cannot go around boasting that they can decipher absolutely any type of encryption method because of the way quantum computers process in parallel.
I have nothing to hide
from people I completely trust.
To my understanding there are algorithms already available to defeat Quantum computers for some time.
Lattice-based cryptography
Multivariate cryptography
Supersingular elliptic curve isogeny cryptography
Symmetric key quantum resistance
They are not to expensive computationally and are available today?
y2k would have been problematic if so much remediation was not done in the 90's