11.05.2023 Use casesTechnology

Quantum doomsday planning (2/2): The post-quantum technology landscape

This post aims to assist you in assessing the risk of quantum computing to your organization’s IT assets. This is the second installment in our series, where our first post described quantum computers' present and hypothetical future capabilities, and showed how various protocols could be attacked.

This second post focuses on the present-day technology that offers protection against the quantum computing risk. We will delve into the standardization process of post-quantum cryptography and explore the solutions currently available for transitioning towards becoming quantum-resistant.

0. Introduction

Our previous post explained what a quantum computer is and why it has become a central research topic. We described the low-probability high-impact quantum risk by stating the state of the art in quantum computing and the main achievements by companies and researchers. We also elaborated on how your security mechanisms could be impacted and how a quantum attack would work. Note that quantum computers have many other potential applications than attacking cryptography, such as chemical and biological engineering, and the simulation of quantum mechanics which could lead to materials discovery and drug development.

Because of the cryptographic risk quantum computers would represent, post-quantum cryptography has been a growing field. Post-quantum cryptography is the class of cryptographic schemes immune to quantum attacks.

The standardization of post-quantum cryptographic primitives is ongoing, mainly by the National Institute for Standards and Technology (NIST), while the International Organization for Standardization (ISO) and the Internet Engineering Task Force (IETF) are also working towards the development of post-quantum cryptography standards. In fact, the IETF has even established a working group that focuses specifically on post-quantum encryption.

With that upcoming standardization it is becoming imperative to consider adapting cryptographic mechanisms. An approach is to gradually adopt hybrid solutions to benefit from the fact that classical algorithms are well established. This hedging method consists in combining classical and post-quantum primitives, such that the combination is safe as long as at least one of the two methods is safe.

Indeed, post-quantum algorithms and their implementations are relatively new and could potentially have vulnerabilities in the future. This means that the deployed technologies need to support the implementation of both sets of standards simultaneously. Many projects such as Open Quantum Safe, are open source and aim to support the development and prototyping of post-quantum cryptography.

In this post we’ll elaborate on :

What post-quantum cryptography is.
The current post-quantum cryptography standards state focusing on the efforts made by NIST.
The resources and solutions available for a transition to hybrid protocols.

1. What is post-quantum cryptography?

Post-quantum cryptography consists of public-key cryptographic schemes designed to withstand attacks from both classical and quantum computers. Traditional cryptography relies on the hardness of mathematical problems such as the discrete logarithm problem or factoring large integers. However, a quantum computer would be able to solve these problems a lot faster which renders most of today’s cryptographic systems vulnerable. Post-quantum cryptography relies on well-understood constructions, such as NP-hard mathematical problems that are believed to be hard even for quantum computers. For more on the underlying theory, see BQP complexity class.

Although post-quantum cryptography has recently gained more interest in research and industry, it is not a new topic. Conferences on this subject have been taking place since as early as 2006.

It is important differentiate post-quantum cryptography from so-called quantum cryptography, which consists mainly of quantum key distribution systems. Post-quantum cryptography is run on classical computers while being quantum-resistant. Quantum cryptography on the other hand, uses the principles of quantum mechanics.

Depending on their foundational mathematical concepts, post-quantum cryptography scheme mainly fall in one of the following five categories:

Lattice-based: based on the hardness of well-known lattice problems such as the shortest vector problem (SVP) and the learning with errors (RLWE) problem.
Code-based: based on the hardness of problems from coding theory such as syndrome decoding and learning parity with noise (LPN).
Multivariate: based on the hardness of solving multivariate systems of equations.
Hash-based: digital signature schemes based on the security of cryptographic hash functions.

In addition to the aforementioned categories, post-quantum cryptography can also be based on zero-knowledge proofs, such as Picnic, which rely on the ability to prove a statement without revealing said statement. Isogeny-based systems, such as cSIDH, use the properties of isogenies of elliptic curves for their security.

The adoption of post-quantum cryptography faces many challenges including the larger size of keys and signatures, slower speed and potential implementations' reliability issues against side channels.

