CRYSTALS-Dilithium: LWE-based digital signature

31 May 2023

Introduction

The NIST standardization process in the post-quantum domain has identified two cryptographic schemes to be considered “primary” solutions. Regarding Key Encapsulation Mechanisms (KEMs), i.e., key derivation schemes, CRYSTALS-Kyber was selected, while for digital signatures the choice fell on CRYSTALS-Dilithium (that has now been standardized under the ML-DSA name). Within modern cryptographic communication protocols, Dilithium will replace the schemes currently used for digital signatures, including RSA and those based on elliptic curves, both proven to be vulnerable to attacks by a quantum computer.

CRYSTALS-Dilithium

Similarly to Kyber, Dilithium bases its security on certain computational problems defined over lattices, which are considered intractable even for a quantum computer. In particular, as will be analyzed later, the generation of the public-private key pair occurs through the definition of an instance of Module-LWE. For completeness, we also mention the Short Integer Solution (SIS)[1] problem, namely the problem of finding small-norm solutions to a linear system, formally defined as: Given a matrix $\mathbf{A}\in\mathbb{Z}^{k\times m}$ , a positive integer $q$ , and a positive real number $\beta$ , find a vector $\mathbf{x}\in\mathbb{Z}^m$ such that

$0\leq ||\mathbf{x}|| < \beta$ ;
$\mathbf{A}\cdot \mathbf{x} \equiv \mathbf{0}\mod q$ .

Before going into the details of the Dilithium signature scheme, it is useful to fix some notation.

$q$ is a prime number
$\mathbb{Z}_q$ denotes the set $\{0,\dots,q-1\}$
$R_q=\mathbb{Z}_q[X]/(X^n+1)$ denotes the set of polynomials in $X$ with coefficients in $\mathbb{Z}_q$ with the relation $X^n=-1$
$S_\eta$ denotes a subset of $R_q$ with coefficients bounded by $\eta$
Let $S$ be a set, $s\leftarrow S$ indicates that $s$ is sampled uniformly from $S$
$B_{\tau}$ denotes the subset of $R_q$ consisting of polynomials with $\tau$ coefficients equal to $\pm 1$ and the rest equal to $0$
$\textsf{H}$ is a hash function with codomain $B_{\tau}$

As a digital signature scheme, the phases that make up Dilithium, reported below in a simplified form, are identified as Key Generation, Signing, and Verification.

Key Generation

In this phase, the private key and the public key are generated, which will be used respectively to produce and verify a signature. A public matrix $\mathbf{A}$ is sampled uniformly, where each component is a polynomial in the set $R_q$ . The entries of the private key $(\mathbf{s_1}, \mathbf{s_2})$ are sampled uniformly from the set $S_{\eta}$ . Using the matrix $\mathbf{A}$ and the vectors $(\mathbf{s_1}, \mathbf{s_2})$ , the vector $\mathbf{t}$ is computed, which, together with $\mathbf{A}$ , forms the public key of the signature scheme. As mentioned earlier, key generation in Dilithium consists of creating an instance of Module-LWE. In fact, to recover the secrets $(\mathbf{s_1},\mathbf{s_2})$ of the private key given the public key $(\mathbf{A},\mathbf{t})$ , an attacker would need to solve the Module-LWE problem and, given the assumption of its intractability, this provides strong security guarantees for the scheme. It is worth noting that, unlike other lattice-based schemes participating in the NIST process, the secret vectors $(\mathbf{s_1}, \mathbf{s_2})$ are sampled uniformly rather than according to a discrete Gaussian distribution. The authors argue that, thanks to this choice, it is possible to reduce the risk of certain side-channel attacks that could make some implementations insecure. It is also important to note that, since the random matrix $\mathbf{A}$ consists of $k\cdot l$ polynomials in $R_q$ , its representation would be excessively large, making transmission quite costly and thus the use of Dilithium less practical. The adopted solution is to generate $\mathbf{A}$ from a smaller seed; in this way, it is sufficient to transmit only the identified seed within the public key.

Signing

The signing of a message in Dilithium is carried out using the approach known as Fiat-Shamir with Aborts, introduced by Ukrainian-American mathematician Vadim Lyubashevsky in 2009. In this strategy, the signature scheme is derived from an identification protocol in which interactivity is removed using the Fiat-Shamir transform, as is done for the Schnorr signature in EdDSA. In an identification protocol, a Prover must demonstrate to a Verifier that they possess a certain secret, in this case the pair $(\mathbf{s_1},\mathbf{s_2})$ , without revealing it.

The identification scheme depicted above involves an interaction between the parties that is preparatory to sending the proof $\mathbf{z}$ . In a signature scheme, these two preliminary communications can be removed, allowing the prover to generate the challenge $c$ by computing it as the hash of the concatenation of the message $m$ and the commitment $\mathbf{w}$ .

It should be noted that, following the signature scheme described above, for some unfortunate choices of the vector $\mathbf{y}$ , an attacker may be able to extract information about the private key from the signature $(\mathbf{z},c)$ . A so-called rejection sampling phase is therefore required to address this possibility, repeating the signing process whenever certain parameters fall outside a secure regime. Indeed, to complete the Fiat-Shamir with Aborts construction, it is necessary to introduce this check before sending the signature. In the Dilithium scheme, rejection sampling is performed through a loop that terminates only when the coefficients of the signature fall within certain bounds derived from the scheme’s parameters. In Dilithium, several optimizations are introduced that allow only the most significant bits of the commitment $\mathbf{w'}$ to be considered. In order to preserve the correctness of the operations, it is necessary to transmit a hint that enables signature verification even when only a truncated version of the commitment vector is available. While sending a hint requires adding approximately 100 bytes to the signature size, this same measure allows the public key size to be reduced by about a factor of 2.

Verification

In the verification step, it is checked that the commitment $c$ , contained in the signature, matches the output of the hash function computed on the concatenation of the message $m$ and $\mathbf{w'}$ , where $\mathbf{w'}$ is derived from the signature $\sigma=(z,c)$ and the public key $\mathbf{A}$ . Also in the signature verification process, some optimizations have been introduced which, by working only with the most significant bits, significantly reduce the size of the digital signature.

Performance

The main goal of the authors of CRYSTALS-Dilithium is to design a scheme that minimizes the sizes of both the public key and the message signature. This choice is intended to support the use of Dilithium in contexts such as secure web browsing, where it is necessary to transmit a chain of certificates containing multiple signatures and their corresponding public keys used for verification.

In the graph shown above, a comparison is provided between the performance of Dilithium and two of the most widely used traditional schemes (RSA and EdDSA), in terms of transmitted data size (on the left), i.e., public key and signature, and computational cost of the components described in the previous sections (on the right). While computational efficiency in required cycles is not an issue – Dilithium is comparable to EdDSA and much more efficient than RSA – transmission costs require further investigation. In fact, it can be observed that in Dilithium the size of the public key and signature is significantly larger than that produced by traditional algorithms. Moreover, this size exceeds the Maximum Transmission Unit (MTU), typically set to 1500 bytes and representing the maximum capacity of an IP packet. The transition process to post-quantum schemes must therefore carefully take this issue into account in order to mitigate its effects in terms of latency and packet fragmentation. [1] In Dilithium, variations of SIS play a fundamental role in a more in-depth security analysis, beyond the scope of this article.

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 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 the end of 2020 focusing in particular on issues related to quantum technologies.

Marco Rinaudo, a bachelor’s degree in Mathematics from the University of Turin and a master’s degree with a specialization in Cryptography from the University of Trento. Following a 2022 curricular internship at Telsy, he has been part of the Cryptography Research Group since January 2023.