FIPS 204
Federal Information Processing Standards Publication

Module-Lattice-Based Digital
Signature Standard
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

Foreword
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

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

Abstract
Digital signatures are used to detect unauthorized modifications to data and to authenticate the identityof the signatory. In addition, the recipient of signed data can use a digital signature as evidence indemonstrating 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; postquantum; public-key cryptography.

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

Federal Information Processing Standards Publication 204
Published: August 13, 2024
Effective: August 13, 2024

Announcing theModule-Lattice-Based Digital Signature Standard
Federal Information Processing Standards (FIPS) publications are developed by the National Institute ofStandards and Technology (NIST) under 15 U.S.C. 278g-3 and issued by the Secretary of Commerce under
40 U.S.C. 11331.
1. Name of Standard. Module-Lattice-Based Digital Signature Standard (FIPS 204).
2. Category of Standard. Computer Security. Subcategory. Cryptography.
3. Explanation. This standard specifies ML-DSA, a lattice-based digital signature algorithm for applications
that require a digital signature rather than a written signature. Additional digital signature schemes are
specified and approved in other NIST Special Publications and FIPS publications (e.g., FIPS 186-5 [1]).
A digital signature is represented in a computer as a string of bits and computed using a set of rules
and parameters that allow the identity of the signatory and the integrity of the data to be verified.
Digital signatures may be generated on both stored and transmitted data.
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 thesignatory’s public key. Only the user who possesses the private key can generate a signature that canbe 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. Additionalparameter sets may be specified and approved in future NIST Special Publications.
4. Approving Authority. Secretary of Commerce.
5. Maintenance Agency. Department of Commerce, National Institute of Standards and Technology,
Information Technology Laboratory (ITL).
6. Applicability. This standard is applicable to all federal departments and agencies for the protection ofsensitive unclassified information that is not subject to section 2315 of Title 10, United States Code,or section 3502 (2) of Title 44, United States Code. Either this standard, FIPS 205, FIPS 186-5, or NIST
Special Publication 800-208 shall be used in designing and implementing public-key-based signaturesystems that federal departments and agencies operate or that are operated for them under contract.
In the future, additional digital signature schemes may be specified and approved in FIPS or NIST
Special Publications.
The adoption and use of this standard are available to private and commercial organizations.

iFIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

7. Applications. A digital signature algorithm allows an entity to authenticate the integrity of signed
data and the identity of the signatory. The recipient of a signed message 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. A digital signature algorithm is intended for use in electronic mail, electronic funds
transfer, electronic data interchange, software distribution, data storage, and other applications that
require data integrity assurance and data origin authentication.
8. Implementations. A digital signature algorithm may be implemented in software, firmware, hardware,or any combination thereof. NIST will develop a validation program to test implementations forconformance to the algorithm in this standard. For every computational procedure that is specified inthis standard, a conforming implementation may replace the given set of steps with any mathematicallyequivalent set of steps. In other words, different procedures that produce the correct output for every
input are permitted.
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.
9. Other Approved Security Functions. Digital signature implementations that comply with this standard
shall employ cryptographic algorithms that have been approved for protecting Federal Governmentsensitive information. Approved cryptographic algorithms and techniques include those that areeither:a. Specified in a Federal Information Processing Standards (FIPS) publication,b. Adopted in a FIPS or NIST recommendation, orc. Specified in the list of approved security functions in SP 800-140C.
10. Export Control. Certain cryptographic devices and technical data regarding them are subject to federal
export controls. Exports of cryptographic modules that implement this standard and technical data
regarding them must comply with these federal regulations and be licensed by the Bureau of Industry
and Security of the U.S. Department of Commerce. Information about export regulations is available
at https://www.bis.doc.gov.
11. Patents. The algorithm in this standard may be covered by U.S. or foreign patents.
12. Implementation Schedule. This standard becomes effective immediately upon final publication.
13. Specifications. Federal Information Processing Standards (FIPS) 204, Module-Lattice-Based Digital
Signature Standard (affixed).
14. Qualifications. The security of a digital signature system depends on maintaining the secrecy of thesignatory’s private keys. Signatories shall, therefore, guard against the disclosure of their private
keys. While it is the intent of this standard to specify general security requirements for generating
digital signatures, conformance to this standard does not ensure that a particular implementation issecure. It is the responsibility of an implementer to ensure that any module that implements a digital
signature capability is designed and built in a secure manner.
Similarly, the use of a product containing an implementation that conforms to this standard does notguarantee the security of the overall system in which the product is used. The responsible authority ineach agency or department shall ensure that an overall implementation provides an acceptable levelof security.

iiFIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

Since a standard of this nature must be flexible enough to adapt to advancements and innovations inscience and technology, this standard will be reviewed every five years in order to assess its adequacy.
15. Waiver Procedure. The Federal Information Security Management Act (FISMA) does not allow for
waivers to Federal Information Processing Standards (FIPS) that are made mandatory by the Secretaryof Commerce.
16. Where to Obtain Copies of the Standard. This publication is available by accessing https://csrc.nist.
gov/publications. Other computer security publications are available at the same website.
17. How to Cite This Publication. NIST has assigned NIST FIPS 204 as the publication identifier for this
FIPS, per the NIST Technical Series Publication Identifier Syntax. NIST recommends that it be cited asfollows:
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
18. Inquiries and Comments. Inquiries and comments about this FIPS may be submitted to fips-204comments@nist.gov.

iii

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

Federal Information Processing Standards Publication 204
Specification for the

Module-Lattice-Based Digital Signature Standard
Table of Contents
1 Introduction1

1.1

Purpose and Scope . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.2

Context . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

2 Glossary of Terms, Acronyms, and Symbols

2

2.1

Terms and Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

2.2

Acronyms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

2.3

Mathematical Symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

2.4

Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4.1 Rings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4.2 Vectors and Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
NTT Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7
7
7
8

2.5

3 Overview of the ML-DSA Signature Scheme

9

3.1

Security Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

3.2Computational Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

3.3

ML-DSA Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

3.4

Hedged and Deterministic Signing . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

3.5

Use of Digital Signatures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

3.6

Additional Requirements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.6.1 Randomness Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.6.2 Public-Key and Signature Length Checks . . . . . . . . . . . . . . . . . . . . .
3.6.3 Intermediate Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.6.4 No Floating-Point Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . .
Use of Symmetric Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12
12
12
12
13
13

3.7

4 Parameter Sets

15

5 External Functions

17

5.1

ML-DSA Key Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

5.2

ML-DSA Signing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

5.3

ML-DSA Verifying . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18

iv

FIPS 204

5.4

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

Pre-Hash ML-DSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4.1 HashML-DSA Signing and Verifying . . . . . . . . . . . . . . . . . . . . . . . .

6 Internal Functions

18
19
22

6.1

ML-DSA Key Generation (Internal) . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22

6.2

ML-DSA Signing (Internal) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

6.3

ML-DSA Verifying (Internal) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

7 Auxiliary Functions

28

7.1

Conversion Between Data Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

7.2

Encodings of ML-DSA Keys and Signatures . . . . . . . . . . . . . . . . . . . . . . . .

33

7.3

Pseudorandom Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

36

7.4

High-Order and Low-Order Bits and Hints . . . . . . . . . . . . . . . . . . . . . . . .

39

7.5

NTT and NTT−1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42

7.6

Arithmetic Under NTT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

45

References

47

Appendix A — Montgomery Multiplication

50

Appendix B — Zetas Array

51

Appendix C — Loop Bounds

52

Appendix D — Differences from the CRYSTALS-DILITHIUM Submission

54

D.1

Differences Between Version 3.1 and the Round 3 Version of CRYSTALS-DILITHIUM . .

D.2

Differences Between Version 3.1 of CRYSTALS-DILITHIUM and FIPS 204 Initial Public Draft 54

D.3

Changes From FIPS 204 Initial Public Draft . . . . . . . . . . . . . . . . . . . . . . . .

v

54

54

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

List of Tables
Table 1
Table 2
Table 3ML-DSA parameter sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Sizes (in bytes) of keys and signatures of ML-DSA . . . . . . . . . . . . . . . . . .
While loop and XOF output limits for a 2−256 or less probability of failure . . . . .

15
16
52

List of Algorithms
Algorithm 1
Algorithm 2
Algorithm 3
Algorithm 4
Algorithm 5
Algorithm 6
Algorithm 7
Algorithm 8
Algorithm 9
Algorithm 10
Algorithm 11
Algorithm 12
Algorithm 13
Algorithm 14
Algorithm 15
Algorithm 16
Algorithm 17
Algorithm 18
Algorithm 19
Algorithm 20
Algorithm 21
Algorithm 22
Algorithm 23
Algorithm 24
Algorithm 25
Algorithm 26
Algorithm 27
Algorithm 28
Algorithm 29
Algorithm 30
Algorithm 31
Algorithm 32
Algorithm 33
Algorithm 34
Algorithm 35
Algorithm 36
Algorithm 37
Algorithm 38

ML-DSA.KeyGen() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ML-DSA.Sign(𝑠𝑘, 𝑀 , 𝑐𝑡𝑥) . . . . . . . . . . . . . . . . . . . . . . . . . . .
ML-DSA.Verify(𝑝𝑘, 𝑀 , 𝜎, 𝑐𝑡𝑥) . . . . . . . . . . . . . . . . . . . . . . . . .
HashML-DSA.Sign(𝑠𝑘, 𝑀 , 𝑐𝑡𝑥, PH) . . . . . . . . . . . . . . . . . . . . . .
HashML-DSA.Verify(𝑝𝑘, 𝑀 , 𝜎, 𝑐𝑡𝑥, PH) . . . . . . . . . . . . . . . . . . . .
ML-DSA.KeyGen_internal(𝜉) . . . . . . . . . . . . . . . . . . . . . . . . . .
ML-DSA.Sign_internal(𝑠𝑘, 𝑀 ′ , 𝑟𝑛𝑑) . . . . . . . . . . . . . . . . . . . . . .
ML-DSA.Verify_internal(𝑝𝑘, 𝑀 ′ , 𝜎) . . . . . . . . . . . . . . . . . . . . . .
IntegerToBits(𝑥, 𝛼) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
BitsToInteger(𝑦, 𝛼) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
IntegerToBytes(𝑥, 𝛼) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
BitsToBytes(𝑦) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
BytesToBits(𝑧) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
CoeffFromThreeBytes(𝑏0 , 𝑏1 , 𝑏2 ) . . . . . . . . . . . . . . . . . . . . . . . .
CoeffFromHalfByte(𝑏) . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
SimpleBitPack(𝑤, 𝑏) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
BitPack(𝑤, 𝑎, 𝑏) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
SimpleBitUnpack(𝑣, 𝑏) . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
BitUnpack(𝑣, 𝑎, 𝑏) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
HintBitPack(𝐡) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
HintBitUnpack(𝑦) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
pkEncode(𝜌, 𝐭1 ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
pkDecode(𝑝𝑘) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
skEncode(𝜌, 𝐾, 𝑡𝑟, 𝐬1 , 𝐬2 , 𝐭0 ) . . . . . . . . . . . . . . . . . . . . . . . . . .
skDecode(𝑠𝑘) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
sigEncode(𝑐,̃ 𝐳, 𝐡) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
sigDecode(𝜎) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
w1Encode(𝐰1 ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
SampleInBall(𝜌) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
RejNTTPoly(𝜌) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
RejBoundedPoly(𝜌) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ExpandA(𝜌) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ExpandS(𝜌) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ExpandMask(𝜌, 𝜇) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Power2Round(𝑟) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Decompose(𝑟) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
HighBits(𝑟) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
LowBits(𝑟) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

vi

17
18
18
20
21
23
25
27
28
28
28
29
29
29
30
30
30
31
31
32
32
33
33
34
34
35
35
35
36
37
37
38
38
38
40
40
40
41

FIPS 204

Algorithm 39
Algorithm 40
Algorithm 41
Algorithm 42
Algorithm 43
Algorithm 44
Algorithm 45
Algorithm 46
Algorithm 47
Algorithm 48
Algorithm 49

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD
MakeHint(𝑧, 𝑟) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
UseHint(ℎ, 𝑟) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
NTT(𝑤) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
NTT−1 (𝑤)̂ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
BitRev8 (𝑚) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
AddNTT(𝑎,̂ 𝑏)̂ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
MultiplyNTT(𝑎,̂ 𝑏)̂ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
AddVectorNTT(𝐯,̂ 𝐰)
̂ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ScalarVectorNTT(𝑐,̂ 𝐯)̂ . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
̂ 𝐯)̂ . . . . . . . . . . . . . . . . . . . . . . . . . . . .
MatrixVectorNTT(𝐌,MontgomeryReduce(𝑎) . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

vii

41
41
43
44
44
45
45
45
46
46
50

FIPS 204

1.

Introduction

1.1

Purpose and Scope

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

This standard defines a digital signature scheme, which includes a method for digital signature generationthat can be used for the protection of binary data (commonly called a “message”) and a method for theverification 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 themethods 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 todetect unauthorized modifications to data and to authenticate the identity of the signatory (one boundto the possession of the private-key). In addition, a signature generated by this scheme can be usedas 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 thesignature 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 threepossible 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 areapproved 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]).

1.2

Context

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 quantumresistant 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 ofcryptographically relevant quantum computers. For the differences between ML-DSA and CRYSTALSDILITHIUM, see Appendix D.

1

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

2.

Glossary of Terms, Acronyms, and Symbols

2.1

Terms and Definitions

approved

FIPS-approved and/or NIST-recommended. An algorithm or technique thatis 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 ofpossession

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 encryptor 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 The entity in a public-key infrastructure (PKI) that is responsible for issuing(CA)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 ofsecret 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.

entityAn individual person, organization, device, or process. Used interchangeably
with party.

equivalent process

Two processes are equivalent if the same output is produced when the samevalues are input to each process (either as input parameters, as values madeavailable 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 issufficiently long to prevent trivial attacks:

2

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

1. (One-way) It is computationally infeasible to find any input that maps toany new pre-specified output.
2. (Collision-resistant) It is computationally infeasible to find any two distinct inputs that map to the same output.
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]) aredesigned to satisfy the following properties:
1. (One-way) It is computationally infeasible to find any input that maps toany new pre-specified output.
2. (Collision-resistant) It is computationally infeasible to find any two distinct inputs that map to the same output.

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 thisstandard include:
1. The computation of a digital signature from data
2. The verification of a digital signature

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 20 + 21 + 23 + 27 = 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 hashvalue.

non-repudiation

A service that is used to provide assurance of the integrity and origin of datain such a way that the integrity and origin can be verified and validated bya third party as having originated from a specific entity in possession of theprivate 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.

3

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

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 notmade 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 theoutcome 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 associatedwith an owner and may be made public. In the case of digital signatures, thepublic key is used to verify a digital signature that was generated using thecorresponding 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.

shallUsed to indicate a requirement of this standard.

shouldUsed to indicate a strong recommendation but not a requirement of thisstandard. 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 generatea digital signature on data.

signature validation

The mathematical verification of the digital signature along with obtaining theappropriate 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 adigital 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 theowner, 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.

4

FIPS 204

2.2

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

Acronyms

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 IRNIST Interagency or Internal ReportNTT

Number Theoretic Transform

OID

Object Identifier

PQC

Post-Quantum Cryptography

RBG

Random Bit Generator

SHA

Secure Hash Algorithm

SHAKE

Secure Hash Algorithm KECCAKSPSpecial Publication

SUF-CMA

Strongly existentially UnForgeable under Chosen Message Attack

XOF

eXtendable-Output Function

2.3

Mathematical Symbols

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

The prime number 𝑞 = 223 − 213 + 1 = 8380417.

𝔹

The set {0, 1, … , 255} of integers represented by a byte.

ℕ

The set of natural numbers {1, 2, 3, …}.

ℤ

The ring of integers.

ℤ𝑚

The ring of integers modulo 𝑚 whose set of elements is {0, 1, … , 𝑚 − 1}.

