Quantum computers will break the encryption that protects the internet
economist.com
economist.com
And just like upgrading SSL 3.0->TLS 1.1->TLS 1.2->TLS 1.3 was done due to discovered weaknesses yet mostly transparently and with no Y2Kish hype of "the internet is broken", so will we upgrade to quantum resistant algorithms if and when QCs become a reality.
The only popular public-key encryption schemes are based on RSA and ECC, both of which are broken by variants of Shor's algorithm.
Yes, popular symmetric cryptography is safe to the best of our knowledge, but that doesn't help much since virtually all symmetric crypto that is actually applicable at scale relies on some initial public-key crypto for bootstrapping.
And yes, there's research into post-quantum public-key cryptography, but it's pretty underwhelming so far. It seems possible, but at a horrible loss of performance (keys are sized on the order of kilobytes or more, as opposed to 32 bytes for ECC).
I'm pretty pessimistic about the consequences of quantum computing, to be honest.
Shor's algorithm requires O(n^3) time and 3n logical qubits to break an n-bit key. The state of the art in quantum error correction requires high tens of thousands to low hundreds of thousands of physical qubits to achieve the logical qubits needed to break a typical 2048-bit RSA semiprime. 4096-bit keys are even farther off.
Research in post-quantum cryptography is really important, but I think you should take most of the non-scientific reporting about quantum computing and cryptography with a (large) grain of salt. The Economist is actually very level headed in its coverage here and it still neglects to mention that realistically we're far off, even if we can achieve 50% improvements in quantum error correction and stability year over year for over a decade.
I also think you're being too uncharitable to post-quantum cryptography. You'll find that many of the lattice-based systems (particular the various flavors of LWE) are very fast (and getting faster) and perform reasonably well in real world experiments. I'm cautiously optimistic we'll have lattice-based schemes with keys smaller by an order of magnitude in a decade, and very optimistic we'll have achieved that before 2048-bit RSA can be broken on a quantum computer.
You seem to be ignoring the possibility of a technological breakthrough that will produce a major improvement in QEC in one fell swoop. Granted that is unlikely, but it's not impossible. And given what is at stake, I think it's a possibility that needs to be taken seriously despite the long odds.
Except in the case where the result of a low-likelihood event is potentially catastrophic, c.f. Fukushima.
For that reason postulating when and how we'll have a giant leap forward in quantum error correction is closer to thinking about how to resolve the Riemann Hypothesis or Navier-Stokes, or when a deadly asteroid might finally be on a collision path with Earth. It's reasonable to be concerned about quantum computing's risk to cryptography, but it's infeasible to productively model whether or not we'll suddenly jump forwards by decades in research time.
To state this another way: if the most informed thing you can state about the likelihood of an event is that it could happen, it's probably not feasible to model the likelihood of that event in a way that makes risk assessment productive.
Take Apple (my dev machine) or DigitalOcean (my server provider. They already have root. If my MBP came with a custom-to-me symmetric key to communicate with Apple I could get a signature from them of the symmetric key that DigitalOcean generated for me.
The real issue is that everyone is reactive so these types of things don't get fixed until there's a proof-of-concept attack that works. I remember people talking about how states would propagandize social media platforms in the early 2000s and nobody took them seriously; myself included. Though I never mocked them because I didn't see how they were wrong I just saw no evidence that it was happening so I figured someone else was already on it.
Nobody is magically on it. National security podcasts are stressing about quantum computers because they know it's probably going to break PKI.
The thing I still don't understand about quantum is that it seems to break entropy once you get enough qubits because it covers too many options at once. I keep meaning to experiment with it to understand it better, but I don't have enough time.
And that if a system isn't 'popular' right now it doesn't count?
You have a strange standard for 'dangerous'.
On the other hand... I doubt we'll have working quantum computers for at least the next 500 years.
If you mean personal quantum computers, commercially, I would give it about a century, give or take a decade.
Running stable at 0.004K for only a few milliseconds in a lab is not practical.
https://www.forbes.com/sites/fredcampbell/2018/03/14/how-cap...
I don't understand quantum computing well enough to know if that's a reliable instinct though. Is it anywhere near the mark?
That being said, Mahadev's recent research constructing a quantum verification protocol using the LWE is exciting along similar lines to what you're thinking. It allows us to say with authority that one of the following must be true:
1. LWE protocols are not post-quantum resistant, or
2. Quantum verification is possible via LWE-based cryptography.
>> When Dr Shor made his discovery such computers were the stuff of science fiction. But in 2001 researchers at ibm announced that they had built one, programmed it with Shor’s algorithm, and used it to work out that the prime factors of 15 are three and five. This machine was about the most primitive quantum computer imaginable.
The context which was lacking is that I meant on a large scale and not simply the most primitive thing. And no I am not fabricating anything, see here [1] for some of the main stream discussion by someone who is more articulate and knows more about it than me.
Let's keep in mind that just this week it was announced that a grad student figured out an algorithm to verify that the computations done by hypothetical quantum computers actually are giving a correct answer [2].
I seriously don't think you know what you are talking about when it comes to the idea that its "already been done", D-Wave is not a "quantum computer" in the sense of this article or shors algorithm.
However, you are correct that my comment was overly hyperbolic and lacking context. Next time this comes up on here I will try to do a better job and not use phrases like "its a hoax" because to be honest, its not a hoax, it might be possible one day they will exist. I personally believe at that point there will be so many other advances that non quantum computers will simply outperform everything else.
[1] https://www.quantamagazine.org/gil-kalais-argument-against-q...
[2] https://www.quantamagazine.org/graduate-student-solves-quant...
As an aside, I'm actually well versed in the difference between quantum annealing and Turing like computation as I got my PhD in an ultra cold atomic physics lab.
Sure, it's not a gate model, but they have a pile of working, useful applications already. Significantly more useful than anything MS is doing on the topic, that's for sure.
Sorry, I don't think your words make sense.
"Mr Steel says one of his clients has thousands of apps that need updating. As chips migrate into everything from cars and children’s toys to lighting systems and smart electricity meters, the amount of work will only grow."
The need is clear and there is even a timeline. NIST is planning to release proposals for quantum-resistant algorithms in 2024. According to the article, Brian LaMacchia, an expert from Microsoft, predicts availability of a “cryptographically interesting” quantum computer in 2030 to 2040.
The question is, when does it become sensible to start a company intended on serving the millions of other companies who will need assistance making this sort of transition? It feels too early now, but is it? Are there sensible steps to be taken now? If you're reading this and you happen to be fifteen years old, thinking about what you might want to launch when you get out of university, is this something worth diving into?
The uncertain timeline carries considerable risk, but if you wanted a shot at building a sustainable company that might be worth tens of millions in two decades, this problem seems like an obvious candidate.
https://en.wikipedia.org/wiki/Transistor_count#Microprocesso...
I just thought that was interesting...
Because of interest in using quantum computers to factor big numbers there's a reason to do something other than Shor's algorithm with a big machine that can't run Shor's algorithm and thus get a big impressive number. This approach has factored six or seven digit numbers. Which your PC could also trivially do, and it doesn't use Shor's algorithm either.
Also obligatory link to the best quantum computing blog out there: https://www.scottaaronson.com/blog/. Very good at dispelling hype.
You can see round one submissions on the left.
On the bright side there is also a branch of cryptography called post-quantum cryptography, which is a collection of algorithms designed to be more resistant in the face of quantum computers https://en.wikipedia.org/wiki/Post-quantum_cryptography.
Asymmetric crypto that depends on prime factorization or discreet logarithms (such as RSA and EDSA) are indeed fatally weakened by large enough quantum computer, but it is not a problem for other mathematically one way "hard" crypto constructs like hash trees or the McEliece cryptosystem.
QC solves one kind of problems, that are hard for classical computers, but not another (see all the links to post-quantum crypto in the comments). OTOH there will be a very large window during which QC will be cheap enough to rent by the hour on AWS, but equipping every lightbulb with a QC will be prohibitively expensive (think current GPU prices).
Current state of the (disputable) art: less than twenty.
By interleaving I almost imagine something like an AES algorithm where the rotated bits actually reference new keys and ciphers that are actually used on the data.
Elliptic Curve encryption for example does not depend (AFAIK) on the difficulty of factoring. (please tell me if this is wrong)
The quantum algorithm that breaks RSA (Shor's algorithm) does it by efficiently solving the hidden subgroup problem[1] for finite Abelian groups. This can be used for factoring integers (which breaks RSA) and also for solving discrete logarithms (which breaks elliptic curve crypto).
Store those packets long enough and even ordinary, non-quantum computers will become fast enough to factor the requisite large numbers within a reasonable period of time to unlock the comparatively primitive encryption which had been in use back when the packets were captured.
We're really just saying that quantum computers could theoretically decrypt those old stored packets sooner than the non-quantum computers will be able to do it.
But the non-quantum computers will definitely be able to do it someday. Those stored packets are not staying encrypted forever, regardless of whether or not quantum computing is eventually made to work effectively and efficiently and economically.
10-20 years a short enough timeframe that all sorts of PII could remain useful. Some people haven’t changed their passwords in a decade or two. If you extend those timeframes out over 100+ years then the sensitivity of PII begins to decline pretty significantly, though admittedly not to zero.
A Quantum Computer that breaks say, 2048-bit RSA also breaks the PFS-enabled Diffie-Hellman style key exchanges, it's almost exactly the same trick, a variant of the Discrete Logarithm Problem.