New post-quantum digital signature proposals: the second NIST competition

Introduction

In response to the threat posed by quantum computers, in 2017 the National Institute of Standards and Technology (NIST) launched a standardization process for the selection of quantum-resistant public-key cryptography algorithms. The process focused on the selection of key encapsulation algorithms and digital signature algorithms. At the end of three rounds of analysis, with the participation of academic experts and industry representatives from the cryptographic community, NIST announced a first selection of algorithms that would proceed to the standardization phase. The chosen algorithms were CRYSTALS-Kyber for key encapsulation and CRYSTALS-Dilithium, Falcon and SPHINCS+ for digital signatures. All selected schemes, with the exception of SPHINCS+, base their security on mathematical problems related to structured lattices¹.

With the aim of diversifying the security assumptions underlying the standardized schemes, in September 2022 NIST announced that the process would continue for a fourth round. The schemes deemed eligible for additional evaluation belong exclusively to the key encapsulation category. NIST therefore considered it appropriate to launch a new standardization process focused on the selection of digital signatures.

To date, the most widely used signature schemes are RSA, ECDSA and, more recently with the publication of the standard FIPS 186-5, EdDSA. Despite their widespread use, these schemes are vulnerable to quantum attacks and will therefore need to be replaced by post-quantum algorithms such as the aforementioned Dilithium, Falcon and SPHINCS+. Recently, NIST published a first draft of the official specifications for Dilithium and SPHINCS+, respectively with documents FIPS 204 and FIPS 205, effectively initiating the final phase of the process that will lead to the first definition of the updated standards.

For the new competition, NIST declared that it is primarily interested in proposals based on security assumptions different from those related to structured lattices. Nevertheless, the institute expressed its openness also to submissions based on structured lattices, provided that they present substantial differences from the schemes already in the standardization phase.

The new submissions

The competition launched in 2017 collected a total of 64 submissions, of which only 19 proposed digital signature algorithms. Despite the limited number, the initial proposals were heterogeneous, with submissions aligned to the main categories of post-quantum problems, such as lattices, linear codes, multivariate systems, hash functions and symmetric primitives. Diversification progressively decreased in subsequent rounds, leading to an excessive representation of algorithms based on structured lattices.

In June 2023, at the end of the new submission phase, NIST received 50 proposals and deemed 40 of them valid and compatible with the competition requirements. In addition to the macro-categories already identified in the 2017 competition, among the new proposals there are algorithms based on supersingular elliptic curve isogenies and others falling under the recent “MPC-in-the-head” paradigm. The main families of problems and the number of candidates for each are reported below, with a comparison between the previous and the new competition.

The new proposals are freely available, with their specifications and implementations, on the official NIST project page.

As in the 2017 competition, NIST defined five security levels. Each level defines security through comparison with a standard symmetric primitive: levels I, III and V refer respectively to AES-128, AES-192 and AES-256; levels II and IV refer respectively to SHA-256 and SHA-384. For example, for an algorithm to be classified at level I, every known attack capable of breaking its security must require a computational cost (classical or quantum) equal to or greater than that required for an exhaustive attack on AES with 128-bit keys. The submitted schemes must therefore propose different parameterizations capable of covering the various security levels. Overall, among the 40 admitted submissions, 297 parameterizations were proposed, with a preponderance of parameters relating to levels I, III and V.

Although the specifications of the schemes have been published for only a few weeks, the cryptographic community has rapidly initiated an in-depth analysis of the submissions. Already in the first days after publication, important vulnerabilities were identified that led to the premature elimination of some proposals. At the time of writing this article, of the 40 schemes initially submitted, 9 are completely broken (3WISE, EagleSign, EHTv3, eMLE Sig 2.0, FuLeeca, HPPC, KAZ-Sign, Xifrat1-Sign, DME-Sign) and 3 have reduced security compared to the original specifications (Biscuit, HuFu, SDitH).

Beyond the basic security requirements, there are some additional properties that are relevant or otherwise desirable in the evaluation of an algorithm. In particular, NIST expressed interest in the following properties:

• Resistance to side-channel attacks. Although side-channel vulnerabilities primarily affect the implementations of an algorithm, there are schemes that are naturally less susceptible to this type of attack. This characteristic significantly simplifies implementations and often makes it possible to avoid costly countermeasures during optimization.
• Resistance to multi-key attacks. In a multi-key attack, an adversary attempts to compromise multiple keys simultaneously. Sometimes, such scenarios are advantageous for the adversary compared to a single attack.
• Misuse-resistance. This term refers to the ability of a cryptographic scheme to reveal little information in the case of incorrect use during implementation or operation.
• Advanced notions. These concern further security properties such as exclusive ownership, message-bound signatures and re-signability

Trade-offs and performance

In the evaluation of a digital signature algorithm, we can identify numerous metrics related to communication costs, performance, efficiency and implementation characteristics. NIST, similarly to the 2017 competition, has not established a clear priority, noting that important real-world scenarios may require different trade-offs. Regardless of the application scenario, it is desirable that a good candidate excels in at least one of the metrics described below:

• Public key and signature sizes. The length of a signature represents the main communication cost, as the transmission of the signature in its entirety is always necessary. As for public keys, on the other hand, in some scenarios it is possible to proceed offline with their storage, thereby reducing the impact of a larger size, which is critical especially in the case of transmission.
• Computational costs. The computational efficiency of a signature scheme is evaluated primarily by analyzing the private operations (the signing algorithm) and public operations (the verification algorithm). Since signature schemes typically use static keys², the cost of generating a new key pair is often secondary. The precise evaluation of these costs depends on the characteristics of the platform on which the scheme will be implemented. For this reason NIST requires both software and hardware implementations, with analysis on heterogeneous platforms (e.g. desktop, embedded, FPGA).

Compared to classical cryptography, where schemes with optimal characteristics exist with respect to all the previous metrics, post-quantum cryptography requires greater trade-offs and presents a general increase in key and signature sizes. In NIST’s intentions, a broader selection of cryptographic standards compared to the past will favor the adoption of post-quantum schemes in most application scenarios.

The figure below shows a graph of signature and public key sizes, comparing the new submitted proposals, the winning signature schemes from the post-quantum competition and the pre-quantum standards. To simplify the comparison, the graph reports only the level I and II parameterizations. A red border on the new proposals indicates that security vulnerabilities have been detected³.

Case study: TLS and WebPKI

One of the main applications of digital signatures concerns the protection of web communications and in particular their use in the TLS protocol.

The TLS protocol, which stands for “Transport Layer Security,” is a fundamental security protocol used on the Internet to ensure the privacy and integrity of communications between clients and servers. This protocol operates at the transport layer, providing an additional layer of security to the underlying protocol, usually TCP. TLS uses an advanced combination of cryptographic primitives to prevent unauthorized interception of data during transfer and to authenticate the parties involved.

A fundamental element in the implementation of TLS is the Public Key Infrastructure (PKI) of the web. WebPKI is a set of standards, protocols and services that manages the creation, distribution and management of public cryptographic keys and digital certificates. In the context of TLS, WebPKI plays a crucial role in verifying the identity of servers and websites. Every web server that wishes to use TLS must obtain a digital certificate from a trusted certification authority (CA). This certificate contains the server’s public key together with other information and is used to demonstrate the authenticity of the website to clients, through the use of digital signatures.

The migration of classical signature algorithms to the new post-quantum standards represents one of the greatest challenges of the transition process initiated by NIST. The non-negligible increase in the costs of the new schemes, in terms of communication or efficiency, makes a direct replacement of the algorithms used in WebPKI complex. In particular, schemes with short signature lengths (for communications during the TLS protocol), with a reduced combined length of public key and signature (for the transmission of certificates) and efficient in the verification phase (for certificate checking by clients) are desirable. Below is a comparison between the signature schemes in the standardization phase and ECDSA-P256, widely used in the WebPKI context.

From the table above it is evident that none of the new schemes allows a direct replacement in the web context. The only apparent exception, constituted by Falcon, in turn presents implementation challenges that require the use of floating-point arithmetic, limiting its deployment possibilities.

Among the newly submitted proposals, we can attempt a preliminary analysis by identifying the schemes with characteristics compatible with the requirements of TLS and WebPKI. Concretely, we consider the values of Dilithium2 and ECDSA as threshold values. Below are the schemes that reach or improve upon these values in the previously identified metrics.

Even considering the new schemes, it remains difficult to directly replace classical signatures. On the other hand, some of the new proposals present interesting characteristics, particularly with regard to signature sizes. This characteristic, if supported over time by a confirmation of security and performance, could favor these candidates for adoption in the web context.

Conclusions

With the announcement of the winning algorithms in the NIST competition, the post-quantum transition process has taken an important step forward, marking the path for the future adoption of quantum-resistant schemes. These solutions are to be considered valid and applicable in the short term to most use cases. The new process dedicated to digital signatures should therefore not be considered as an alternative to the previous one, nor would it be wise for industry to wait for its conclusion before starting the transition. NIST’s objective is in fact to expand the offering of post-quantum algorithms, so as to more easily reach particular scenarios and at the same time guarantee an appropriate diversification of security assumptions.

As in the case of the previous competition, it is plausible that the process will require multiple rounds and several years before reaching a conclusion.

This article belongs to a series of contributions, edited by the Telsy Cryptography Research Group, devoted to quantum computing and its implications on Cryptography. For reference to other articles, please refer to the index.

For other articles related to Quantum and Cryptography topics, please refer to the related categories in the blog.

The author

Edoardo Signorini, a graduate in Mathematics with a curriculum in cryptography from the University of Trento, did his Master’s Thesis in Post-Quantum Cryptography (PQC) at Telsy in 2020. He is currently a cryptographer within the research group at Telsy and holds an Industrial PhD in Pure and Applied Mathematics at the Polytechnic University of Turin. His work focuses on research in PQC and the analysis and development of cryptographic protocols.