A simple way to estimate when quantum computers will be able to break all modern (not post quantum) encryption algorithms

By I_g_o_r | Simple solutions to complex problems | 26 Nov 2024

A day when quantum computers will be able to break all modern (not post quantum) encryption algorithms is called the Q-day (or the first quantum supremacy day or the first quantum crypto break day). It has a very significant importance for all digital infrastructures of mankind, because all our digital data, currencies, networks, etc. are secured by encryption algorithms.

A 2023 survey conducted by GRI found that the majority of mainstream cryptography experts had believed that quantum computers will be able to break RSA-2048 encryption within 30 years (see [1]). Mainstream experts are experts employed by governments or corporations, in contrast to independent experts, who are not employed, financed or dependent on such entities. Even so, that the majority of mainstream experts, in 2024, reduced their time estimates for the Q-day to 2+ years (see [2]), independent experts always pointed out that these estimates, by mainstream experts, underestimate speeds of technological and scientific developments.

Neven’s Law proposed by Hartmut Neven, director of Google’s Quantum AI Lab, provides a theory on the potential improvement capabilities of quantum computers that states: “Quantum computing power is improving at a doubly exponential growth compared to conventional computing.” This growth means that quantum computing power is growing by powers of powers of two [2^2 (4), 2^4 (16), 2^8 (256)]. See [3].

The majority of mainstream experts had believed in the fallacy that because quantum systems are unstable (and this instability results in multiple errors), it will be needed decades to learn how to stabilize quantum systems. What all these experts had missed, is that to reduce rates of errors we do not need to stabilize quantum systems (hardware), but we do can reduce rates of errors by means of errors reductions algorithms/software. A practical efficiency and effectiveness of this approach was demonstrated by Microsoft and Atom Computing. See [4].

In his book “Cryptography Apocalypse: Preparing for the Day When Quantum Computing Breaks Today's Crypto”, published in 2019, independent expert Roger A. Grimes had warned mankind that: "There is a very real possibility that quantum supremacy and the quantum crypto break have already happened within a private entity and the rest of the public world simply does not know about it. It is generally believed that if a major country’s government was able to obtain quantum supremacy and, in particular, perform the quantum crypto break first, they would have every incentive to keep the accomplishments silent."

The Cloud Security Alliance (CSA), a non-profit organization for cloud and cybersecurity awareness, had estimated the Q-Day's arrival to be April 14, 2030, signifying the advent of a quantum computer that can break the current cyber security infrastructure. See [5]. No one can see the future, but they gave the forecast with a precision of up to a single day. This point out to a real possibility that there was a plan, on when to release information about the quantum break to the public.

What interesting, is that the initial plans to be ready for the Q-day by 2030, are now accelerating with proposals to do it in the first 100 days of 2025. See [6]. It seems, there is a super important serious reason for this urgent acceleration.

In their paper, titled “Quantum Annealing Public Key Cryptographic Attack Algorithm Based on D-Wave Advantage,” Chinese researchers explained how to transform cryptographic attacks problems into combinatorial optimization problems, making them more manageable for quantum systems. In fact, they reduced the problem of hacking 50-bit RSA algorithm (factoring a 50-bit prime number) into an equivalent combinatorial optimization problem and solved it, by using D-Wave’s quantum computers, which are accessible through cloud services for around $2,000 an hour.

Despite these fast developments and multiple demonstrations that 50-bit RSA encryption was broken by modern quantum computers, the majority of mainstream experts still believe that it will be required at least 2 years of developments to break modern 2048-bit encryptions.

“Security researchers who have taken a look at the report generally don't consider the demonstration as posing any current threat to modern encryption systems, which typically use 2048-bit — or sometimes even larger — keys. Breaking these 2048-bit keys still remains computationally unfeasible, and the new research has not changed that fact.”

“Realistically, achieving the computational power necessary to break RSA-2048 encryption — which requires around 10,000 stable, error-corrected qubits — remains at least a few years away, given current technological limitations," says Avesta Hojjati, head of R&D at DigiCert.” See [2].