ℤ𝑛𝑚

The set of 𝑛-tuples over ℤ𝑚 equipped with the ℤ-module structure.

𝑅

The ring of single-variable polynomials over ℤ modulo 𝑋 256 + 1, also denoted byℤ[𝑋]/(𝑋 256 + 1).

𝑅𝑚

The ring of single-variable polynomials over ℤ𝑚 modulo 𝑋 256 + 1, also denoted byℤ𝑚 [𝑋]/(𝑋 256 + 1).

5

FIPS 204

1

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD
255

𝐵𝜏

The set of all polynomials 𝑝 = ∑𝑖=0 𝑝𝑖 𝑋 𝑖 in 𝑅𝑞 that are such that exactly 𝜏 of thecoefficients of 𝑝𝑖 are from the set {−1, 1}, and all other coefficients are zero. (See
Section 7.3.)

ΠUsed to denote a direct product of two or more rings, where addition and multiplication are performed componentwise.

𝑇𝑞

The ring Π255
𝑗=0 ℤ𝑞 .

𝐴×𝐵

Cartesian product of two sets 𝐴, 𝐵.

[𝑎, 𝑏]For two integers 𝑎 ≤ 𝑏, [𝑎, 𝑏] denotes the set of integers {𝑎, 𝑎 + 1, … , 𝑏}.

bitlen 𝑎

The bit length of a positive integer 𝑎. The bit length of 𝑎 is the number of digits thatwould appear in a base-2 representation of 𝑎, where the most significant digit in
the representation is assumed to be a 1 (e.g., bitlen 32 = 6 and bitlen 31 = 5).1

BitRev8 (𝑟)Bit reversal of an 8-bit integer 𝑟. If 𝑟 = 𝑟0 + 2𝑟1 + 4𝑟2 + … + 128𝑟7 with 𝑟𝑖 ∈ {0, 1},
then BitRev8 (𝑟) = 𝑟7 + 2𝑟6 + 4𝑟5 + … + 128𝑟0 .

0x

Prefix to an integer written in hexadecimal representation.

log2 𝑥The base 2 logarithm of 𝑥. For example, log2 (16) = 4.

modIf 𝛼 is a positive integer and 𝑚 ∈ ℤ or 𝑚 ∈ ℤ𝛼 , then 𝑚 mod 𝛼 denotes the uniqueelement 𝑚′ ∈ ℤ in the range 0 ≤ 𝑚′ < 𝛼 such that 𝑚 and 𝑚′ are congruent
modulo 𝛼.

mod±If 𝛼 is a positive integer and 𝑚 ∈ ℤ or 𝑚 ∈ ℤ𝛼 , then 𝑚 mod± 𝛼 denotes the uniqueelement 𝑚′ ∈ ℤ in the range −⌈𝛼/2⌉ < 𝑚′ ≤ ⌊𝛼/2⌋ such that 𝑚 and 𝑚′ arecongruent modulo 𝛼.

⌊𝑥⌋

The largest integer less than or equal to the real number 𝑥, called the floor of 𝑥. For
example, ⌊2.1⌋ = 2, and ⌊4⌋ = 4.

⌈𝑥⌉

The least integer greater than or equal to the real number 𝑥, called the ceiling of 𝑥.
For example, ⌈5⌉ = 5 and ⌈5.3⌉ = 6.

‖⋅‖∞

The infinity norm. For an element 𝑤 ∈ ℤ, ‖𝑤‖∞ = |𝑤|, the absolute value of𝑤. For an element 𝑤 ∈ ℤ𝑞 ,‖𝑤‖∞ = ∣𝑤 mod± 𝑞∣ . For an element 𝑤 of 𝑅 or 𝑅𝑞 ,‖𝑤‖∞ = max0≤𝑖<256 ‖𝑤𝑖 ‖∞ . For a length-𝑚 vector 𝐰 with entries from 𝑅 or 𝑅𝑞 ,‖𝐰‖∞ = max0≤𝑖<𝑚 ‖𝑤[𝑖]‖∞ .

𝑎!

The factorial quantity 1 ⋅ 2 ⋅ 3 ⋅ … ⋅ 𝑎. The value 0! is defined as 1.

(𝑎𝑏)

For 𝑎 ≥ 𝑏, the quantity 𝑎!/(𝑏!(𝑎 − 𝑏)!).

𝑠←𝑥

In pseudocode, this notation means that the variable 𝑠 is assigned the value of theexpression 𝑥.

𝑠 ← 𝔹ℓIn pseudocode, this notation means that the variable 𝑠 is assigned the value of anarray of ℓ random bytes. The bytes must be generated using randomness from anapproved RBG. See Section 3.6.1.

In this specification, bitlen 𝑎 is only ever called with a small finite number of values for 𝑎, so it may be helpful toprecompute bitlen 𝑎 for these values and hard code the results, rather than computing them on the fly.

6

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD𝑥∈𝑆←𝑦Type casting. The variable 𝑥 is assigned a value in a set 𝑆 that is constructed fromthe value of an expression 𝑦 in a possibly different set 𝑇. The set 𝑇 and the mappingfrom 𝑇 to 𝑆 are not explicitly specified, but they should be obvious from the context
in which this statement appears.

[[𝑎 < 𝑏]]

A Boolean predicate. A comparison operator inside double square brackets [[𝑎 < 𝑏]]denotes that the expression should be evaluated as a Boolean. Booleans can also
be interpreted as elements of ℤ2 with 1 denoting true and 0 denoting false.

⟨⟨𝑓(𝑥)⟩⟩A temporary variable that stores the output of a computation 𝑓(𝑥) so that it can beused many times without needing to be recomputed. This is equivalent to defining atemporary variable 𝑦 ← 𝑓(𝑥). Naming the variable ⟨⟨𝑓(𝑥)⟩⟩ makes the pseudocode
less cluttered.

𝑎||𝑏Concatenation of two bit or byte strings 𝑎 and 𝑏.

𝑎∘𝑏

Multiplication of 𝑎 and 𝑏 in the ring 𝑇𝑞 .

𝑎 ⋅ 𝑏 or 𝑎𝑏

Multiplication in any of the rings ℤ, ℤ𝑚 , 𝑅, or 𝑅𝑚 .

𝑎+𝑏

Addition of 𝑎 and 𝑏.

𝑎/𝑏

Division of integers. When this notation is used, 𝑎 and 𝑏 are always integers. If 𝑏
cannot be assumed to divide 𝑎, then either ⌊𝑎/𝑏⌋ or ⌈𝑎/𝑏⌉ is used.

⊥

Blank symbol that indicates failure or the lack of an output from an algorithm.

2.4

Notation

2.4.1

Rings

Elements of the rings ℤ, ℤ𝑞 , ℤ2 , 𝑅, and 𝑅𝑞 are denoted by italicized lowercase letters (e.g., 𝑤). Elementsof the ring 𝑇𝑞 are length-256 arrays of elements of ℤ𝑞 , and they are denoted by italicized letters with a
hat symbol (e.g., 𝑤̂ ). The addition and multiplication of elements of 𝑇𝑞 are performed entry-wise. Thus,
the 𝑖th entry of the product of two elements 𝑢̂ and 𝑣̂ of 𝑇𝑞 is 𝑢[𝑖]̂ ⋅ 𝑣[𝑖]̂ ∈ ℤ𝑞 . The multiplication operationin 𝑇𝑞 is denoted by the symbol ∘ (see Section 2.3).
When a product 𝑎 ⋅ 𝑏 or a sum 𝑎 + 𝑏 is written and either 𝑎 or 𝑏 is a congruence class modulo 𝑚 (i.e., ifeither 𝑎 or 𝑏 is an element of ℤ𝑚 or 𝑅𝑚 ), then the product or sum is also understood to be a congruenceclass modulo 𝑚 (i.e., an element of ℤ𝑚 or 𝑅𝑚 ). Likewise, an element of 𝑅 or ℤ may be “typecast” to anelement of 𝑅𝑚 or ℤ𝑚 , respectively, and may be used as the input of a function specified to act on anelement of 𝑅𝑚 or ℤ𝑚 , respectively. In both cases, the element itself or its coefficients are mapped fromℤ to ℤ𝑚 by taking the unique congruence class modulo 𝑚 that contains the integer.
The coefficients of an element 𝑤 of 𝑅 or 𝑅𝑚 are denoted by 𝑤𝑖 so that 𝑤 = 𝑤0 + 𝑤1 𝑋 + … + 𝑤255 𝑋 255 .
If 𝑤 is in 𝑅 (respectively, 𝑅𝑚 ) and 𝑡 is in ℤ (respectively, ℤ𝑑 ), then 𝑤(𝑡) denotes the polynomial 𝑤 =𝑤0 + 𝑤1 𝑋 + … + 𝑤255 𝑋 255 evaluated at 𝑋 = 𝑡.

2.4.2

Vectors and Matrices

Vectors with elements in 𝑅 or 𝑅𝑚 are denoted by bold lowercase letters (e.g., 𝐯). Matrices with elements
in 𝑅 or 𝑅𝑚 are denoted by bold uppercase letters (e.g., 𝐀).

7

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

If 𝑆 is a ring and 𝐯 is a length-𝐿 vector over 𝑆, then the entries in the vector 𝐯 are expressed as𝑣[0], 𝑣[1], … , 𝑣[𝐿 − 1].
The entries of a 𝐾 × 𝐿 matrix 𝐀 over 𝑆 are denoted as 𝐀[𝑖, 𝑗], where 0 ≤ 𝑖 < 𝐾 and 0 ≤ 𝑗 < 𝐿.
The set of all length-𝐿 vectors over 𝑆 is denoted by 𝑆 𝐿 . The set of all 𝐾 × 𝐿 matrices over 𝑆 is denoted
by 𝑆 𝐾×𝐿 . A length-𝐿 vector can also be treated as an 𝐿 × 1 matrix.

2.5

NTT Representation

The Number Theoretic Transform (NTT) is a specific isomorphism between the rings 𝑅𝑞 and 𝑇𝑞 . Let
𝜁 = 1753 ∈ ℤ𝑞 , which is a 512th root of unity. If 𝑤 ∈ 𝑅𝑞 , thenNTT(𝑤) = (𝑤(𝜁0 ), 𝑤(𝜁1 ), … , 𝑤(𝜁255 )) ∈ 𝑇𝑞 ,(2.1)

where 𝜁𝑖 = 𝑤(𝜁 2BitRev8 (𝑖)+1 ) mod 𝑞. See Section 7.5 for an implementation discussion for NTT and NTT−1 .
The motivation for using NTT is that multiplication is considerably faster in the ring 𝑇𝑞 . Since NTT is an
isomorphism, for any 𝑎, 𝑏 ∈ 𝑅𝑞 ,NTT(𝑎𝑏) = NTT(𝑎) ∘ NTT(𝑏).
(2.2)
If 𝐀 is a matrix with entries from 𝑅𝑞 , then NTT(𝐀) denotes the matrix computed via the entry-wise
application of NTT to 𝐀. The symbol ∘ is also used to denote the matrix multiplication of matrices withentries in 𝑇𝑞 . Thus, NTT(𝐀𝐁) = NTT(𝐀) ∘ NTT(𝐁). Explicit algorithms for linear algebra over 𝑇𝑞 are
given in Section 7.6.

8

FIPS 204

3.

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

Overview of the ML-DSA Signature Scheme

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 threemain 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).

3.1

Security Properties

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, theadversary 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].

3.2Computational Assumptions

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 𝐬 ∈ ℤ𝑛𝑞given a set of random “noisy” linear equations2 satisfied by 𝐬. The SIS problem is to find a non-zero solution𝐭 ∈ ℤ𝑛𝑞 for a given linear system over ℤ𝑞 of the form 𝐀𝐭 = 𝟎 such that ‖𝐭‖∞ is small. For appropriate
choices of parameters, these problems are intractable for the best known techniques, including Gaussianelimination.
When the module ℤ𝑛𝑞 in LWE and SIS is replaced by a module over a ring larger than ℤ𝑞 (e.g., 𝑅𝑞 ), theresulting 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 𝑅𝑞 and a nonstandard variant of
MSIS called SelfTargetMSIS [16].

3.3ML-DSA Construction

ML-DSA is a Schnorr-like signature with several optimizations. The Schnorr signature scheme applies theFiat-Shamir heuristic to an interactive protocol between a verifier who knows 𝑔 (the generator of a group inwhich discrete logs are believed to be difficult) and the value 𝑦 = 𝑔𝑥 and a prover who knows 𝑔 and 𝑥. Theinteractive protocol, where the prover demonstrates knowledge of 𝑥 to the verifier, consists of three steps:
1. Commitment: The prover generates a random positive integer 𝑟 that is less than the order of 𝑔 andcommits to its value by sending 𝑔𝑟 to the verifier.
2. Challenge: The verifier sends a random positive integer 𝑐 that is less than the order of 𝑔 to theprover.
2

Specifically, the LWE problem is to solve a system of equations of the form 𝐀𝐬 + 𝐞 = 𝑏, where 𝐀 and 𝑏 are given
and 𝐞 is not given but known to be small.

9

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

3. Response: The prover returns 𝑠 = 𝑟 − 𝑐𝑥 reduced modulo the order of 𝑔, and the verifier checks
whether 𝑔𝑠 ⋅ 𝑦𝑐 = 𝑔𝑟 .
This protocol is made noninteractive and turned into a signature scheme by replacing the verifier’s random
choice of 𝑐 in step 2 with a deterministic process that pseudorandomly derives 𝑐 from a hash of thecommitment 𝑔𝑟 concatenated with the message to be signed. For this signature scheme, 𝑦 is the public
key, and 𝑥 is the private key.
The basic idea of ML-DSA and similar lattice signature schemes is to build a signature scheme froman analogous interactive protocol, where a prover who knows matrices 𝐀 ∈ ℤ𝐾×𝐿
, 𝐒1 ∈ ℤ𝑞𝐿×𝑛 , and𝑞
𝐒2 ∈ ℤ𝐾×𝑛with small coefficients (for 𝐒1 and 𝐒2 ) demonstrates knowledge of these matrices to a verifier𝑞
who knows 𝐀 and 𝐓 ∈ ℤ𝐾×𝑛
= 𝐀𝐒1 + 𝐒2 . Such an interactive protocol would proceed as follows:𝑞
1. Commitment: The prover generates 𝐲 ∈ ℤ𝐿
𝑞 with small coefficients and commits to its value by
sending 𝐰Approx = 𝐀𝐲 + 𝐲2 to the verifier, where 𝐲2 ∈ ℤ𝐾
𝑞 is a vector with small coefficients.
2. Challenge: The verifier sends a vector 𝐜 ∈ ℤ𝑛
𝑞 with small coefficients to the prover.
3. Response: The prover returns 𝐳 = 𝐲 + 𝐒1 𝐜, and the verifier checks that 𝐳 has small coefficientsand that 𝐀𝐳 − 𝐓𝐜 ≈ 𝐰Approx .
As written, the above protocol has a security flaw: the response 𝐳 will be biased in a direction related
to the private value 𝐒1 . Likewise 𝐫 = 𝐰Approx − 𝐀𝐳 + 𝐓𝐜 = 𝐲2 + 𝐒2 𝐜 is biased in a direction related
to the private value 𝐒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 𝐳; if coefficients of 𝐳 fall outside of a specified range, the signing process isaborted, and the signer starts over from a new value of 𝐲. Likewise, similar rejection sampling must also
be applied to 𝐫. 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 (𝐀, 𝐓), and the private key is (𝐒1 , 𝐒2 ).
In the ML-DSA standard, a number of tweaks and modifications are added to this basic framework forsecurity or efficiency reasons:• To reduce key and signature size and to use fast NTT-based polynomial multiplication, ML-DSA
uses module-structured matrices. Relative to the basic scheme described above, it replaces
dimension-𝑛 × 𝑛 blocks of matrices and dimension-𝑛 blocks of vectors with polynomials in the ring𝑛
𝑅𝑞 . Thus, instead of 𝐀 ∈ ℤ𝐾×𝐿
, 𝐓 ∈ ℤ𝐾×𝑛
, 𝐲 ∈ ℤ𝐿
, 𝐒1 ∈ ℤ𝑞𝐿×𝑛 , 𝐒𝟐 ∈ ℤ𝐾×𝑛𝑞𝑞𝑞𝑞 , 𝐜 ∈ ℤ𝑞 , ML-DSA
has 𝐀 ∈ 𝑅𝑞𝑘×ℓ , 𝐭 ∈ 𝑅𝑞𝑘 , 𝐬1 ∈ 𝑅𝑞ℓ , 𝐬2 ∈ 𝑅𝑞𝑘 , 𝐲 ∈ 𝑅𝑞ℓ , 𝑐 ∈ 𝑅𝑞 , where ℓ = 𝐿/𝑛 and 𝑘 = 𝐾/𝑛.
• To further reduce the size of the public key, the matrix 𝐀 is pseudorandomly derived from a 256-bit
public seed 𝜌, which is included in the ML-DSA public key in place of 𝐀.
• For a still further reduction in public key size, the ML-DSA public key substitutes a compressedvalue 𝐭1 for 𝐭, which drops the 𝑑 low-order bits of each coefficient.
• To obtain beyond unforgeability (BUFF) properties noted in [14], ML-DSA does not directly sign
the message 𝑀 but rather signs a message representative 𝜇 that is obtained by hashing theconcatenation of a hash of the public key and 𝑀 .