For example, the larger signature and key sizes may not fit in the initial congestion window used in TCP leading to network-level challenges. This is especially true in the case of TLS where middleboxes assume that the handshake fits in a single network packet which is not the case when adding the majority of post-quantum key encapsulation mechanisms (KEMs). Even if the larger signatures fit in the TCP congestion window, there may still be a significant slowdown due to the relatively low average internet speed. Another challenge is the storage of parameters during protocol execution which may lead to increased latency and bandwidth consumption.

For widespread adoption of post-quantum cryptography standards, the transition should require minimal software updates and new hardware. Until quantum computers pose an imminent threat, standards are likely to be integrated into hybrid solutions. Classical algorithms have a well-established track record, while post-quantum cryptography, being relatively novel, may reveal vulnerabilities in the upcoming years. Furthermore, striking a balance between security, computational complexity, and resource usage is essential.

Implementing hybrid solutions presents challenges, as a KEM does not directly substitute a Diffie-Hellman (DH) key exchange. Consequently, systems must be capable of simultaneously implementing and supporting both methods.

To address these challenges, some companies and researchers have started to develop tools to help incorporate hybrid solutions. Organizations such as Amazon Web Services (AWS), IBM, Microsoft, PQShield, and wolfSSL among many more are collaborating with NIST to support the migration to quantum-safe solutions.

In the following sections we’ll present the different potential NIST standards and the different solutions that incorporate them.

The terms “post-quantum”, “quantum-safe”, “quantum-proof”, “quantum-resistant”, and “quantum-resilient” are equivalent.

2. The NIST standardisation process

As mentioned above, the substantial task of developing post-quantum cryptography standards has taken the form of a competition organized by NIST. It started with a first call for proposals in December of 2016 then, in July of 2022, the candidates to be standardized and the fourth-round candidates were announced. As with previous cryptographic standards AES and SHA-3, NIST’s competition was a public process where anyone could submit an algorithm proposal, and researchers all around the world worked on analyzing candidates from a security and performance perspective. Researchers having submitted a candidates have extra incentives to attempt to break other contestants, a dynamic that indeed worked relatively well to identify the fittest algorithms.

According to this NIST timeline, we could expect to see some finalized version of the draft standards we have now in 2024.

In each round of the NIST competition, the selection of algorithms was based on many criteria such as:

Security: security levels offered (see Table 1 below), confidence in security proof, known attacks, classical vs quantum complexity.
Performance: size of parameters, decryption failures, speed of : key generation, encryption, decryption, signing, verifying signatures.
Algorithm and implementation characteristics: simplicity, clarity of documentation, ease of implementation, amount of code required, resilience to and ease of protection against side-attacks.

As we move towards post-quantum cryptography, the classic DH key exchange is most likely to be replaced by a key encapsulation mechanism (KEM). A KEM is a key establishment technique to which there are three main parts: key derivation, encapsulation, decapsulation. It can just be seen as a way to encrypt a symmetric key.

KEMs uses a combination of private and public keys to transmit a symmetric key. The main difference between KEMs and DH is that KEMs generate a shared secret by encapsulating a randomly generated symmetric key with a public key and then decapsulating it with a private key, whereas DH involves exchanging public values from which is computed the shared secret value.

As of today, NIST has selected some (future) standard algorithms, and a fourth round is ongoing to identify more standards. The algorithms selected for standardization in 2022 are:

CRYSTALS-Kyber (KEM, lattice-based)
CRYSTALS-Dilithium (signature, lattice-based)
FALCON (signature, lattice-based)
SPHINCS+ (signature, hash-based)

The round 4 candidates are:

BIKE (KEM, code-based)
Classic McEliece (KEM, code-based)
HQC (KEM, code-based)

Note that the isogeny-based scheme SIKE had been submitted to round 4, but was withdrawn after it was proven to be insecure.

To learn more about NIST’s process and the status quo, you can consult the following resources:

NIST’s status update on the third round.
NIST’s status reports.
The public discussion forum.
The lists of selected algorithms and of round 4 submissions.