Let us look at implications of these admissions, by mainstream experts. First of all, 2048-bit encryptions are used in highly secure government, military communications channels, applications, and special projects. The majority of the current infrastructure uses encryptions of up to 256-bit. See [7-8]. If 2 years of progress in QCs is required to break 2048-bit encryptions then it only requires several months to break 128, 192, 256, 512-bit encryptions. This means that all (not post-quantum) crypto blockchains can be hacked in 2025+ by QCs. Secondly, the length of private keys is crucial in cases when there is no an algorithm, which reduces an exponential complexity to a polynomial complexity, but it has no any significant difference if such algorithms exist, as is the case with Shor’s algorithms. This fact is shown in results of calculations, presented in the next sections of this post. Thirdly, the 10,000 number of qubits mentioned is in 3-33 times bigger than other published estimations of mainstream experts (see [10]). Fourthly, wise people say: “Watch what they do, not what they say”. Publicly, they say that RSA-2048 encryptions are secure, but what they do is the opposite to what they say. They declared that RSA-2048 no longer VS-NfD compliant, starting 2024 (see[9]).

Mainstream experts can not express their opinions freely, because they are restricted by their obligations to their employers. Otherwise, they will lose their high-paying jobs, contracts, grants, etc. Just recall, what mainstream experts told us during the Covid-19 period.

“While some experts predict Q-Day to arrive in 2030, QUANTUM DEFEN5E (QD5) warns it may come as early as 2025.” See [5]

RSA-512 encryption can be broken by ordinary computers with total costs less than $10 (see [12]). Google claims that the quantum chip “Willow” can perform calculations over 1,000,000,000,000,000,000,000,000,000 times faster than ordinary computers do (see [13-14] ). If this claim is true then quantum computers can break all modern encryptions, today.

Very respected expert, Dr. Ed Gerck, claims RSA-2048 was broken (see [15]).

In this post, we consider a simple way to estimate when quantum computers (QCs) will be able to break all modern (not post-quantum) encryptions algorithms, using simple math, very conservative assumptions, and data published by Chinese researchers, who breached modern encryption algorithms for 50-bit RSA encryptions.

Let us, denote by UT (unit of time) a time required to solve this problem (to break 50-bit encryption), using the combinatorial optimization algorithm on a D-Wave Advantage QC, used by the Chinese experts. As a fact, there is no an optimization method which reduces a complexity of a general combinatorial problem from exponential to polynomial or even to exponential with big reduction in number of possible cases to search for. We do not know properties of the algorithm used by the Chinese experts, but we can make several assumptions about them and make our estimates based on these assumptions. The main assumption is that this algorithm requires full search for the optimum. This means that the number of searched combinations is proportional to 2^50. The alternative assumption/hypothesis is that this optimization algorithm reduces, in some way, the number of searched combinations. This means that the number of searched combinations is proportional to 2^49 or 2^48 … or 2^40.

In 1994, Peter Shor, the MIT Math Professor, devised a quantum algorithm for generating prime factors of large numbers much more efficiently than classical computers. Shor's algorithm is a quantum computer algorithm that can find prime factors of an integer number in polynomial time. This means that problems with exponential complexity (factoring on prime numbers) are reduced, by this algorithm to problems with polynomial complexity. It allows us to factorize a number X into prime numbers in O(logX ^3) time and O(logX) space. See [11]. In fact, he invented several polynomial-time algorithms for prime factorization and finding discrete logarithms on quantum computers.

Now, we make our assumption that a speed of Shor’s algorithm on a quantum computer with entangled qubits has a similar processing speed (or at least not less) as the processing speed of the quantum computer used by the Chinese researchers. The Chinese researchers had used a D-Wave Advantage quantum computer available to public, which is not the most powerful. Governments and big corporations have more powerful quantum computers, but they restrict access to them, only to a limited number of mainstream experts, on the grounds of national or corporate security.

If X~2^M then logX is ~M and (logX)^3 is ~M^3. This means, that Shor’s algorithm reduces an exponential complexity of factoring an integer number on prime numbers (or finding discrete logarithms) to polynomial complexity in time, with degree 3. Now, we can estimate a time to factor a number with M bits on prime numbers (or finding discrete logarithms) in UTs, using the formula:

T=M^3/2^K, where K=50, 49, ...40,

and where T is a time to break M-bit encryption algorithm, based on prime numbers factoring (M=2^7, …,2^15) on QCs, using Shor’s algorithms, and UT is a time to break 50-bit RSA encryption on the D-Wave Advantage QC, using the optimization algorithm, developed by the Chinese experts.

For K=50 we have: