How Many Qubits Will It Take to Break Secure Public Key Cryptography Algorithms? (googleblog.com) 53
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?
640. (Score:2, Funny)
640 qubits ought to be enough for anybody.
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)
If a million qubits can solve the problem in a week, technically, the larger system will use considerably more time.
And noisy qubits with error correction all estimation, not solving
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:And 4K RSA? SSH keys? (Score:5, Informative)
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. That's not how many more qubits you need, it's more like the time it takes if you've got enough cubits, but 2 is a small enough number that cryptography types aren't willing to gamble.
Grover's algorithm is sqrt(N). sqrt(2^512) / sqrt(2^256) is still a gigantic number, which is why the recommendation for AES is to double your key length and not worry about it. Or just not worry about it if you're a normal mortal.
Re: (Score:2)
Re: And 4K RSA? SSH keys? (Score:2)
While I don't understand all the details, from what I'm reading SSH is expected to rely on a new key exchange algorithm called ML-KEM, and this is designed to address standards defined by FIPS 203-205. Some Google searches should get you closer to an authoritative answer (if there even is one).
Noah: (Score:3, 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.
Re: (Score:2)
1/300 the length of a milliHelen.
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:3)
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)
Re: (Score:2)
The problem you're presenting [in your 2nd paragraph] is for symmetric ciphers. But that's not the problem presented by TFA. There the question is to take a public key and produce the private key. There the math is well-defined for validation.
Additionally, albeit this is well beyond my expertise, re a plausible but incorrect decryption [of a symmetric cipher], you're dealing with a few issues.
a) you're basically asking for the equivalent of the intersection of multiple checksum/hash functions. Possible, but
Some things to note here (Score:3)
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 gets you excatly nothing.
So, nothing to see here. Seriously.
Re: (Score:3)
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)
Yes, I suspect the same.
Re: (Score:3)
It's looking like the quantum computing world is running into the practical limitations of the kind that AI will be encountering soon. The difference being that QC didn't try to secure Terawatts of utility capacity prior to having anything to show for itself.
Re: (Score:2)
With QCs it is more that adding QBits increses effort much more than linearly. That means you are going to hit a wall at relatively low numbers. In that situations, tech breakgroughs give you a constant factor (which we have observed seveal times over the last 40 years or so), but they never lead to scalability and that wall is still there. Given that breaking RSA requires 3x the number of effective (error corrected) QBits than the keylenght, and these need to stay entangled over a long computation, even to
Re: (Score:2)
Worse, there is now no uncontaminated internet to steal for a second time. It's too polluted with hallucinations from the first wave of LLMs.
Re: (Score:3)
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.
Re: (Score:2)
Are you sure? They talk about error correction and that usually means a single compuation.
Re: (Score:2)
The paper [arxiv.org] talks about the execution time in section "3.2 Physical Costs."
It's extremely jargon heavy, but a "shot" is a single execution of the algorithm, and they estimate the per-shot time at 12 hours. That's still ridiculous, but they're proposing to use a couple different types of quantum state storage so I don't think you'd actually need to maintain coherence in your computational qubits for that long. That requirement is more like milliseconds, which is still pushing it for current superconducting QCs
Re: (Score:2)
re state of the rat & RSA2048... yeah, it's still state of the rat. At least 18 months ago, the last time I was directly involved therein, Google, Fastly & CloudFlare only allowed 2048 bit RSA keys on their CDNs/LBs [also 256bit EC].
They didn't care what you had on your origins [and for that, keepalive/pipelining is a thing], but for computation reasons they don't allow big RSA keys on their outward facing systems [and ditto Google's internal LBs].
I do agree that 1M qbits is believed currently impos
Re: (Score:2)
Well, if you like living on the edge, sure, do 2048 bit. Probably out of reach for the foreseeable future, but only probably.
As to "classified labs", nothing is hiding there. They would have to be much more advanced on too many things.
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.
Re: (Score:2)
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.
I wish. Sadly, cryptocurrencies aren't so vulnerable. It's a simple matter to replace ECDSA with ML-DSA for wallet keys. Yes, it'll require updating a bit of infrastructure so that everyone looking at transactions on the blockchain understands the new signatures, and everyone will have to generate new wallet keys and enter transactions to transfer their coins from their old key to new, but there are no fundamental problems to solve, just work to do.
Also, you don't "factor" to break ECC.
Re: (Score:2)
It's also a problem of scaling - adding extra qubits reduces coherence time and increases the likelihood of errors.
A million qubits might simply be impossible for quite a long time. And that's RSA-2048. That's been deemed within reach for a couple of decades now and to move to RSA-4096.
No, we are not, in fact... (Score:2)