The standards being developed will provide quantum-resistant cryptography to manage the quantum risk. However it is unlikely that a single algorithm will be selected as a replacement since the each algorithm offers different trade-offs, especially in terms of key sizes and signature sizes. The choice of which standard to adopt will highly depend on the application and which characteristics are more important for that specific use case. Considering blockchains for example, the largeness of the key sizes is one of the most significant disadvantages of the current post-quantum signature schemes.

In the next section we will elaborate on some of these possible solutions.

Cryptographers-designing-post-quantum-algorithms.

3. Post-quantum solutions available today

In this section, we’ll summarize what technology providers offer today in terms of post-quantum cryptography, and how they can be integrated into the scenarios discussed in our previous post including TLS, end-to-end encryption, and VPNs.

Moreover, various guidelines are available to assist in navigating the transition to hybrid solutions and prioritizing certain aspects, such as the NIST migration project.

3.1. Cloud services

AliBaba Cloud

Alibaba Cloud has incorporated quantum random number generators to their cloud services to improve the security of financial transactions. These numbers can then be incorporated to other encryption protocols such as TLS and IPSec.

Moreover, AliBaba offers an open-source quantum development platform, it is a simulator driven tool for quantum algorithms and quantum computers. The source code can be found at https://github.com/alibaba/acqdp. They also have a public Quantum Computing Cloud Platform where an 11-qubit quantum computing service is available.

AWS

AWS integrated a hybrid post-quantum key exchange option for TLS, which combines elliptic curve Diffie-Hellman (ECDH) with the KEM Kyber-512. This is available in AWS' key management service (AWS KMS). AWS recommends testing the feature before incorporating it because, as we have previously mentioned, bandwidth requirements and performance characteristics of hybrid protocols are different from those of classic key exchange mechanisms. Codes sample for the SDK KMS are available in the repository aws-samples/aws-kms-pq-tls-example. The integration of hybrid modes in AWS' s2n TLS library is presented in the pq-crypto/ directory. Based on the IETF Internet Drafts (which are not RFC yet), it supports TLS 1.2 and TLS 1.3.

Cloudflare

Cloudflare provides a post-quantum option for secure tunnels which relies on a hybrid method that combines the elliptic-curve based key agreement protocol X25519 (pre-quantum) with the Kyber-512 or Kyber-768 post-quantum KEMs. The source code for this solution is on GitHub in the cloudflare/cloudflared repository, and support for the post-quantum key exchanges in Go can be found in cloudflare/qtls-pq. In theory the hybrid protocol guarantees 256-bit security against quantum attackers and as much against classic attackers. The post-quantum option is free since March 2023 and can be enabled by adding the option --post-quantum to the cloudflared utility.

Google

Google now uses post-quantum cryptography in its internal communication network. They chose to deploy a hybrid approach of NTRU-HRSS and X25529 in their internal encryption-in-transit protocol Application Layer Transport Security, this is the same choice that was made for the CECPQ2 experiment on Google Chrome in 2018 hence they reused BoringSSL’s CECPQ2 implementation.

Google is also working on developing post-quantum cloud capabilities and helping their customers manage the transition to post-quantum cryptography.

IBM

IBM has post-quantum TLS modes available in IBM cloud, supporting post-quantum curl request to endpoints of the the IBM Key Protect service. Key Protect uses the Kyber algorithm.Tthe quantum-safe TLS option is only supported through the Key Protect software development kit. There are three different hybrid parameters sets supported :

p256_kyber512: combines Kyber-512 with ECDH using P-256 curve. It provides L1 security.
p384_kyber768: combines Kyber-768 with ECDH using P-384 curve. It provides L3 security.
p521_kyber1024: combines Kyber-1024 with ECDH using P-521 curve. It provides L5 security.

The hybrid algorithms used are based on guidance from the Open Quantum Safe project community. There also is a quantum-safe mode that uses only the three different security levels of the Kyber algorithm (no longer hybrid, only post-quantum).

