NIST FIPS 204 日本語訳

Federal Information Processing Standards Publication

Category: Computer Security

Subcategory: Cryptography

Information Technology Laboratory National Institute of Standards and Technology Gaithersburg, MD 20899-8900

This publication is available free of charge from: https://doi.org/10.6028/NIST.FIPS.204

Published August 13, 2024

U.S. Department of Commerce Gina M. Raimondo, Secretary

National Institute of Standards and Technology Laurie E. Locascio, NIST Director and Under Secretary of Commerce for Standards and Technology

The Federal Information Processing Standards Publication Series of the National Institute of Standards and Technology is the official series of publications relating to standards and guidelines developed under 15 U.S.C. 278g-3, and issued by the Secretary of Commerce under 40 U.S.C. 11331.

Comments concerning this Federal Information Processing Standard publication are welcomed and should be submitted using the contact information in the “Inquiries and comments” clause of the announcement section.

Kevin M. Stine, Director Information Technology Laboratory

Digital signatures are used to detect unauthorized modifications to data and to authenticate the identity of the signatory. In addition, the recipient of signed data can use a digital signature as evidence in demonstrating to a third party that the signature was, in fact, generated by the claimed signatory. This is known as non-repudiation since the signatory cannot easily repudiate the signature at a later time. This standard specifies ML-DSA, a set of algorithms that can be used to generate and verify digital signatures. ML-DSA is believed to be secure, even against adversaries in possession of a large-scale quantum computer.

Keywords: cryptography; digital signatures; Federal Information Processing Standards; lattice; post-quantum; public-key cryptography.

Federal Information Processing Standards Publication 204

Published: August 13, 2024 Effective: August 13, 2024

Federal Information Processing Standards (FIPS) publications are developed by the National Institute of Standards and Technology (NIST) under 15 U.S.C. 278g-3 and issued by the Secretary of Commerce under 40 U.S.C. 11331.

Signature generation uses a private key to generate a digital signature. Signature verification uses a public key that corresponds to but is not the same as the private key. Each signatory possesses a key-pair composed of a private key and a corresponding public key. Public keys may be known by the public, but private keys must be kept secret. Anyone can verify the signature by employing the signatory’s public key. Only the user who possesses the private key can generate a signature that can be verified by the corresponding public key.

The digital signature is provided to the intended verifier along with the signed data. The verifying entity verifies the signature by using the claimed signatory’s public key. Similar procedures may be used to generate and verify signatures for both stored and transmitted data.

This standard specifies several parameter sets for ML-DSA that are approved for use. Additional parameter sets may be specified and approved in future NIST Special Publications.

The adoption and use of this standard are available to private and commercial organizations.

Information about validation programs is available at https://csrc.nist.gov/projects/cmvp. Examples for digital signature algorithms are available at https://csrc.nist.gov/projects/cryptographic-standards-and-guidelines/example-values.

Agencies are advised that digital signature key pairs shall not be used for other purposes.

Similarly, the use of a product containing an implementation that conforms to this standard does not guarantee the security of the overall system in which the product is used. The responsible authority in each agency or department shall ensure that an overall implementation provides an acceptable level of security.

Since a standard of this nature must be flexible enough to adapt to advancements and innovations in science and technology, this standard will be reviewed every five years in order to assess its adequacy.

National Institute of Standards and Technology (2024) Module-Lattice-Based Digital Signature Standard. (Department of Commerce, Washington, D.C.), Federal Information Processing Standards Publication (FIPS) NIST FIPS 204. https://doi.org/10.6028/NIST.FIPS.204

Federal Information Processing Standards Publication 204

This standard defines a digital signature scheme, which includes a method for digital signature generation that can be used for the protection of binary data (commonly called a “message”) and a method for the verification and validation of those digital signatures. NIST Special Publication (SP) 800-175B [2], Guideline for Using Cryptographic Standards in the Federal Government: Cryptographic Mechanisms, includes a general discussion of digital signatures.

This standard specifies the mathematical steps that need to be performed for key generation, signature generation, and signature verification. In order for digital signatures to be valid, additional assurances are required, such as assurance of identity and of private key possession. SP 800-89, Recommendation for Obtaining Assurances for Digital Signature Applications [3], specifies the required assurances and the methods for obtaining them.

The digital signature scheme approved in this standard is the Module-Lattice-Based Digital Signature Algorithm (ML-DSA), which is based on the Module Learning With Errors problem [4]. ML-DSA is believed to be secure, even against adversaries in possession of a large-scale fault-tolerant quantum computer. In particular, ML-DSA is believed to be strongly unforgeable, which implies that the scheme can be used to detect unauthorized modifications to data and to authenticate the identity of the signatory (one bound to the possession of the private-key). In addition, a signature generated by this scheme can be used as evidence in demonstrating to a third party that the signature was, in fact, generated by the claimed signatory. The latter property is known as non-repudiation since the signatory cannot easily repudiate the signature at a later time.

This standard gives algorithms for ML-DSA key generation, signature generation, and signature verification (Section 5), and for supporting algorithms used by them (Section 7). ML-DSA is standardized with three possible parameter sets, each of which corresponds to a different security strength. Section 4 describes the global parameters used by these algorithms and enumerates the parameter sets for ML-DSA that are approved by this standard. ML-DSA can be used in place of other digital signature schemes specified in NIST FIPS and Special Publications (e.g., FIPS 186-5, Digital Signature Standard (DSS) [1]).

Over the past several years, there has been steady progress toward building quantum computers. The security of many commonly used public-key cryptosystems will be at risk if large-scale quantum computers are ever realized. This would include key-establishment schemes and digital signatures that are based on integer factorization and discrete logarithms (both over finite fields and elliptic curves). As a result, in 2016, NIST initiated a public Post-Quantum Cryptography (PQC) Standardization process to select quantum-resistant public-key cryptographic algorithms for standardization. A total of 82 candidate algorithms were submitted to NIST for consideration.

After three rounds of evaluation and analysis, NIST selected the first four algorithms for standardization. ML-DSA is derived from one of the selected schemes, CRYSTALS-DILITHIUM [5, 6], and is intended to protect sensitive U.S. Government information well into the foreseeable future, including after the advent of cryptographically relevant quantum computers. For the differences between ML-DSA and CRYSTALS-DILITHIUM, see Appendix D.

approved — FIPS-approved and/or NIST-recommended. An algorithm or technique that is either 1) specified in a FIPS or NIST recommendation, 2) adopted in a FIPS or NIST recommendation, or 3) specified in a list of NIST-approved security functions.

assurance of possession — Confidence that an entity possesses a private key and any associated keying material.

asymmetric cryptography — Cryptography that uses two separate keys to exchange data — one to encrypt or digitally sign the data and one to decrypt the data or verify the digital signature. Also known as public-key cryptography.

bit string — An ordered sequence of zeros and ones.

byte — An integer from the set {0, 1, 2, …, 255}.

byte string — An ordered sequence of bytes.

certificate — A set of data that uniquely identifies a public key that has a corresponding private key and an owner that is authorized to use the key pair. The certificate contains the owner’s public key and possibly other information and is digitally signed by a certification authority (i.e., a trusted party), thereby binding the public key to the owner.

certification authority (CA) — The entity in a public-key infrastructure (PKI) that is responsible for issuing certificates and exacting compliance with a PKI policy.

claimed signatory — From the verifier’s perspective, the claimed signatory is the entity that purportedly generated a digital signature.

destroy — An action applied to a key or a piece of secret data. After a key or a piece of secret data is destroyed, no information about its value can be recovered.

digital signature — The result of a cryptographic transformation of data that, when properly implemented, provides a mechanism to verify origin authenticity and data integrity and to enforce signatory non-repudiation.

entity — An individual person, organization, device, or process. Used interchangeably with party.

equivalent process — Two processes are equivalent if the same output is produced when the same values are input to each process (either as input parameters, as values made available during the process, or both).

eXtendable-Output Function (XOF) — A function on bit strings in which the output can be extended to any desired length. Approved XOFs (e.g., those specified in FIPS 202 [7]) are designed to satisfy the following properties as long as the specified output length is sufficiently long to prevent trivial attacks:

fresh random value — A previously unused output of a random bit generator.

hash function — A function on bit strings in which the length of the output is fixed. Approved hash functions (such as those specified in FIPS 180 [8] and FIPS 202 [7]) are designed to satisfy the following properties:

hash value — See message digest.

key — A parameter used in conjunction with a cryptographic algorithm that determines its operation. Examples of cryptographic algorithms applicable to this standard include:

key pair — A public key and its corresponding private key.

little-endian — The property of a byte string having its bytes positioned in order of increasing significance. In particular, the leftmost (first) byte is the least significant, and the rightmost (last) byte is the most significant. The term “little-endian” may also be applied in the same manner to bit strings (e.g., the 8-bit string 11010001 corresponds to the byte \(2^0 + 2^1 + 2^3 + 2^7 = 139\)).

message — The data that is signed. Also known as signed data during the signature verification and validation process.

message digest — The result of applying a hash function to a message. Also known as a hash value.

non-repudiation — A service that is used to provide assurance of the integrity and origin of data in such a way that the integrity and origin can be verified and validated by a third party as having originated from a specific entity in possession of the private key (i.e., the signatory).

owner — A key pair owner is the entity authorized to use the private key of a key pair.

party — An individual person, organization, device, or process. Used interchangeably with entity.

public-key infrastructure (PKI) — A framework that is established to issue, maintain, and revoke public key certificates.

private key — A cryptographic key that is used with an asymmetric (public-key) cryptographic algorithm. The private key is uniquely associated with the owner and is not made public. The private key is used to compute a digital signature that may be verified using the corresponding public key.

pseudorandom — A process or data produced by a process is said to be pseudorandom when the outcome is deterministic yet also effectively random as long as the internal action of the process is hidden from observation. For cryptographic purposes, “effectively random” means “computationally indistinguishable from random within the limits of the intended security strength.”

public key — A cryptographic key that is used with an asymmetric (public-key) cryptographic algorithm and is associated with a private key. The public key is associated with an owner and may be made public. In the case of digital signatures, the public key is used to verify a digital signature that was generated using the corresponding private key.

security category — A number associated with the security strength of a post-quantum cryptographic algorithm, as specified by NIST (see [9, Sect. 5.6]).

security strength — A number associated with the amount of work (i.e., the number of operations) that is required to break a cryptographic algorithm or system.

seed — A bit string used as input to a pseudorandom process.

shall — Used to indicate a requirement of this standard.

should — Used to indicate a strong recommendation but not a requirement of this standard. Ignoring the recommendation could lead to undesirable results.

