11 min

Quantum-Resistant Cryptography: Challenges and Actions

Digital transition - Ludovic PERRET - February 21, 2021

What would you say about a company whose 10-year strategic plans, exploration plans, or R&D secrets that make up its future industrial added value were stolen today to be exploited in a few years’ time without these actions being detectable? You would certainly answer that the company has, at the very least, lost some of its value, if not already compromised its future.

In the near future, estimated at 5 to 10 years, what will you say about a company whose most valuable information is constantly and systematically exposed to attacks, which are, on top of it, undetectable? You will certainly answer that the survival of this company is threatened and that its CEO and CIO should have anticipated this threat and implemented appropriate countermeasures early enough.

These two scenarios are far from fictional: they illustrate the very real threat that the future capabilities of quantum computers represent for our IT infrastructures, and in particular for the resistance of standard cryptographic protocols.

The aim of this article is to clarify the nature and status of this quantum threat to cybersecurity, the progress made by institutions to standardise reliable solutions to this threat, and the recommendations that can be made to help companies implement protective countermeasures today.

What should we expect from quantum computers?

“Quantum supremacy” or “quantum advantage” is a concept that refers to the moment when a quantum computer is shown to be superior to the most advanced of all classical “supercomputers”. The threshold of 50 qubits is the commonly accepted limit for quantum supremacy.

In October 2019, Google announced that it had achieved quantum supremacy; in September 2020, IBM announced in its roadmap that a quantum computer of 1,000 qubits should be expected by 2023; and in December 2020, a team from the University of Science and Technology of China announced that it had significantly surpassed Google’s results. Most recently, a team of researchers from the Sorbonne University, CNRS and the American start-up QC Ware announced that they had achieved a quantum advantage.  In practical terms, such announcements — even if their interpretation is still a matter of debate within the scientific community — show very fast and concrete progress towards a quantum computer with effective computational capabilities.

What are the threats to infrastructure security?

In practice, the quantum computer promises a machine that uses quantum physics phenomena to increase its computing power tenfold. The quantum computer thus enables certain mathematical problems to be solved much more efficiently than with a conventional machine, thus challenging the security of the encryption algorithms used in cryptography.

Two types of cryptographic systems are commonly used.

1/ Private or symmetric key systems are not threatened: the same secret key is used to encrypt and decrypt messages, typically with the AES (Advanced Encryption Standard) algorithm. The quantum computer speeds up the search for the secret key, but a simple way to protect the system against this threat is to double the length of the keys.

2/ Public or asymmetric key systems are threatened: a public key is used to encrypt the message and a private key is used to decrypt it. 

Public key cryptography systems are built on mathematical problems that are complex to solve for classical computers but easy to unravel for quantum machines.

  • The RSA public key encryption — named after its inventors R. Rivest, A. Shamir, and L. Adelman (2002 Turing Award) — relies on the difficulty of breaking down a large number into a product of its prime factors.
  • The Diffie-Hellman key exchange relies on the difficulty of finding a discrete logarithm in finite fields or elliptic curves.

The security of a cryptosystem is measured by the complexity, or execution time, of the best attack against it. The security level is defined as the binary logarithm of the execution time of the best attack. For example, the RSA-1024 standard has a security level of 80 bits. The best attack with classical computers requires about  operations, i.e. approximately 400 years. With a quantum machine, RSA or Diffie-Hellman encryption see their security level drop to zero bit, which means that they can no longer guarantee any security.

The connection to a secure website is a very common use case: the public key system allows you to initiate and authenticate a transaction between your computer’s browser and the website’s server and to exchange private keys. These private keys will then be used to encrypt the whole transaction with a symmetric algorithm (which is much faster). The questioning of the security of public key systems therefore challenges the confidentiality of private keys and hence of all the data exchanged (personal data, banking data, e-commerce…).

In practice, public key cryptography is used almost everywhere and all communications that are now secure are affected by the arrival of quantum computers: communications on Internet networks (https, IPSec VPN), mobile messaging apps (Signal, WhatsApp…), digital signature protocols, blockchain applications, etc.

Why do we need to act now?

Back in 2016, the NIST (National Institute of Standards and Technologies – an agency of the US Department of Commerce) announced that this threat would become a reality by 2030. Some confusion or uncertainty still exists among experts about this deadline (2025? 2030?). However, the NSA (US National Security Agency) pointed out, as early as 2015, that the progress of quantum computers had reached such a point that the risk could no longer be ignored and that organisations immediately had to start a transition to quantum-resistant cryptographic solutions. More specifically, an objective has been made public to transition US administrations to quantum-resistant cryptography by 2024 (M. Scholl, NIST, 2017).

Besides, we must be aware that the threat is already present.  Indeed, according to the “Harvest Now, Decrypt Later” principle, data can already be collected and stored by organisations with significant storage capacity, in view of their subsequent decryption and use.

All sectors of activity and all companies are concerned and must act quickly. For sectors that manage secret and sensitive long-lived  data — such as defence, finance, aerospace, energy, automotive, pharmaceuticals, and healthcare — an urgent stake is already there.

In October 2018, the research and advisory firm Gartner ranked quantum computers at the top of the list of future IT disruptions for which CIOs are ill-prepared.

What are the answers to this threat?

A first operational answer is provided by “quantum-resistant cryptography” or “post-quantum cryptography”. Indeed, a practical approach is to build quantum-resistant public key cryptosystems, based on mathematical problems that differ from those used in the threatened algorithms. Quantum-resistant cryptography includes cryptography based on Euclidean networks, multivariate cryptography, cryptography based on error-correcting codes, isogenies, and cryptographic hash functions.