10

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD• To reduce signature size, rather than including the commitment 𝐰Approx = 𝐀𝐲+𝐲2 in the signature,
the ML-DSA signature uses a rounded version of 𝐰 = 𝐀𝐲 as a commitment 𝐰1 and includes only
the hash 𝑐 ̃ of 𝐰1 ||𝜇.
• To ensure that 𝐰1 can be reconstructed by the verifier from 𝐳 and the compressed value 𝐭1 , thesignature must also include a hint 𝐡 ∈ 𝑅2𝑘 computed by the signer using the signer’s private key.
• Additionally, to ensure correctness, a second stage of rejection sampling must be included (Line 28
of Algorithm 7)
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 thedimension of the matrix 𝐀. For example, in ML-DSA-65, the matrix 𝐀 is a 6 × 5 matrix over 𝑅𝑞 .

3.4

Hedged and Deterministic Signing

For ML-DSA to be secure, the signer’s commitment value 𝐲 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, therandomness leading to 𝐲 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 thedeterministic variant makes the risk of side-channel attacks (particularly fault attacks) more difficult tomitigate. 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 ofAlgorithm 4.

3.5

Use of Digital Signatures

Secure key management is an essential requirement for the use of digital signatures. This is contextdependent and involves more than the key generation, signing, and signature verification algorithms inthis 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 identityand 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 ofidentity and proof of possession are provided in [3].

11FIPS 204

3.6

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

Additional Requirements

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

3.6.1

Randomness Generation

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 havea security strength of at least 192 bits for ML-DSA-65 and 256 bits for ML-DSA-87. For ML-DSA-44, theRBG 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, thenthe claimed security strength of ML-DSA-44 is reduced from category 2 to category 1.
Additionally, the value 𝑟𝑛𝑑 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 purposeof 𝑟𝑛𝑑 is to facilitate countermeasures to side-channel attacks and fault attacks on deterministic signatures,such as [22, 23, 24].3 For this purpose, even a weak RBG may be preferable to the fully deterministic
variants of Algorithms 2 and 4.

3.6.2

Public-Key and Signature Length Checks

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

3.6.3

Intermediate Values

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 verificationof signatures on plaintext messages that are intended to be confidential. Intermediate values of theverification algorithm may reveal information about its inputs (i.e., the message, signature, and publickey), 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:
1. The seed 𝜉 generated in step 1 of ML-DSA.KeyGen can be stored for the purpose of later expansion
3

In addition, when signing is deterministic, there is leakage through timing side channels of information about
the message but not the private key). If the signer does not want to reveal the message being signed, hedged
signatures should be used (see Section 3.2 in [6]).

12FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

using ML-DSA.KeyGen_internal. As the seed can be used to compute the private key, it is sensitive
data and shall be treated with the same safeguards as a private key.
2. The matrix 𝐀̂ generated in step 3 of ML-DSA.KeyGen_internal can be stored so that it need not
be recomputed in later operations. Likewise, the matrix 𝐀̂ generated in step 5 of the verification
algorithm ML-DSA.Verify_internal can also be stored. In either case, the matrix 𝐀̂ is data that is
easily computed from the public key and does not require any special protections.
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.

3.6.4

No Floating-Point Arithmetic

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 ⌊𝑥/𝑦⌋ or ⌈𝑥/𝑦⌉ is used in all pseudocode
in this standard in which division is performed (e.g., 𝑥/𝑦), and 𝑦 may not divide 𝑥. Both of these canbe computed without floating-point arithmetic, as ordinary integer division 𝑥/𝑦 computes ⌊𝑥/𝑦⌋, and⌈𝑥/𝑦⌉ = ⌊(𝑥 + 𝑦 − 1)/𝑦⌋ for non-negative integers 𝑥 and positive integers 𝑦. If 𝑦 is a power of two, it
may be more efficient to use bit shift operations than integer division.

3.7

Use of Symmetric Cryptography

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 theoutput 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 ℓ ≥ 1:
SHAKE256(str, 8ℓ) = SHAKE256(BytesToBits(str), 8ℓ).
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 sequenceof 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:• ctx ← SHAKE256.Init()
Initializes a hash function context.
• ctx ← SHAKE256.Absorb(ctx, str)
Injects data to be used in the absorbing phase of SHAKE256 and updates context ctx.

13

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD• (ctx, out) ← SHAKE256.Squeeze(ctx, 8ℓ)
Extracts ℓ output bytes produced during the squeezing phase of SHAKE256 and updates context
ctx.
While the above functions are specified in terms of the Keccak-𝑓 permutation rather than the eXtendableOutput Function (XOF), SHAKE256, they are defined so that any series of commands of the followingform:
1. ctx ← SHAKE256.Init()
2. For 𝑖 = 1 to 𝑚: ctx ← SHAKE256.Absorb(ctx, str𝑖 )3. For 𝑗 = 1 to 𝑘: (ctx, out𝑗 ) ← SHAKE256.Squeeze(ctx, 8𝑏𝑗 )4. output ← out1 || … ||out𝑘will yield the same output as a single SHAKE256 call:
output ← SHAKE256(str1 || … ||str𝑚 , 8𝑏1 + … + 8𝑏𝑘 ).
This equivalence holds whether or not |str𝑖 | and 𝑏𝑗 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:
1. H(str, ℓ) = SHAKE256(str, 8ℓ)
2. G(str, ℓ) = SHAKE128(str, 8ℓ)
3. H.Init() = SHAKE256.Init()
4. G.Init() = SHAKE128.Init()
5. H.Absorb(ctx, str) = SHAKE256.Absorb(ctx, str)
6. G.Absorb(ctx, str) = SHAKE128.Absorb(ctx, str)
7. H.Squeeze(ctx, ℓ) = SHAKE256.Squeeze(ctx, 8ℓ)
8. G.Squeeze(ctx, ℓ) = SHAKE128.Squeeze(ctx, 8ℓ)
In addition to SHAKE128 and SHAKE256, HashML-DSA.Sign and HashML-DSA.Verify may call otherapproved 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) torelate bits, bytes, and words.

14

FIPS 204

4.

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

Parameter Sets
Table 1. ML-DSA parameter sets
Parameters(see Sections 6.1 and 6.2 of this document)
𝑞 - modulus [see §6.1]
𝜁 - a 512th root of unity in ℤ𝑞 [see §7.5]
𝑑 - # of dropped bits from 𝐭 [see §6.1]
𝜏 - # of ±1’s in polynomial 𝑐 [see §6.2]
𝜆 - collision strength of 𝑐 ̃ [see §6.2]
𝛾1 - coefficient range of 𝐲 [see §6.2]
𝛾2 - low-order rounding range [see §6.2](𝑘, ℓ) - dimensions of 𝐀 [see §6.1]
𝜂 - private key range [see §6.1]
𝛽 = 𝜏 ⋅ 𝜂 [see §6.2]
𝜔 - max # of 1’s in the hint 𝐡 [see §6.2]
Challenge entropy log2 (256𝜏 ) + 𝜏 [see §6.2]
Repetitions (see explanation below)
Claimed security strength

Values assigned by each parameter set
ML-DSA-44 ML-DSA-65 ML-DSA-87
838041783804178380417
1753
1753
1753
13
13
13
39
49
60
128
192
256
17
19
2
2
219
(𝑞 − 1)/88 (𝑞 − 1)/32 (𝑞 − 1)/32
(4,4)
(6,5)
(8,7)
2
4
2
78
196
120
80
55
75
192
225
257
4.25
5.1
3.85
Category 2 Category 3 Category 5

Three ML-DSA parameter sets are included in Table 1. Each parameter set assigns values for all of theparameters 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 signingalgorithm from eq. 5 in [5]. The names of the parameter sets are of the form “ML-DSA-𝑘ℓ,” where (𝑘, ℓ)
are the dimensions of the matrix 𝐀.
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 aprescribed 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 lessrealistic 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 isclaimed 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 𝐀̂ to speed up signing and verifying. Alternatively, if one wants to reduce

15

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

the space needed for the private key, one can store only the 32-byte seed 𝜉, 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
Private Key
ML-DSA-44
2560
ML-DSA-65
4032
ML-DSA-87
4896

Public Key
1312
1952
2592

16

Signature Size
2420
3309
4627

FIPS 204

5.

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

External Functions

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.

5.1

ML-DSA Key Generation

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.

Algorithm 1 ML-DSA.KeyGen()
Generates a public-private key pair.
Output: Public key 𝑝𝑘 ∈ 𝔹32+32𝑘(bitlen (𝑞−1)−𝑑)and private key 𝑠𝑘 ∈ 𝔹32+32+64+32⋅((ℓ+𝑘)⋅bitlen (2𝜂)+𝑑𝑘) .
▷ choose random seed
1: 𝜉 ← 𝔹32
2: if 𝜉 = NULL thenreturn ⊥▷ return an error indication if random bit generation failed
3:
4: end if
5: return ML-DSA.KeyGen_internal (𝜉)5.2

ML-DSA Signing

The signing algorithm ML-DSA.Sign (Algorithm 2) takes a private key, a message, and a context string as
input4 . 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 togenerate a 256-bit (32-byte) random seed 𝑟𝑛𝑑. If the deterministic variant is desired, then 𝑟𝑛𝑑 is set
to the fixed zero string {0}32 . The value 𝑟𝑛𝑑, the private key, and the encoded message are input to
ML-DSA.Sign_internal (Algorithm 7), which produces the signature.

4

By default, the context is the empty string, though applications may specify the use of a non-empty context string.

17

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

Algorithm 2 ML-DSA.Sign(𝑠𝑘, 𝑀 , 𝑐𝑡𝑥)
Generates an ML-DSA signature.
Input: Private key 𝑠𝑘 ∈ 𝔹32+32+64+32⋅((ℓ+𝑘)⋅bitlen (2𝜂)+𝑑𝑘) , message 𝑀 ∈ {0, 1}∗ ,context string 𝑐𝑡𝑥 (a byte string of 255 or fewer bytes).
Output: Signature 𝜎 ∈ 𝔹𝜆/4+ℓ⋅32⋅(1+bitlen (𝛾1 −1))+𝜔+𝑘 .
1: if |𝑐𝑡𝑥| > 255 then2:
return ⊥▷ return an error indication if the context string is too long
3: end if
4:
5: 𝑟𝑛𝑑 ← 𝔹32▷ for the optional deterministic variant, substitute 𝑟𝑛𝑑 ← {0}32
6: if 𝑟𝑛𝑑 = NULL then7:
return ⊥▷ return an error indication if random bit generation failed
8: end if
9:
10: 𝑀 ′ ← BytesToBits(IntegerToBytes(0, 1) ∥ IntegerToBytes(|𝑐𝑡𝑥|, 1) ∥ 𝑐𝑡𝑥) ∥ 𝑀
11: 𝜎 ← ML-DSA.Sign_internal(𝑠𝑘, 𝑀 ′ , 𝑟𝑛𝑑)
12: return 𝜎

5.3

ML-DSA Verifying

The verification algorithm ML-DSA.Verify (Algorithm 3) takes a public key, a message, a signature, and acontext 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 isaccomplished by calling ML-DSA.Verify_internal (Algorithm 8) with the public key, the encoded message,
and the signature.

Algorithm 3 ML-DSA.Verify(𝑝𝑘, 𝑀 , 𝜎, 𝑐𝑡𝑥)
Verifies a signature 𝜎 for a message 𝑀.
Input: Public key 𝑝𝑘 ∈ 𝔹32+32𝑘(bitlen (𝑞−1)−𝑑) , message 𝑀 ∈ {0, 1}∗ ,signature 𝜎 ∈ 𝔹𝜆/4+ℓ⋅32⋅(1+bitlen (𝛾1 −1))+𝜔+𝑘 ,context string 𝑐𝑡𝑥 (a byte string of 255 or fewer bytes).
Output: Boolean.
1: if |𝑐𝑡𝑥| > 255 then2:
return ⊥▷ return an error indication if the context string is too long
3: end if
4:
5: 𝑀 ′ ← BytesToBits(IntegerToBytes(0, 1) ∥ IntegerToBytes(|𝑐𝑡𝑥|, 1) ∥ 𝑐𝑡𝑥) ∥ 𝑀
6: return ML-DSA.Verify_internal(𝑝𝑘, 𝑀 ′ , 𝜎)

5.4

Pre-Hash ML-DSA

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,

18

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

the platform may require hardware support for hashing to achieve acceptable performance but lackhardware support for SHAKE256 specifically. For some use cases, this may be addressed by signing adigest 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 algorithmof HashML-DSA takes the content to be signed, the private key, and a context as input, as well as a hashfunction 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 useof 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 identifiershould 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 𝑟𝑛𝑑 shall be generated by thecryptographic module that generates the signature (i.e., that runs ML-DSA.Sign_internal). However, allother 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 thatgenerates 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, andthat digest is signed along with other attributes. If the content is not hashed at the application level, thepre-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 levelor 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 𝜆 bits of classical security strength
against both collision and second preimage attacks [7, Table 4].6 The verification of a signature that iscreated 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.

5.4.1

HashML-DSA Signing and Verifying

In the HashML-DSA version, the message input to ML-DSA.Sign_internal is the result of applying either ahash 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 andlength.
5
6

In the case of a XOF this would also include the length of the output from the XOF.
Obtaining at least 𝜆 bits of classical security strength against collision attacks requires that the digest to be signed
be at least 2𝜆 bits in length.

19

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

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.

Algorithm 4 HashML-DSA.Sign(𝑠𝑘, 𝑀 , 𝑐𝑡𝑥, PH)
Generate a “pre-hash” ML-DSA signature.
Input: Private key 𝑠𝑘 ∈ 𝔹32+32+64+32⋅((ℓ+𝑘)⋅bitlen (2𝜂)+𝑑𝑘) , message 𝑀 ∈ {0, 1}∗ ,context string 𝑐𝑡𝑥 (a byte string of 255 or fewer bytes), pre-hash function PH.
Output: ML-DSA signature 𝜎 ∈ 𝔹𝜆/4+ℓ⋅32⋅(1+bitlen (𝛾1 −1))+𝜔+𝑘 .
1: if |𝑐𝑡𝑥| > 255 then2:
return ⊥▷ return an error indication if the context string is too long
3: end if
4:
5: 𝑟𝑛𝑑 ← 𝔹32▷ for the optional deterministic variant, substitute 𝑟𝑛𝑑 ← {0}32
6: if 𝑟𝑛𝑑 = NULL then7:
return ⊥▷ return an error indication if random bit generation failed
8: end if
9:
10: switch PH do
11:case SHA-256:
12:
OID ← 0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x01

▷ 2.16.840.1.101.3.4.2.1
PH𝑀 ← SHA256(𝑀 )14:case SHA-512:
15:
OID ← 0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x03
▷ 2.16.840.1.101.3.4.2.3
16:
PH𝑀 ← SHA512(𝑀 )17:case SHAKE128:
18:
OID ← 0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x0B
▷ 2.16.840.1.101.3.4.2.11
19:
PH𝑀 ← SHAKE128(𝑀 , 256)20:case …
21:…
22: end switch
23: 𝑀 ′ ← BytesToBits(IntegerToBytes(1, 1) ∥ IntegerToBytes(|𝑐𝑡𝑥|, 1) ∥ 𝑐𝑡𝑥 ∥ OID ∥ PH𝑀 )24: 𝜎 ← ML-DSA.Sign_internal(𝑠𝑘, 𝑀 ′ , 𝑟𝑛𝑑)
25: return 𝜎
13:

Algorithm 5 presents the signature verification for HashML-DSA . This function constructs 𝑀 ′ in the same
way as Algorithm 4 and passes the resulting 𝑀 ′ to Algorithm ML-DSA.Verify_internal for verification. As
with the pre-hash signature generation, 𝑀 ′ may be constructed outside of the cryptographic modulethat performs ML-DSA.Verify_internal. However, in the case of HashML-DSA , the hash or XOF of thecontent 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

20

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

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.

Algorithm 5 HashML-DSA.Verify(𝑝𝑘, 𝑀 , 𝜎, 𝑐𝑡𝑥, PH)
Verifies a pre-hash HashML-DSA signature.
Input: Public key 𝑝𝑘 ∈ 𝔹32+32𝑘(bitlen (𝑞−1)−𝑑) , message 𝑀 ∈ {0, 1}∗ ,signature 𝜎 ∈ 𝔹𝜆/4+ℓ⋅32⋅(1+bitlen (𝛾1 −1))+𝜔+𝑘 ,context string 𝑐𝑡𝑥 (a byte string of 255 or fewer bytes), pre-hash function PH.
Output: Boolean.
1: if |𝑐𝑡𝑥| > 255 then2:
return false
3: end if
4:
5: switch PH do
6:case SHA-256:
7:
OID ← 0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x01

▷ 2.16.840.1.101.3.4.2.1
PH𝑀 ← SHA256(𝑀 )9:case SHA-512:
10:
OID ← 0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x03
▷ 2.16.840.1.101.3.4.2.3
11:PH𝑀 ← SHA512(𝑀 )12:case SHAKE128:
13:
OID ← 0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x0B
▷ 2.16.840.1.101.3.4.2.11
14:
PH𝑀 ← SHAKE128(𝑀 , 256)15:case …
16:…
17: end switch
18: 𝑀 ′ ← BytesToBits(IntegerToBytes(1, 1) ∥ IntegerToBytes(|𝑐𝑡𝑥|, 1) ∥ 𝑐𝑡𝑥 ∥ OID ∥ PH𝑀 )19: return ML-DSA.Verify_internal(𝑝𝑘, 𝑀 ′ , 𝜎)8:21

FIPS 204

6.

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

Internal Functions

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.7

6.1

ML-DSA Key Generation (Internal)

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 𝜉 is expanded as needed using an XOF (i.e., a byte-variant of SHAKE256) denoted by H to produce
other random values.8 In particular:• A 32-byte public random seed 𝜌. Using this seed, a polynomial matrix 𝐀 ∈ 𝑅𝑞𝑘×ℓ is pseudorandomly
sampled9 from 𝑅𝑞𝑘×ℓ .
• A 64-byte private random seed 𝜌′ . Using this seed, the polynomial vectors 𝐬1 ∈ 𝑅𝑞ℓ and 𝐬2 ∈ 𝑅𝑞𝑘
are pseudorandomly sampled from the subset of polynomial vectors whose coordinate polynomials
have short coefficients (i.e., in the range [−𝜂, 𝜂]).
• A 32-byte private random seed 𝐾 for use during signing.
The core cryptographic operation computes the public value𝐭 = 𝐀𝐬1 + 𝐬2 .
The vector 𝐭 together with the matrix 𝐀 may be considered an expanded form of the public key. The vector
𝐭 is compressed in the actual public key by dropping the 𝑑 least significant bits from each coefficient, thus
producing the polynomial vector 𝐭1 . This compression is an optimization for performance, not security.
The low-order bits of 𝐭 can be reconstructed from a small number of signatures and, therefore, need not
be regarded as secret.
The ML-DSA public key 𝑝𝑘 is a byte encoding of the public random seed 𝜌 and the compressed polynomial
vector 𝐭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
7

In some cases, it is permissible to modify the format of the private key in these interfaces (see Sections 4 and 3.6.3.)
Single-byte encodings of the parameters 𝑘 and ℓ are included in the XOF input for domain separation. For
implementations that use the seed in place of the private key, this ensures that the expansion will produce anunrelated key if the seed is mistakenly expanded using a parameter set other than the one originally intended.
9More precisely, since only the NTT form of 𝐀, 𝐀̂ ∈ 𝑇𝑞𝑘×ℓ = NTT(𝐀) is needed in subsequent calculations, thê is only
code actually computes 𝐀̂ as a pseudorandom sample over 𝑇𝑞𝑘×ℓ , and the sampling of 𝐀 = NTT−1 (𝐀)implicit (i.e., it could be computed but is not).
8

22

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

vectors 𝐬1 and 𝐬2 , and a polynomial vector 𝐭0 encoding the 𝑑 least significant bits of each coefficient of
the uncompressed public-key polynomial 𝐭.

Algorithm 6 ML-DSA.KeyGen_internal(𝜉)Generates a public-private key pair from a seed.
Input: Seed 𝜉 ∈ 𝔹32
Output: Public key 𝑝𝑘 ∈ 𝔹32+32𝑘(bitlen (𝑞−1)−𝑑)and private key 𝑠𝑘 ∈ 𝔹32+32+64+32⋅((ℓ+𝑘)⋅bitlen (2𝜂)+𝑑𝑘) .
1: (𝜌, 𝜌′ , 𝐾) ∈ 𝔹32 × 𝔹64 × 𝔹32 ← H(𝜉||IntegerToBytes(𝑘, 1)||IntegerToBytes(ℓ, 1), 128)2:
▷ expand seed
3: 𝐀̂ ← ExpandA(𝜌)▷ 𝐀 is generated and stored in NTT representation as 𝐀̂
4: (𝐬1 , 𝐬2 ) ← ExpandS(𝜌′ )5: 𝐭 ← NTT−1 (𝐀̂ ∘ NTT(𝐬1 )) + 𝐬2
▷ compute 𝐭 = 𝐀𝐬1 + 𝐬2
6: (𝐭1 , 𝐭0 ) ← Power2Round(𝐭)▷ compress 𝐭
7:▷ PowerTwoRound is applied componentwise (see explanatory text in Section 7.4)
8: 𝑝𝑘 ← pkEncode(𝜌, 𝐭1 )9: 𝑡𝑟 ← H(𝑝𝑘, 64)
10: 𝑠𝑘 ← skEncode(𝜌, 𝐾, 𝑡𝑟, 𝐬1 , 𝐬2 , 𝐭0 )▷ 𝐾 and 𝑡𝑟 are for use in signing
11: return (𝑝𝑘, 𝑠𝑘)

6.2

ML-DSA Signing (Internal)

ML-DSA.Sign_internal (Algorithm 7) outputs a signature encoded as a byte string. It takes a private
key 𝑠𝑘 encoded as a byte string, a formatted message 𝑀 ′ encoded as a bit string, and a 32-byte string
𝑟𝑛𝑑 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 𝑟𝑛𝑑, while the optional deterministic variants use the constant byte string {0}32 (seeSection 3).
In both variants, the signer first extracts the following from the private key: the public random seed 𝜌,
the 32-byte private random seed 𝐾, the 64-byte hash of the public key 𝑡𝑟, the secret polynomial vectors
𝐬1 and 𝐬2 , and the polynomial vector 𝐭0 encoding the 𝑑 least significant bits of each coefficient of theuncompressed public-key polynomial 𝐭. 𝜌 is then expanded to the same matrix 𝐀 as in key generation.
Before the message 𝑀 is signed, it is concatenated with the public-key hash 𝑡𝑟 and hashed down to a64-byte message representative 𝜇 using H.
The signer produces an additional 64-byte seed 𝜌″ for private randomness during each signing operation.
𝜌″ is computed as 𝜌″ ← H(𝐾||𝑟𝑛𝑑||𝜇, 64). In the default hedged variant, 𝑟𝑛𝑑 is the output of an RBG,
while in the deterministic variant, 𝑟𝑛𝑑 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 theloop 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 abyte string and output.10 The rejection sampling loop follows the Fiat-Shamir With Aborts paradigm [10]10Implementations may limit the number of iterations in this loop to not exceed a finite maximum value. If this23

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

and (aside from the rejection step) is similar in structure to Schnorr signatures [30] (e.g., EdDSA [31]). The
signer first produces a “commitment” 𝐰1 and then pseudorandomly derives a “challenge” 𝑐 from 𝐰1 andthe message representative 𝜇. Finally, the signer computes a response 𝐳.
In more detail, the main computations involved in the rejection sampling loop are as follows:• Using the ExpandMask function (Algorithm 34), the seed 𝜌″ , and a counter 𝜅, a polynomial vector𝐲 ∈ 𝑅𝑞ℓ is pseudorandomly sampled from the subset of polynomial vectors whose coefficients aremoderately short (i.e., in the range [−𝛾1 + 1, 𝛾1 ]).
• From 𝐲, the signer computes the commitment 𝐰1 by computing 𝐰 = 𝐀𝐲 and then rounding to a
nearby multiple of 2𝛾2 using HighBits (Algorithm 37).
• 𝐰1 and 𝜇 are concatenated and hashed to produce the commitment hash 𝑐.̃ This uses the function
w1Encode (Algorithm 28). The byte string 𝑐 ̃is used to pseudorandomly sample a polynomial 𝑐 ∈ 𝑅𝑞
that has coefficients in {−1, 0, 1} and Hamming weight 𝜏. The sampling is done with the function
SampleInBall (Algorithm 29).11• The signer computes the response 𝐳 = 𝐲 + 𝑐𝐬1 and performs various validity checks. If any of thechecks fails, the signer will continue the rejection sampling loop.
• If the checks pass, the signer can compute a hint polynomial 𝐡, which will allow the verifier toreconstruct 𝐰1 using the compressed public key along with the other components of the signature.
This uses the function MakeHint (Algorithm 39). The signer will then output the final signature,
which is a byte encoding of the commitment hash 𝑐,̃ the response 𝐳, and the hint 𝐡.
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 thesigning algorithm. These precomputed products are denoted in the pseudocode by a pair of double angle
brackets enclosing the variables being multiplied (e.g., ⟨⟨𝑐𝐬1 ⟩⟩).

option is used and the maximum number of iterations is exceeded without producing a valid signature, the signingalgorithm shall return a constant that represents an error and no other output, destroying the results of theunsuccessful signing attempts. See Appendix C.
11
The length of 𝑐 ̃ is determined by the desired security with respect to the “message-bound signatures” property
described in [14]. Here, a length of 𝜆/4 bytes or equivalently 2𝜆 bits is required for 𝜆 bits of classical security.

24

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

Algorithm 7 ML-DSA.Sign_internal(𝑠𝑘, 𝑀 ′ , 𝑟𝑛𝑑)
Deterministic algorithm to generate a signature for a formatted message 𝑀 ′ .
Input: Private key 𝑠𝑘 ∈ 𝔹32+32+64+32⋅((ℓ+𝑘)⋅bitlen (2𝜂)+𝑑𝑘) , formatted message 𝑀 ′ ∈ {0, 1}∗ , andper message randomness or dummy variable 𝑟𝑛𝑑 ∈ 𝔹32 .
Output: Signature 𝜎 ∈ 𝔹𝜆/4+ℓ⋅32⋅(1+bitlen (𝛾1 −1))+𝜔+𝑘 .
1: (𝜌, 𝐾, 𝑡𝑟, 𝐬1 , 𝐬2 , 𝐭0 ) ← skDecode(𝑠𝑘)2: 𝐬1̂ ← NTT(𝐬1 )3: 𝐬2̂ ← NTT(𝐬2 )4: 𝐭0̂ ← NTT(𝐭0 )5: 𝐀̂ ← ExpandA(𝜌)▷ 𝐀 is generated and stored in NTT representation as 𝐀̂′
6: 𝜇 ← H(BytesToBits(𝑡𝑟)||𝑀 , 64)▷ message representative that may optionally be
computed in a different cryptographic module
7: 𝜌″ ← H(𝐾||𝑟𝑛𝑑||𝜇, 64)▷ compute private random seed
8: 𝜅 ← 0▷ initialize counter 𝜅
9: (𝐳, 𝐡) ← ⊥10: while (𝐳, 𝐡) = ⊥ do
▷ rejection sampling loop″ℓ11:𝐲 ∈ 𝑅𝑞 ← ExpandMask(𝜌 , 𝜅)12:𝐰 ← NTT−1 (𝐀̂ ∘ NTT(𝐲))13:
𝐰1 ← HighBits(𝐰)▷ signer’s commitment
14:▷ HighBits is applied componentwise (see explanatory text in Section 7.4)
15:𝑐 ̃ ← H(𝜇||w1Encode(𝐰1 ), 𝜆/4)
▷ commitment hash16:𝑐 ∈ 𝑅𝑞 ← SampleInBall(𝑐)̃
▷ verifier’s challenge17:𝑐 ̂ ← NTT(𝑐)18:⟨⟨𝑐𝐬1 ⟩⟩ ← NTT−1 (𝑐 ̂ ∘ 𝐬1̂ )19:⟨⟨𝑐𝐬2 ⟩⟩ ← NTT−1 (𝑐 ̂ ∘ 𝐬2̂ )20:𝐳 ← 𝐲 + ⟨⟨𝑐𝐬1 ⟩⟩▷ signer’s response21:
𝐫0 ← LowBits(𝐰 − ⟨⟨𝑐𝐬2 ⟩⟩)22:▷ LowBits is applied componentwise (see explanatory text in Section 7.4)
23:
if ||𝐳||∞ ≥ 𝛾1 − 𝛽 or ||𝐫0 ||∞ ≥ 𝛾2 − 𝛽 then (z, h) ← ⊥▷ validity checks
24:
else
25:
⟨⟨𝑐𝐭0 ⟩⟩ ← NTT−1 (𝑐 ̂ ∘ 𝐭0̂ )26:
𝐡 ← MakeHint(−⟨⟨𝑐𝐭0 ⟩⟩, 𝐰 − ⟨⟨𝑐𝐬2 ⟩⟩ + ⟨⟨𝑐𝐭0 ⟩⟩)▷ Signer’s hint27:
▷ MakeHint is applied componentwise (see explanatory text in Section 7.4)
28:
if ||⟨⟨𝑐𝐭0 ⟩⟩||∞ ≥ 𝛾2 or the number of 1’s in 𝐡 is greater than 𝜔, then (z, h) ← ⊥29:
end if30:
end if31:
𝜅←𝜅+ℓ▷ increment counter
32: end while±
33: 𝜎 ← sigEncode(𝑐,̃ 𝐳 mod 𝑞, 𝐡)
34: return 𝜎

6.3

ML-DSA Verifying (Internal)

