How Many Qubits Will It Take to Break Secure Public Key Cryptography Algorithms? (googleblog.com) 36
Wednesday Google security researchers published a preprint demonstrating that 2048-bit RSA encryption "could theoretically be broken by a quantum computer with 1 million noisy qubits running for one week," writes Google's security blog.
"This is a 20-fold decrease in the number of qubits from our previous estimate, published in 2019... " The reduction in physical qubit count comes from two sources: better algorithms and better error correction — whereby qubits used by the algorithm ("logical qubits") are redundantly encoded across many physical qubits, so that errors can be detected and corrected... [Google's researchers found a way to reduce the operations in a 2024 algorithm from 1000x more than previous work to just 2x. And "On the error correction side, the key change is tripling the storage density of idle logical qubits by adding a second layer of error correction."]
Notably, quantum computers with relevant error rates currently have on the order of only 100 to 1000 qubits, and the National Institute of Standards and Technology (NIST) recently released standard PQC algorithms that are expected to be resistant to future large-scale quantum computers. However, this new result does underscore the importance of migrating to these standards in line with NIST recommended timelines.
The article notes that Google started using the standardized version of ML-KEM once it became available, both internally and for encrypting traffic in Chrome...
"The initial public draft of the NIST internal report on the transition to post-quantum cryptography standards states that vulnerable systems should be deprecated after 2030 and disallowed after 2035. Our work highlights the importance of adhering to this recommended timeline."
"This is a 20-fold decrease in the number of qubits from our previous estimate, published in 2019... " The reduction in physical qubit count comes from two sources: better algorithms and better error correction — whereby qubits used by the algorithm ("logical qubits") are redundantly encoded across many physical qubits, so that errors can be detected and corrected... [Google's researchers found a way to reduce the operations in a 2024 algorithm from 1000x more than previous work to just 2x. And "On the error correction side, the key change is tripling the storage density of idle logical qubits by adding a second layer of error correction."]
Notably, quantum computers with relevant error rates currently have on the order of only 100 to 1000 qubits, and the National Institute of Standards and Technology (NIST) recently released standard PQC algorithms that are expected to be resistant to future large-scale quantum computers. However, this new result does underscore the importance of migrating to these standards in line with NIST recommended timelines.
The article notes that Google started using the standardized version of ML-KEM once it became available, both internally and for encrypting traffic in Chrome...
"The initial public draft of the NIST internal report on the transition to post-quantum cryptography standards states that vulnerable systems should be deprecated after 2030 and disallowed after 2035. Our work highlights the importance of adhering to this recommended timeline."
And 4K RSA? SSH keys? (Score:2)
I think most of my SSH keys are 4Kb RSA. If they need a million qubits for 2Kb, do they have to square that for 4K?
Is there a good post-quantum recommendation for ssh keys?
Re: (Score:2)
Stay with that 4096 bit key. Nobody is going to break it in the next 100 years.
Re: And 4K RSA? SSH keys? (Score:2)
Re: And 4K RSA? SSH keys? (Score:4)
Re: (Score:2)
What are you worried about? If it's keeping an ssh connection secure, if you hear about someone that's not DWave inventing a half million qubit quantum computer then toss both your EC and RSA keys and use Kyber.
If it's keeping data secret and you really want to keep it that way forever, use AES. AES512 if you're paranoid.
Re: And 4K RSA? SSH keys? (Score:3)
"If they need a million qubits for 2Kb, do they have to square that for 4K"
If they did, it seems like that would be a problem for the first 2Kib. Following that logic, 1000 qubits could handle 1Kib, and 32 qubits could handle 512 bits (which it obviously cannot).
Re: (Score:2)
Re:And 4K RSA? SSH keys? (Score:4)
So I guess for 4 kb RSA, maybe that becomes 1.4 million noisy qubits and 10 days.
Both those numbers seem crazy large to me given where current state of the art Quantum computing is.
Holding a quantum state for a week while Grover's algorithm runs all it's iterations seems very, very far away to me.
Re: (Score:2)
You use Shor's algorithm on RSA. It's order log(N).
Grover's algorithm would work on things like AES. If you can get it to work at all, which is iffy even compared to Shor's algorithm.
The N isn't the key length, it's the search space. RSA's search space is, roughly, N = 2^n where n is the key length in bits. 2^4096 / 2^2048 is 2^2048 so a 4096 bit key is ridiculously stronger than a 2048 bit one. BUT, if you have a quantum computer that can run Shor's algorithm on it, log(2^4096) / log(2^2048) is only 2. Tha
Noah: (Score:2, Funny)
What's a qubit?
Re: (Score:3)
Nobody else will probably get the joke, but I did!
Re: (Score:2, Informative)
I did not, but ChatGPT 4o did and explained it to me:
ChatGPT said:
The joke "Noah: What's a qubit?" plays on the similarity in sound between "qubit" (a concept from quantum computing) and "cubit", an ancient unit of measurement famously used in the biblical story of Noah’s Ark.
Here’s the breakdown:
In the Bible, Noah is instructed to build the Ark with specific dimensions given in cubits.
A cubit is a historical unit of length, roughly the length of a forearm (about 18 inches).
A qubit, on the other
Re:Noah: (Score:5, Informative)
It's more specifically a reference to a Bill Cosby bit [youtu.be] about Noah getting direction from THE LORD to build the Ark and make it however many cubits in size.
Re:Noah: (Score:4, Informative)
"How long can you tread water?"
Re: (Score:2)
Sahwing and a miss! AI failed you.
It's a reference to a Bill Cosby joke routine about that subject.
Re: (Score:1)
Did you read what ChatGPT said? It literally explained the concept behind the joke. The only thing it didn't do is correctly attribute it to a rapist comedian.
Re: Noah: (Score:2)
Which ironically it was likely explicitly coded by hand not to do.
Re: (Score:3)
ChatGPT explained the biblical context. But, the quote AC was referencing in his GP was a direct reference to the specific comedy bit that was done by Bill Cosby.
One is a biblical story. The other is a joke about the biblical story and who caught the reference to the joke. You missed it, even after the joke was explained. I'd have thought a smart guy like you could have discerned that clear distinction. But, here I am as disappointed as your father ever was.
Re: (Score:2)
Riiighhtt
Re: Noah: (Score:2)
I did. Was going to make it, but was beat to it.
Why not instantaneous? (Score:2)
I have two questions. One, why would this not be instantaneous? I thought the point of quantum computing was that all states were visited in parallel, with it collapsing on the final state pretty much instantly. You set up the starting state, and it collapses into the result. At least that's what I've always heard.
The second, is how do you know when you've successfully decrypted the data? What if you end up with data that looks correct (like a credit card number, or a valid sentence that even makes sense),
Re:Why not instantaneous? (Score:5, Informative)
That is a common misconception about quantum computing. One that I shared until I started learning more about it. No, it doesn't do everything all at once in parallel.
Here is an excellent video [youtube.com] that, if you are willing to part with about 30 minutes in time, will make you 10 billion percent better informed than you are now, or I was. I really think everyone with these question should watch this.
Re: (Score:2)
I spent the thirty minutes. It's heady stuff even in the dumbed down form. Now I understand it even less than before.
Re: (Score:2)
Pop sci explanations are rarely very good.
A quantum computer is a highly programmable random number generator. The trick is to come up with a circuit that makes the random numbers you get as output have a distribution that is related to your problem in some usable way. Each run gives you one sample.
Suppose you've set things up so your answer is the mean or the mode of that distribution. Depending on how good your computer and algorithm are, i.e. what the shape of that distribution is and how noisy your resu
Re: (Score:2)
Some things to note here (Score:2)
The use of "teoretically" and then "1M noisy Qbits" and "1 week" and finally "RSA 2048". Now, how should I put this?
1. 1M QBits are so far out of reach (because they still need to get entangled and stay that way), this may as well a prediction for the next millenia.
2. A QC calculation 1 week long? Are you serious? That is probably even harder than (1).
3. RSA 2048? That was the state of things a decade or so ago. And if people were smart and used encryption with perfect forward secrecy, breaking that key get
Re: (Score:2)
Meanwhile, the steady march of breathless press releases anticipating larger numbers of Qbits seems to have dried up. MS turned out to have nithing and Google abruptly went silent about the time they were anticipating crowing about success.
I'm guessing they discovered some new and exciting way that Qbits lose coherence.
Re: (Score:2)
They don't mean that a single calculation is a week long. That would be ridiculous. They mean that their hypothetical computer would hypothetically need about a week to run enough times to provide enough samples to give a reasonable confidence in the answer.
So, not happening any time soon (Score:4, Insightful)
Re: (Score:2)
We may be a bit closer... Microsoft [microsoft.com] has stuff going in this arena. Will it actually pan out? Who knows. All the while China is waiting in the wings with what they make.
Once someone is able to factor ECC algorithms and has the ability to put bogus transactions on blockchains, say buh-bye to cryptocurrencies as we know it.
No, we are not, in fact... (Score:2)