signatory — The entity that generates a digital signature on data using a private key.

signature generation — The process of using a digital signature algorithm and a private key to generate a digital signature on data.

signature validation — The mathematical verification of the digital signature along with obtaining the appropriate assurances (e.g., public-key validity, private-key possession, etc.).

signature verification — The process of using a digital signature algorithm and a public key to verify a digital signature on data.

signed data — The data or message upon which a digital signature has been computed. Also see message.

trusted third party (TTP) — An entity other than the key pair owner and the verifier that is trusted by the owner, the verifier, or both. Sometimes shortened to “trusted party.”

verifier — The entity that verifies the authenticity of a digital signature using the public key of the signatory.

AES — Advanced Encryption Standard

API — Application Programming Interface

DER — Distinguished Encoding Rules

FIPS — Federal Information Processing Standard

ML-DSA — Module-Lattice-Based Digital Signature Algorithm

MLWE — Module Learning With Errors

NIST — National Institute of Standards and Technology

NIST IR — NIST Interagency or Internal Report

NTT — Number Theoretic Transform

OID — Object Identifier

PQC — Post-Quantum Cryptography

RBG — Random Bit Generator

SHA — Secure Hash Algorithm

SHAKE — Secure Hash Algorithm KECCAK

SP — Special Publication

SUF-CMA Strongly existentially UnForgeable under Chosen Message Attack

XOF — eXtendable-Output Function

The following symbols and mathematical expressions are used in this standard.

\(q\) — The prime number \(q = 2^{23} - 2^{13} + 1 = 8380417\).

\(\mathbb{B}\) — The set \(\{0, 1, \ldots, 255\}\) of integers represented by a byte.

\(\mathbb{N}\) — The set of natural numbers \(\{1, 2, 3, \ldots\}\).

\(\mathbb{Z}\) — The ring of integers.

\(\mathbb{Z}_m\) — The ring of integers modulo \(m\) whose set of elements is \(\{0, 1, \ldots, m - 1\}\).

\(\mathbb{Z}_m^n\) — The set of \(n\)-tuples over \(\mathbb{Z}_m\) equipped with the \(\mathbb{Z}\)-module structure.

\(R\) — The ring of single-variable polynomials over \(\mathbb{Z}\) modulo \(X^{256} + 1\), also denoted by \(\mathbb{Z}[X]/(X^{256} + 1)\).

\(R_m\) — The ring of single-variable polynomials over \(\mathbb{Z}_m\) modulo \(X^{256} + 1\), also denoted by \(\mathbb{Z}_m[X]/(X^{256} + 1)\).

\(B_\tau\) — The set of all polynomials \(p = \sum_{i=0}^{255} p_i X^i\) in \(R_q\) that are such that exactly \(\tau\) of the coefficients of \(p_i\) are from the set \(\{-1, 1\}\), and all other coefficients are zero. (See Section 7.3.)

\(\Pi\) — Used to denote a direct product of two or more rings, where addition and multiplication are performed componentwise.

\(T_q\) — The ring \(\Pi_{j=0}^{255} \mathbb{Z}_q\).

\(A \times B\) — Cartesian product of two sets \(A, B\).

\([a, b]\) — For two integers \(a \le b\), \([a, b]\) denotes the set of integers \(\{a, a + 1, \ldots, b\}\).

\(\mathsf{bitlen}\, a\) — The bit length of a positive integer \(a\). The bit length of \(a\) is the number of digits that would appear in a base-\(2\) representation of \(a\), where the most significant digit in the representation is assumed to be a \(1\) (e.g., \(\mathsf{bitlen}\, 32 = 6\) and \(\mathsf{bitlen}\, 31 = 5\)).¹

\(\mathsf{BitRev}_8(r)\) — Bit reversal of an 8-bit integer \(r\). If \(r = r_0 + 2r_1 + 4r_2 + \ldots + 128r_7\) with \(r_i \in \{0, 1\}\), then \(\mathsf{BitRev}_8(r) = r_7 + 2r_6 + 4r_5 + \ldots + 128r_0\).

0x — Prefix to an integer written in hexadecimal representation.

\(\log_2 x\) — The base 2 logarithm of \(x\). For example, \(\log_2(16) = 4\).

