How Many Qubits Will It Take to Break Secure Public Key Cryptography Algorithms?

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."

And 4K RSA? SSH keys?

[crow]

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:

[gweihir]

Stay with that 4096 bit key. Nobody is going to break it in the next 100 years.

Re: And 4K RSA? SSH keys?

[Big Hairy Gorilla]

What about ed25519 keys? How does that compare to 4096 rsa?

Re: And 4K RSA? SSH keys?

[reanjr]

"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:

[carlhaagen]

For your actual SSH keys you can stick to RSA 4096 or better still, Ed25519. As for the key exchange phase, which I presume is what you're really asking about, there are two post-quantum alternatives available today: ML-KEM x25519 (aka "mlkem768x25519-sha256" in OpenSSH) and NTRU Prime ("sntrup761x25519-sha512").

Noah:

[Anonymous Coward]

What's a qubit?

Re:

[battingly]

Nobody else will probably get the joke, but I did!

Re:

[snikulin]

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:

[Entrope]

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:

[SlashbotAgent]

Sahwing and a miss! AI failed you.

It's a reference to a Bill Cosby joke routine about that subject.

Re:

[MachineShedFred]

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:

[reanjr]

Which ironically it was likely explicitly coded by hand not to do.

Re:

[SlashbotAgent]

Riiighhtt

Why not instantaneous?

[Dan East]

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:

[AlanObject]

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:

[ceoyoyo]

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:

[carlhaagen]

No. It's not going to create an avalanche effect. The "singularity" isn't about to happen.

Some things to note here

[gweihir]

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:

[sjames]

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:

[ceoyoyo]

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

[RUs1729]

First, we are still very, very far from having a QC with one million qubits. Second, we can keep a few hundred qubits in superposition and entangled for (much) less than one second.

Re:

[ctilsie242]

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...

[carlhaagen]

...even 5 years from breaking RSA 2048 with anything quantum. Once there, the way to surpass RSA 4096 is yet longer. If you want to stick with RSA instead of something modern like Ed25519, then move to 4096 bit keys today and you can stop thinking about this at least another decade.