Key Negotiation in the Post-Quantum Era

Introduction

Cryptography, understood as the set of information protection schemes, is typically divided into symmetric or private key cryptography and asymmetric or public key cryptography. Schemes or protocols that exploit a k (private key) secret already shared between the parties, commonly called Alice and Bob, belong to symmetric cryptography.

For example, in the case of a confidential communication, Alice encrypts the \texttt{msg} message that she wants to transmit by combining it with the k secret. Once he receives the \texttt{ct} cipher, Bob is able to decrypt it thanks to the knowledge of the same k secret.

In asymmetric cryptography, however, each user has a unique (sk, pk) key pair. 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 the parties.

In the case of a confidential communication from Alice to Bob, the key pair involved (sk_{\textbf{B}}, pk_{\textbf{B}}) is that relating to the receiver. Alice encrypts \texttt{msg} with Bob’s pk_{\textbf{B}} public key and the latter is able to decrypt \texttt{ ct} with your sk_{\textbf{B}} private key.

At a high level, therefore, it can be seen that in the first case the same key is used both in the encryption and decryption phase, while in the second two distinct 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. Asymmetric cryptography is used for the negotiation of a shared secret and, starting from this, the encryption takes place using symmetric cryptographic techniques.

Therefore, the negotiation of cryptographic keys is a fundamental primitive within secure communication protocols. To date, the most widespread technique for its implementation is given by the Diffie-Hellman (DH) asymmetric cryptographic protocol. In addition to implementation simplicity and efficiency, one of the peculiarities that contributes to the popularity of Diffie-Hellman is its non-interactivity. In fact, given two communicating parties, they are able to establish a shared secret to be used as a cryptographic key without the need for any interaction, as long as each party knows the public key of the other.

Unfortunately, assuming the existence of a suitable quantum computer, Shor’s algorithm is able to completely break the mathematical foundations behind DH, greatly impacting the security of the asymmetric cryptography in use today.

Following the first relevant developments in quantum computing technologies and given the potential catastrophic impact on information security, NIST launched a standardization process in 2017 to identify Post-Quantum Cryptography (PQC) solutions or alternatives to Diffie-Hellman which are also considered resistant to quantum computers (quantum-resistant). However, non-interactive cryptographic key negotiation solutions based on mathematical foundations other than those of DH have proved to be insecure or generally not very mature. Consequently, NIST’s evaluation focused on key exchange mechanisms with properties different from those guaranteed by DH, called Key Encapsulation Mechanisms (KEM).

A KEM is an asymmetric cryptographic protocol of interactive key exchange, in fact even if the parties know each other’s public keys, unlike DH, at least one communication phase 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.

Click the link to read the full article.

For other articles related to Quantum and Cryptography topics, please refer to the related 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.