Key Negotiation in the Post-Quantum Era

09 Sep 2022

Introduction

Cryptography, understood as the set of schemes for protecting information, is typically divided into symmetric or private key cryptography and asymmetric or public key cryptography. Symmetric encryption involves schemes or protocols that exploit a secret $k$ (private key) already shared between the parties, commonly referred to as Alice and Bob.

For example, in the case of confidential communication (see fig. 1), Alice encrypts the message $\texttt{msg}$ she wants to transmit by combining it with the secret $k$ . Once Bob receives the ciphertext $\texttt{ct}$ , he is able to decrypt it thanks to his knowledge of the same secret $k$ .

Cifratura Simmetrica — Fig. 1: Symmetric Encryption

In asymmetric encryption, on the other hand, each user has a unique pair of keys $(sk,pk)$ . $sk$ is called the private key and must be kept secret by each user, while $pk$ is called the public key and can be shared between parties.

In the case of confidential communication from Alice to Bob (see fig. 2), the key pair involved $(sk_{\textbf{B}}, pk_{\textbf{B}})$ is that relating to the recipient. Alice encrypts $\texttt{msg}$ with Bob’s public key $pk_{\textbf{B}}$ , and Bob is able to decrypt $\texttt{ct}$ with his private key $sk_{\textbf{B}}$ .

Cifratura Asimmetrica — Fig. 2: Asymmetric Encryption

At a high level, therefore, we can see that in the first case the same key is used for both encryption and decryption, while in the second case two separate keys are involved.

Symmetric cryptographic primitives have the advantage of being more computationally efficient. On the other hand, asymmetric cryptography does not assume the availability of a pre-shared secret to be used as a cryptographic key.
To integrate these advantages, in practice the two techniques are combined in hybrid cryptographic schemes (see fig. 3). Asymmetric cryptography is used to negotiate a shared secret and, starting from this, encryption is performed using symmetric cryptography techniques.

Therefore, cryptographic key negotiation is a fundamental primitive within secure communication protocols. To date, the most widely used technique for its implementation is the Diffie-Hellman (DH) asymmetric cryptographic protocol. In addition to its simplicity of implementation and efficiency, one of the features that contributes to the popularity of Diffie-Hellman is its <em>non-interactivity</em>. In fact, given two communicating parties, they can establish a shared secret to use as a cryptographic key without the need for any interaction, provided that each party knows the other’s public key.

Unfortunately, assuming the existence of a suitable quantum computer, the Shor algorithm is capable of completely breaking the mathematical foundations underlying DH, greatly impacting the security of asymmetric cryptography in use today[1].

Following the first significant developments in quantum computing technologies and given the potential catastrophic impact on information security, in 2017 NIST launched a standardization process to identify solutions for Post-Quantum Cryptography (PQC) solutions, i.e., alternatives to Diffie-Hellman that are considered resistant even to quantum computers (quantum-resistant). However, non-interactive cryptographic key negotiation solutions based on mathematical foundations other than those of DH have proven to be insecure or generally immature. As a result, NIST’s evaluation focused on key exchange mechanisms with properties different from those guaranteed by DH, known as Key Encapsulation Mechanisms (KEM).

A KEM is an asymmetric cryptographic protocol for interactive key exchange. In fact, even if the parties know each other’s public keys, unlike DH, at least one phase of communication is necessary. In some cases, this structural distinction between DH and quantum-resistant alternatives constitutes a non-trivial variation in the design of cryptographic protocols, representing one of the challenges of the transition to the post-quantum era.

The following sections provide a high-level overview of DH and KEMs in order to highlight this difference.

Diffie-Hellman

The Diffie-Hellman protocol sees two parties obtain the same secret $k$ by combining their private key with the other party’s public key.

In fig. 4.1, Alice and Bob do not know each other’s public keys, so two rounds of communication are necessary to complete the negotiation. For example, this use is common in the Transfer Layer Security (TLS) protocol, where each communication session requires each user to initialize a new pair of keys called <em>ephemeral</em>, as they can only be used during the relevant session.

