How Many Qubits Will It Take to Break Secure Public Key Cryptography Algorithms? (googleblog.com)
- Reference: 0177716857
- News link: https://it.slashdot.org/story/25/05/24/0530234/how-many-qubits-will-it-take-to-break-secure-public-key-cryptography-algorithms
- Source link: https://security.googleblog.com/2025/05/tracking-cost-of-quantum-factori.html
"This is a 20-fold decrease in the number of qubits from [3]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 [4]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 [5]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 [6]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."
[1] https://arxiv.org/abs/2505.15917
[2] https://security.googleblog.com/2025/05/tracking-cost-of-quantum-factori.html
[3] https://arxiv.org/abs/1905.09749
[4] https://eprint.iacr.org/2024/222
[5] https://www.federalregister.gov/documents/2024/08/14/2024-17956/announcing-issuance-of-federal-information-processing-standards-fips-fips-203-module-lattice-based
[6] https://nvlpubs.nist.gov/nistpubs/ir/2024/NIST.IR.8547.ipd.pdf
Re: (Score:3)
Nobody else will probably get the joke, but I did!
Re: (Score:2)
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: (Score:3)
It's more specifically a reference to [1]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.
[1] https://youtu.be/bputeFGXEjA
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:2)
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: (Score:2)
Riiighhtt
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: (Score:3)
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 [1]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.
[1] https://www.youtube.com/watch?v=RQWpF2Gb-gU
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
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:2)
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.
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.