Breaking Encryption: Once More unto the Breach, dear Friends, Once More

Jantje Silomon

17 January 2023

While the West was settling down to the Christmas holidays and looking forward to a quiet turn-of-the-year, a group of researchers uploaded a paper to arxiv.org, an open-access repository with over 2 million scholarly articles. The site is well-known with the natural science community, having started off in the 1990s as a preprint repository for physics papers. While articles are moderated, they are not peer-reviewed by arXiv, though they may have been submitted for (or even passed) such review elsewhere.

So far, so good. Nothing out of the ordinary here. The paper’s title “factoring integers with sublinear resources on a superconducting quantum processor” is again nothing that would necessarily draw the attention of non-specialist outlets. However, it seems that Bruce Schneier’s blog post entitled “Breaking RSA with a Quantum Computer” discussing the paper lit-up the topic like a beacon in the night. Numerous outlets picked the story up, including the Financial Times running it as “Chinese researchers claim to find way to break encryption using quantum computers”.

Encryption has become an essential part of daily life, whether users are aware of it or just blissfully take its benefits for granted, for example when shopping online, sending messages, or storing data in the cloud. It is therefore not surprising that a potential report of current state-of-the-art encryption being breakable caused a stir – and that is without even looking at government, intelligence, or military uses of encryption!

Skipping over a couple of days of reporting, most experts agreed that the paper is more speculation than anything, with Scott Aaronson going as far as calling it “one of the most actively misleading quantum computing papers I’ve seen in 25 years, and I’ve seen … many”. So, all in all, the paper does not change anything, encryption is safe, and daily life can continue? Yes… but burying one’s heads in the sand is not an option either.

Only a Matter of Time

One way of evaluating encryption is looking at how computationally secure it is against brute-force attacks. These attacks systematically check all possible key combinations until the correct key is found. Longer keys are not only more difficult to break but exponentially so. At the same time, ‘faster’ computers counter that, which is why some encryption algorithms that were used in the past and relied on short keys are no longer considered safe. For example, the 1970s DES encryption would have required around half a million years to break when it came out, dropping down to thousands of years and possibly weeks in the late 80s and early 90s. Further tech advances were showcased in several challenges, reducing the time to break DES to 96 days in 1997, 56 hours in 1998, and just over 22 hours in 1999 with specialised equipment.

Jumping to the present, there are numerous different encryption standards and industry regulations enforcing certain requirements, with NIST for example providing a list of up-to-date recommendations. Different applications favour different encryption standards, though they fall into two main types: symmetric and asymmetric. The former uses the same key to encrypt and decrypt data, with AES being one widely used example, short for Advanced Encryption Standard. An example of the latter is RSA (Rivest–Shamir–Adleman), which uses a public key to encrypt and a private key to decrypt data. Although it was also publicly described in the late 1970s, it relies on the practical difficulty of factoring two large prime numbers. The algorithm was released to the public domain in September 2000, a few weeks before its (US only) patent was due to expire. Unbeknown to the public, Clifford Cocks had created an equivalent system in 1973, however, it was classified as top-secret by the British GCHQ and did not become public until 1997.

With current encryption algorithms, brute-forcing attacks have again ‘gone-up’ to taking unrealistic amounts of time, for example around 300 trillion years to break RSA-2048 bit. Thus, yes, it is rather safe for a while longer, until we find a practical way of solving the factoring problem, say using a… quantum leap.

Enter Shor’s Algorithm

In 1994, Peter Shor developed an algorithm for finding prime factors on a quantum computer – a print of his paper also available on arXiv. Without going into details of how it works, it essentially does not brute force the entire key. The key step requires using a quantum computer and is, in short, sandwiched between two parts that use classical computation. The juicy middle quantum part is used to find the period of a function that contains the key (and boggles the mind – a non-math explanation by Scott Aaronson about halfway down the article here), then classical computing kicks in again to find the greatest common divisor.

And yes, there are several quantum computers out there, but they are still in their infancy in terms of their qubit quantity and quality: Google’s 2018 Bristlecone had 72 qubits and IBM’s 2022 Osprey 433 qubits. Forschungszentrum Jülich launched a 5,000 qubit system in 2022, albeit running a different type of system that is not as well suited to running Shor’s algorithm. Reports claim that it would take eight hours to break RSA 2048-bit with a 20 million qubit computer, or 177 days with 13,436 qubit and multimode memory. So again, nothing to worry about for now, right? Unless of course there was an even faster way to break encryption… using only 372 qubits.

Something to Schnorr Through?

The paper suggested exactly that, implying that breaking RSA-2048 was possible using an application of Claus Peter Schnorr’s 2021 fast factoring integer algorithm combined with another algorithm (the QAOA – Quantum Approximate Optimisation Algorithm – to be precise). However, the authors neglected two points, the crucial one that was almost swept under the carpet in the paper’s conclusion: “It should be pointed out that the quantum speedup of the algorithm is unclear due to the ambiguous convergence of QAOA“. In Aaronson’s words: ““Unclear” is an understatement here. It seems to me that a miracle would be required for the approach here to yield any benefit at all […]”. Put differently, those two algorithms could break the encryption with only a few hundred qubits, if they work together as expected… but there is no evidence at all that this may be the case!

Despite the paper being a red-herring, it is clear that even RSA-2048 and other current encryption will be broken given technological advancement, particularly given all sorts of funding being poured into various quantum tech components, security, and start-ups. NIST and other organisations have been working on quantum-resistant cryptography for years, pushing ahead with several algorithms for standardisation, and the White House’s Office of Management and Budget released a memorandum outlining the need for federal agencies’ to begin the migration. However, educational policies are lacking, with the UK being one of the first to have launched a government-funded quantum computing programme and pushed educational policies such as doctoral centres. EU’s Quantum Flagship seeks to coordinate research projects across the states but synergies are not yet fully utilised.

To cut a long story short, it is highly unlikely that current encryption will be broken overnight. But that does not mean the problems can be blissfully ignored. It is time to get the ball rolling, from taking stock of current systems utilised to planning migration, all the while bolstering educational policies beyond combatting the current cyber security skills gap.