In fig. 4.2, on the other hand, the mutual public keys are known from the outset and no further interaction between the parties is involved in obtaining $k$ . This scenario is typical when the key pairs involved are static or long-term in nature, i.e., part of a Public Key Infrastructure (PKI) or cached for reuse. The use of static keys alone is common in devices with limited resources, such as smartcards, where it is particularly convenient to avoid continuously generating new key pairs by keeping one fixed. The use of ephemeral keys offers additional security properties a priori, but as just highlighted, it is not always a viable option. Furthermore, even in protocols such as TLS, where ephemeral keys are widely used, static keys are also used in parallel for authentication purposes.

Key Encapsulation Mechanism

Although the objective of a KEM is the same as that of DH, namely the sharing between parties of a secret to be used as a key for symmetric encryption, the logic behind its implementation is different. In DH, the roles of the two parties involved are essentially interchangeable, which is not the case in encapsulation. A KEM is much closer, in spirit and design, to asymmetric encryption, with the cryptographic key pair of only one of the two parties involved.
In fact, even the encryption of the secret itself using an asymmetric scheme is a viable option. Generally, however, encapsulation mechanisms are preferred as they easily avoid security issues that can arise when the secret to be used as a symmetric key is encrypted asymmetrically.

Similar to what was described above for DH, in fig. 5.1, the first interaction involves Bob sending his public key $pk_{\textbf{B}}$ . Following the encapsulation step, Alice obtains the shared secret $k$ and sends an encapsulated message $\texttt{ct}$ which, combined with knowledge of the private key $sk_{\textbf{B}}$ , will allow Bob to trace it back to her through a further decapsulation step.

In fig. 5.2, on the other hand, we see that even if Alice knows Bob’s public key a priori, an interaction is still necessary to send the encapsulated message.

Comparing the schemes presented for DH and KEM, we realize that, in the case of public keys that are not known a priori, the two strategies are similar in terms of interactions and, therefore, we expect to be able to replace one with the other in current cryptographic protocols in an almost transparent way. On the other hand, analyzing the case with public keys known at the outset, DH does not require any interaction, unlike KEM. More generally, therefore, this means that the transition to the post-quantum era by replacing DH with quantum-resistant KEM is not immediate. Furthermore, the transition is even more complex for those cryptographic protocols that use variations or extensions of DH, exploiting the properties of the mathematical objects involved. This is the case with Extended Triple Diffie-Hellman (X3DH) cryptographic key negotiation, used in the Signal messaging protocol, for example, for which a paradigm shift to KEM is not trivial.

Finally, it should be noted that, although not an intrinsic feature of KEMs, the encapsulation schemes currently being considered in the NIST standardization process are characterized by public keys that are much larger than those involved in DH. This aspect does not represent a problem from a strictly theoretical cryptographic point of view, but it will have to be taken into serious consideration from an implementation point of view during the transition to quantum-resistant solutions.

<hr />

[1] As discussed in the previous article, the DH protocol and the RSA scheme constitute almost all of the asymmetric cryptography in use today, and both are susceptible to Shor’s algorithm.

This article is part of a series of contributions by the Telsy Cryptography Research Group dedicated to quantum computing and its implications for cryptography. For other articles, please refer to the index of the section.

For other articles related to quantum and cryptography, please refer to the relevant categories in the blog.

The authors

Francesco Stocco, a master’s degree in Mathematics at the University of Padua and the Université de Bordeaux attending the course of study “Algebra Geometry And Number Theory” (ALGANT), joined the Telsy research group in Cryptography at end of 2020 focusing in particular on issues related to quantum technologies.

Marco Rinaudo, a bachelor’s degree in Mathematics at the University of Turin and a student of the master’s degree course in Mathematics with a specialization in Cryptography at the University of Trento, currently an intern in the Telsy research group.