This is a non-issue IMO. Contrary to popular belief QCs are not magical oracles that can do arbitrary exponential calculations in polynomial time. Instead QCs can do only very specific things better than conventional computers and there are a surprisingly low number of known algorithms for QCs even though people have been looking. While it's true that Shor's algorithm allows a QC to potentially factor integers in polynomial time breaking RSA, there are other popular encryption schemes with no known quantum weaknesses and there's a whole field called Post-Quantum Cryptography looking at this property explicitly.
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.
You probably mean well, but this is dangerous misinformation. There are no popular public-key encryption schemes that are safe against quantum computing.
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.
I'm not pessimistic about them. I'm actually (weakly) pessimistic I'll see significant cryptographic breaks due to large scale quantum computers within thirty years. We are very, very far off from quantum computers that can break RSA or even elliptic curve systems (which are a bit easier to break for quantum computers). Google's Bristlecone has 72 physical qubits but I don't recall seeing any published information about how many logical qubits they managed to achieve.
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.
> even if we can achieve 50% improvements in quantum error correction and stability year over year for over a decade
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.
I'm not ignoring that, I'm just treating it exactly as it is: very unlikely. All sorts of things could happen, but what could happen - independent of quantifiable likelihood - is not a realistic baseline for a risk modeling exercise.
That's not comparable. Fukushima's failure was due to fairly basic and straightforward precautions being in error or missing entirely. In other words they were avoidable, known knowns. In contrast we do not actually know how to achieve a breakthrough in quantum error correction except through the normal course of research. We don't just have known unknowns presenting obstacles to the path forward, we have unknown unknowns which must be resolved before further breakthroughs can be achieved.
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.
SIDH keys can be as small as 330 bytes. That's not much bigger than a modern RSA key. Lattice keys are also in the (higher) hundreds of bytes, and were briefly (as an experiment) deployed in Chrome.
In fairness, SIDH trades off the tiny key sizes for a slower key exchange time. Personally I think there's more potential in getting lattice keys smaller since the LWE-type systems are fast.
I think some combination of a web-of-trust and symmetric cryptography (or even OTPs for the really scary stuff, like code updates to self-driving cars) will work if we need them to.
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.
Not sure why you're greyed out (hopefully not because you're being downvoted) because you're absolutely right - all asymmetric cryptography we have right now will be broken.
On the other hand... I doubt we'll have working quantum computers for at least the next 500 years.
Instinctively, I want to think that post-quantum crypto means both ends. That is to say, if it transpires that quantum computing can break all pre-quantum encryption schemes, it ought to follow that there will be post-quantum encryption schemes that it can't.
I don't understand quantum computing well enough to know if that's a reliable instinct though. Is it anywhere near the mark?
No, that's not really correct. The theoretical capability of a quantum computer to "collapse" to optimal routes to solutions during computation does not imply the existence of cryptographic trapdoor functions which are likewise intractable. More concisely: the existence of a quantum computer does not imply the existence of problems it cannot solve. They're orthogonal things.
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.
"Damgerous misinformation" to say quantum computers are not magical oracles? The entire subject of QC is literally a hoax! The only danger is that if people dont think they are magical they might want to cut off the funding. If I were to say I know a magical oracle who can break encryption with pure thought, it wouldnt be much different than the kinds of claims you hear about quantum computers on a daily basis. I used to do experimental physics for many years, all of my colleages and I thought quantum computers were a joke. Main stream physics people understand there is an intense debate over whether or not its even possible to build a quantum computer. Nothing to see here, its just the QC hype train doing its thing.
I said this in another comment, but there's two sides to this QC thing: People who think QCs are magic and can do everything, and people who think they know better when they tell people that QCs are not magic and cannot do everything. In reality, you're both slightly skewed. To undermine the potential of QCs is a blunder, as big a blunder as thinking they can do everything. The hype train is exactly where it needs to be.
There isn't a debate about whether it's possible since it's already been done...
Your comment is either lacking context to explain what you really mean or simple fabrication. Neither is acceptable
What I meant was the debate which has been taking place in the main stream of physics for many years now is whether or not its possible to build a quantum computer on the scale where it can do anything useful. In the article we read:
>> 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.
Thanks for the additional response. I agree that there are fundamental technical questions that are very difficult.
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.
Yeah, because peer review does such a good job of winnowing out bad 'research.' Which is why we are now a nanotech economy running on controlled nuclear fusion reactors.
Physcial qubits currently suffer from noise problems and so logical qubits have to be simulated. You can't just implement them directly in a scalable way in hardware. So, you could say that a meaningful, scalable quantum computer of any kind has not yet been built. You can certainly say that a quantum computer capable of breaking real world encryption is very far from current reality.
Saying there's a lot of work to do and it's unclear whether there will be a practical solution in our lifetimes is very different from calling it a hoax. Comment even makes an absurd appeal to authority. It's intellectually dishonest and doesn't belong here
He/she does go on to explain what they mean by that: press releases deliberately talk up the `magical' aspect of quantum computing, and this is at least in part necessary for further funding. You can argue about whether the word `hoax' is warranted. But I didn't misunderstand the sentiment. It's not an antiscience claim, but merely hyperbole to drive home a point.
You can literally sign up for D-Wave Leap and submit problems to their quantum annealer for free. How much more real does QC need to be before people believe it?
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.
I imagine that state intelligence agencies are logging all encrypted communication today in the hopes that it will be much easier to decrypt them at some point in the future. That’s terrifying.
Yeah, I was working in cutting edge storage a while ago and heard the biggest customers were Facebook and “a three letter acronym we can’t talk about”. This sort of infrastructure might be cool to work on, were it not for the fact that it violates the constitution and is counter to the public good.
I think they're trying to say OP made a contradiction. On one hand, they think its a non-issue, yet on the other hand they admit that when quantum becomes an every day reality we will have to change everything.
I think the theory is that at the time QC is starting to threaten current encryption there will be new algorithms available and the transition will be not difficult. Seems pretty likely.
There's always someone in these threads who thinks they are blessing people with knowledge that QCs are not as powerful and amazing as people think. While it's certainly a revelation to know that, it doesn't tell the full story. QCs are still able to perform those specific tasks really well, and we haven't even begun to get our hands on a personal quantum computer which will ultimately give rise to more algorithms and general discoveries about them. It's not like the internet is done when QCs come into play, but there's always someone who thinks they have an unpopular opinion about the power of quantum computers when in reality both sides are usually biased or misinformed.
It's interesting to look at this through the lens of startup creation. Here is an example of something where there will clearly be customers that need assistance from technologically sophisticated companies. Quote:
"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.
Are you imagining something akin to the Y2K-style surge in COBOL consulting jobs? I imagine it could be lucrative, but I also imagine most companies will just drag their feet as long as they can, so it will be a frustrating sales experience as it always is absent a clear deadline or at least significant time pressure.
If you are good at hyping up vaporware then now may be a good time. If you are interested in really helping people it will probably take many years before there is anything real to do.
I'd like to see quantum computers actually do anything practical, anything at all, instead of making wild promises of what they might or might not be capable of. Stop promising, start delivering.
Do you keep up with the development of QCs at all or are you just an eager consumer? They're only able to make QCs with a small number of qubits at the moment and can't add more without running into sound disruption issues so it's a ways away from being able to do anything practical.
I'm far from convinced about QC yet, but the first transistor was in 1947 and now the CPU in my phone has over 3 billion. Looks like they took 30 years to get from that first transistor to the TMS 1000 with 8,000 transistors on it.
I'm on Mobile and having a hard time finding the link but I'm pretty sure the Google quantum computing team (and probably others) have built low qubit computers that have factored numbers into it's prime factors.
With Shor's algorithm (the thing that would make this headline about "Quantum computers will break the encryption that protects the Internet" true) AFAIK the answer is that quantum computers have found 21 = 7 x 3
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.
Breaking crypto makes for a good headline but the most important application of QCs will be simulating quantum states, eg modeling molecular interactions. And obviously there is plenty of work that remains to be done in this nascent field.
Adding to that: I heard that in modern chemistry there are trillions of experiments to be run and not enough time to run them all. Using QC to cull the search space can lead to discovery of some very interesting compounds. This could be “the industrial revolution” of the field.
I’m concerned with the ability of conventional computers to keep up with cryptography in the quantum age of computation. But can’t we just jack up the current algorithms to have higher order problem sets to solve? In other words can’t we turn something like a SHA-256 into a SHA-2048 and take a hit on the time complexity to generate such cryptographic (in this case a hashing algorithm) products? Can’t we just scale up the problem size and assume that the solution will be exponentially more difficult to solve?
I see this playing out similarly to the Y2K situation. There will be a race to upgrade all cryptographic security measures currently in place to handle the new power in computation. In the beginning however those who would have access to such power would make a mint supplying a service (AWS and the like) to compute these products.
Y2K was a trivial issue that everyone knew how to fix for decades. Computing was important to how the world ran, but not nearly as ubiquitous as it is now. It still took a large effort to upgrade everything for Y2K.
Cryptography is based on "hard problems", something that is easy to solve one way, but hard the other way. Quantum computers provide algorithms that can severely break some of these (namely RSA with Shor's Algorithm https://en.wikipedia.org/wiki/Shor%27s_algorithm), and speed up all the others (namely Grovers Algorithm https://en.wikipedia.org/wiki/Grover%27s_algorithm). So it's not possible to simply increase bits to ensure algorithms are still secure, but it will work for most of them.
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.
This is not true, symmetric block ciphers (AES) are at worst about halved in strength.
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.
In that case can we start computing cryptographic products with quantum computers such that there is no gap? If we reduce the time complexity of factoring a prime number to linear wouldn’t we be able to produce larger cryptographic products? Effectively going back to where we started but with more computing power? Surely this would require easy access to quantum computation to be practical and thus a gap in power, but necessity would drive the market to make this type of power more mainstream.
> In that case can we start computing cryptographic products with quantum computers such that there is no gap?
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).
This is no news for the academia, more particularly for theoretical mathematicians. It's a well known fact that RSA and all other cryptography methods based on basic number theory results, will become useless with the appropriate usage of QC. Mathematicians have already suggested that non-commutative group-based cryptography is the appropriate solution to this issue. Yet, there's no ideal group that seems to be the right fit, for the proper implementation of these new, secure algorithms. The braids group used to be an ideal example, until it was found to be linear, thus heavily exposed to linear-based type of attacks. So, the only part that remains unsolved is which group could be ideally defined to support the theory that addresses this issue. Mathematicians are already aware of this challenge, perhaps this post by The Economist suggests that more funding should be given for the according research.
And there are methods to defend crypto against QC. New algorithms will become more popular as quantum computers become more capable. It is a problem we will face someday and it’s good to start thinking about it and working on it now.
5 years ago most people didn't care about encryption. Most websites, disks, E-Mails, USB sticks, downloads were unencrypted - this hasn't changed much. Not to mention the software pool on closed-source Hardware. I'm not exactly sure who would have to be afraid of what. :-)
I wonder if you could significantly increase the qubits required by layering or interleaving cryptographic functions.
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.
QCs will likely break existing crypto currencies. Which begs the question - if someone does own a QC how much crypto can they steal without devaluing the currency in the process.
Why are we so worried about quantum computers when there's backdoored random number generators (Dual-EC DRBG) and stuff in play? I just don't understand it.
You're falling into the fallacy of relative privation. "Why are we so worried about __________ when __________?", implying that you can't be concerned about both.
Not sure what you mean by in play. Dual EC DRBG was widely discredited in 2013/2014; it's not part of the gamut of viable cryptographic tools anymore. Anyone still using it today is hopelessly out of date, but that's a different problem entirely than the threat/promise of quantum computing.
At one point I thought I had found a fast factoring algorithm but I found that the internet no longer much depends on the difficulty of factoring large numbers and stopped work on the project.
Elliptic Curve encryption for example does not depend (AFAIK) on the difficulty of factoring. (please tell me if this is wrong)
Elliptic curve crypto (the kind that is in common use, like ECDH) is just as broken by quantum computers as RSA.
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).
The other answers have given good info, but speaking to your supposed factoring algorithm in particular - most of the internet's public key cryptography still relies on factoring problems. Your algorithm would be enormously useful and dangerous. You would likely be able to break anything that reduces to the hidden subgroup problem using it, which means you'd be breaking both elliptic curve and non-elliptic curve systems.
There are many applications of a fast factoring algorithm in number theory, and many people who would love to get their hands on one for that reason. You'd be exceptionally famous if you developed a very fast algorithm for this. That is to say nothing of the fact that it would say something about the fundamental complexity of various problems.
At some time we shall discover that Shor’s algorithm is polynomial but the greatest monomial has a constant of size 10^30000 and we shall go on living.
The problems arise when data is intercepted now. Sure, some encrypted information won’t be useful/sensitive once the advent of cryptographically significant quantum computers comes but if any packets are simply stored now and saved for the future, that encryption will be rendered broken and the information leaked once there’s a practical Shor’s/Grover’s implementation.
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.
That’s true, but the absolute values of the timeframes involved are quite different. Classical computing is speeding up, for sure, but breaking RSA-4096 (as an example) will take significantly longer to be feasible than the 10-20 year estimate for quantum computers. That’s assuming that classical computers are still roughly following Moore’s Law. For quantum computers, the difference between RSA-2048 and RSA-4096 is pretty negligible (it’s linear) while it’s exponentially more difficult for classical computers.
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.
Unfortunately that’s a problem regardless of quantum computing because the computational power of classical computing continues to even without the threat of QC on the horizon.
PFS is not magic, it depends on exactly the same type of trapdoor algorithm as other asymmetric cryptography but using randomly chosen keys which are then forgotten. Forgetting the keys + Breaking them being too hard = Forward Secrecy. If someone finds out the key later, they can decrypt the messages, just as if they'd been told it at the time.
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.
That's only really useful in key exchange scenarios (DH/ECDH). A lot of implementations use RSA or similar to directly encrypt packets of information, though it's generally not recommended for reasons such as this.
If QC were able to factor primes, discover alternative inversions of noninvertible matrices... the obvious uses would be monetization, hacking and other legal and illegal crimes: crypto mining and hacking banking and finance.
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.