When will a quantum computer break RSA?

Caute_cautim — Tue, 27 Aug 2024 01:01:27 GMT

Hi All

My most trusted source for this is the Global Risk Institute's yearly "Quantum Threat Report" (https://lnkd.in/dWi5DaVj) by Michele Mosca and Marco Piani, which gives a risk based approach to the estimation based on experts' opinions. The TL;DR conclusion is that around mid-30s it will be more likely than unlikely that a cryptographically relevant quantum computer will exist.

Today I knew about the paper "Estimation of Shor’s Circuit for 2048-bit Integers based on Quantum Simulator" by Fujitsu researchers (https://lnkd.in/dEqWA8eX). They evaluate the computational resources necessary for factoring general composite large integers by Shor algorithm using an ideal quantum computer. That is:
- They don't take advantage of beneficial properties in the numbers they select,
- They assume a fault tolerant quantum computer. A real quantum computer will need some level of overhead for error correction.

Also, they do not take advantage of the latest improvements to Shor's algorithm by Regev, Ragavan and Vaikuntanathan (on different papers, reach them through https://lnkd.in/dMCsUSNv). So, the circuit depth and gate number estimations might be improved. I can't guess if the error correction overhead and these algorithmic improvements cancel out, but let's assume for a moment that they do. We just want to get ball-park figures.

Their estimation is that RSA-2048 will need 2.23 × 10^12 gates with depth 1.80 × 10^12. As a reference, IBM's Quantum roadmap (https://lnkd.in/dFu52wJR) expects to support 10^9-gate circuits in 2033+. So, the target is still unreachable by a factor of 1000 gates.

Conclusion: Unless the hardware development accelerates beyond the current predictions or algorithmic improvements significantly reduce circuit requirements, the target of 2033 or beyond seems to be a good estimation.

However it could come sooner than you expect:

The integration of classical supercomputing, ASIC-enhanced AI and memcomputing, quantum interconnects, AI-driven optimizations, and quantum black box oracles forms a threat to RSA encryption today. These researchers only take into account commercially available quantum computing capability and not the interconnect of a hybridized network with classical supercomputing, AI, quantum oracles and other techniques and capabilities to derive prime factors.

In this approach you need far lesser Qubits, an approach that was also pointed out by the Chinese back in 2023, claiming they could break 2048-bit RSA, using a 372-qubit quantum computer. Yet here the assumption is made that there is still time until 2033 ... That really is not the right message ...

Regards

Caute_Cautim

topic When will a quantum computer break RSA? in Tech Talk

When will a quantum computer break RSA?