Furthermore, the IBM zSystems platform with IBM z16 offers the possibility to implement the lattice-based Dilithium or Kyber algorithms, for digital signature and key encapsulation capabilities, in its HSM.

Additionally, the IBM Quantum Safe initiative offers resources to get started with the transition to quantum-safe cryptography.

Microsoft

Microsoft Azure offers a post-quantum fork of TLS adding quantum-safe key exchange and authentication algorithms using liboqs, an open-source C library for quantum-safe cryptographic algorithms from the Open Quantum Safe project. However, it is still at the experimental stage and they do not recommend using this implementation to protect any sensitive data. The supported algorithms for key exchange are BIKE, Kyber, FrodoKEM, and HQC. Hybrid algorithms are also supported, if the post-quantum algorithm claims to provide L1 or L2 security then it is combined with ECDH using the P-256 curve. If it claims L3 or L4 security, it is combined with ECDH using the P-384 curve and finally, if it claims L5 security it is combined with ECDH curve P-521.

In the scope of their post-quantum cryptography efforts, they have also participated in the development of other elements of the Open Quantum Safe project such as the post-quantum crypto VPN and the post-quantum SSH. Additionally, Microsoft offers quantum cloud computing on their quantum hardware.

Tencent

Tencent offers a quantum circuit and quantum algorithm simulation open-source software platform that supports hybrid computing models called TensorCircuit along with quantum parametric amplifiers (noise control and error correcting algorithms).

3.2. VPN services

Here are some VPN providers that have a post-quantum option.

TLS-based

By integrating the implementation of post-quantum TLS to TLS-based VPNs, they become resistant to quantum attacks.

Microsoft offers a post-quantum TLS-based VPN option but it is still experimental as is often the case when using post-quantum cryptography today. The project is available on GitHub. Microsoft researchers have co-designed the Frodo, SIDH (which has since been broken), Picnic and qTesla algorithms and contributed these implementations to the Open Quantum Safe project. Additionally, they provide software and instructions for building a post-quantum secure VPN appliance with a Raspberry Pi 3.

QST-VPN is another quantum-safe TLS-based VPN option, the core functionality of QST-VPN is also provided by OpenVPN. To try it out the easiest way is to use the AWS pre-configured cloud instance. Supporting documentation is also available.

IPsec-based

In order to make IPsec-based VPNs quantum-safe, the idea is to create a hybrid IKE. This often comes with trade-offs between setup time, fragmentation, anonymity and protection against downgrade and DoS attacks. An alternative could be to use pre-shared keys like the previous version IKEv1 is configured.

Juniper Networks offers an IPsec-based VPN. When using Junos OS starting release 22.4R1, some selected Juniper SRX models and the virtual vSRX firewall will support RFC8784 which enables the creation of quantum-safe IPsec tunnels: "If the preshared key has sufficient entropy and the Pseudorandom Function (PRF), encryption, and authentication transforms are quantum secure, then the resulting system is believed to be quantum secure".

WireGuard-based

The WireGuard protocol an be hardened against quantum attacks by leveraing its pre-shared key (PSK) feature, when derived from a post-quantum KEM. (When said mode is not in use, the PSK value is set to an all-zero string.)

Using the WireGuard PSK feature, the Mullvad VPN supports quantum-resistant tunnels on all of their WireGuard servers using Classic McEliece and soon Kyber-1024. It is still an experimental feature available on the desktop application on Windows, Linux and macOS; it can be enabled in the command line interface with: mullvad tunnel wireguard quantum-resistant-tunnel set on. The code for the desktop application is available at: https://github.com/mullvad/mullvadvpn-app.

This is also an active area of research, Hulsing et al. have proposed a post-quantum WireGuard using a combination of two KEMs in the handshake protocol, Classic McEliece and Saber. Moreover, in a paper entitled Tiny WireGuard Tweak, Jacob Appelbaum, Chloe Martindale, and Peter Wu elaborate on a trick to harden WireGuard against quantum attacks, as proposed by WireGuard’s author Jason Donenfeld (namely, hashing long-term public keys before they are sent).

3.3. Hardware providers