A second complementary answer is provided by “quantum cryptography” and in particular quantum key distribution (QKD). QKD — whose security relies on the laws of quantum physics — allows the exchange of a secret key that is then used to secure a classical symmetric cryptographic protocol.  Some technological challenges still need to be resolved in order to deal with long distances, integration with telecommunications infrastructures, and deployment costs.

To assist with and foster this transition, the President of the French Republic Emmanuel Macron announced on 21 January 2021 a national investment plan in quantum technologies. This plan aims to rank France among the world’s top three countries in quantum technologies and includes investments amounting to €1.8 billion over 5 years, with a €150-million component on quantum-resistant cryptography.

What are the standards for quantum-resistant cryptography?

In 2016, the NIST launched an international call to standardize quantum-resistant algorithms. The NIST’s priority is to have standards for two functionalities: digital signature and key exchange. The NIST has called on the international scientific community to submit their best algorithms and to analyse the level of confidence that can be attributed to said algorithms.

Twenty-four international research teams from 26 countries (including 13 teams with at least one French researcher) sent in their submissions. In 2020, the second selection round selected 15 submissions, with the prospect of a final decision in 2022.

From a scientific and technical point of view, these algorithms are more complex, with very different characteristics from current standards and often longer keys. This raises performance issues depending on the expected objectives and the hardware or application environment. In practice, depending on the use cases, different algorithms may be used. These differences explain the very long time it takes for the NIST to select standard algorithms and complexify the incorporation of new cryptosystems into existing applications.

Finally, it is important to point out that China — which is always very active on quantum issues —completed the selection phase of its new standards in January 2020.

What are the technical solutions for quantum-resistant cryptography?

Nowadays, the NIST in the US and the ANSSI (French National Agency for the Security of Information Systems) advocate for a hybrid approach that allows to retain the existing classical cryptography layer, and only requires the incorporation of an additional layer of quantum-resistant cryptography.

This strategy has many advantages:

–         The migration risk is reduced as the existing layer is not questioned (the current security level is not degraded).

–         Companies can keep their product certifications more easily.

–         The transition to quantum-resistant cryptography can be made seamlessly.

CryptoNext Security is a start-up that spun off from French university research (CNRS, INRIA, and Sorbonne University) and whose founders have an algorithm in the final phase of the NIST process.  CryptoNext Security already offers a hybrid library of quantum-resistant cryptography that integrates all the final candidate algorithms of the NIST standardisation process and meets the requirements of the main use cases.

What actions and migration plans should companies implement?

The full deployment of a new cryptographic standard such as AES (private key cryptography) took 20 years. According to experts, 10 years would be the minimum time required to transition from our public key infrastructure to quantum-resistant algorithms.

For companies, this transition is a huge challenge and a path strewn with obstacles that involves a multitude of systems and stakeholders. However, the sooner a company invests and structures its approach towards quantum-resistant cryptography, the sooner it will have a competitive advantage over its competitors. And in practice, if the threat appears to be a disruption, the implementation of this transition must be handled in a structured manner within the framework of a migration plan that forms an integral part of the company’s ongoing cybersecurity plan.

Without waiting for the results of the NIST competition or, worse, a potential transformation of the threat into a real (undetectable) attack, every company can now get down to work to establish a quantum transition plan. This transition plan should include the following components:

–         The mapping of systems and applications that use cryptography, and especially public key cryptography.

–         The establishment of a quantum-resistant cryptography policy, timed objectives, and a strategy to achieve them.

–         The drafting of an action plan.

Of course, this migration plan for cryptographic solutions must be set up in parallel with a mapping of the most critical data that will enable to set migration priorities. This migration plan also questions stakeholders such as suppliers, their development plans, and the protection of their critical systems.

Transition actions might affect very sensitive areas in terms of sovereignty, security, and performance, such as payment systems or certain communications in the aerospace or defence sectors. And since the deployment of this next-generation cryptography can significantly affect a company’s IT infrastructure (key size, file format, …), it is necessary to carry out tests as soon as possible. Understandably, the implementation of these actions will take time and must therefore be well anticipated.

Every company can initiate the process by immediately activating two levers:

1/ Crypto-agility:

Today, cryptographic algorithms are often “hard-coded” into the application software. Changing them is therefore quite inflexible and very expensive. In a simplified way, the choice of a cryptographic algorithm must be made “configurable” so that companies can benefit from it in several ways:

–         Anticipating: this transition can be initiated immediately to allow cryptosystems to smoothly evolve in line with the recommended standards.

–         Creating technical flexibility to change algorithms according to use cases and performance requirements, or to switch from one provider of quantum-resistant cryptographic solutions to another.

–         Creating flexibility to adapt to standards that may differ between territories, for example the US and China.

2/ The initiation of projects on limited perimeters:

While the security of an infrastructure against the quantum threat can of course only be assessed holistically, it seems essential to immediately start migration projects on limited perimeters of the company. This will make it possible to initiate and test the approach, but also — and more importantly — to integrate and disseminate the challenges, culture, and expertise of quantum-resistant cryptography within the teams.

Some large organizations already took the leap and initiated projects in their quantum transition plan.  For example, CryptoNext Security is working with NATO to provide a quantum-safe version of a well-known secure messaging application. CryptoNext is also a technological partner of Thales allowing the integration of a quantum-safe module for Thales Luna HSM (Hardware Security Module) ;  HSM being the root of trust of many enterprises’ IT infrastructure.

To conclude, the US National Academy of Sciences has effectively summarised the challenges that companies face in a study published in 2018: “Even if a quantum computer that can decrypt current cryptographic ciphers is more than a decade off, the hazard of such a machine is high enough — and the time frame for transitioning to a new security protocol is sufficiently long and uncertain — that prioritization of the development, standardization, and deployment of post-quantum cryptography is critical for minimizing the chance of a potential security and privacy disaster.”

Send this to a friend