The algorithm ML-DSA.Verify_internal (Algorithm 8) takes a public key 𝑝𝑘 encoded as a byte string, amessage 𝑀 encoded as a bit string, and a signature 𝜎 encoded as a byte string as input. No randomness is25

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

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 inTable 1. If an implementation of ML-DSA.Verify_internal can accept inputs for 𝜎 or 𝑝𝑘 of any otherlength, 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 𝜌 and the compressed polynomial vector 𝐭1 from thepublic key 𝑝𝑘 and then extracts the signer’s commitment hash 𝑐,̃ response 𝐳, and hint 𝐡 from the signature
𝜎. The verifier may find that the hint was not properly byte-encoded, denoted by the symbol “⊥,” inwhich 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 𝐀 from 𝜌, as is done in key generation and signing, and creates a message representative 𝜇 byhashing the concatenation of 𝑡𝑟 (i.e., the hash of the public key 𝑝𝑘) and the message 𝑀. The verifier
then attempts to reconstruct the signer’s commitment (i.e., the polynomial vector 𝐰1 ) from the public
key 𝑝𝑘 and the signature 𝜎. In ML-DSA.Sign_internal, 𝐰1 is computed by rounding 𝐰 = 𝐀𝐲. In
ML-DSA.Verify_internal, the reconstructed value of 𝐰1 is called 𝐰′1 since it may have been computed ina different way if the signature is invalid. This 𝐰′1 is computed through the following process:• Derive the challenge polynomial 𝑐 from the signer’s commitment hash 𝑐,̃ just as similarly is done in
ML-DSA.Sign_internal.
• Use the signer’s response 𝐳 to compute𝐰′Approx = 𝐀𝐳 − 𝑐𝐭1 ⋅ 2𝑑 .
Assuming the signature was computed correctly, as in ML-DSA.Sign_internal, it follows that𝐰 = 𝐀𝐲 = 𝐀𝐳 − 𝑐𝐭 + 𝑐𝐬2 ≈ 𝐰′Approx = 𝐀𝐳 − 𝑐𝐭1 ⋅ 2𝑑
because 𝑐 and 𝐬2 have small coefficients, and 𝐭1 ⋅ 2𝑑 ≈ 𝐭 .
• Use the signer’s hint 𝐡 to obtain 𝐰′1 from 𝐰′Approx .
Finally, the verifier checks that the signer’s response 𝐳 and the signer’s hint 𝐡 are valid and that thereconstructed 𝐰′1 is consistent with the signer’s commitment hash 𝑐.̃ More precisely, the verifier checks
that all of the coefficients of 𝐳 are sufficiently small (i.e., in the range (−(𝛾1 − 𝛽), 𝛾1 − 𝛽)), 𝐡 contains nomore than 𝜔 nonzero coefficients, and 𝑐 ̃matches the hash 𝑐′̃ of the message representative 𝜇 concatenatedwith 𝐰′1 (represented as a byte string). If all of these checks succeed, then ML-DSA.Verify_internal returns
true. Otherwise, it returns false.

26

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

Algorithm 8 ML-DSA.Verify_internal(𝑝𝑘, 𝑀 ′ , 𝜎)Internal function to verify a signature 𝜎 for a formatted message 𝑀 ′ .
Input: Public key 𝑝𝑘 ∈ 𝔹32+32𝑘(bitlen (𝑞−1)−𝑑) and message 𝑀 ′ ∈ {0, 1}∗ .
Input: Signature 𝜎 ∈ 𝔹𝜆/4+ℓ⋅32⋅(1+bitlen (𝛾1 −1))+𝜔+𝑘 .
Output: Boolean
1: (𝜌, 𝐭1 ) ← pkDecode(𝑝𝑘)
2: (𝑐,̃ 𝐳, 𝐡) ← sigDecode(𝜎)▷ signer’s commitment hash 𝑐,̃ response 𝐳, and hint 𝐡
3: if 𝐡 = ⊥ then return false▷ hint was not properly encoded
4: end if
5: 𝐀̂ ← ExpandA(𝜌)▷ 𝐀 is generated and stored in NTT representation as 𝐀̂
6: 𝑡𝑟 ← H(𝑝𝑘, 64)
7: 𝜇 ← (H(BytesToBits(𝑡𝑟)||𝑀 ′ , 64))
▷ message representative that may optionally be
computed in a different cryptographic module
8: 𝑐 ∈ 𝑅𝑞 ← SampleInBall(𝑐)̃
▷ compute verifier’s challenge from 𝑐 ̃′−1′̂
9: 𝐰Approx ← NTT (𝐀 ∘ NTT(𝐳) − NTT(𝑐) ∘ NTT(𝐭1 ⋅ 2𝑑 ))▷ 𝐰Approx= 𝐀𝐳 − 𝑐𝐭1 ⋅ 2𝑑′′
10: 𝐰1 ← UseHint(𝐡, 𝐰Approx )▷ reconstruction of signer’s commitment
11:▷ UseHint is applied componentwise (see explanatory text in Section 7.4)
12: 𝑐 ′̃ ← H(𝜇||w1Encode(𝐰′1 ), 𝜆/4)▷ hash it; this should match 𝑐 ̃′
13: return [[ ||𝐳||∞ < 𝛾1 − 𝛽]] and [[𝑐 ̃ = 𝑐 ̃ ]]27

FIPS 204

7.

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

Auxiliary Functions

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

7.1

Conversion Between Data Types

While the primary data type in ML-DSA is a byte string, other data types are used as well. The goal inthis 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.

Algorithm 9 IntegerToBits(𝑥, 𝛼)Computes a base-2 representation of 𝑥 mod 2𝛼 using little-endian order.
Input: A nonnegative integer 𝑥 and a positive integer 𝛼.
Output: A bit string 𝑦 of length 𝛼.
1: 𝑥′ ← 𝑥
2: for 𝑖 from 0 to 𝛼 − 1 do
3:𝑦[𝑖] ← 𝑥′ mod 2
4:𝑥′ ← ⌊𝑥′ /2⌋
5: end for
6: return 𝑦Algorithm 10 BitsToInteger(𝑦, 𝛼)Computes the integer value expressed by a bit string using little-endian order.
Input: A positive integer 𝛼 and a bit string 𝑦 of length 𝛼.
Output: A nonnegative integer 𝑥.
1: 𝑥 ← 0
2: for 𝑖 from 1 to 𝛼 do3:
𝑥 ← 2𝑥 + 𝑦[𝛼 − 𝑖]4: end for5: return 𝑥
Algorithm 11 IntegerToBytes(𝑥, 𝛼)Computes a base-256 representation of 𝑥 mod 256𝛼 using little-endian order.
Input: A nonnegative integer 𝑥 and a positive integer 𝛼.
Output: A byte string 𝑦 of length 𝛼.
1: 𝑥′ ← 𝑥
2: for 𝑖 from 0 to 𝛼 − 1 do
3:𝑦[𝑖] ← 𝑥′ mod 256
4:𝑥′ ← ⌊𝑥′ /256⌋
5: end for
6: return 𝑦28

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

Algorithm 12 BitsToBytes(𝑦)Converts a bit string into a byte string using little-endian order.
Input: A bit string 𝑦 of length 𝛼.
Output: A byte string 𝑧 of length ⌈𝛼/8⌉.
1: 𝑧 ∈ 𝔹⌈𝛼/8⌉ ← 0⌈𝛼/8⌉
2: for 𝑖 from 0 to 𝛼 − 1 do
3:𝑧 [⌊𝑖/8⌋] ← 𝑧 [⌊𝑖/8⌋] + 𝑦[𝑖] ⋅ 2𝑖 mod 8
4: end for5: return 𝑧
Algorithm 13 BytesToBits(𝑧)Converts a byte string into a bit string using little-endian order.
Input: A byte string 𝑧 of length 𝛼.
Output: A bit string 𝑦 of length 8𝛼.
1: 𝑧 ′ ← 𝑧
2: for 𝑖 from 0 to 𝛼 − 1 do
3:for 𝑗 from 0 to 7 do
4:𝑦[8𝑖 + 𝑗] ← 𝑧′ [𝑖] mod 2
5:𝑧 ′ [𝑖] ← ⌊𝑧 ′ [𝑖]/2⌋
6:
end for
7: end for
8: return 𝑦▷ convert the byte 𝑧[𝑖] into 8 bits

Algorithms 14 and 15 translate byte strings into coefficients of polynomials in 𝑅. CoeffFromThreeBytes
uses a 3-byte string to either generate an element of {0, 1, … , 𝑞 − 1} or return the blank symbol ⊥.
CoeffFromHalfByte uses an element of {0, 1, … , 15} to either generate an element of {−𝜂, −𝜂+1, … , 𝜂}or return ⊥. These two procedures will be used in the uniform sampling algorithms RejNTTPoly and
RejBoundedPoly, which are discussed in Section 7.3.

Algorithm 14 CoeffFromThreeBytes(𝑏0 , 𝑏1 , 𝑏2 )Generates an element of {0, 1, 2, … , 𝑞 − 1} ∪ {⊥}.
Input: Bytes 𝑏0 , 𝑏1 , 𝑏2 .
Output: An integer modulo 𝑞 or ⊥.
1: 𝑏2′ ← 𝑏2
2: if 𝑏2′ > 127 then3:𝑏2′ ← 𝑏2′ − 128
4: end if
5: 𝑧 ← 216 ⋅ 𝑏2′ + 28 ⋅ 𝑏1 + 𝑏0
6: if 𝑧 < 𝑞 then return 𝑧
7: else return ⊥8: end if▷ set the top bit of 𝑏2′ to zero▷ 0 ≤ 𝑧 ≤ 223 − 1▷ rejection sampling

29

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

Algorithm 15 CoeffFromHalfByte(𝑏)Let 𝜂 ∈ {2, 4}. Generates an element of {−𝜂, −𝜂 + 1, … , 𝜂} ∪ {⊥}.
Input: Integer 𝑏 ∈ {0, 1, … , 15}.
Output: An integer between −𝜂 and 𝜂, or ⊥.
1: if 𝜂 = 2 and 𝑏 < 15 then return 2 − (𝑏 mod 5)
2: else3:
if 𝜂 = 4 and 𝑏 < 9 then return 4 − 𝑏else return ⊥4:
5:
end if
6: end if▷ rejection sampling from {−2, … , 2}
▷ rejection sampling from {−4, … , 4}

Algorithms 16–19 efficiently translate an element 𝑤 ∈ 𝑅 into a byte string and vice versa under theassumption that the coefficients of 𝑤 are in a restricted range. SimpleBitPack assumes that 𝑤𝑖 ∈ [0, 𝑏]
for some positive integer 𝑏 and packs 𝑤 into a byte string of length 32 ⋅ bitlen 𝑏. BitPack allows for the
more general restriction 𝑤𝑖 ∈ [−𝑎, 𝑏]. The BitPack algorithm works by merely subtracting 𝑤 from the255
polynomial ∑𝑖=0 𝑏𝑋 𝑖 .

Algorithm 16 SimpleBitPack(𝑤, 𝑏)
Encodes a polynomial 𝑤 into a byte string.
Input: 𝑏 ∈ ℕ and 𝑤 ∈ 𝑅 such that the coefficients of 𝑤 are all in [0, 𝑏].
Output: A byte string of length 32 ⋅ bitlen 𝑏.
1: 𝑧 ← ()▷ set 𝑧 to the empty bit string
2: for 𝑖 from 0 to 255 do
3:𝑧 ← 𝑧||IntegerToBits(𝑤𝑖 , bitlen 𝑏)
4: end for5: return BitsToBytes(𝑧)Algorithm 17 BitPack(𝑤, 𝑎, 𝑏)
Encodes a polynomial 𝑤 into a byte string.
Input: 𝑎, 𝑏 ∈ ℕ and 𝑤 ∈ 𝑅 such that the coefficients of 𝑤 are all in [−𝑎, 𝑏].
Output: A byte string of length 32 ⋅ bitlen (𝑎 + 𝑏).
1: 𝑧 ← ()▷ set 𝑧 to the empty bit string
2: for 𝑖 from 0 to 255 do
3:𝑧 ← 𝑧||IntegerToBits(𝑏 − 𝑤𝑖 , bitlen (𝑎 + 𝑏))
4: end for5: return BitsToBytes(𝑧)SimpleBitUnpack and BitUnpack are used to decode the byte strings produced by the above functions.
For some choices of 𝑎 and 𝑏, there exist malformed byte strings that will cause SimpleBitUnpack and
BitUnpack to output polynomials whose coefficients are not in the ranges [0, 𝑏] and [−𝑎, 𝑏], respectively.
This can be a concern when running SimpleBitUnpack and BitUnpack on inputs that may come from an
untrusted source.

30

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

Algorithm 18 SimpleBitUnpack(𝑣, 𝑏)
Reverses the procedure SimpleBitPack.
Input: 𝑏 ∈ ℕ and a byte string 𝑣 of length 32 ⋅ bitlen 𝑏.
Output: A polynomial 𝑤 ∈ 𝑅 with coefficients in [0, 2𝑐 − 1], where 𝑐 = bitlen 𝑏.
When 𝑏 + 1 is a power of 2, the coefficients are in [0, 𝑏].
1: 𝑐 ← bitlen 𝑏
2: 𝑧 ← BytesToBits(𝑣)
3: for 𝑖 from 0 to 255 do
4:𝑤𝑖 ← BitsToInteger((𝑧[𝑖𝑐], 𝑧[𝑖𝑐 + 1], … 𝑧[𝑖𝑐 + 𝑐 − 1]), 𝑐)
5: end for
6: return 𝑤
Algorithm 19 BitUnpack(𝑣, 𝑎, 𝑏)
Reverses the procedure BitPack.
Input: 𝑎, 𝑏 ∈ ℕ and a byte string 𝑣 of length 32 ⋅ bitlen (𝑎 + 𝑏).
Output: A polynomial 𝑤 ∈ 𝑅 with coefficients in [𝑏 − 2𝑐 + 1, 𝑏], where 𝑐 = bitlen (𝑎 + 𝑏).
When 𝑎 + 𝑏 + 1 is a power of 2, the coefficients are in [−𝑎, 𝑏].
1: 𝑐 ← bitlen (𝑎 + 𝑏)
2: 𝑧 ← BytesToBits(𝑣)
3: for 𝑖 from 0 to 255 do
4:𝑤𝑖 ← 𝑏 − BitsToInteger((𝑧[𝑖𝑐], 𝑧[𝑖𝑐 + 1], … 𝑧[𝑖𝑐 + 𝑐 − 1]), 𝑐)
5: end for
6: return 𝑤
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 𝐡 ∈ 𝑅2𝑘 such that the total number of coefficients in 𝐡[0], 𝐡[1], … , 𝐡[𝑘−1]that are equal to 1 is no more than 𝜔. This constraint enables encoding and decoding procedures that are
more efficient (although more complex) than BitPack and BitUnpack.
HintBitPack (𝐡) outputs a byte string 𝑦 of length 𝜔 + 𝑘. The last 𝑘 bytes of 𝑦 contain information about
how many nonzero coefficients are present in each of the polynomials 𝐡[0], 𝐡[1], … , 𝐡[𝑘 − 1], and thefirst 𝜔 bytes of 𝑦 contain information about exactly where those nonzero terms occur. HintBitUnpack
reverses the procedure performed by HintBitPack and recovers the vector 𝐡.

31

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