Arm

The chip designer Arm partnered with the TLS library provider wolfSSL, which focused on embedded software, to offer post-quantum TLS optimized for Arm processors. wolfSSL demonstrated a post-quantum TLS 1.3 handshake (using Kyber) between a server and a machine using an Arm Cortex-M4 chip. wolfSSL leverages liboqs and the pqm4 library, which includes implementations of post-quantum schemes optimized for the Cortex-M4 family. Note that a similar library, pqm3, exists for the Cortex-M3 line of processors.

Intel

Intel has invested in quantum computing, including research in qubit architecture and algorithms, control electronics, interconnects, quantum software toolchains and compilers. As part of this effort, they published a software development kit (SDK), the Intel Quantum SDK. It allows developers to program new quantum algorithms to execute on simulators or real quantum hardware.

Regarding real quantum hardware, Intel has not disclosed the exact number of qubits it is using or the technology being used. However, they have made significant strides in cryogenic quantum control with the cryoprober, the cryogenic quantum control chip Horse Ridge and the silicon spin qubit devices fabricated on Intel’s research and development equipment.

Their post-quantum cryptography efforts is mostly research and exploring the different solutions.

Marvell

Marvell bring improvements to the in 5G security standards by using HSMs in the 5G network from connected end devices to the back-end core network. One use case is the 3rd Generation Partnership Authentication Framework with post-quantum cryptography. Their LiquidSecurity2 hardware security model can be certified and updated to support post-quantum cryptography.

Nvidia

Nvidia cuQuantum is an SDK of optimized libraries and tools for accelerating quantum computing workflows. Documentation is available here. NVIDIA QODA is an open unified environment of powerful computers and quantum processors creating a coherent hybrid quantum-classical programming model. The company has also released DGX Quantum a system that couples GPUs and quantum computing and uses newly open-sourced CUDA quantum software platform.

PQshield

PQshield provides optimized software as well as hardware IP block designs for post-quantum cryptography, suitable for FPGAs and ASIC designs. PQshield also offers the PQCryptoLib hybrid cryptographic library provides support for classical and hybrid key derivation and for implementation within the TLS key schedule, supporting multiple post-quantum cryptography algorithms as well as many classical schemes.

Thalès

Thales, together with ISARA Quantum-Safe Security Solutions, offers clients solutions to facilitate preparation and implementation of post quantum crypto agility. They also offer tools to assess post-quantum readiness through cryptographic agility and risk assessment.

By combining their Cryptosmart application and the 5G SIM, they have developed a hybrid post-quantum mobile solution using the Kyber algorithm, securing any data exchanged during the talk.

Thales have contributed to the creation to the FALCON post-quantum cryptographic algorithm. Additionally, they have developed goliboqs, a Go wrapper around liboqs, which contains C implementations of NIST post-quantum candidate algorithms including BIKE, FrodoKem, Kyber, SIKE, Picnic, and qTesla. This enables Linux Go applications to use quantum-resistant key encapsulation mechanisms. An example implementation of a post-quantum key exchange for TLS is available here.

4. Conclusion

As quantum computing engineering continues to progress, the study of post-quantum cryptography is becoming increasingly important. Nonetheless, the field remains in its infancy as anticipate NIST’s final standardization and draft FIPS/SP documents. Following this, the FIPS certification will be amended, and the FIPS 140-3 document updated.

Even so, some post-quantum solutions are already available for initial deployment. It is important to note that a hybrid approach using classical and post-quantum cryptography is recommended for the first phase of deployment.

During the transition to a hybrid or fully post-quantum system, prioritizing key exchange and encryption over signatures is recommended, as the latter can be addressed later in the transition process. However, various challenges remain, particularly in the deployment of post-quantum cryptography in large organizations, as well as interoperability, performance issues, and the security and reliability of implementations, especially when dealing with embedded devices and defence against side-channel attacks.

In the medium to longer term, we can also expect on-chip hardware acceleration for post-quantum schemes, via instruction set extensions, such as those being experimentally developed based on the RISC-V architecture.