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