Algorithm 20 HintBitPack(𝐡)Encodes a polynomial vector 𝐡 with binary coefficients into a byte string.
Input: A polynomial vector 𝐡 ∈ 𝑅2𝑘 such that the polynomials 𝐡[0], 𝐡[1],...,𝐡[𝑘 − 1] havecollectively at most 𝜔 nonzero coefficients.
Output: A byte string 𝑦 of length 𝜔 + 𝑘 that encodes 𝐡 as described above.
1: 𝑦 ∈ 𝔹𝜔+𝑘 ← 0𝜔+𝑘2: Index ← 0▷ Index for writing the first 𝜔 bytes of 𝑦
3: for 𝑖 from 0 to 𝑘 − 1 do
▷ look at 𝐡[𝑖]4:for 𝑗 from 0 to 255 do
5:
if 𝐡[𝑖]𝑗 ≠ 0 then6:𝑦[Index] ← 𝑗▷ store the locations of the nonzero coefficients in 𝐡[𝑖]7:Index ← Index + 1
8:
end if
9:end for10:𝑦[𝜔 + 𝑖] ← Index▷ after processing 𝐡[𝑖], store the value of Index
11: end for
12: return 𝑦Algorithm 21 HintBitUnpack(𝑦)Reverses the procedure HintBitPack.
Input: A byte string 𝑦 of length 𝜔 + 𝑘 that encodes 𝐡 as described above.
Output: A polynomial vector 𝐡 ∈ 𝑅2𝑘 or ⊥.
1: 𝐡 ∈ 𝑅2𝑘 ← 0𝑘
2: Index ← 0▷ Index for reading the first 𝜔 bytes of 𝑦
3: for 𝑖 from 0 to 𝑘 − 1 do
▷ reconstruct 𝐡[𝑖]4:if 𝑦[𝜔 + 𝑖] < Index or 𝑦[𝜔 + 𝑖] > 𝜔 then return ⊥▷ malformed input
5:
end if
6:
First ← Index
7:
while Index < 𝑦[𝜔 + 𝑖] do▷ 𝑦[𝜔 + 𝑖] says how far one can advance Index
8:
if Index > First then9:
if 𝑦[Index − 1] ≥ 𝑦[Index] then return ⊥▷ malformed input
10:
end if11:
end if12:𝐡[𝑖]𝑦[Index] ← 1▷ 𝑦[Index] says which coefficient in 𝐡[𝑖] should be 1
13:
Index ← Index + 1
14:
end while
15: end for
16: for 𝑖 from Index to 𝜔 − 1 do
▷ read any leftover bytes in the first 𝜔 bytes of 𝑦17:
if 𝑦[𝑖] ≠ 0 then return ⊥▷ malformed input
18:
end if
19: end for
20: return 𝐡32

FIPS 204

7.2

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

Encodings of ML-DSA Keys and Signatures

Algorithms 22–27 translate keys and signatures for ML-DSA into byte strings. These procedures takecertain sequences of algebraic objects, encode them consecutively into byte strings, and perform therespective 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.

Algorithm 22 pkEncode(𝜌, 𝐭1 )Encodes a public key for ML-DSA into a byte string.
Input:𝜌 ∈ 𝔹32 , 𝐭1 ∈ 𝑅𝑘 with coefficients in [0, 2bitlen (𝑞−1)−𝑑 − 1].
Output: Public key 𝑝𝑘 ∈ 𝔹32+32𝑘(bitlen (𝑞−1)−𝑑) .
1: 𝑝𝑘 ← 𝜌
2: for 𝑖 from 0 to 𝑘 − 1 do
3:
𝑝𝑘 ← 𝑝𝑘 || SimpleBitPack (𝐭1 [𝑖], 2bitlen (𝑞−1)−𝑑 − 1)
4: end for5: return 𝑝𝑘
Algorithm 23 pkDecode(𝑝𝑘)Reverses the procedure pkEncode.
Input: Public key 𝑝𝑘 ∈ 𝔹32+32𝑘(bitlen (𝑞−1)−𝑑) .
Output: 𝜌 ∈ 𝔹32 , 𝐭1 ∈ 𝑅𝑘 with coefficients in [0, 2bitlen (𝑞−1)−𝑑 − 1].
𝑘1: (𝜌, 𝑧0 , … , 𝑧𝑘−1 ) ∈ 𝔹32 × (𝔹32(bitlen (𝑞−1)−𝑑) ) ← 𝑝𝑘
2: for 𝑖 from 0 to 𝑘 − 1 do
3:
𝐭1 [𝑖] ← SimpleBitUnpack(𝑧𝑖 , 2bitlen (𝑞−1)−𝑑 − 1)
4: end for5: return (𝜌, 𝐭1 )▷ This is always in the correct range

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.

33

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

Algorithm 24 skEncode(𝜌, 𝐾, 𝑡𝑟, 𝐬1 , 𝐬2 , 𝐭0 )Encodes a secret key for ML-DSA into a byte string.
Input: 𝜌 ∈ 𝔹32 , 𝐾 ∈ 𝔹32 , 𝑡𝑟 ∈ 𝔹64 , 𝐬1 ∈ 𝑅ℓ with coefficients in [−𝜂, 𝜂], 𝐬2 ∈ 𝑅𝑘 withcoefficients in [−𝜂, 𝜂], 𝐭0 ∈ 𝑅𝑘 with coefficients in [−2𝑑−1 + 1, 2𝑑−1 ].
Output: Private key 𝑠𝑘 ∈ 𝔹32+32+64+32⋅((𝑘+ℓ)⋅bitlen (2𝜂)+𝑑𝑘) .
1: 𝑠𝑘 ← 𝜌||𝐾||𝑡𝑟
2: for 𝑖 from 0 to ℓ − 1 do
3:𝑠𝑘 ← 𝑠𝑘 || BitPack (𝐬1 [𝑖], 𝜂, 𝜂)
4: end for
5: for 𝑖 from 0 to 𝑘 − 1 do
6:
𝑠𝑘 ← 𝑠𝑘 || BitPack (𝐬2 [𝑖], 𝜂, 𝜂)
7: end for
8: for 𝑖 from 0 to 𝑘 − 1 do
9:𝑠𝑘 ← 𝑠𝑘 || BitPack (𝐭0 [𝑖], 2𝑑−1 − 1, 2𝑑−1 )10: end for
11: return 𝑠𝑘
Algorithm 25 skDecode(𝑠𝑘)Reverses the procedure skEncode.
Input: Private key 𝑠𝑘 ∈ 𝔹32+32+64+32⋅((ℓ+𝑘)⋅bitlen (2𝜂)+𝑑𝑘) .
Output: 𝜌 ∈ 𝔹32 , 𝐾 ∈ 𝔹32 , 𝑡𝑟 ∈ 𝔹64 ,𝐬1 ∈ 𝑅ℓ , 𝐬2 ∈ 𝑅𝑘 , 𝐭0 ∈ 𝑅𝑘 with coefficients in [−2𝑑−1 + 1, 2𝑑−1 ].
ℓ

1: (𝜌, 𝐾, 𝑡𝑟, 𝑦0 , … , 𝑦ℓ−1 , 𝑧0 , … , 𝑧𝑘−1 , 𝑤0 , … , 𝑤𝑘−1 ) ∈ 𝔹32 × 𝔹32 × 𝔹64 × (𝔹32⋅bitlen (2𝜂) )32⋅bitlen (2𝜂) 𝑘

×

32𝑑 𝑘

) × (𝔹 ) ← 𝑠𝑘
(𝔹
2: for 𝑖 from 0 to ℓ − 1 do
3:𝐬1 [𝑖] ← BitUnpack(𝑦𝑖 , 𝜂, 𝜂)▷ this may lie outside [−𝜂, 𝜂] if input is malformed
4: end for
5: for 𝑖 from 0 to 𝑘 − 1 do
6:𝐬2 [𝑖] ← BitUnpack(𝑧𝑖 , 𝜂, 𝜂)▷ this may lie outside [−𝜂, 𝜂] if input is malformed
7: end for
8: for 𝑖 from 0 to 𝑘 − 1 do
9:
𝐭0 [𝑖] ← BitUnpack(𝑤𝑖 , 2𝑑−1 − 1, 2𝑑−1 )▷ this is always in the correct range
10: end for
11: return (𝜌, 𝐾, 𝑡𝑟, 𝐬1 , 𝐬2 , 𝐭0 )Next, sigEncode and sigDecode translate ML-DSA signatures into byte strings and vice versa. When
verifying a signature, sigDecode might take input that comes from an untrusted source. Thus, care isrequired when using BitUnpack. As used here, BitUnpack always returns values in the correct range.

34

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

Algorithm 26 sigEncode(𝑐,̃ 𝐳, 𝐡)
Encodes a signature into a byte string.
Input: 𝑐 ̃ ∈ 𝔹𝜆/4 , 𝐳 ∈ 𝑅ℓ with coefficients in [−𝛾1 + 1, 𝛾1 ], 𝐡 ∈ 𝑅2𝑘 .
Output: Signature 𝜎 ∈ 𝔹𝜆/4+ℓ⋅32⋅(1+bitlen (𝛾1 −1))+𝜔+𝑘 .
1: 𝜎 ← 𝑐 ̃
2: for 𝑖 from 0 to ℓ − 1 do
3:𝜎 ← 𝜎 || BitPack (𝐳[𝑖], 𝛾1 − 1, 𝛾1 )4: end for
5: 𝜎 ← 𝜎 || HintBitPack (𝐡)6: return 𝜎
Algorithm 27 sigDecode(𝜎)Reverses the procedure sigEncode.
Input: Signature 𝜎 ∈ 𝔹𝜆/4+ℓ⋅32⋅(1+bitlen (𝛾1 −1))+𝜔+𝑘 .
Output: 𝑐 ̃ ∈ 𝔹𝜆/4 , 𝐳 ∈ 𝑅ℓ with coefficients in [−𝛾1 + 1, 𝛾1 ], 𝐡 ∈ 𝑅2𝑘 , or ⊥.
ℓ

1: (𝑐,̃ 𝑥0 , … , 𝑥ℓ−1 , 𝑦) ∈ 𝔹𝜆/4 × (𝔹32⋅(1+bitlen (𝛾1 −1)) ) × 𝔹𝜔+𝑘 ← 𝜎
2: for 𝑖 from 0 to ℓ − 1 do
3:𝐳[𝑖] ← BitUnpack(𝑥𝑖 , 𝛾1 − 1, 𝛾1 ) ▷ this is in the correct range, as 𝛾1 is a power of 2
4: end for
5: 𝐡 ← HintBitUnpack(𝑦)6: return (𝑐,̃ 𝐳, 𝐡)

w1Encode is a specific subroutine used in ML-DSA.Sign. The procedure w1Encode encodes a polynomial
vector 𝐰1 into a string of bytes so that it can be processed by the function H.

Algorithm 28 w1Encode(𝐰1 )Encodes a polynomial vector 𝐰1 into a byte string.
Input: 𝐰1 ∈ 𝑅𝑘 whose polynomial coordinates have coefficients in [0, (𝑞 − 1)/(2𝛾2 ) − 1].
Output: A byte string representation 𝐰̃ 1 ∈ 𝔹32𝑘⋅bitlen ((𝑞−1)/(2𝛾2 )−1) .
1: 𝐰̃ 1 ← ()2: for 𝑖 from 0 to 𝑘 − 1 do
3:𝐰̃ 1 ← 𝐰̃ 1 || SimpleBitPack (𝐰1 [𝑖], (𝑞 − 1)/(2𝛾2 ) − 1)
4: end for5: return 𝐰̃ 1

35

FIPS 204

7.3

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

Pseudorandom SamplingThis section specifies various algorithms for generating algebraic objects pseudorandomly from a seed𝜌, where 𝜌 is a byte string whose length varies depending on the algorithm. The first procedure to be
defined is SampleInBall. As in Section 2.3, 𝐵𝜏 denotes the set of all polynomials 𝑐 ∈ 𝑅 such that• Each coefficient of 𝑐 is either −1, 0, or 1, and• Exactly 𝜏 of the coefficients of 𝑐 are nonzero.
SampleInBall pseudorandomly generates an element of 𝐵𝜏 using the XOF of a seed 𝜌. The procedure
is based on the Fisher-Yates shuffle. H is applied to 𝜌, and the first 8 bytes of the output are used tochoose the signs of the nonzero entries of 𝑐.12 Subsequent bytes are used to choose the positions of
those nonzero entries.

Algorithm 29 SampleInBall(𝜌)Samples a polynomial 𝑐 ∈ 𝑅 with coefficients from {−1, 0, 1} and Hamming weight 𝜏 ≤ 64.
Input: A seed 𝜌 ∈ 𝔹𝜆/4
Output: A polynomial 𝑐 in 𝑅.
1: 𝑐 ← 0
2: ctx ← H.Init()
3: ctx ← H.Absorb(ctx, 𝜌)
4: (ctx, 𝑠) ← H.Squeeze(ctx, 8)
5: ℎ ← BytesToBits(𝑠)6: for 𝑖 from 256 − 𝜏 to 255 do
7:(ctx, 𝑗) ← H.Squeeze(ctx, 1)
8:while 𝑗 > 𝑖 do
9:(ctx, 𝑗) ← H.Squeeze(ctx, 1)
10:
end while11:
𝑐𝑖 ← 𝑐 𝑗
12:
𝑐𝑗 ← (−1)ℎ[𝑖+𝜏−256]
13: end for
14: return 𝑐▷ ℎ is a bit string of length 64▷ rejection sampling in {0, … , 𝑖}
▷ 𝑗 is a pseudorandom byte that is ≤ 𝑖

Algorithms 30–34 are the pseudorandom procedures RejNTTPoly, RejBoundedPoly, ExpandA, ExpandS,
and ExpandMask. Each generates elements of 𝑅 or 𝑇𝑞 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 𝐲 in 𝑅𝑘 that disguises thesecret key in the ML-DSA.Sign_internal procedure (Algorithm 7). In addition to the seed 𝜌, ExpandMask
also accepts an integer input 𝜇 that is incorporated into the pseudorandom procedure that generates 𝐬.

12

The parameter 𝜏 is always less than or equal to 64, and thus 8 bytes are sufficient to choose the signs for all 𝜏
nonzero entries of 𝐜.

36

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

Algorithm 30 RejNTTPoly(𝜌)Samples a polynomial ∈ 𝑇𝑞 .
Input: A seed 𝜌 ∈ 𝔹34 .
Output: An element 𝑎̂ ∈ 𝑇𝑞 .
1: 𝑗 ← 0
2: ctx ← G.Init()
3: ctx ← G.Absorb(ctx, 𝜌)
4: while 𝑗 < 256 do
5:(ctx, 𝑠) ← G.Squeeze(ctx, 3)
6:𝑎[𝑗]̂ ← CoeffFromThreeBytes(𝑠[0], 𝑠[1], 𝑠[2])7:if 𝑎[𝑗]̂ ≠ ⊥ then8:𝑗 ←𝑗+19:
end if
10: end while
11: return 𝑎̂

Algorithm 31 RejBoundedPoly(𝜌)Samples an element 𝑎 ∈ 𝑅 with coefficients in [−𝜂, 𝜂] computed via rejection sampling from 𝜌.
Input: A seed 𝜌 ∈ 𝔹66 .
Output: A polynomial 𝑎 ∈ 𝑅.
1: 𝑗 ← 0
2: ctx ← H.Init()
3: ctx ← H.Absorb(ctx, 𝜌)
4: while 𝑗 < 256 do
5:𝑧 ← H.Squeeze(ctx, 1)6:
𝑧0 ← CoeffFromHalfByte(𝑧 mod 16)
7:
𝑧1 ← CoeffFromHalfByte(⌊𝑧/16⌋)
8:
if 𝑧0 ≠ ⊥ then9:𝑎𝑗 ← 𝑧010:
𝑗 ←𝑗+111:
end if12:
if 𝑧1 ≠ ⊥ and 𝑗 < 256 then13:
𝑎𝑗 ← 𝑧1
14:
𝑗 ←𝑗+115:
end if
16: end while
17: return 𝑎37

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

Algorithm 32 ExpandA(𝜌)Samples a 𝑘 × ℓ matrix 𝐀̂ of elements of 𝑇𝑞 .
Input: A seed 𝜌 ∈ 𝔹32 .
Output: Matrix 𝐀̂ ∈ (𝑇𝑞 )𝑘×ℓ .
1: for 𝑟 from 0 to 𝑘 − 1 do
2:for 𝑠 from 0 to ℓ − 1 do
3:𝜌′ ← 𝜌||IntegerToBytes(𝑠, 1)||IntegerToBytes(𝑟, 1)
̂ 𝑠] ← RejNTTPoly(𝜌′ )4:𝐀[𝑟,▷ seed 𝜌′ depends on 𝑠 and 𝑟
5:end for
6: end for7: return 𝐀̂

Algorithm 33 ExpandS(𝜌)Samples vectors 𝐬1 ∈ 𝑅ℓ and 𝐬2 ∈ 𝑅𝑘 , each with polynomial coordinates whose coefficients arein the interval [−𝜂, 𝜂].
Input: A seed 𝜌 ∈ 𝔹64 .
Output: Vectors 𝐬1 , 𝐬2 of polynomials in 𝑅.
1: for 𝑟 from 0 to ℓ − 1 do
2:
𝐬𝟏 [𝑟] ← RejBoundedPoly(𝜌||IntegerToBytes(𝑟, 2))
3: end for
4: for 𝑟 from 0 to 𝑘 − 1 do
5:𝐬𝟐 [𝑟] ← RejBoundedPoly(𝜌||IntegerToBytes(𝑟 + ℓ, 2))
6: end for7: return (𝐬𝟏 , 𝐬𝟐 )▷ seed depends on 𝑟

▷ seed depends on 𝑟 + ℓ

Algorithm 34 ExpandMask(𝜌, 𝜇)Samples a vector 𝐲 ∈ 𝑅ℓ such that each polynomial 𝐲[𝑟] has coefficients between −𝛾1 + 1 and𝛾1 .
Input: A seed 𝜌 ∈ 𝔹64 and a nonnegative integer 𝜇.
Output: Vector 𝐲 ∈ 𝑅ℓ .
1: 𝑐 ← 1 + bitlen (𝛾1 − 1)
2: for 𝑟 from 0 to ℓ − 1 do
3:𝜌′ ← 𝜌||IntegerToBytes(𝜇 + 𝑟, 2)4:𝑣 ← H(𝜌′ , 32𝑐)5:𝐲[𝑟] ← BitUnpack(𝑣, 𝛾1 − 1, 𝛾1 )6: end for7: return 𝐲38▷ 𝛾1 is always a power of 2
▷ seed depends on 𝜇 + 𝑟

FIPS 204

7.4

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

High-Order and Low-Order Bits and Hints

This specification uses the auxiliary functions Power2Round, Decompose, HighBits, LowBits, MakeHint,
and UseHint and explicitly defines these functions, where 𝑟 ∈ ℤ𝑞 , 𝑟1 , 𝑟0 ∈ ℤ, and ℎ is a Boolean (orequivalently an element of ℤ2 ). However, this specification also uses these functions where 𝐫, 𝐳 ∈ 𝑅𝑞𝑘 ,𝐫1 , 𝐫0 ∈ 𝑅𝑘 , and 𝐡 ∈ 𝑅2𝑘 . In this case, the functions are applied coefficientwise to the polynomials in thevectors. In particular:• For 𝐫 ∈ 𝑅𝑞𝑘 , define (𝐫1 , 𝐫0 ) ∈ (𝑅𝑘 )2 = Power2Round(𝐫) so that:((𝐫1 [𝑖])𝑗 , (𝐫0 [𝑖])𝑗 ) = Power2Round((𝐫[𝑖])𝑗 ).
• For 𝐫 ∈ 𝑅𝑞𝑘 , define (𝐫1 , 𝐫0 ) ∈ (𝑅𝑘 )2 = Decompose(𝐫) so that:((𝐫1 [𝑖])𝑗 , (𝐫0 [𝑖])𝑗 ) = Decompose((𝐫[𝑖])𝑗 ).
• For 𝐫 ∈ 𝑅𝑞𝑘 , define 𝐫1 = HighBits (𝐫) so that:(𝐫1 [𝑖])𝑗 = HighBits((𝐫[𝑖])𝑗 ).
• For 𝐫 ∈ 𝑅𝑞𝑘 , define 𝐫0 = LowBits(𝐫) so that:(𝐫0 [𝑖])𝑗 = LowBits((𝐫[𝑖])𝑗 ).
• For 𝐳, 𝐫 ∈ 𝑅𝑞𝑘 , define 𝐡 ∈ 𝑅2𝑘 = MakeHint(𝐳, 𝐫) so that:(𝐡[𝑖])𝑗 = MakeHint((𝐳[𝑖])𝑗 , (𝐫[𝑖])𝑗 ).
• For 𝐡 ∈ 𝑅2𝑘 and 𝐫 ∈ 𝑅𝑞𝑘 , define 𝐫1 ∈ 𝑅𝑘 = UseHint(𝐡, 𝐫) so that:𝐫1 [𝑖]𝑗 = UseHint((𝐡[𝑖])𝑗 , (𝐫[𝑖])𝑗 ).
These algorithms are used to support the key compression optimization of ML-DSA. They involve dropping
the 𝑑 low-order bits of each coefficient of the polynomial vector 𝐭 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 𝐰1 ∈ 𝑅𝑘 , which represents 𝐰 ∈ 𝑅𝑞𝑘 rounded to a nearby multipleof 𝛼 = 2𝛾2 . The signer directly obtains 𝐰1 using the function HighBits, and the part rounded off (i.e., 𝐫0 )is obtained by LowBits. 𝐫0 is used by the signer in the rejection sampling procedure.
Power2Round decomposes an input 𝑟 ∈ ℤ𝑞 into integers that represent the high- and low-order bits of𝑟 mod 𝑞 in the straightforward bitwise way, 𝑟 mod 𝑞 = 𝑟1 ⋅ 2𝑑 + 𝑟0 , where 𝑟0 = (𝑟 mod 𝑞) mod± 2𝑑 and𝑟1 = (𝑟 mod 𝑞 − 𝑟0 )/2𝑑 .
However, for the purpose of computations related to hints, this method of decomposing 𝑟 has theundesirable property that when 𝑟 is close to 𝑞 − 1 or 0, a small rounding error in 𝑟 can cause 𝑟1 to change
by more than 1, even accounting for wrap-around. In contrast to other unequal pairs of values of 𝑟1 ⋅ 2𝑑
and 𝑟1′ ⋅ 2𝑑 , the distance (mod𝑞) between ⌊𝑞/2𝑑 ⌋ ⋅ 2𝑑 and 0 may be very small.

39

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

To avoid this problem, this specification defines Decompose, which is similar to Power2Round except:• 𝑟 is generally decomposed as 𝑟 mod 𝑞 = 𝑟1 ⋅ 𝛼 + 𝑟0 , where 𝛼 = 2𝛾2 is a divisor of 𝑞 − 1.
• If the straightforward rounding procedure would return (𝑟1 = (𝑞 − 1)/𝛼, 𝑟0 ∈ [−(𝛼/2) + 1, 𝛼/2]),
Decompose instead returns (𝑟1 = 0, 𝑟0 − 1).
The functions HighBits and LowBits — which only return 𝑟1 and 𝑟0 , respectively — and MakeHint andUseHint 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].