mod — If \(\alpha\) is a positive integer and \(m \in \mathbb{Z}\) or \(m \in \mathbb{Z}_\alpha\), then \(m \bmod \alpha\) denotes the unique element \(m' \in \mathbb{Z}\) in the range \(0 \le m' < \alpha\) such that \(m\) and \(m'\) are congruent modulo \(\alpha\).

\(\mathrm{mod}^{\pm}\) — If \(\alpha\) is a positive integer and \(m \in \mathbb{Z}\) or \(m \in \mathbb{Z}_\alpha\), then \(m \bmod^{\pm} \alpha\) denotes the unique element \(m' \in \mathbb{Z}\) in the range \(-\lceil \alpha/2 \rceil < m' \le \lfloor \alpha/2 \rfloor\) such that \(m\) and \(m'\) are congruent modulo \(\alpha\).

\(\lfloor x \rfloor\) — The largest integer less than or equal to the real number \(x\), called the floor of \(x\). For example, \(\lfloor 2.1 \rfloor = 2\), and \(\lfloor 4 \rfloor = 4\).

\(\lceil x \rceil\) — The least integer greater than or equal to the real number \(x\), called the ceiling of \(x\). For example, \(\lceil 5 \rceil = 5\) and \(\lceil 5.3 \rceil = 6\).

\(\|\cdot\|_\infty\) — The infinity norm. For an element \(w \in \mathbb{Z}\), \(\|w\|_\infty = |w|\), the absolute value of \(w\). For an element \(w \in \mathbb{Z}_q\), \(\|w\|_\infty = \left| w \bmod^{\pm} q \right|\). For an element \(w\) of \(R\) or \(R_q\), \(\|w\|_\infty = \max_{0 \le i < 256} \|w_i\|_\infty\). For a length-\(m\) vector \(\mathbf{w}\) with entries from \(R\) or \(R_q\), \(\|\mathbf{w}\|_\infty = \max_{0 \le i < m} \|w[i]\|_\infty\).

\(a!\) — The factorial quantity \(1 \cdot 2 \cdot 3 \cdot \ldots \cdot a\). The value \(0!\) is defined as 1.

\(\binom{a}{b}\) — For \(a \ge b\), the quantity \(a!/(b!(a - b)!)\).

\(s \leftarrow x\) — In pseudocode, this notation means that the variable \(s\) is assigned the value of the expression \(x\).

\(s \leftarrow \mathbb{B}^\ell\) — In pseudocode, this notation means that the variable \(s\) is assigned the value of an array of \(\ell\) random bytes. The bytes must be generated using randomness from an approved RBG. See Section 3.6.1.

\(x \in S \leftarrow y\) — Type casting. The variable \(x\) is assigned a value in a set \(S\) that is constructed from the value of an expression \(y\) in a possibly different set \(T\). The set \(T\) and the mapping from \(T\) to \(S\) are not explicitly specified, but they should be obvious from the context in which this statement appears.

\([[a < b]]\) — A Boolean predicate. A comparison operator inside double square brackets \([[a < b]]\) denotes that the expression should be evaluated as a Boolean. Booleans can also be interpreted as elements of \(\mathbb{Z}_2\) with 1 denoting true and 0 denoting false.

\(\langle\langle f(x)\rangle\rangle\) — A temporary variable that stores the output of a computation \(f(x)\) so that it can be used many times without needing to be recomputed. This is equivalent to defining a temporary variable \(y \leftarrow f(x)\). Naming the variable \(\langle\langle f(x)\rangle\rangle\) makes the pseudocode less cluttered.

\(a||b\) — Concatenation of two bit or byte strings \(a\) and \(b\).

\(a \circ b\) — Multiplication of \(a\) and \(b\) in the ring \(T_q\).

\(a \cdot b\) or \(ab\) — Multiplication in any of the rings \(\mathbb{Z}, \mathbb{Z}_m, R\), or \(R_m\).

\(a + b\) — Addition of \(a\) and \(b\).

\(a/b\) — Division of integers. When this notation is used, \(a\) and \(b\) are always integers. If \(b\) cannot be assumed to divide \(a\), then either \(\lfloor a/b \rfloor\) or \(\lceil a/b \rceil\) is used.

\(\bot\) — Blank symbol that indicates failure or the lack of an output from an algorithm.

Elements of the rings \(\mathbb{Z}\), \(\mathbb{Z}_q\), \(\mathbb{Z}_2\), \(R\), and \(R_q\) are denoted by italicized lowercase letters (e.g., \(w\)). Elements of the ring \(T_q\) are length-\(256\) arrays of elements of \(\mathbb{Z}_q\), and they are denoted by italicized letters with a hat symbol (e.g., \(\hat{w}\)). The addition and multiplication of elements of \(T_q\) are performed entry-wise. Thus, the \(i\)th entry of the product of two elements \(\hat{u}\) and \(\hat{v}\) of \(T_q\) is \(\hat{u}[i] \cdot \hat{v}[i] \in \mathbb{Z}_q\). The multiplication operation in \(T_q\) is denoted by the symbol \(\circ\) (see Section 2.3).

When a product \(a \cdot b\) or a sum \(a + b\) is written and either \(a\) or \(b\) is a congruence class modulo \(m\) (i.e., if either \(a\) or \(b\) is an element of \(\mathbb{Z}_m\) or \(R_m\)), then the product or sum is also understood to be a congruence class modulo \(m\) (i.e., an element of \(\mathbb{Z}_m\) or \(R_m\)). Likewise, an element of \(R\) or \(\mathbb{Z}\) may be “typecast” to an element of \(R_m\) or \(\mathbb{Z}_m\), respectively, and may be used as the input of a function specified to act on an element of \(R_m\) or \(\mathbb{Z}_m\), respectively. In both cases, the element itself or its coefficients are mapped from \(\mathbb{Z}\) to \(\mathbb{Z}_m\) by taking the unique congruence class modulo \(m\) that contains the integer.

The coefficients of an element \(w\) of \(R\) or \(R_m\) are denoted by \(w_i\) so that \(w = w_0 + w_1 X + \ldots + w_{255} X^{255}\). If \(w\) is in \(R\) (respectively, \(R_m\)) and \(t\) is in \(\mathbb{Z}\) (respectively, \(\mathbb{Z}_d\)), then \(w(t)\) denotes the polynomial \(w = w_0 + w_1 X + \ldots + w_{255} X^{255}\) evaluated at \(X = t\).

Vectors with elements in \(R\) or \(R_m\) are denoted by bold lowercase letters (e.g., \(\mathbf{v}\)). Matrices with elements in \(R\) or \(R_m\) are denoted by bold uppercase letters (e.g., \(\mathbf{A}\)).

If \(S\) is a ring and \(\mathbf{v}\) is a length-\(L\) vector over \(S\), then the entries in the vector \(\mathbf{v}\) are expressed as

The entries of a \(K \times L\) matrix \(\mathbf{A}\) over \(S\) are denoted as \(\mathbf{A}[i,j]\), where \(0 \le i < K\) and \(0 \le j < L\).

The set of all length-\(L\) vectors over \(S\) is denoted by \(S^L\). The set of all \(K \times L\) matrices over \(S\) is denoted by \(S^{K \times L}\). A length-\(L\) vector can also be treated as an \(L \times 1\) matrix.

The Number Theoretic Transform (NTT) is a specific isomorphism between the rings \(R_q\) and \(T_q\). Let \(\zeta = 1753 \in \mathbb{Z}_q\), which is a \(512^{\text{th}}\) root of unity. If \(w \in R_q\), then

where \(\zeta_i = w(\zeta^{2\mathsf{BitRev}_8(i)+1}) \bmod q\). See Section 7.5 for an implementation discussion for NTT and \(\mathsf{NTT}^{-1}\).

The motivation for using NTT is that multiplication is considerably faster in the ring \(T_q\). Since NTT is an isomorphism, for any \(a, b \in R_q\),

If \(\mathbf{A}\) is a matrix with entries from \(R_q\), then \(\mathsf{NTT}(\mathbf{A})\) denotes the matrix computed via the entry-wise application of NTT to \(\mathbf{A}\). The symbol \(\circ\) is also used to denote the matrix multiplication of matrices with entries in \(T_q\). Thus, \(\mathsf{NTT}(\mathbf{AB}) = \mathsf{NTT}(\mathbf{A}) \circ \mathsf{NTT}(\mathbf{B})\). Explicit algorithms for linear algebra over \(T_q\) are given in Section 7.6.

ML-DSA is a digital signature scheme based on CRYSTALS-DILITHIUM [6]. It consists of three main algorithms: ML-DSA.KeyGen (Algorithm 1), ML-DSA.Sign (Algorithm 2), and ML-DSA.Verify (Algorithm 3). The ML-DSA scheme uses the Fiat-Shamir With Aborts construction [10, 11] and bears the most resemblance to the schemes proposed in [12, 13].

This document also defines a closely related but domain-separated signature scheme, HashML-DSA, which differs from ML-DSA in that it includes an additional pre-hashing step before signing. It consists of three main algorithms: ML-DSA.KeyGen (Algorithm 1), which is the same key generation algorithm used for ML-DSA; HashML-DSA.Sign (Algorithm 4); and HashML-DSA.Verify (Algorithm 5).

ML-DSA is designed to be strongly existentially unforgeable under chosen message attack (SUF-CMA). That is, it is expected that even if an adversary can get the honest party to sign arbitrary messages, the adversary cannot create any additional valid signatures based on the signer’s public key, including on messages for which the signer has already provided a signature.

Beyond unforgeability, ML-DSA is designed to satisfy additional security properties described in [14].

Security for lattice-based digital signature schemes is typically related to the Learning With Errors (LWE) problem and the short integer solution (SIS) problem. The LWE problem [15] is to recover a vector \(\mathbf{s} \in \mathbb{Z}_q^n\) given a set of random “noisy” linear equations² satisfied by \(\mathbf{s}\). The SIS problem is to find a non-zero solution \(\mathbf{t} \in \mathbb{Z}_q^n\) for a given linear system over \(\mathbb{Z}_q\) of the form \(\mathbf{A}\mathbf{t} = \mathbf{0}\) such that \(\|\mathbf{t}\|_\infty\) is small. For appropriate choices of parameters, these problems are intractable for the best known techniques, including Gaussian elimination.

When the module \(\mathbb{Z}_q^n\) in LWE and SIS is replaced by a module over a ring larger than \(\mathbb{Z}_q\) (e.g., \(R_q\)), the resulting problems are called Module Learning With Errors (MLWE) [4] and Module Short Integer Solution (MSIS). The security of ML-DSA is based on the MLWE problem over \(R_q\) and a nonstandard variant of MSIS called SelfTargetMSIS [16].

ML-DSA is a Schnorr-like signature with several optimizations. The Schnorr signature scheme applies the Fiat-Shamir heuristic to an interactive protocol between a verifier who knows \(g\) (the generator of a group in which discrete logs are believed to be difficult) and the value \(y = g^x\) and a prover who knows \(g\) and \(x\). The interactive protocol, where the prover demonstrates knowledge of \(x\) to the verifier, consists of three steps:

This protocol is made noninteractive and turned into a signature scheme by replacing the verifier’s random choice of \(c\) in step 2 with a deterministic process that pseudorandomly derives \(c\) from a hash of the commitment \(g^r\) concatenated with the message to be signed. For this signature scheme, \(y\) is the public key, and \(x\) is the private key.

The basic idea of ML-DSA and similar lattice signature schemes is to build a signature scheme from an analogous interactive protocol, where a prover who knows matrices \(\mathbf{A} \in \mathbb{Z}_q^{K \times L}\), \(\mathbf{S}_1 \in \mathbb{Z}_q^{L \times n}\), and \(\mathbf{S}_2 \in \mathbb{Z}_q^{K \times n}\) with small coefficients (for \(\mathbf{S}_1\) and \(\mathbf{S}_2\)) demonstrates knowledge of these matrices to a verifier who knows \(\mathbf{A}\) and \(\mathbf{T} \in \mathbb{Z}_q^{K \times n} = \mathbf{A}\mathbf{S}_1 + \mathbf{S}_2\). Such an interactive protocol would proceed as follows:

As written, the above protocol has a security flaw: the response \(\mathbf{z}\) will be biased in a direction related to the private value \(\mathbf{S}_1\). Likewise \(\mathbf{r} = \mathbf{w}_{\text{Approx}} - \mathbf{A}\mathbf{z} + \mathbf{T}\mathbf{c} = \mathbf{y}_2 + \mathbf{S}_2\mathbf{c}\) is biased in a direction related to the private value \(\mathbf{S}_2\). However, this flaw can be corrected when converting the interactive protocol into a signature scheme. As with Schnorr signatures, the signer derives the challenge by a pseudorandom process from a hash of the commitment concatenated with the message. To correct the bias, the signer applies rejection sampling to \(\mathbf{z}\); if coefficients of \(\mathbf{z}\) fall outside of a specified range, the signing process is aborted, and the signer starts over from a new value of \(\mathbf{y}\). Likewise, similar rejection sampling must also be applied to \(\mathbf{r}\). These checks are analogous to those done at Line 23 of Algorithm 7. In the simplified Fiat-Shamir With Aborts signature, the public key is \((\mathbf{A}, \mathbf{T})\), and the private key is \((\mathbf{S}_1, \mathbf{S}_2)\).

In the ML-DSA standard, a number of tweaks and modifications are added to this basic framework for security or efficiency reasons:

In this document, the abbreviations ML-DSA-44, ML-DSA-65, and ML-DSA-87 are used to refer to ML-DSA with the parameter choices given in Table 1. In these abbreviations, the numerical suffix refers to the dimension of the matrix \(\mathbf{A}\). For example, in ML-DSA-65, the matrix \(\mathbf{A}\) is a \(6 \times 5\) matrix over \(R_q\).

For ML-DSA to be secure, the signer’s commitment value \(\mathbf{y}\) must not be used to sign more than one message, and it must not be easily guessed by an attacker. This requires randomness. In principle, the randomness leading to \(\mathbf{y}\) can be produced either with the use of fresh randomness at signing time or pseudorandomly from the message being signed and a precomputed random value included in the signer’s private key.

By default, this standard specifies the signing algorithm to use both types of randomness. This is referred to as the “hedged” variant of the signing procedure. The use of fresh randomness during signing helps mitigate side-channel attacks, while the use of precomputed randomness protects against the possibility that there may be flaws in the random number generator used by the signer at signing time.

This document also permits a fully deterministic variant of the signing procedure in case the signer has no access to a fresh source of randomness at signing time. However, the lack of randomness in the deterministic variant makes the risk of side-channel attacks (particularly fault attacks) more difficult to mitigate. Therefore, this variant should not be used on platforms where side-channel attacks are a concern and where they cannot be otherwise mitigated.

Only implementing the hedged variant (i.e., without the deterministic variant) is sufficient to guarantee interoperability. The same verification algorithm will work to verify signatures produced by either variant, so implementing the deterministic variant in addition to the hedged variant does not enhance interoperability. The hedged and deterministic signing procedure differ only at line 5 of Algorithm 2 and line 5 of Algorithm 4.

Secure key management is an essential requirement for the use of digital signatures. This is context-dependent and involves more than the key generation, signing, and signature verification algorithms in this document. Guidance for key management is provided in the SP 800-57 series [9, 17, 18].

Digital signatures are most useful when bound to an identity. Binding a public key to an identity requires proof of possession of the private key. In the PKI context, issuing certificates involves assurances of identity and proof of possession. When a public-key certificate is not available, users of digital signatures should determine whether a public key needs to be bound to an identity. Methods for obtaining assurances of identity and proof of possession are provided in [3].

This section describes several required assurances when implementing ML-DSA. These are in addition to the considerations in Section 3.5.

Algorithm 1, implementing key generation for ML-DSA, uses an RBG to generate the 256-bit random seed 𝜉. The seed 𝜉 shall be a fresh (i.e., not previously used) random value generated using an approved RBG, as prescribed in SP 800-90A, SP 800-90B, and SP 800-90C [19, 20, 21]. Moreover, the RBG used shall have a security strength of at least 192 bits for ML-DSA-65 and 256 bits for ML-DSA-87. For ML-DSA-44, the RBG should have a security strength of at least 192 bits and shall have a security strength of at least 128 bits. If an approved RBG with at least 128 bits of security but less than 192 bits of security is used, then the claimed security strength of ML-DSA-44 is reduced from category 2 to category 1.

Additionally, the value \(rnd\) is generated using an RBG in the default “hedged” variants of Algorithms 2 and 4 for ML-DSA and HashML-DSA signing, respectively. While this value should ideally be generated by an approved RBG, other methods for generating fresh random values may be used. The primary purpose of \(rnd\) is to facilitate countermeasures to side-channel attacks and fault attacks on deterministic signatures, such as [22, 23, 24].³ For this purpose, even a weak RBG may be preferable to the fully deterministic variants of Algorithms 2 and 4.

Algorithm 3, implementing verification for ML-DSA, and Algorithm 5, implementing verification for HashML-DSA, specify the length of the signature \(\sigma\) and the public key \(pk\) in terms of the parameters described in Table 1. If an implementation of ML-DSA can accept inputs for \(\sigma\) or \(pk\) of any other length, it shall return false whenever the lengths of either of these inputs differ from their lengths specified in this standard. Failing to check the length of \(pk\) or \(\sigma\) may interfere with the security properties that ML-DSA is designed to have, like strong unforgeability.

The data used internally by the key generation and signing algorithms in intermediate computation steps could be used by an adversary to gain information about the private key and thereby compromise security. The data used internally by verification algorithms is similarly sensitive for some applications, including the verification of signatures that are used as bearer tokens (i.e., authentication secrets) or the verification of signatures on plaintext messages that are intended to be confidential. Intermediate values of the verification algorithm may reveal information about its inputs (i.e., the message, signature, and public key), and in some applications, security or privacy requires one or more of these inputs to be confidential. Therefore, implementations of ML-DSA shall ensure that any potentially sensitive intermediate data is destroyed as soon as it is no longer needed.

Two particular cases in which implementations may refrain from destroying intermediate data are:

In certain situations (e.g., deterministic signing and the verification of confidential messages and signatures), additional care must be taken to protect implementations against side-channel attacks or fault attacks. A cryptographic device may leak critical information through side channels, which allows internal data or keying material to be extracted without breaking the cryptographic primitives.

Implementations of ML-DSA shall not use floating-point arithmetic, as rounding errors in floating point operations may lead to incorrect results in some cases. Either \(\lfloor x/y \rfloor\) or \(\lceil x/y \rceil\) is used in all pseudocode in this standard in which division is performed (e.g., \(x/y\)), and \(y\) may not divide \(x\). Both of these can be computed without floating-point arithmetic, as ordinary integer division \(x/y\) computes \(\lfloor x/y \rfloor\), and \(\lceil x/y \rceil = \lfloor (x+y-1)/y \rfloor\) for non-negative integers \(x\) and positive integers \(y\). If \(y\) is a power of two, it may be more efficient to use bit shift operations than integer division.

This standard makes use of the functions SHAKE256 and SHAKE128, as defined in FIPS 202 [7]. While FIPS 202 specifies these functions as inputting and outputting bit strings, most implementations treat inputs and outputs as byte strings.

This standard will always call these functions with an output length of a multiple of eight bits and treat the output of these functions as a byte string, which will be the same byte string that would result from taking the bit string expected from a literal reading of FIPS 202 and processing it with BitsToBytes. However, to allow the signing of messages that are not a whole number of bytes, this document will overload SHAKE256 so that its input may be a bit string but will usually be a byte string. The following equivalence will hold for any byte string str and integer \(\ell \ge 1\):

In addition to using a mostly byte-oriented variant of the API defined in FIPS 202 for SHAKE256 and SHAKE128, this standard sometimes makes use of the incremental API defined in SP 800-185 [25]. This API consists of three functions for each variant of SHAKE. These functions can be used to absorb a sequence of arbitrary-length strings and squeeze a sequence of arbitrary-length strings. These functions perform buffering to handle any incomplete data blocks while absorbing or squeezing. For example, for SHAKE256:

While the above functions are specified in terms of the Keccak-\(f\) permutation rather than the eXtendable-Output Function (XOF), SHAKE256, they are defined so that any series of commands of the following form:

will yield the same output as a single SHAKE256 call:

This equivalence holds whether or not \(|\mathsf{str}_i|\) and \(b_j\) are multiples of the SHAKE256 block length.

Since all outputs of SHAKE128 and SHAKE256 in this document give a whole number of bytes, the wrapper functions H and G are defined as follows:

In addition to SHAKE128 and SHAKE256, HashML-DSA.Sign and HashML-DSA.Verify may call other approved hash functions for pre-hashing. The pseudocode in this standard also treats these functions as returning a byte string as output while supporting either a bit string or a byte string as input. Here, it should be noted that the hash functions defined in [8] use different rules (i.e., big-endian ordering) to relate bits, bytes, and words.

Table 1. ML-DSA parameter sets

Three ML-DSA parameter sets are included in Table 1. Each parameter set assigns values for all of the parameters used in the ML-DSA algorithms for key generation, signing, and verification. For informational purposes, some parameters used in the analysis of these algorithms are also included in the table. In particular, “repetitions” refers to the expected number of repetitions of the main loop in the signing algorithm from eq. 5 in [5]. The names of the parameter sets are of the form “ML-DSA-\(k\ell\),” where \((k, \ell)\) are the dimensions of the matrix \(\mathbf{A}\).

These parameter sets were designed to meet certain security strength categories defined by NIST in its original Call for Proposals [26]. These security strength categories are explained further in SP 800-57, Part 1 [9].

Using this approach, security strength is not described by a single number, such as “128 bits of security.” Instead, each ML-DSA parameter set is claimed to be at least as secure as a generic block cipher with a prescribed key size or a generic hash function with a prescribed output length. More precisely, it is claimed that the computational resources needed to break ML-DSA are greater than or equal to the computational resources needed to break the block cipher or hash function when these computational resources are estimated using any realistic model of computation. Different models of computation can be more or less realistic and, accordingly, lead to more or less accurate estimates of security strength. Some commonly studied models are discussed in [27].

Concretely, the parameter set ML-DSA-44 is claimed to be in security strength category 2, ML-DSA-65 is claimed to be in category 3, and ML-DSA-87 is claimed to be in category 5 [6]. For additional discussion of the security strength of MLWE-based cryptosystems, see [28].

The sizes of keys and signatures that correspond to each parameter set are given in Table 2. Certain optimizations are possible when storing ML-DSA public and private keys. If additional space is available, one can precompute and store \(\hat{\mathbf{A}}\) to speed up signing and verifying. Alternatively, if one wants to reduce the space needed for the private key, one can store only the 32-byte seed \(\xi\), which is sufficient to generate the other parts of the private key. For additional details, see Section 3.1 in [6].

Table 2. Sizes (in bytes) of keys and signatures of ML-DSA

The signing, verifying, and key generation functions can be split into “external” and “internal” components to simplify APIs and Cryptographic Algorithm Validation Program (CAVP) testing. The external components generate randomness and perform various checks before calling their internal counterparts. The internal components are deterministic and can assume that the external components did not encounter error conditions.

The distinction between external and internal functions also simplifies the presentation of algorithms for signing and verification by grouping the operations that are shared between ML-DSA.Sign and HashML-DSA.Sign in ML-DSA.Sign_internal and grouping the operations that are shared between ML-DSA.Verify and HashML-DSA.Verify in ML-DSA.Verify_internal.

The key generation algorithm ML-DSA.KeyGen takes no input and outputs a public key and a private key, which are both encoded as byte strings.

The algorithm uses an approved RBG to generate a 256-bit (32-byte) random seed 𝜉 that is given as input to ML-DSA.KeyGen_internal (Algorithm 6), which produces the public and private keys.

Generates a public-private key pair.

The signing algorithm ML-DSA.Sign (Algorithm 2) takes a private key, a message, and a context string as input\(^{4}\). It outputs a signature that is encoded as a byte string.

For the default “hedged” version of ML-DSA signing, the algorithm (at line 5) uses an approved RBG to generate a 256-bit (32-byte) random seed \(rnd\). If the deterministic variant is desired, then \(rnd\) is set to the fixed zero string \(\{0\}^{32}\). The value \(rnd\), the private key, and the encoded message are input to ML-DSA.Sign_internal (Algorithm 7), which produces the signature.

Generates an ML-DSA signature.

The verification algorithm ML-DSA.Verify (Algorithm 3) takes a public key, a message, a signature, and a context string as input. The public key, signature, and context string are all encoded as byte strings, while the message is a bit string. ML-DSA.Verify outputs a Boolean value that is true if the signature is valid with respect to the message and the public key and false if the signature is invalid. The verification is accomplished by calling ML-DSA.Verify_internal (Algorithm 8) with the public key, the encoded message, and the signature.

Verifies a signature \(\sigma\) for a message \(M\).

For some cryptographic modules that generate ML-DSA signatures, hashing the message in step 6 of ML-DSA.Sign_internal may result in unacceptable performance if the message 𝑀 is large. For example, the platform may require hardware support for hashing to achieve acceptable performance but lack hardware support for SHAKE256 specifically. For some use cases, this may be addressed by signing a digest of the message along with some domain separation information rather than signing the message directly. This version of ML-DSA is known as “pre-hash” ML-DSA or HashML-DSA . In general, the “pure” ML-DSA version is preferred.

While key generation for HashML-DSA is the same as for ML-DSA, it is not the same for the signing algorithm HashML-DSA.Sign or the verification algorithm HashML-DSA.Verify. Like ML-DSA, the signing algorithm of HashML-DSA takes the content to be signed, the private key, and a context as input, as well as a hash function or XOF that is to be used to pre-hash the content to be signed. The context string has a maximum length of 255 bytes. By default, the context is the empty string, though applications may specify the use of a non-empty context string.

The identifier for a signature (e.g., the object identifier [OID]) should indicate whether the signature is a ML-DSA signature or a pre-hash HashML-DSA signature. In the case of pre-hash signatures, the identifier should also indicate the hash function or XOF used to compute the pre-hash. 5 While a single key pair may be used for both ML-DSA and HashML-DSA signatures, it is recommended that each key pair only be used for one version or the other. If a non-empty context string is to be used, this should either be indicated by the signature’s identifier or by the application with which the signature is being used.

If the default “hedged” variant of is used, the 32-byte random value \(rnd\) shall be generated by the cryptographic module that generates the signature (i.e., that runs ML-DSA.Sign_internal). However, all other steps of signing may be performed outside of the cryptographic module that generates the signature. In the case of pre-hashing, the hash or XOF of the content to be signed must be computed within a FIPS 140-validated cryptographic module, but it may be a different cryptographic module than the one that generates the signature.

If the content to be signed is large, hashing of the content is often performed at the application level. For example, in the Cryptographic Message Syntax [29], a digest of the content may be computed, and that digest is signed along with other attributes. If the content is not hashed at the application level, the pre-hash version of ML-DSA signing may be used.

In order to maintain the same level of security strength when the content is hashed at the application level or using HashML-DSA, the digest that is signed needs to be generated using an approved hash function or XOF (e.g., from FIPS 180 [8] or FIPS 202 [7]) that provides at least \(\lambda\) bits of classical security strength against both collision and second preimage attacks [7, Table 4].⁶ The verification of a signature that is created in this way will require the verify function to generate a digest from the message in the same way to be used as input for the verification function.

In the HashML-DSA version, the message input to ML-DSA.Sign_internal is the result of applying either a hash function or a XOF to the content to be signed. The output of the hash function or XOF is prepended by a one-byte domain separator, one byte that indicates the length of the context string, the context string, and the distinguished encoding rules (DER) encoding of the hash function or XOF’s OID. The domain separator has a value of one for “pre-hash” signing. The DER encoding of the OID includes the tag and length.

Algorithm 4 shows the DER encodings of the OIDs for SHA-256, SHA-512, and SHAKE128. However, it may be used with other hash functions or XOFs.

Generate a “pre-hash” ML-DSA signature.

Algorithm 5 presents the signature verification for HashML-DSA. This function constructs \(M'\) in the same way as Algorithm 4 and passes the resulting \(M'\) to Algorithm ML-DSA.Verify_internal for verification. As with the pre-hash signature generation, \(M'\) may be constructed outside of the cryptographic module that performs ML-DSA.Verify_internal. However, in the case of HashML-DSA, the hash or XOF of the content must be computed within a FIPS 140-validated cryptographic module, which may be a different cryptographic module than the one that performs ML-DSA.Verify_internal.

As noted in Section 5.4, the identifier associated with the signature should indicate whether ML-DSA or the pre-hash version HashML-DSA of signature verification should be used, as well as the hash function or XOF to be used to compute the pre-hash. A non-empty context string should be used in verification if one is specified either in the signature’s identifier or by the application with which the signature is being used.

Verifies a pre-hash HashML-DSA signature.

This section describes the functions for ML-DSA key generation, signature generation, and signature verification. Where randomness is required, the random values are provided as inputs to the functions. The interfaces specified in this section will be used when testing of ML-DSA implementations is performed through the CAVP.

Other than for testing purposes, the interfaces for key generation and signature generation specified in this section should not be made available to applications, as any random values required for key generation and signature generation shall be generated by the cryptographic module. Section 5 provides guidance on the interfaces to be made available to applications.⁷

The internal key generation algorithm ML-DSA.KeyGen_internal takes a 32-byte random seed as input and outputs a public key and a private key that are both encoded as byte strings.

The seed \(\xi\) is expanded as needed using an XOF (i.e., a byte-variant of SHAKE256) denoted by H to produce other random values.⁸ In particular:

The core cryptographic operation computes the public value

The vector \(\mathbf{t}\) together with the matrix \(\mathbf{A}\) may be considered an expanded form of the public key. The vector \(\mathbf{t}\) is compressed in the actual public key by dropping the \(d\) least significant bits from each coefficient, thus producing the polynomial vector \(\mathbf{t}_1\). This compression is an optimization for performance, not security. The low-order bits of \(\mathbf{t}\) can be reconstructed from a small number of signatures and, therefore, need not be regarded as secret.

The ML-DSA public key \(pk\) is a byte encoding of the public random seed \(\rho\) and the compressed polynomial vector \(\mathbf{t}_1\).

The ML-DSA private key 𝑠𝑘 is a byte encoding of the public random seed 𝜌, a private random seed 𝐾 for use during signing, a 64-byte hash 𝑡𝑟 of the public key for use during signing, the secret polynomial

vectors \(\mathbf{s}_1\) and \(\mathbf{s}_2\), and a polynomial vector \(\mathbf{t}_0\) encoding the \(d\) least significant bits of each coefficient of the uncompressed public-key polynomial \(\mathbf{t}\).

ML-DSA.Sign_internal (Algorithm 7) outputs a signature encoded as a byte string. It takes a private key \(sk\) encoded as a byte string, a formatted message \(M'\) encoded as a bit string, and a 32-byte string \(rnd\) as input. There are two ways that a signing algorithm can use ML-DSA.Sign_internal: “hedged” and “deterministic.” The default “hedged” variants of ML-DSA.Sign and HashML-DSA.Sign use a fresh random value for \(rnd\), while the optional deterministic variants use the constant byte string \(\{0\}^{32}\) (see Section 3).

In both variants, the signer first extracts the following from the private key: the public random seed \(\rho\), the \(32\)-byte private random seed \(K\), the \(64\)-byte hash of the public key \(tr\), the secret polynomial vectors \(\mathbf{s}_1\) and \(\mathbf{s}_2\), and the polynomial vector \(\mathbf{t}_0\) encoding the \(d\) least significant bits of each coefficient of the uncompressed public-key polynomial \(\mathbf{t}\). \(\rho\) is then expanded to the same matrix \(\mathbf{A}\) as in key generation.

Before the message \(M\) is signed, it is concatenated with the public-key hash \(tr\) and hashed down to a \(64\)-byte message representative \(\mu\) using H.

The signer produces an additional \(64\)-byte seed \(\rho''\) for private randomness during each signing operation. \(\rho''\) is computed as \(\rho'' \leftarrow \mathsf{H}(K \| rnd \| \mu, 64)\). In the default hedged variant, \(rnd\) is the output of an RBG, while in the deterministic variant, \(rnd\) is a \(32\)-byte string that consists entirely of zeros. This is the only difference between the deterministic and hedged variant of ML-DSA.Sign.

The main part of the signing algorithm consists of a rejection sampling loop in which each iteration of the loop either produces a valid signature or an invalid signature whose release would leak information about the private key. The loop is repeated until a valid signature is produced, which can then be encoded as a byte string and output.¹⁰ The rejection sampling loop follows the Fiat-Shamir With Aborts paradigm [10] and (aside from the rejection step) is similar in structure to Schnorr signatures [30] (e.g., EdDSA [31]). The signer first produces a “commitment” \(\mathbf{w}_1\) and then pseudorandomly derives a “challenge” \(c\) from \(\mathbf{w}_1\) and the message representative \(\mu\). Finally, the signer computes a response \(\mathbf{z}\).

In more detail, the main computations involved in the rejection sampling loop are as follows:

In addition, there is an alternative way of implementing the validity checks on 𝐳 and the computation of 𝐡, which is described in Section 5.1 of [6]. This method may also be used in implementations of ML-DSA.

In Algorithm 7, variables are sometimes used to store products to avoid recomputing them later in the signing algorithm. These precomputed products are denoted in the pseudocode by a pair of double angle brackets enclosing the variables being multiplied (e.g., \(\langle\langle c\mathbf{s}_1 \rangle\rangle\)).

Deterministic algorithm to generate a signature for a formatted message \(M'\).

The algorithm ML-DSA.Verify_internal (Algorithm 8) takes a public key \(pk\) encoded as a byte string, a message \(M\) encoded as a bit string, and a signature \(\sigma\) encoded as a byte string as input. No randomness is required for ML-DSA.Verify_internal. It produces a Boolean value (i.e., a value that is true if the signature is valid with respect to the message and public key and false if the signature is invalid) as output. Algorithm 8 specifies the lengths of the signature 𝜎 and the public key 𝑝𝑘 in terms of the parameters described in Table 1. If an implementation of ML-DSA.Verify_internal can accept inputs for 𝜎 or 𝑝𝑘 of any other length, it shall return false whenever the length of either of these inputs differs from its specified length.

The verifier first extracts the public random seed \(\rho\) and the compressed polynomial vector \(\mathbf{t}_1\) from the public key \(pk\) and then extracts the signer’s commitment hash \(\tilde{c}\), response \(\mathbf{z}\), and hint \(\mathbf{h}\) from the signature \(\sigma\). The verifier may find that the hint was not properly byte-encoded, denoted by the symbol “\(\bot\),” in which case the verification algorithm will immediately return false to indicate that the signature is invalid.

Assuming that the signature is successfully extracted from its byte encoding, the verifier pseudorandomly derives \(\mathbf{A}\) from \(\rho\), as is done in key generation and signing, and creates a message representative \(\mu\) by hashing the concatenation of \(tr\) (i.e., the hash of the public key \(pk\)) and the message \(M\). The verifier then attempts to reconstruct the signer’s commitment (i.e., the polynomial vector \(\mathbf{w}_1\)) from the public key \(pk\) and the signature \(\sigma\). In ML-DSA.Sign_internal, \(\mathbf{w}_1\) is computed by rounding \(\mathbf{w} = \mathbf{A}\mathbf{y}\). In ML-DSA.Verify_internal, the reconstructed value of \(\mathbf{w}_1\) is called \(\mathbf{w}'_1\) since it may have been computed in a different way if the signature is invalid. This \(\mathbf{w}'_1\) is computed through the following process:

Assuming the signature was computed correctly, as in ML-DSA.Sign_internal, it follows that

because \(c\) and \(\mathbf{s}_2\) have small coefficients, and \(\mathbf{t}_1 \cdot 2^d \approx \mathbf{t}\).

Finally, the verifier checks that the signer’s response \(\mathbf{z}\) and the signer’s hint \(\mathbf{h}\) are valid and that the reconstructed \(\mathbf{w}'_1\) is consistent with the signer’s commitment hash \(\tilde{c}\). More precisely, the verifier checks that all of the coefficients of \(\mathbf{z}\) are sufficiently small (i.e., in the range \((-(\gamma_1 - \beta), \gamma_1 - \beta)\)), \(\mathbf{h}\) contains no more than \(\omega\) nonzero coefficients, and \(\tilde{c}\) matches the hash \(\tilde{c}'\) of the message representative \(\mu\) concatenated with \(\mathbf{w}'_1\) (represented as a byte string). If all of these checks succeed, then ML-DSA.Verify_internal returns true. Otherwise, it returns false.

This section provides pseudocode for subroutines utilized by ML-DSA, including functions for data-type conversions, arithmetic, and sampling.

While the primary data type in ML-DSA is a byte string, other data types are used as well. The goal in this section is to construct procedures for translating between the various algebraic objects defined in Section 2.3. Algorithms 9–13 are intermediate procedures for converting between bit strings, byte strings, and integers.

Converts a bit string into a byte string using little-endian order.

Converts a byte string into a bit string using little-endian order.

Algorithms 14 and 15 translate byte strings into coefficients of polynomials in \(R\). CoeffFromThreeBytes uses a 3-byte string to either generate an element of \(\{0, 1, \dots, q - 1\}\) or return the blank symbol \(\bot\). CoeffFromHalfByte uses an element of \(\{0, 1, \dots, 15\}\) to either generate an element of \(\{-\eta, -\eta+1, \dots, \eta\}\) or return \(\bot\). These two procedures will be used in the uniform sampling algorithms RejNTTPoly and RejBoundedPoly, which are discussed in Section 7.3.

Generates an element of \(\{0, 1, 2, \dots, q - 1\} \cup \{\bot\}\).

Let \(\eta \in \{2, 4\}\). Generates an element of \(\{-\eta, -\eta + 1, \dots, \eta\} \cup \{\bot\}\).

Algorithms 16–19 efficiently translate an element \(w \in R\) into a byte string and vice versa under the assumption that the coefficients of \(w\) are in a restricted range. SimpleBitPack assumes that \(w_i \in [0, b]\) for some positive integer \(b\) and packs \(w\) into a byte string of length \(32 \cdot \mathsf{bitlen}\, b\). BitPack allows for the more general restriction \(w_i \in [-a, b]\). The BitPack algorithm works by merely subtracting \(w\) from the polynomial \(\sum_{i=0}^{255} bX^i\).

Encodes a polynomial \(w\) into a byte string.

Encodes a polynomial \(w\) into a byte string.

SimpleBitUnpack and BitUnpack are used to decode the byte strings produced by the above functions. For some choices of \(a\) and \(b\), there exist malformed byte strings that will cause SimpleBitUnpack and BitUnpack to output polynomials whose coefficients are not in the ranges \([0, b]\) and \([-a, b]\), respectively. This can be a concern when running SimpleBitUnpack and BitUnpack on inputs that may come from an untrusted source.

Reverses the procedure \(\mathsf{SimpleBitPack}\).

Reverses the procedure \(\mathsf{BitPack}\).

Algorithms 20 and 21 carry out byte-string-to-polynomial conversions for polynomials with sparse binary coefficients. In particular, the signing and verification algorithms (Sections 6.2 and 6.3) make use of a “hint,” which is a vector of polynomials \(\mathbf{h} \in R_2^k\) such that the total number of coefficients in \(\mathbf{h}[0], \mathbf{h}[1], \ldots, \mathbf{h}[k-1]\) that are equal to \(1\) is no more than \(\omega\). This constraint enables encoding and decoding procedures that are more efficient (although more complex) than \(\mathsf{BitPack}\) and \(\mathsf{BitUnpack}\).

\(\mathsf{HintBitPack}\) \((\mathbf{h})\) outputs a byte string \(y\) of length \(\omega + k\). The last \(k\) bytes of \(y\) contain information about how many nonzero coefficients are present in each of the polynomials \(\mathbf{h}[0], \mathbf{h}[1], \ldots, \mathbf{h}[k - 1]\), and the first \(\omega\) bytes of \(y\) contain information about exactly where those nonzero terms occur. \(\mathsf{HintBitUnpack}\) reverses the procedure performed by \(\mathsf{HintBitPack}\) and recovers the vector \(\mathbf{h}\).

Encodes a polynomial vector \(\mathbf{h}\) with binary coefficients into a byte string.

Reverses the procedure \(\mathsf{HintBitPack}\).

Algorithms 22–27 translate keys and signatures for ML-DSA into byte strings. These procedures take certain sequences of algebraic objects, encode them consecutively into byte strings, and perform the respective decoding procedures.

First, pkEncode and pkDecode translate ML-DSA public keys into byte strings and vice versa. When verifying a signature, pkDecode might be run on an input that comes from an untrusted source. Thus, care is required when using SimpleBitUnpack. As used here, SimpleBitUnpack always returns values in the correct range.

Encodes a public key for ML-DSA into a byte string.

Reverses the procedure pkEncode.

Next, skEncode and skDecode translate ML-DSA secret keys into byte strings and vice versa. Note that there exist malformed inputs that can cause skDecode to return values that are not in the correct range. Hence, skDecode should only be run on inputs that come from trusted sources.

Encodes a secret key for ML-DSA into a byte string.

Reverses the procedure skEncode.

w1Encode is a specific subroutine used in ML-DSA.Sign. The procedure w1Encode encodes a polynomial vector \(\mathbf{w}_1\) into a string of bytes so that it can be processed by the function H.

This section specifies various algorithms for generating algebraic objects pseudorandomly from a seed \(\rho\), where \(\rho\) is a byte string whose length varies depending on the algorithm. The first procedure to be defined is SampleInBall. As in Section 2.3, \(B_\tau\) denotes the set of all polynomials \(c \in R\) such that

SampleInBall pseudorandomly generates an element of \(B_\tau\) using the XOF of a seed \(\rho\). The procedure is based on the Fisher-Yates shuffle. H is applied to \(\rho\), and the first \(8\) bytes of the output are used to choose the signs of the nonzero entries of \(c\).12 Subsequent bytes are used to choose the positions of those nonzero entries.

Algorithms 30–34 are the pseudorandom procedures RejNTTPoly, RejBoundedPoly, ExpandA, ExpandS, and ExpandMask. Each generates elements of \(R\) or \(T_q\) under different input and output conditions. RejNTTPoly and ExpandA make use of the more efficient XOF G, whereas the other three procedures use the XOF H.

The procedure ExpandMask (Algorithm 34) generates a polynomial vector \(\mathbf{y}\) in \(R^k\) that disguises the secret key in the ML-DSA.Sign_internal procedure (Algorithm 7). In addition to the seed \(\rho\), ExpandMask also accepts an integer input \(\mu\) that is incorporated into the pseudorandom procedure that generates \(\mathbf{s}\).

Samples a polynomial \(\in T_q\).

Samples an element \(a \in R\) with coefficients in \([-\eta, \eta]\) computed via rejection sampling from \(\rho\).

Samples a \(k \times \ell\) matrix \(\hat{\mathbf{A}}\) of elements of \(T_q\).

Samples vectors \(\mathbf{s}_1 \in R^\ell\) and \(\mathbf{s}_2 \in R^k\), each with polynomial coordinates whose coefficients are in the interval \([-\eta, \eta]\).

Samples a vector \(\mathbf{y} \in R^\ell\) such that each polynomial \(\mathbf{y}[r]\) has coefficients between \(-\gamma_1 + 1\) and \(\gamma_1\).

This specification uses the auxiliary functions Power2Round, Decompose, HighBits, LowBits, MakeHint, and UseHint and explicitly defines these functions, where \(r \in \mathbb{Z}_q\), \(r_1, r_0 \in \mathbb{Z}\), and \(h\) is a Boolean (or equivalently an element of \(\mathbb{Z}_2\)). However, this specification also uses these functions where \(\mathbf{r}, \mathbf{z} \in R_q^k\), \(\mathbf{r}_1, \mathbf{r}_0 \in R^k\), and \(\mathbf{h} \in R_2^k\). In this case, the functions are applied coefficientwise to the polynomials in the vectors. In particular:

These algorithms are used to support the key compression optimization of ML-DSA. They involve dropping the \(d\) low-order bits of each coefficient of the polynomial vector \(\mathbf{t}\) from the public key using the function Power2Round. However, in order to make this optimization work, additional information called a “hint” needs to be provided in the signature to allow the verifier to reconstruct enough of the information in the dropped public-key bits to verify the signature. Hints are created during signing and used during verification by the functions MakeHint and UseHint, respectively. In the verification of a valid signature, the hint allows the verifier to recover \(\mathbf{w}_1 \in R^k\), which represents \(\mathbf{w} \in R_q^k\) rounded to a nearby multiple of \(\alpha = 2\gamma_2\). The signer directly obtains \(\mathbf{w}_1\) using the function HighBits, and the part rounded off (i.e., \(\mathbf{r}_0\)) is obtained by LowBits. \(\mathbf{r}_0\) is used by the signer in the rejection sampling procedure.

Power2Round decomposes an input \(r \in \mathbb{Z}_q\) into integers that represent the high- and low-order bits of \(r \bmod q\) in the straightforward bitwise way, \(r \bmod q = r_1 \cdot 2^d + r_0\), where \(r_0 = (r \bmod q) \bmod^{\pm} 2^d\) and \(r_1 = (r \bmod q - r_0)/2^d\).

However, for the purpose of computations related to hints, this method of decomposing \(r\) has the undesirable property that when \(r\) is close to \(q-1\) or 0, a small rounding error in \(r\) can cause \(r_1\) to change by more than 1, even accounting for wrap-around. In contrast to other unequal pairs of values of \(r_1 \cdot 2^d\) and \(r_1' \cdot 2^d\), the distance (mod\(q\)) between \(\lfloor q/2^d \rfloor \cdot 2^d\) and 0 may be very small.

To avoid this problem, this specification defines Decompose, which is similar to Power2Round except:

The functions HighBits and LowBits — which only return \(r_1\) and \(r_0\), respectively — and MakeHint and UseHint use Decompose. For additional discussion of the mathematical properties of these functions that are relevant to the correctness and security of ML-DSA, see Section 2.4 in [6].

Returns \(r_0\) from the output of \(\mathsf{Decompose}(r)\).

Computes hint bit indicating whether adding \(z\) to \(r\) alters the high bits of \(r\).

Returns the high bits of \(r\) adjusted according to hint \(h\).

The following algorithms implement the NTT and its inverse (\(\mathsf{NTT}^{-1}\)), which is important for efficiency. There are other optimizations that are not included in this standard. In particular, \(\bmod q\) and \(\bmod^{\pm} q\) are expensive operations whose use can be minimized by using Montgomery Multiplication (see Appendix A).

An element of \(R_q\) is a polynomial in \(\mathbb{Z}_q[X]/(X^{256}+1)\), and an element of \(T_q\) is a tuple in \(\Pi_{j=0}^{255}\mathbb{Z}_q\). The \(\mathsf{NTT}\) algorithm takes a polynomial \(w \in R_q\) as input and returns \(\hat{w} \in T_q\). \(\mathsf{NTT}^{-1}\) takes \(\hat{w} \in T_q\) as input and returns \(w\) such that \(\hat{w} = \mathsf{NTT}(w)\).

This document always distinguishes between elements of \(R_q\) and elements of \(T_q\). However, the natural data structure for both of these sets is as an integer array of size \(256\). This would allow the \(\mathsf{NTT}\) and \(\mathsf{NTT}^{-1}\) algorithms to perform computation in place on an integer array passed by reference. That optimization is not included in this document.

In Section 2.5, \(\zeta = 1753 \in \mathbb{Z}_q\), which is a \(512\)th root of unity modulo \(q\). On input \(w \in R_q\), the algorithm outputs

where \(\zeta_i = w(\zeta^{2\mathsf{BitRev}_8(i)+1}) \bmod q\).

The values \(\zeta^{\mathsf{BitRev}_8(k)} \bmod q\) for \(k = 1, \ldots, 255\) used in line 10 of Algorithms 41 and 42 are pre-computed into an array \(\mathsf{zetas}[1..255]\). The table of zetas is given in Appendix B. If Montgomery Multiplication is used (see Appendix A), then the zetas array would typically be stored in Montgomery form.

\(\mathsf{NTT}\) and \(\mathsf{NTT}^{-1}\) use \(\mathsf{BitRev}_8\), which reverses the order of bits in an 8-bit integer.

Computes the NTT.

Computes the inverse of the NTT.

Transforms a byte by reversing the order of bits in its 8-bit binary expansion.

The \(\mathsf{NTT}\) converts elements of the ring \(R_q\) (where addition and multiplication are denoted by \(+\) and \(\cdot\), respectively) into elements of the ring \(T_q\) (where addition and multiplication are denoted by \(+\) and \(\circ\), respectively). This section gives explicit algorithms for linear algebra over the ring \(T_q\).

The ring \(T_q\) is defined to be the direct product ring \(\Pi_{i=0}^{255}\mathbb{Z}_q\). Thus, an element \(\hat{a} \in T_q\) is an array of length \(256\), and its elements are denoted by \(\hat{a}[0], \hat{a}[1], \ldots, \hat{a}[255] \in \mathbb{Z}_q\).

Computes the sum \(\hat{a} + \hat{b}\) of two elements \(\hat{a}, \hat{b} \in T_q\).

Computes the product \(\hat{a} \circ \hat{b}\) of two elements \(\hat{a}, \hat{b} \in T_q\).

Computes the sum \(\hat{\mathbf{v}} + \hat{\mathbf{w}}\) of two vectors \(\hat{\mathbf{v}}, \hat{\mathbf{w}}\) over \(T_q\).

Computes the product \(\hat{c} \circ \hat{\mathbf{v}}\) of a scalar \(\hat{c}\) and a vector \(\hat{\mathbf{v}}\) over \(T_q\).

Computes the product \(\hat{\mathbf{M}} \circ \hat{\mathbf{v}}\) of a matrix \(\hat{\mathbf{M}}\) and a vector \(\hat{\mathbf{v}}\) over \(T_q\).

[1] National Institute of Standards and Technology (2023) Digital signature standard (DSS), (U.S. Department of Commerce, Washington, DC), Federal Information Processing Standards Publication (FIPS) 186-5. https://doi.org/10.6028/NIST.FIPS.186-5.

[2] Barker E (2020) Guideline for using cryptographic standards in the federal government: Cryptographic mechanisms, (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-175B, Rev. 1 [or as amended]. https://doi.org/10.6028/NIST.SP.800-175Br1.

[3] Barker E (2006) Recommendation for obtaining assurances for digital signature applications, National Institute of Standards and Technology, Gaithersburg, MD. NIST Special Publication (SP) 800-89 [or as amended]. https://doi.org/10.6028/NIST.SP.800-89.

[4] Langlois A, Stehlé D (2015) Worst-case to average-case reductions for module lattices. Designs, Codes and Cryptography 75(3):565–599. https://doi.org/10.1007/s10623-014-9938-4.

[5] Bai S, Ducas L, Kiltz E, Lepoint T, Lyubashevsky V, Schwabe P, Seiler G, Stehlé D (2020) CRYSTALS-Dilithium: Algorithm specifications and supporting documentation, Submission to the NIST’s post-quantum cryptography standardization process. Available at https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standardization/round-3-submissions.

[6] Bai S, Ducas L, Kiltz E, Lepoint T, Lyubashevsky V, Schwabe P, Seiler G, Stehlé D (2021) CRYSTALS-Dilithium: Algorithm specifications and supporting documentation (Version 3.1). Available at https://pq-crystals.org/dilithium/data/dilithium-specification-round3-20210208.pdf.

[7] National Institute of Standards and Technology (2015) SHA-3 standard: Permutation-based hash and extendable-output functions, (U.S. Department of Commerce, Washington, DC), Federal Information Processing Standards Publication (FIPS) 202. https://doi.org/10.6028/NIST.FIPS.202.

[8] National Institute of Standards and Technology (2015) Secure hash standard (SHS), (U.S. Department of Commerce, Washington, DC), Federal Information Processing Standards Publication (FIPS) 180-4. https://doi.org/10.6028/NIST.FIPS.180-4.

[9] Barker E (2020) Recommendation for key management: Part 1 - general, (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-57 Part 1, Rev. 5 [or as amended]. https://doi.org/10.6028/NIST.SP.800-57pt1r5.

[10] Lyubashevsky V (2009) Fiat-Shamir with aborts: Applications to lattice and factoring-based signatures. Advances in Cryptology – ASIACRYPT 2009, ed Matsui M (Springer Berlin Heidelberg, Berlin, Heidelberg), pp 598–616. https://doi.org/10.1007/978-3-642-10366-7_35.

[11] Lyubashevsky V (2012) Lattice signatures without trapdoors. EUROCRYPT (Springer), Lecture Notes in Computer Science, Vol. 7237, pp 738–755. https://doi.org/10.1007/978-3-642-29011-4_43.

[12] Güneysu T, Lyubashevsky V, Pöppelmann T (2012) Practical lattice-based cryptography: A signature scheme for embedded systems. CHES (Springer), Vol. 7428, pp 530–547. https://doi.org/10.1007/97 8-3-642-33027-8_31.

[13] Bai S, Galbraith SD (2014) An improved compression technique for signatures based on learning with errors. Topics in Cryptology – CT-RSA 2014, ed Benaloh J (Springer International Publishing, Cham), pp 28–47. https://doi.org/10.1007/978-3-319-04852-9_2.

[14] Cremers C, Düzlü S, Fiedler R, Janson C, Fischlin M (2021) BUFFing signature schemes beyond unforgeability and the case of post-quantum signatures. 2021 IEEE Symposium on Security and Privacy (SP) (IEEE Computer Society, Los Alamitos, CA, USA), pp 1696–1714. https://doi.org/10.110 9/SP40001.2021.00093.

[15] Regev O (2005) On lattices, learning with errors, random linear codes, and cryptography. Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing STOC ’05 (Association for Computing Machinery, New York, NY, USA), p 84–93. https://doi.org/10.1145/1060590.1060603.

[16] Kiltz E, Lyubashevsky V, Schaffner C (2018) A concrete treatment of Fiat-Shamir signatures in the quantum random-oracle model. Advances in Cryptology – EUROCRYPT 2018, eds Nielsen JB, Rijmen V (Springer International Publishing, Cham), pp 552–586. https://doi.org/10.1007/978-3-319-78372 -7_18.

[17] Barker E, Barker W (2019) Recommendation for key management: Part 2 - best practices for key management organizations, National Institute of Standards and Technology, Gaithersburg, MD. NIST Special Publication (SP) 800-57 Part 2, Rev. 1. https://doi.org/10.6028/NIST.SP.800-57pt2r1.

[18] Barker E, Dang Q (2019) Recommendation for key management: Part 3 - application-specific key management guidance, National Institute of Standards and Technology, Gaithersburg, MD. NIST Special Publication (SP) 800-57 Part 3, Rev. 1. http://doi.org/10.6028/NIST.SP.800-57pt3r1.

[19] Barker E, Kelsey J (2015) Recommendation for random number generation using deterministic random bit generators, (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-90A, Rev. 1. https://doi.org/10.6028/NIST.SP.800-90Ar1.

[20] Sönmez Turan M, Barker E, Kelsey J, McKay K, Baish M, Boyle M (2018) Recommendation for the entropy sources used for random bit generation, (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-90B. https://doi.org/10.6028/NIST.SP.800-90B.

[21] Barker E, Kelsey J, McKay K, Roginsky A, Turan MS (2024) Recommendation for random bit generator (RBG) constructions, (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-90C 4pd. https://doi.org/10.6028/NIST.SP.800-90C.4pd.

[22] Bruinderink LG, Pessl P (2018) Differential fault attacks on deterministic lattice signatures. IACR Transactions on Cryptographic Hardware and Embedded Systems (3):21–43. https://doi.org/10.131 54/tches.v2018.i3.21-43.

[23] Poddebniak D, Somorovsky J, Schinzel S, Lochter M, Rösler P (2018) Attacking deterministic signature schemes using fault attacks. 2018 IEEE European Symposium on Security and Privacy (EuroS&P) (IEEE), pp 338–352. https://doi.org/10.1109/EuroSP.2018.00031.

[24] Samwel N, Batina L, Bertoni G, Daemen J, Susella R (2018) Breaking ed25519 in wolfssl. Topics in Cryptology–CT-RSA 2018: The Cryptographers’ Track at the RSA Conference 2018, San Francisco, CA, USA, April 16-20, 2018, Proceedings (Springer), pp 1–20. https://doi.org/10.1007/978-3-319-76953 -0_1.

[25] Kelsey J, Chang S, Perlner R (2016) SHA-3 Derived Functions: cSHAKE, KMAC, TupleHash and ParallelHash, (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-185 [or as amended]. https://doi.org/10.6028/NIST.SP.800-185.

[26] National Institute of Standards and Technology (2016) Submission requirements and evaluation criteria for the post-quantum cryptography standardization process. Available at https://csrc.nist.go v/CSRC/media/Projects/Post-Quantum-Cryptography/documents/call-for-proposals-final-dec-201 6.pdf.

[27] Alagic G, Apon D, Cooper D, Dang Q, Dang T, Kelsey J, Lichtinger J, Liu YK, Miller C, Moody D, Peralta R, Perlner R, Robinson A, Smith-Tone D (2022) Status report on the third round of the NIST post-quantum cryptography standardization process (National Institute of Standards and Technology, Gaithersburg, MD), NIST Interagency or Internal Report (IR) 8413. https://doi.org/10.6028/NIST.IR.8413-upd1.

[28] Avanzi R, Bos J, Ducas L, Kiltz E, Lepoint T, Lyubashevsky V, Schanck JM, Schwabe P, Seiler G, Stehlé D (2020) CRYSTALS-Kyber algorithm specifications and supporting documentation, 3rd Round submission to the NIST’s post-quantum cryptography standardization process. Available at https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standar dization/round-3-submissions.

[29] Housley R (2009) Cryptographic Message Syntax (CMS), Internet Engineering Task Force (IETF) request for comments (RFC) 5652, https://doi.org/10.17487/RFC5652.

[30] Schnorr C (1990) Efficient identification and signatures for smart cards. Advances in Cryptology — CRYPTO’ 89 Proceedings, ed Brassard G (Springer New York, New York, NY), pp 239–252. https: //doi.org/10.1007/0-387-34805-0_22.

[31] Josefsson S, Liusvaara I (2017) Edwards-Curve Digital Signature Algorithm (EdDSA), RFC 8032. https: //doi.org/10.17487/RFC8032.

[32] Lyubashevsky V (2021) Round 3 Official Comment: CRYSTALS-DILITHIUM. Available at https://groups .google.com/a/list.nist.gov/g/pqc-forum/c/BjfjRMIdnhM/m/W7kkVOFDBAAJ.

[33] Hamburg M (2024) Dilithium hint unpacking. Available at https://groups.google.com/a/list.nist.gov/ g/pqc-forum/c/TQo-qFbBO1A/m/YcYKjMblAAAJ.

[34] Mattsson (on behalf of Sönke Jendral) JP (2024) Dilithium hint unpacking. Available at https://grou ps.google.com/a/list.nist.gov/g/pqc-forum/c/TQo-qFbBO1A/m/sLjseYlSAwAJ.

[35] Lee S (2024) Updates for FIPS 203. Available at https://groups.google.com/a/list.nist.gov/g/pqc-for um/c/Rb0nFvfFTEQ/m/lw-k7tVdBQAJ.

This document uses modular multiplications of the form \(a \cdot b\) modulo \(q\). This is an expensive operation that is often sped up in practice through the use of Montgomery Multiplication.

If \(a\) is an integer modulo \(q\), then its Montgomery form with multiplier \(2^{32}\) is \(r \equiv a \cdot 2^{32} \bmod q\).

Suppose that two integers \(u\) and \(v\) modulo \(q\) are in Montgomery form. Their product modulo \(q\) is \(c = u \cdot v \cdot 2^{-32}\), which is also in Montgomery form. If the integer product of \(u\) and \(v\) does not overflow a 64-bit signed integer, then one can compute \(c\) by first performing the integer multiplication \(u \cdot v\) and then “reducing” the product by multiplying by \(2^{-32}\) modulo \(q\). This last operation can be done efficiently as follows.

The MontgomeryReduce function takes an integer \(a\) with absolute value at most \(2^{31}q\) as input. It returns an integer \(r\) such that \(r = a \cdot 2^{-32} \bmod q\). The output is in Montgomery form with multiplier \(2^{32} \bmod q\). An implementation would typically input a 64-bit input and return a 32-bit output. The “modulo \(2^{32}\)” operation simply extracts the 32 least significant bits of a 64-bit value. The value \((a - t \cdot q)\) on line 3 is an integer divisible by \(2^{32}\). Therefore, the division consists of simply taking the most significant 32 bits of a 64-bit value. Extracting the four low- or high-order bytes is often done using typecasting.

With this algorithm, the modular product of \(a\) and \(b\) is \(c = \mathsf{MontgomeryReduce}(a \cdot b)\), where \(a, b,\) and \(c\) are in Montgomery form. The return value of the algorithm is not necessarily less than \(q\) in absolute value, but it is less than \(2q\) in absolute value. This is not a concern in practice since the objective of Montgomery Multiplication is to efficiently work with modular values that fit in a 32-bit register. If necessary, the result can be normalized to an integer in \((-q, q)\) using a comparison and an integer addition.

Converting an integer modulo \(q\) to Montgomery form by multiplying by \(2^{32}\) modulo \(q\) is an expensive operation. When a sequence of modular operations is to be performed, the operands are converted once to Montgomery form. The operations are then performed, and the factor \(2^{32}\) is extracted from the final result.

The values \(\zeta^{\mathsf{BitRev}_8(k)} \bmod q\) for \(k = 1, \ldots, 255\) used in the NTT Algorithms 41 and 42 may be pre-computed and stored in an array zetas\([1..255]\). This table of zetas is given below.

zetas[0..255] = {

There are four algorithms in this standard with loops that iterate an indeterminate number of times, though the expected number of iterations is a small constant in each case. Three of the four algorithms involve sampling from the output of an XOF, where the amount of output required from the XOF is proportional to the number of iterations that are performed.

Implementations should not bound the number of iterations in these loops or the amount of output that is extracted from the XOFs when executing these functions.¹⁴ If an implementation bounds the number of iterations or the number of bytes that may be extracted from the XOF, it shall not use a limit lower than those presented in Table 3. The limits yield a probability of approximately \(2^{-256}\) (or less) of being reached in a correct implementation of this standard. The probability is calculated under standard assumptions about the output distributions of XOFs and hash functions.

Table 3. While loop and XOF output limits for a \(2^{-256}\) or less probability of failure

Implementations may limit the number of iterations of a while loop or the number of bytes drawn from the XOF to not exceed the maximum values in Table 3. If this option is used and the maximum number of iterations or XOF output bytes is exceeded, the algorithm shall destroy all intermediate results. If a return value or exception is produced, it shall be the same for any execution in which the maximum number of iterations or output bytes is exceeded.

There is essentially no performance penalty for using a larger than necessary limit, as the limit will only be reached on a faulty execution of the loop. Because of this, limits were chosen that lower-bound the probability of reaching them to \(2^{-256}\).

Table 1 contains the expected repetitions in the rejection sampling loop of ML-DSA.Sign_internal. These are 4.25, 5.1, and 3.85 for Categories 2, 3, and 5, respectively. Therefore, the probability that the number of repetitions exceeds \(n\) is less than or equal to \(\left(\frac{5.1-1}{5.1}\right)^n\) for all categories. Solving \(\left(\frac{5.1-1}{5.1}\right)^n \le 2^{-256}\) yields \(n = 814\).

Let \(X\) be the number of coefficients generated in \(n\) iterations of the while loop of RejBoundedPoly¹⁵. Then \(X\) is \(\mathit{Binomial}(2n, \theta)\), where \(\theta\) is either \(\frac{9}{16}\) or \(\frac{15}{16}\), depending on the parameter \(\eta\). For \(\theta = \frac{9}{16}\), the probability that fewer than \(256\) coefficients are generated in 481 iterations of the main loop in RejBoundedPoly is less than \(2^{-256}\). Each iteration consumes one byte of output from H.

The number of valid coefficients generated in \(n\) calls to G.Squeeze in RejNTTPoly is \(\mathit{Binomial}(n, 2^{-23}q)\). It follows that after \(298\) calls, the probability of failure is less than \(2^{-256}\). Each iteration consumes three bytes of output from G.

Step 9 in SampleInBall is executed every time a pseudorandom byte is greater than a value \(i\) in the range \([256-\tau, 255]\). The parameter \(\tau\) is 39, 49, and 60 for categories 2, 3, and 5, respectively. Therefore, the probability that this step is executed more than \(n\) times in a single iteration of the for loop is less than or equal to \((\frac{59}{256})^n \le (\frac{\tau}{256})^n\). Solving \((\frac{59}{256})^n \le 2^{-256}\) yields a bound of \(n = 121\) for the while loop on step 8 of SampleInBall. Each iteration consumes one byte of output from H.

Each call to SampleInBall extracts eight bytes from H and then performs \(\tau\) iterations of the for loop, each of which extracts an indeterminate amount of data from H. The probability that more than \(n\) bytes of output will be required from H during an execution of SampleInBall for a given value of \(\tau\) is

\(P(n, 60)\) is less than \(2^{-256}\) when \(n\) is 221 or greater. Implementations may limit the number of bytes extracted from H to \(n \ge 221\). Such implementations must stop the execution of SampleInBall, return a constant that represents an error and no other output, and destroy all intermediate results after \(n\) bytes of output have been consumed.

ML-DSA is derived from Version 3.1 of CRYSTALS-DILITHIUM [6]. Version 3.1 differs slightly from the most recent version that appears on the NIST website (i.e., Version 3 CRYSTALS-DILITHIUM [5]). Appendices D.1, D.2, and D.3 document the differences between Versions 3 and 3.1, the differences between Version 3.1 and the initial public draft of the ML-DSA, and the differences between the initial public draft and the ML-DSA standard as published in this document, respectively.

The lengths of the variables \(\rho'\) (private random seed) and \(\mu\) (message representative) in the signing algorithm were increased from 384 to 512 bits. The increase in the length of \(\mu\) corrects a security flaw that appeared in the third-round submission, where a collision attack against SHAKE256 with a 384-bit output would make it so that parameters targeting NIST security strength category 5 could only meet category 4 [32].

Additionally, the length of the variable \(tr\) (the hash of the public key) was reduced from 384 to 256 bits. In key generation, the variable \(\varsigma\) was relabeled as \(\rho'\) and increased in size from 256 bits to 512 bits.

D.2 Differences Between Version 3.1 of CRYSTALS-DILITHIUM and FIPS 204 Initial Public Draft

In order to ensure the properties noted in [14], ML-DSA increases the length of 𝑡𝑟 to 512 bits and increases the length of 𝑐 ̃to 384 and 512 bits for the parameter sets ML-DSA-65 and ML-DSA-87, respectively. In draft ML-DSA, only the first 256 bits of 𝑐 ̃are used in the generation of 𝑐.

In Version 3.1 of the CRYSTALS-DILITHIUM submission, the default version of the signing algorithm is deterministic with \(\rho'\) being generated pseudorandomly from the signer’s private key and the message, and an optional version of the signing algorithm has \(\rho'\) sampled instead as a 512-bit random string. In ML-DSA, \(\rho'\) is generated by a “hedged” procedure in which \(\rho'\) is pseudorandomly derived from the signer’s private key, the message, and a 256-bit string \(rnd\), which should be generated by an Approved RBG by default. The ML-DSA standard also allows for an optional deterministic version in which \(rnd\) is a 256-bit constant string.

The draft ML-DSA standard also included pseudocode that unintentionally omitted a check for malformed input while unpacking the hint [33]. Failure to perform this check results in a signature scheme that is not strongly existentially unforgeable [34].

D.3 Changes From FIPS 204 Initial Public Draft

In the final version of the ML-DSA standard, the omitted malformed input check was restored to the hint unpacking algorithm (Algorithm 21). Additionally, in the final version of ML-DSA, all of the bits of 𝑐 ̃are used in the generation of 𝑐 (Algorithm 29), and ExpandMask (Algorithm 34) is modified to take output bits from the beginning of the output of H.

Based on comments that were submitted on the draft version, more details were provided for the pre-hash version HashML-DSA in Section 5.4. These modifications include domain separation for the cases in which the message is signed directly and cases in which a digest of the message is signed. The changes were made by explicitly defining external functions for both versions of the signing and verification functions that call an internal function corresponding to the signing or verification functions from the draft FIPS. Domain separation is included in the input to the internal function (see Algorithms 2, 3, 4, 5, 7, and 8). To simplify APIs and for testing purposes, this document also introduced a similar external/internal split for key generation (see Algorithms 1 and 6), but this is a purely editorial change, as the external key generation algorithm is functionally equivalent to the key-generation algorithm from the draft FIPS.

Finally, to offer misuse resistance against the possibility that keys for different parameter sets might be expanded from the same seed [35], domain separation was added to line 1 of Algorithm 6.