Algorithm 35 Power2Round(𝑟)Decomposes 𝑟 into (𝑟1 , 𝑟0 ) such that 𝑟 ≡ 𝑟1 2𝑑 + 𝑟0 mod 𝑞.
Input: 𝑟 ∈ ℤ𝑞 .
Output: Integers (𝑟1 , 𝑟0 ).
1: 𝑟+ ← 𝑟 mod 𝑞±
2: 𝑟0 ← 𝑟+ mod 2𝑑
3: return ((𝑟+ − 𝑟0 )/2𝑑 , 𝑟0 )Algorithm 36 Decompose(𝑟)Decomposes 𝑟 into (𝑟1 , 𝑟0 ) such that 𝑟 ≡ 𝑟1 (2𝛾2 ) + 𝑟0 mod 𝑞.
Input: 𝑟 ∈ ℤ𝑞 .
Output: Integers (𝑟1 , 𝑟0 ).
1: 𝑟+ ← 𝑟 mod 𝑞±
2: 𝑟0 ← 𝑟+ mod (2𝛾2 )3: if 𝑟+ − 𝑟0 = 𝑞 − 1 then4:
𝑟1 ← 05:
𝑟0 ← 𝑟 0 − 1
6: else 𝑟1 ← (𝑟+ − 𝑟0 )/(2𝛾2 )7: end if
8: return (𝑟1 , 𝑟0 )Algorithm 37 HighBits(𝑟)Returns 𝑟1 from the output of Decompose (𝑟).
Input: 𝑟 ∈ ℤ𝑞 .
Output: Integer 𝑟1 .
1: (𝑟1 , 𝑟0 ) ← Decompose(𝑟)2: return 𝑟1

40

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

Algorithm 38 LowBits(𝑟)Returns 𝑟0 from the output of Decompose (𝑟).
Input: 𝑟 ∈ ℤ𝑞 .
Output: Integer 𝑟0 .
1: (𝑟1 , 𝑟0 ) ← Decompose(𝑟)2: return 𝑟0

Algorithm 39 MakeHint(𝑧, 𝑟)
Computes hint bit indicating whether adding 𝑧 to 𝑟 alters the high bits of 𝑟.
Input: 𝑧, 𝑟 ∈ ℤ𝑞 .
Output: Boolean.
1: 𝑟1 ← HighBits(𝑟)2: 𝑣1 ← HighBits(𝑟 + 𝑧)
3: return [[𝑟1 ≠ 𝑣1 ]]Algorithm 40 UseHint(ℎ, 𝑟)
Returns the high bits of 𝑟 adjusted according to hint ℎ.
Input: Boolean ℎ, 𝑟 ∈ ℤ𝑞 .
Output: 𝑟1 ∈ ℤ with 0 ≤ 𝑟1 ≤ 𝑞−12𝛾 .
2

1: 𝑚 ← (𝑞 − 1)/(2𝛾2 )2: (𝑟1 , 𝑟0 ) ← Decompose(𝑟)3: if ℎ = 1 and 𝑟0 > 0 return (𝑟1 + 1) mod 𝑚
4: if ℎ = 1 and 𝑟0 ≤ 0 return (𝑟1 − 1) mod 𝑚
5: return 𝑟1

41

FIPS 204

7.5

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

NTT and NTT−1

The following algorithms implement the NTT and its inverse (NTT−1 ), which is important for efficiency.
There are other optimizations that are not included in this standard. In particular, mod 𝑞 and mod± 𝑞 are
expensive operations whose use can be minimized by using Montgomery Multiplication (see Appendix A).
An element of 𝑅𝑞 is a polynomial in ℤ𝑞 [𝑋]/(𝑋 256 + 1), and an element of 𝑇𝑞 is a tuple in Π255
𝑗=0 ℤ𝑞 . The
NTT algorithm takes a polynomial 𝑤 ∈ 𝑅𝑞 as input and returns 𝑤̂ ∈ 𝑇𝑞 . NTT−1 takes 𝑤̂ ∈ 𝑇𝑞 as input
and returns 𝑤 such that 𝑤̂ = NTT(𝑤).
This document always distinguishes between elements of 𝑅𝑞 and elements of 𝑇𝑞 . However, the natural
data structure for both of these sets is as an integer array of size 256. This would allow the NTT and
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, 𝜁 = 1753 ∈ ℤ𝑞 , which is a 512th root of unity modulo 𝑞. On input 𝑤 ∈ 𝑅𝑞 , the algorithm
outputs(7.1)
NTT(𝑤) = (𝑤(𝜁0 ), 𝑤(𝜁1 ), … , 𝑤(𝜁255 )) ∈ 𝑇𝑞 ,where 𝜁𝑖 = 𝑤(𝜁 2BitRev8 (𝑖)+1 ) mod 𝑞.
The values 𝜁 BitRev8 (𝑘) mod 𝑞 for 𝑘 = 1, … , 255 used in line 10 of Algorithms 41 and 42 are pre-computed
into an array 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.
NTT and NTT−1 use BitRev8 , which reverses the order of bits in an 8-bit integer.

42

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

Algorithm 41 NTT(𝑤)Computes the NTT.
255

Input: Polynomial 𝑤(𝑋) = ∑𝑗=0 𝑤𝑗 𝑋 𝑗 ∈ 𝑅𝑞 .
Output: 𝑤̂ = (𝑤[0],̂… , 𝑤[255])
̂∈ 𝑇𝑞 .
1: for 𝑗 from 0 to 255 do
2:𝑤[𝑗]̂ ← 𝑤𝑗
3: end for
4: 𝑚 ← 0
5: 𝑙𝑒𝑛 ← 128
6: while 𝑙𝑒𝑛 ≥ 1 do
7:𝑠𝑡𝑎𝑟𝑡 ← 08:
while 𝑠𝑡𝑎𝑟𝑡 < 256 do
9:
𝑚←𝑚+1
10:
𝑧 ← zetas[𝑚]11:
for 𝑗 from 𝑠𝑡𝑎𝑟𝑡 to 𝑠𝑡𝑎𝑟𝑡 + 𝑙𝑒𝑛 − 1 do
12:𝑡 ← (𝑧 ⋅ 𝑤[𝑗̂ + 𝑙𝑒𝑛]) mod 𝑞
13:𝑤[𝑗̂ + 𝑙𝑒𝑛] ← (𝑤[𝑗]̂ − 𝑡) mod 𝑞
14:𝑤[𝑗]̂ ← (𝑤[𝑗]̂ + 𝑡) mod 𝑞
15:
end for16:
𝑠𝑡𝑎𝑟𝑡 ← 𝑠𝑡𝑎𝑟𝑡 + 2 ⋅ 𝑙𝑒𝑛
17:
end while18:
𝑙𝑒𝑛 ← ⌊𝑙𝑒𝑛/2⌋
19: end while
20: return 𝑤̂

43▷ 𝑧 ← 𝜁 BitRev8 (𝑚) mod 𝑞

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

Algorithm 42 NTT−1 (𝑤)̂Computes the inverse of the NTT.
Input: 𝑤̂ = (𝑤[0],̂… , 𝑤[255])
̂∈ 𝑇𝑞 .
255
Output: Polynomial 𝑤(𝑋) = ∑𝑗=0 𝑤𝑗 𝑋 𝑗 ∈ 𝑅𝑞 .
1: for 𝑗 from 0 to 255 do2:
𝑤𝑗 ← 𝑤[𝑗]̂
3: end for
4: 𝑚 ← 256
5: 𝑙𝑒𝑛 ← 1
6: while 𝑙𝑒𝑛 < 256 do
7:𝑠𝑡𝑎𝑟𝑡 ← 08:
while 𝑠𝑡𝑎𝑟𝑡 < 256 do
9:
𝑚←𝑚−1
10:
𝑧 ← −𝑧𝑒𝑡𝑎𝑠[𝑚]11:
for 𝑗 from 𝑠𝑡𝑎𝑟𝑡 to 𝑠𝑡𝑎𝑟𝑡 + 𝑙𝑒𝑛 − 1 do
12:𝑡 ← 𝑤𝑗13:
𝑤𝑗 ← (𝑡 + 𝑤𝑗+𝑙𝑒𝑛 ) mod 𝑞
14:
𝑤𝑗+𝑙𝑒𝑛 ← (𝑡 − 𝑤𝑗+𝑙𝑒𝑛 ) mod 𝑞
15:
𝑤𝑗+𝑙𝑒𝑛 ← (𝑧 ⋅ 𝑤𝑗+𝑙𝑒𝑛 ) mod 𝑞
16:
end for17:
𝑠𝑡𝑎𝑟𝑡 ← 𝑠𝑡𝑎𝑟𝑡 + 2 ⋅ 𝑙𝑒𝑛
18:
end while19:
𝑙𝑒𝑛 ← 2 ⋅ 𝑙𝑒𝑛
20: end while
21: 𝑓 ← 8347681
22: for 𝑗 from 0 to 255 do
23:
𝑤𝑗 ← (𝑓 ⋅ 𝑤𝑗 ) mod 𝑞
24: end for
25: return 𝑤▷ 𝑧 ← −𝜁 BitRev8 (𝑚) mod 𝑞▷ 𝑓 = 256−1 mod 𝑞

Algorithm 43 BitRev8 (𝑚)Transforms a byte by reversing the order of bits in its 8-bit binary expansion.
Input: A byte 𝑚 ∈ [0, 255].
Output: A byte 𝑟 ∈ [0, 255].
1: 𝑏 ← IntegerToBits(𝑚, 8)
2: 𝑏rev ∈ {0, 1}8 ← (0, … , 0)
3: for 𝑖 from 0 to 7 do
4:𝑏rev [𝑖] ← 𝑏 [7 − 𝑖]5: end for
6: 𝑟 ← BitsToInteger(𝑏rev , 8)
7: return r
44

FIPS 204

7.6

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

Arithmetic Under NTT

The NTT converts elements of the ring 𝑅𝑞 (where addition and multiplication are denoted by + and ⋅,respectively) into elements of the ring 𝑇𝑞 (where addition and multiplication are denoted by + and ∘,respectively). This section gives explicit algorithms for linear algebra over the ring 𝑇𝑞 .
The ring 𝑇𝑞 is defined to be the direct product ring Π255
𝑖=0 ℤ𝑞 . Thus, an element 𝑎 ̂ ∈ 𝑇𝑞 is an array of length
256, and its elements are denoted by 𝑎[0],̂ 𝑎[1],
̂ … , 𝑎[255]̂∈ ℤ𝑞 .

Algorithm 44 AddNTT(𝑎,̂ 𝑏)̂
Computes the sum 𝑎̂ + 𝑏̂ of two elements 𝑎,̂ 𝑏̂ ∈ 𝑇𝑞 .
Input: 𝑎,̂ 𝑏̂ ∈ 𝑇𝑞 .
Output: 𝑐 ̂ ∈ 𝑇𝑞 .
1: for 𝑖 from 0 to 255 do
̂
2:
𝑐[𝑖]
̂ ← 𝑎[𝑖]̂ + 𝑏[𝑖]3: end for
4: return 𝑐 ̂
Algorithm 45 MultiplyNTT(𝑎,̂ 𝑏)̂
Computes the product 𝑎̂ ∘ 𝑏̂ of two elements 𝑎,̂ 𝑏̂ ∈ 𝑇𝑞 .
Input: 𝑎,̂ 𝑏̂ ∈ 𝑇𝑞 .
Output: 𝑐 ̂ ∈ 𝑇𝑞 .
1: for 𝑖 from 0 to 255 do
̂
2:
𝑐[𝑖]
̂ ← 𝑎[𝑖]̂ ⋅ 𝑏[𝑖]3: end for
4: return 𝑐 ̂
Algorithm 46 AddVectorNTT(𝐯,̂ 𝐰)
̂Computes the sum 𝐯̂ + 𝐰̂ of two vectors 𝐯,̂ 𝐰̂ over 𝑇𝑞 .
Input: ℓ ∈ ℕ, 𝐯̂ ∈ 𝑇𝑞ℓ , 𝐰̂ ∈ 𝑇𝑞ℓ .
Output: 𝐮̂ ∈ 𝑇𝑞ℓ .
1: for 𝑖 from 0 to ℓ − 1 do
2:𝐮[𝑖]
̂ ← AddNTT(𝐯[𝑖],̂ 𝐰[𝑖])
̂
3: end for
4: return 𝐮̂45

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

Algorithm 47 ScalarVectorNTT(𝑐,̂ 𝐯)̂
Computes the product 𝑐 ̂ ∘ 𝐯̂ of a scalar 𝑐 ̂ and a vector 𝐯̂ over 𝑇𝑞 .
Input: 𝑐 ̂ ∈ 𝑇𝑞 , ℓ ∈ ℕ, 𝐯̂ ∈ 𝑇𝑞ℓ .
Output: 𝐰̂ ∈ 𝑇𝑞ℓ .
1: for 𝑖 from 0 to ℓ − 1 do
2:𝐰[𝑖]
̂ ← MultiplyNTT(𝑐,̂ 𝐯[𝑖])̂
3: end for
4: return 𝐰̂̂ 𝐯)̂
Algorithm 48 MatrixVectorNTT(𝐌,Computes the product 𝐌̂ ∘ 𝐯̂ of a matrix 𝐌̂ and a vector 𝐯̂ over 𝑇𝑞 .
Input: 𝑘, ℓ ∈ ℕ, 𝐌̂ ∈ 𝑇𝑞𝑘×ℓ , 𝐯̂ ∈ 𝑇𝑞ℓ .
Output: 𝐰̂ ∈ 𝑇𝑞𝑘 .
1: 𝐰̂ ← 0𝑘
2: for 𝑖 from 0 to 𝑘 − 1 do
3:for 𝑗 from 0 to ℓ − 1 dô 𝑗], 𝐯[𝑗]))4:𝐰[𝑖]̂ ← AddNTT(𝐰[𝑖],̂ MultiplyNTT(𝐌[𝑖,̂
5:end for
6: end for7: return 𝐰̂

46

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

References[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) CRYSTALSDilithium: Algorithm specifications and supporting documentation, Submission to the NIST’s postquantum cryptography standardization process. Available at https://csrc.nist.gov/Projects/post-qua
ntum-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) CRYSTALSDilithium: 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 andextendable-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. Departmentof 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 ofStandards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-57 Part 1, Rev. 5 [oras 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 signaturescheme 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 witherrors. 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.

47

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD[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 andPrivacy (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. Proceedingsof 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 thequantum 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 theentropy 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 signatureschemes 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.go48

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

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, 3rdRound 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.

49

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

Appendix A — Montgomery Multiplication
This document uses modular multiplications of the form 𝑎 ⋅ 𝑏 modulo 𝑞. This is an expensive operationthat is often sped up in practice through the use of Montgomery Multiplication.
If 𝑎 is an integer modulo 𝑞, then its Montgomery form with multiplier 232 is 𝑟 ≡ 𝑎 ⋅ 232 mod 𝑞. 13
Suppose that two integers 𝑢 and 𝑣 modulo 𝑞 are in Montgomery form. Their product modulo 𝑞 is
𝑐 = 𝑢 ⋅ 𝑣 ⋅ 2−32 , which is also in Montgomery form. If the integer product of 𝑢 and 𝑣 does not overflow a
64-bit signed integer, then one can compute 𝑐 by first performing the integer multiplication 𝑢 ⋅ 𝑣 and then“reducing” the product by multiplying by 2−32 modulo 𝑞. This last operation can be done efficiently as
follows.
The MontgomeryReduce function takes an integer 𝑎 with absolute value at most 231 𝑞 as input. It returns
an integer 𝑟 such that 𝑟 = 𝑎 ⋅ 2−32 mod 𝑞. The output is in Montgomery form with multiplier 232 mod 𝑞.
An implementation would typically input a 64-bit input and return a 32-bit output. The “modulo 232 ”
operation simply extracts the 32 least significant bits of a 64-bit value. The value (𝑎 − 𝑡 ⋅ 𝑞) on line 3 is an
integer divisible by 232 . 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.

Algorithm 49 MontgomeryReduce(𝑎)Computes 𝑎 ⋅ 2−32 mod 𝑞.
Input: Integer 𝑎 with −231 𝑞 ≤ 𝑎 ≤ 231 𝑞.
Output: 𝑟 ≡ 𝑎 ⋅ 2−32 mod 𝑞.
1: QINV ← 58728449
2: 𝑡 ← ((𝑎 mod 232 ) ⋅ QINV) mod 232
3: 𝑟 ← (𝑎 − 𝑡 ⋅ 𝑞)/232
4: return 𝑟▷ the inverse of 𝑞 modulo 232

With this algorithm, the modular product of 𝑎 and 𝑏 is 𝑐 = MontgomeryReduce(𝑎 ⋅ 𝑏), where 𝑎, 𝑏, and 𝑐
are in Montgomery form. The return value of the algorithm is not necessarily less than 𝑞 in absolute value,
but it is less than 2𝑞 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 (−𝑞, 𝑞) using a comparison and an integer addition.
Converting an integer modulo 𝑞 to Montgomery form by multiplying by 232 modulo 𝑞 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 232 is extracted from the final
result.

13

This section does not distinguish between different versions of the “mod” operator. There are three such versionsof “𝑥 = 𝑎 modulo 𝑞”: i) 𝑥 ∈ [0, 𝑞 − 1]; ii) 𝑥 ∈ [−⌈𝑞/2⌉, ⌊𝑞/2⌋] ; iii) 𝑥 ∈ [−𝑞 + 1, 𝑞 − 1]. The last version
corresponds to the ‶ %″ operator in most programming languages.

50

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

Appendix B — Zetas Array
The values 𝜁 BitRev8 (𝑘) mod 𝑞 for 𝑘 = 1, … , 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] = {0,4808194,3765607,3761513,5178923,

5496691,5234739,5178987,

7778734,3542485,2682288,2129892,3764867,

7375178,557458,7159240,

5010068,4317364,2663378,6705802,4855975,

7946292,676590,7044481,5152541,

1714295,2453983,

1460718,7737789,4795319,2815639,2283733,

3602218,

3182878,2740543,4793971,5269599,2101410,3704823,

1159875,

394148,928749,1095468,

4874037,2071829,4361428,

3241972,2156050,

3415069,

1759347,7562881,4805951,3756790,6444618,6663429,4430364,5483103,3192354,

556856,3870317,2917338,

1853806,

3345963,

1858416,3073009,1277625,5744944,3852015,4183372,5157610,5258977,

8106357,

2508980,2028118,

1937570,4564692,

2811291,

5396636,7270901,

4158088,

1528066,482649,1148858,

5418153,7814814,169688,2462444,5046034,

4213992,4892034,

1987814,5183169,

1736313,235407,5130263,3258457,

5801164,

1787943,5989328,6125690,3482206,

4197502,7080401,

6018354,7062739,

2461387,3035980,

621164,

3901472,7153756,2925816,3374250,

1356448,5604662,2683270,5601629,4912752,

2312838,

7727142,7921254,348812,8052569,

1011223,6026202,4561790,6458164,6143691,1744507,1753,

6444997,5720892,6924527,

2660408,

6600190,

8321269,2772600,

1182243,

87208,

636927,4415111,4423672,6084020,5095502,4663471,8352605,822541,

1009365,5926272,6400920,1596822,4423473,4620952,6695264,4969849,2678278,4611469,4829411,635956,8129971,5925040,4234153,

6607829,2192938,6653329,2387513,4768667,

8111961,

5199961,3747250,

2296099,1239911,4541938,

3195676,

2642980,

1254190,8368000,

2998219,141835,8291116,2513018,7025525,613238,7070156,6161950,

7921677,6458423,4040196,4908348,2039144,6500539,7561656,6201452,6757063,2105286,

6006015,

6346610,586241,

7200804,

527981,5637006,

6903432,

1994046,2491325,6987258,507927,7192532,

7655613,6545891,

5346675,

8041997,2647994,3009748,5767564,4148469,749577,4357667,3980599,2569011,6764887,1723229,

1665318,2028038,

1163598,

5011144,3994671,8368538,

7009900,

3020393,3363542,214880,545376,7609976,3105558,

7277073,508145,7826699,

860144,3430436,140244,

6866265,6195333,

3123762,2358373,6187330,

5365997,6663603,2926054,7987710,8077412,3531229,4405932,

4606686,

1900052,7598542,1054478,7648983 }51

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

Appendix C — Loop Bounds
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 thatis extracted from the XOFs when executing these functions.14 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 thanthose 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
Algorithm

Minimum allowable limit(Loop iterations)

Minimum allowable limit(XOF output bytes)

ML-DSA.Sign_internal
RejBoundedPoly
RejNTTPoly
SampleInBall

814
481
298
121

N/A
481
894
221

Implementations may limit the number of iterations of a while loop or the number of bytes drawn fromthe 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 theprobability of reaching them to 2−256 .

ML-DSA.Sign_internal
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
𝑛5.1−1 𝑛−256
of repetitions exceeds 𝑛 is less than or equal to ( 5.1−1
5.1 ) for all categories. Solving ( 5.1 ) ≤ 2
yields 𝑛 = 814.

RejBoundedPoly
Let 𝑋 be the number of coefficients generated in 𝑛 iterations of the while loop of RejBoundedPoly15 .
9915Then 𝑋 is 𝐵𝑖𝑛𝑜𝑚𝑖𝑎𝑙(2𝑛, 𝜃), where 𝜃 is either 16
or 16, depending on the parameter 𝜂. For 𝜃 = 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.
RejBoundedPoly, RejNTTPoly, and SampleInBall use the incremental APIs described in Section 3.7 in order toextract the amount of output needed from the XOFs, given that the amount needed is not known in advance.
15
Note that 0, 1, or 2 coefficients are generated in each iteration.
14

52

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

RejNTTPoly
The number of valid coefficients generated in 𝑛 calls to G.Squeeze in RejNTTPoly is 𝐵𝑖𝑛𝑜𝑚𝑖𝑎𝑙(𝑛, 2−23 𝑞).
It follows that after 298 calls, the probability of failure is less than 2−256 . Each iteration consumes threebytes of output from G.

SampleInBall
Step 9 in SampleInBall is executed every time a pseudorandom byte is greater than a value 𝑖 in the range[256 − 𝜏 , 255]. The parameter 𝜏 is 39, 49, and 60 for categories 2, 3, and 5, respectively. Therefore, theprobability that this step is executed more than 𝑛 times in a single iteration of the for loop is less than or
59 𝑛
𝜏 𝑛
59 𝑛
equal to ( 256) ≤ ( 256
) . Solving ( 256) ≤ 2−256 yields a bound of 𝑛 = 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 𝜏 iterations of the for loop, eachof which extracts an indeterminate amount of data from H. The probability that more than 𝑛 bytes of
output will be required from H during an execution of SampleInBall for a given value of 𝜏 is⎧1
if 𝑛 ≤ 8{
𝑃 (𝑛, 𝜏 ) = ⎨0
if 𝜏 = 1 and 𝑛 > 8 .
{ ( 257−𝜏 ) 𝑃 (𝑛 − 1, 𝜏 − 1) + ( 𝜏−1 ) 𝑃 (𝑛 − 1, 𝜏 ) if 𝜏 > 1 and 𝑛 > 8
⎩
256
256
𝑃 (𝑛, 60) is less than 2−256 when 𝑛 is 221 or greater. Implementations may limit the number of bytes
extracted from H to 𝑛 ≥ 221. Such implementations must stop the execution of SampleInBall, return aconstant that represents an error and no other output, and destroy all intermediate results after 𝑛 bytes
of output have been consumed.

53

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

Appendix D — Differences from the CRYSTALS-DILITHIUM Submission
ML-DSA is derived from Version 3.1 of CRYSTALS-DILITHIUM [6]. Version 3.1 differs slightly from the mostrecent 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.

D.1 Differences Between Version 3.1 and the Round 3 Version of CRYSTALSDILITHIUM
The lengths of the variables 𝜌′ (private random seed) and 𝜇 (message representative) in the signingalgorithm were increased from 384 to 512 bits. The increase in the length of 𝜇 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 𝑡𝑟 (the hash of the public key) was reduced from 384 to 256 bits.
In key generation, the variable 𝜍 was relabeled as 𝜌′ 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 isdeterministic with 𝜌′ being generated pseudorandomly from the signer’s private key and the message,
and an optional version of the signing algorithm has 𝜌′ sampled instead as a 512-bit random string. In
ML-DSA, 𝜌′ is generated by a “hedged” procedure in which 𝜌′ is pseudorandomly derived from the signer’s
private key, the message, and a 256-bit string 𝑟𝑛𝑑, which should be generated by an Approved RBG bydefault. The ML-DSA standard also allows for an optional deterministic version in which 𝑟𝑛𝑑 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 notstrongly 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 𝑐 ̃ areused 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-hashversion 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 weremade by explicitly defining external functions for both versions of the signing and verification functions

54

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

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.

55