Withdrawn Draft
Warning Notice
The attached draft document has been withdrawn and is provided solely for historical purposes.
It has been followed by the document identified below.
Withdrawal Date August 13, 2024
Original Release Date August 24, 2023

The attached draft document is followed by:
Status Final
Series/Number NIST FIPS 204
Title Module-Lattice-Based Digital Signature Standard
Publication Date August 13, 2024
DOI https://doi.org/10.6028/NIST.FIPS.204
CSRC URL https://csrc.nist.gov/pubs/fips/204/final
Additional Information https://csrc.nist.gov/projects/post-quantum-cryptography/postquantum-cryptography-standardization

1

2

FIPS 204 (Draft)Federal Information Processing Standards Publication

3

4

5

6

7
8
9

Module-Lattice-Based Digital
Signature Standard
Category: Computer Security

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

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

12

Published August 24, 2023

10

Subcategory: Cryptography

13

15

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

16

National Institute of Standards and Technology

17

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

14

18

19
20
21

22
23
24

25

Foreword
The Federal Information Processing Standards Publication Series of the National Institute of Standards andTechnology is the offcial 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.
James A. St. Pierre, Acting Director
Information Technology Laboratory

FIPS 204 (D RAFT )

26

27
28
29
30

31
32
33

34
35

M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

Abstract
Digital signatures are used to detect unauthorized modifcations 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 specifes 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-scalequantum computer.
Keywords: cryptography; digital signatures; Federal Information Processing Standards; lattice; postquantum; public-key cryptography

FIPS 204 (D RAFT )M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

36

Federal Information Processing Standards Publication 204

37

Published: August 24, 2023

38

Announcing the39

Module-Lattice-Based Digital Signature Standard

42

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

43

1. Name of Standard. Module-Lattice-Based Digital Signature Standard (FIPS 204).

44

2. Category of Standard: Computer Security Standard. Subcategory: Cryptography.

40
41

45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

62

63
64

65
66
67
68
69
70
71
72

3. Explanation. This standard specifes a lattice-based digital signature algorithm, ML-DSA, for applications that require a digital signature rather than a written signature. (Additional digital signatureschemes are specifed 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 beverifed. Digital signatures may be generated on both stored and transmitted data.
Signature generation uses a private key to generate a digital signature. Signature verifcation 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 perform the generation of asignature that can be verifed by the corresponding public key.
The digital signature is provided to the intended verifer along with the signed data. The verifying
entity verifes 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 specifes several parameter sets for ML-DSA that are approved for use. Additionalparameter sets may be specifed 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 protectionof sensitive unclassifed 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 or Federal Information
Processing Standard (FIPS) 205 or NIST Special Publication 800-208 shall be used in designing andimplementing public-key-based signature systems that federal departments and agencies operate orthat are operated for them under contract. In the future, additional digital signature schemes may be
specifed and approved in FIPS publications or in NIST Special Publications.
The adoption and use of this standard are available to private and commercial organizations.

iFIPS 204 (D RAFT )

73
74
75
76
77
78
79

80
81
82
83
84
85
86
87
88

89
90
91
92

M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

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, frmware, 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 specifed 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/cryptog
raphic-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 thisstandard shall employ cryptographic algorithms that have been approved for protecting Federal
Government-sensitive information. Approved cryptographic algorithms and techniques include thosethat are either:93a. Specifed in a Federal Information Processing Standards (FIPS) publication,

94

b. Adopted in a FIPS or NIST recommendation, or

95c. Specifed in the list of approved security functions for FIPS 140-3.

100

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 athttps://www.bis.doc.gov.

101

11. Patents. The algorithm in this standard may be covered by U.S. or foreign patents.

102

12. Implementation Schedule. This standard becomes effective immediately upon fnal publication.

96
97
98
99

103
104

105
106
107
108
109
110
111
112
113
114

13. Specifcations. Federal Information Processing Standards (FIPS) 204, Module-Lattice-Based Digital
Signature Standard (affxed).
14. Qualifcations. The security of a digital signature system is dependent on maintaining the secrecy ofthe signatory’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 level of
security.

ii

FIPS 204 (D RAFT )

115
116

117
118
119

120
121

122
123
124
125
126
127
128

129
130

M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

Since a standard of this nature must be fexible enough to adapt to advancements and innovations inscience and technology, this standard will be reviewed every fve 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 ipd as the publication identifer forthis FIPS, per the NIST Technical Series Publication Identifer Syntax. NIST recommends that it becited as follows:
National Institute of Standards and Technology (2023) Module-Lattice-Based Digital
Signature Standard. (Department of Commerce, Washington, D.C.), Federal Information
Processing Standards Publication (FIPS) NIST FIPS 204 ipd. https://doi.org/10.6028/NIST.FIPS.204.ipd
18. Inquiries and Comments. Inquiries and comments about this FIPS may be submitted to fps-204comments@nist.gov.

iii

FIPS 204 (D RAFT )

131
132
133
134
135
136
137
138
139

140
141

142
143
144
145
146
147
148

149
150
151
152
153

M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

Call for Patent Claims
This public review includes a call for information on essential patent claims (claims whose use would be
required for compliance with the guidance or requirements in this Information Technology Laboratory(ITL) draft publication). Such guidance and/or requirements may be directly stated in this ITL Publication
or by reference to another publication. This call also includes disclosure, where known, of the existenceof pending U.S. or foreign patent applications relating to this ITL draft publication and of any relevant
unexpired U.S. or foreign patents.
ITL may require from the patent holder, or a party authorized to make assurances on its behalf, in written
or electronic form, either:a) assurance in the form of a general disclaimer to the effect that such party does not hold and does not
currently intend holding any essential patent claim(s); orb) assurance that a license to such essential patent claim(s) will be made available to applicants desiring
to utilize the license for the purpose of complying with the guidance or requirements in this ITL
draft publication either:(i) under reasonable terms and conditions that are demonstrably free of any unfair discrimination;or(ii) without compensation and under reasonable terms and conditions that are demonstrably freeof any unfair discrimination.
Such assurance shall indicate that the patent holder (or third party authorized to make assurances on its
behalf) will include in any documents transferring ownership of patents subject to the assurance, provisions
suffcient to ensure that the commitments in the assurance are binding on the transferee, and that thetransferee will similarly include appropriate provisions in the event of future transfers with the goal ofbinding each successor-in-interest.

155

The assurance shall also indicate that it is intended to be binding on successors-in-interest regardless ofwhether such provisions are included in the relevant transfer documents.

156

Such statements should be addressed to: fps-204-comments@nist.gov

154

iv

FIPS 204 (D RAFT )M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

157

Federal Information Processing Standards Publication 204

158

Specifcation for the159

Module-Lattice-Based Digital Signature Standard

160

Table of Contents

161

1 Introduction

1

162

1.1

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

1

163

1.2

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

1

164

1.3

Differences Between the ML-DSA Standard and CRYSTALS-D ILITHIUM . . . .
1.3.1 Differences Between Version 3.1 and the Round 3 Version of CRYSTALSD ILITHIUM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.2 Differences Between the ML-DSA Standard and Version 3.1 of CRYSTALSD ILITHIUM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

165
166
167
168

169

2 Glossary of Terms, Acronyms, and Symbols

2
2
3

170

2.1

Terms and Defnitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

171

2.2

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

5

172

2.3

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

6

173

2.4

Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

174

2.5

NTT Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

175

3 Overview of the ML-DSA Signature Scheme

9

176

3.1

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

9

177

3.2

Computational Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

178

3.3

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

9

179

3.4

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

11

180

3.5

Additional Requirements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.5.1 Randomness Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.5.2 Public-Key Validity and Signature Length Checks . . . . . . . . . . . . . . . .
3.5.3 Intermediate Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11
11
11
11

181
182
183

184

4 Parameter Sets

13

185

5 Key Generation

14

186

6 Signing

15

187

7 Verifcation

18v

FIPS 204 (D RAFT )

188

189

7.1

M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

Prehash ML-DSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8 Auxiliary Functions

19
20

190

8.1

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

20

191

8.2

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

24

192

8.3

Hashing and Pseudorandom Sampling . . . . . . . . . . . . . . . . . . . . . . . . .

29

193

8.4

High Order / Low Order Bits and Hints . . . . . . . . . . . . . . . . . . . . . . . .

33

194

8.5

NTT and NTT−1

36. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

195

References

38

196

Appendix A — Security Strength Categories

41

197

Appendix B — Montgomery Reduction

44vi

FIPS 204 (D RAFT )List of Tables

198

199
200
201
202
203

Table 1
ML-DSA Parameter sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Table 2
Sizes (in bytes) of keys and signatures of ML-DSA. . . . . . . . . . . . . . . . .
Table 3NIST Security Strength Categories . . . . . . . . . . . . . . . . . . . . . . . . .
Table 4
Estimated gate counts for the optimal key recovery and collision attacks on AES
and SHA-3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240

13
14
42
43

List of Algorithms

204
205

M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

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

ML-DSA.KeyGen() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ML-DSA.Sign(sk, M) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ML-DSA.Verify(pk, M, σ ) . . . . . . . . . . . . . . . . . . . . . . . . . . .
IntegerToBits(x, α) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
BitsToInteger(y) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
BitsToBytes(y) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
BytesToBits(z) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
CoefFromThreeBytes(b0 , b1 , b2 ) . . . . . . . . . . . . . . . . . . . . . . . .
CoefFromHalfByte(b) . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
SimpleBitPack(w, b) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
BitPack(w, a, b) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
SimpleBitUnpack(v, b) . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
BitUnpack(v, a, b) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
HintBitPack(h) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
HintBitUnpack(y) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
pkEncode(ρ, t1 ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
pkDecode(pk) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
skEncode(ρ, K,tr, s1 , s2 , t0 ) . . . . . . . . . . . . . . . . . . . . . . . . . . .
skDecode(sk) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
sigEncode(c̃, z, h) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
sigDecode(σ ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
w1Encode(w1 ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
SampleInBall(ρ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
RejNTTPoly(ρ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
RejBoundedPoly(ρ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ExpandA(ρ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ExpandS(ρ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ExpandMask(ρ, µ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Power2Round(r) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Decompose(r) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
HighBits(r) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
LowBits(r) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
MakeHint(z, r) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
UseHint(h, r) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
NTT(w) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
NTT−1 (ŵ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

vii

15
17
19
20
20
21
21
21
22
22
22
23
23
24
24
25
25
26
27
28
28
28
30
30
31
31
32
32
34
34
34
35
35
35
36
37

FIPS 204 (D RAFT )241

Algorithm 37

M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

Montgomery_Reduce(a) . . . . . . . . . . . . . . . . . . . . . . . . . . . .

viii

44

FIPS 204 (D RAFT )

242

1.

Introduction

243

1.1

Purpose and Scope

244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261

M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

This standard defnes 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 theverifcation and validation of those digital signatures. (NIST SP 800-175B [2], Guideline for Using
Cryptographic Standards in the Federal Government: Cryptographic Mechanisms, includes a general
discussion of digital signatures.)This standard specifes the mathematical steps that need to be performed for key generation, signature
generation, and signature verifcation. In order for digital signatures to be valid, additional assurances are
required, such as assurance of identity and of private key possession. NIST SP 800-89, Recommendation
for Obtaining Assurances for Digital Signature Applications [3], specifes the required assurances andmethods for obtaining these assurances.
The digital signature scheme approved in this standard is ML-DSA (Module Lattice Digital Signature
Algorithm). It is based on the Module Learning With Errors problem. ML-DSA is believed to be secure
even against adversaries in possession of a large-scale quantum computer. In particular, ML-DSA is
believed to be strongly-unforgeable, which implies that the scheme can be used to detect unauthorized
modifcations to data, and to authenticate the identity of the signatory (one bound to the possession of theprivate-key). In addition, a signature generated by this scheme can be used as evidence in demonstrating
to a third party that the signature was, in fact, generated by the claimed signatory. The latter property is
known as non-repudiation, since the signatory cannot easily repudiate the signature at a later time.

267

This standard gives algorithms for ML-DSA key generation (Section 5), signature (Section 6), andverifcation, (Section 7) and for supporting algorithms used by them (Section 8). ML-DSA is standardized
with three possible parameter sets, each corresponding 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 specifed in
NIST FIPS and Special Publications (e.g., FIPS 186-5 Digital Signature Standard (DSS) [1]).

268

1.2

262
263
264
265
266

269
270
271
272
273
274
275
276
277
278
279
280

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. In particular, this would include key-establishment schemes and digital signatures thatare based on integer factorization and discrete logarithms (both over fnite felds and elliptic curves). As aresult, in 2016, the National Institute of Standards and Technology (NIST) initiated a public process toselect quantum-resistant public-key cryptographic algorithms for standardization. A total of 82 candidate
algorithms were submitted to NIST for consideration for standardization.
After three rounds of evaluation and analysis, NIST selected the frst four algorithms to standardize as aresult of the Post-Quantum Cryptography (PQC) Standardization process. The algorithm in this standard,
ML-DSA, is derived from one of the selected schemes: CRYSTALS-D ILITHIUM [4, 5] and is intended toprotect sensitive U.S. Government information well into the foreseeable future, including after the adventof large-scale fault-tolerant quantum computers.

1

FIPS 204 (D RAFT )M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

1.3 Differences Between the ML-DSA Standard and CRYSTALS282
D ILITHIUM
281

283
284
285
286

287
288

289
290
291
292
293
294

295
296

297
298
299
300
301
302
303
304
305

ML-DSA is derived from Version 3.1 of CRYSTALS-D ILITHIUM [5]. Version 3.1 differs slightly
from the most recent version appearing on the NIST website (Version 3 CRYSTALS-D ILITHIUM [4].)Sections 1.3.1, and 1.3.2 document, respectively, the differences between Versions 3 and 3.1, and thedifferences between Version 3.1 and the ML-DSA standard as published in this document.

1.3.1 Differences Between Version 3.1 and the Round 3 Version of CRYSTALSD ILITHIUM
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 faw thatappeared 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.
Additionally, the length of the variable tr (the hash of the public key) was reduced from 384 to 256 bits. In
key generation, the variable ς was relabeled as ρ ′ and increased in size from 256 bits to 512 bits.

1.3.2 Differences Between the ML-DSA Standard and Version 3.1 of CRYSTALSD ILITHIUM
In order to ensure the properties noted in [6], ML-DSA increases the length of tr to 512 bits, and increases
the length of c̃ to 384 and 512 bits, respectively, for the parameter sets ML-DSA-65 and ML-DSA-87.
In Version 3.1 of the CRYSTALS-D ILITHIUM submission, the default version of the signing algorithm
is deterministic 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, where ρ ′ is pseudorandomly derived from the signer’s
private key, the message, and a 256-bit string, rnd, which by default should be generated by an Approved
RBG. The ML-DSAstandard also allows for an optional deterministic version, where rnd is instead a
256-bit constant string.

2

FIPS 204 (D RAFT )M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

306

2.

Glossary of Terms, Acronyms, and Symbols

307

2.1

Terms and Defnitions

approved

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

313

assurance ofpossession

Confdence that an entity possesses a private key and any associated keying
material.

314

bit string

An ordered sequence of zeros and ones.

315

byte

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

316

byte string

A sequence of bytes.

317

certifcate

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

323

certifcation authority(CA)The entity in a public key infrastructure (PKI) that is responsible for issuingcertifcates and exacting compliance with a PKI policy.

324

claimed signatory

From the verifer’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 for verifying origin authenticity and data
integrity, and enforcing signatory non-repudiation.

entityAn individual (person), organization, device, or process. Used interchangeably
with “party.”

extendable-output
function (XOF)

A function on bit strings in which the output can be extended to any desired
length. Approved XOFs (such as those specifed in FIPS 202 [7]) are designed
to satisfy the following properties as long as the specifed output length issuffciently long to prevent trivial attacks:

308
309
310
311

312

318
319
320
321

322

325

326
327

328
329
330

331
332

333
334
335
336

1. (One-way) It is computationally infeasible to fnd any input that maps toany new pre-specifed output.

337
338

2. (Collision-resistant) It is computationally infeasible to fnd any two
distinct inputs that map to the same output.

339
340

341
342
343

hash function

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

3FIPS 204 (D RAFT )M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

1. (One-way) It is computationally infeasible to fnd any input that maps toany new pre-specifed output.

344
345

2. (Collision-resistant) It is computationally infeasible to fnd any two
distinct inputs that map to the same output.

346
347

348

hash value

See “message digest.”

349

key

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

350
351
352

1. The computation of a digital signature from data and353

2. The verifcation of a digital signature.

354

key pair

A public key and its corresponding private key.

355

message

The data that is signed. Also known as “signed data” during the signature
verifcation 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 data insuch a way that the integrity and origin can be verifed and validated by a third
party as having originated from a specifc entity in possession of the privatekey (i.e., the signatory).

363

owner

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

364

party

An individual (person), organization, device, or process. Used interchangeably
with “entity.”

367

public key
infrastructure (PKI)

A framework that is established to issue, maintain, and revoke public key
certifcates.

368

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 verifed 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 specifed by NIST (see Appendix A, Table 3).

356

357
358

359
360
361
362

365

366

369
370
371

372
373
374
375
376

377
378
379
380
381

382
383

4

FIPS 204 (D RAFT )M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

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.

386

seed

A bit string used as input to a pseudorandom process.

387

shall

Used to indicate a requirement of this standard.

388

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

390

signatory

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

391

signature generation

The process of using a digital signature algorithm and a private key to generatea digital signature on data.

signature validation

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

signature verifcation

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. Alsosee “message.”401

trusted third party(TTP)

An entity (other than the key pair owner and the verifer) that is trusted by theowner, the verifer, or both. Sometimes shortened to “trusted party.”402

verifer

The entity that verifes the authenticity of a digital signature, using the public
key of the signatory.

384
385

389

392

393
394
395

396
397

398
399

400

403

404

2.2

Acronyms

405

AES

Advanced Encryption Standard

406

FIPS

Federal Information Processing Standard

407

ML-DSA

Module-Lattice-Based Digital Signature Algorithm

408

MLWE

Module Learning With Errors

409

NIST

National Institute of Standards and Technology

410

NISTIRNIST Interagency or Internal Report

411

NTT

Number Theoretic Transform

412

PQC

Post-Quantum Cryptography

413

RBG

Random Bit Generator

414

SHA

Secure Hash Algorithm

415

SHAKE

Secure Hash Algorithm K ECCAK

416

SP

Special Publication

417

XOF

eXtendable-Output Function

5

FIPS 204 (D RAFT )M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

418

2.3

Mathematical Symbols

419

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

420

B

The set {0, 1, . . . , 255}.

421

N

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

422

Z

The ring of integers.

423[a, b]For two integers a ≤ b, [a, b] denotes the set of integers {a, a + 1, . . . , b}.

424

Zm

The ring of integers modulo m, also denoted by Z/mZ.

425

R

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

Rm

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

429

q

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

430

Bτ

i
The set of all polynomials p = ∑255
i=0 pi X in Rq that are such that exactly τ of thecoeffcients of pi are from the set {−1, 1}, and all other coeffcients are zero. (Seesubsection 8.3.)

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

435

Tq

The ring Π255
j=0 Zq .

436⊤

If A is a matrix, then A⊤ denotes the transpose of A.

437

log

The base-2 logarithm. For example, log 256 = 8.

438

bitlen a

For a positive integer a, the minimum number of binary digits required to represent
a. For example, bitlen 32 = 6 and bitlen 31 = 5.

440

⌊x⌋

The largest integer less than or equal to the real number x, called the foor of x.

441

⌈x⌉

The least integer greater than or equal to the real number x, called the ceiling of x.

442

mod

If α is a positive integer and m ∈ Z or m ∈ Zα , then m mod α denotes the uniqueelement m′ ∈ Z in the range 0 ≤ m′ < α such that m and m′ are congruent modulo α.

mod±If α is a positive integer and m ∈ Z or m ∈ Zα , then m mod± α denotes the uniqueelement m′ ∈ Z in the range −α/2 < m′ ≤ α/2 such that m and m′ are congruent
modulo α.

a!
�a

The factorial quantity 1 · 2 · 3 · . . . · a.

426

427
428

431
432

433
434

439

443

444
445
446

447

448

449
450

b

brv(r)The quantity a!/(b!(a − b)!).
Bit reversal. If r = r0 + 2r1 + 4r2 + . . . + 128r7 is a byte, with ri ∈ {0, 1}, thenbrv(r) = r7 + 2r6 + 4r5 + . . . + 128r0 .

6

FIPS 204 (D RAFT )451←

If S is a set, then s ← S denotes that s is sampled uniformly at random from S. If
D is a probability distribution on S, then s ← D denotes that s is sampled from S
according to D. If R is an algorithm with input z, then s ← R(z) denotes that s is
the recorded output of a single execution of R(z). This notation is used for bothprobabilistic and deterministic algorithms.

x∈S←yType casting. An element x in a set S is constructed from an element y of a different
set T . The set T , and the mapping from T to S, are not explicitly specifed, but theyshould be obvious from the context in which this statement appears.

wJiK

For a bit string w, wJiK denotes the ith byte of w,

452
453
454
455

456
457
458

459

M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

w[8i] + 2 · w[8i + 1] + 4 · w[8i + 2] + · · · + 128 · w[8i + 7]
where w[ j] is the jth bit of w. That is, when encoding a byte into a bit string,“little-endian” order is used.

460
461

∥·∥∞

The infnity norm. For an element w ∈ Z, ∥w∥∞ = |w|, the absolute value of w.
For an element w ∈ Zq ,∥w∥∞ = w mod± q . For an element w of R or Rq , ∥w∥∞ =max0≤i<256 ∥wi ∥∞ . For a length-m vector w with entries from R or Rq , ∥w∥∞ =max0≤i<m ∥w[i]∥∞ .

[[a < b]]

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

⟨⟨ f (x)⟩⟩A temporary variable that stores the output of a computation f (x), so that this output
can be used many times, without needing to recompute it. This is equivalent todefning a temporary variable y ← f (x). Naming the variable ⟨⟨ f (x)⟩⟩ makes thepseudocode less cluttered.

473

a||b

Concatenation of two bit or byte strings, a and b.

474

a◦b

Multiplication (of a and b) in the ring Tq .

475

a · b or ab

Multiplication in any of the rings Z, Zd , R, Rd .

476

a+b

Addition of a and b.

477

a/b

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

479

A×B

Cartesian product of two sets A, B.

480⊥

Blank symbol. (This symbol indicates failure or lack of an output from an algorithm.)

481

2.4

462
463
464
465

466
467
468

469
470
471
472

478

482
483
484
485
486

Notation

Elements of the rings Z, Zq , Z2 , R, Rq , are denoted by italicized lowercase letters (e.g., w). Elements of thering Tq are length-256 arrays of elements of Zq , and they are denoted by italicized letters with a hat symbol(e.g., ŵ). Addition and multiplication of elements of Tq are performed entry-wise. (Thus, the ith entry of
the product of two elements û and v̂ of Tq is û[i] · v̂[i] ∈ Zq .) As noted in subsection 2.3, the multiplication
operation in Tq is denoted by the symbol ◦.

7

FIPS 204 (D RAFT )

487
488
489
490
491
492
493
494

M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

When a product a · b or a sum a + b is written and either a or b is a congruence class modulo m (i.e., ifeither is an element of Zm or Rm ), then the product is also understood to be a congruence class modulo m.
Likewise when an element of R or Z may be used as the input of a function specifed to act on an elementof Rm or Zm , respectively. In both cases, the element itself or its coeffcients are mapped from Z to Zm bytaking the unique congruence class containing the integer.
The coeffcients of an element w of R or Rm are denoted by wi so that w = w0 + w1 X + . . . + w255 X 255 .
If w is in R (respectively, Rm ) and t is in Z (respectively, Zd ), then w(t) denotes the polynomial w =w0 + w1 X + . . . + w255 X 255 evaluated at X = t.

496

Vectors with elements in R or Rm are denoted by bold lowercase letters, such as, v. Matrices with elements
in R or Rm are denoted by bold uppercase letters, such as, A.

497

If S is a ring and v is a length-L vector over S, then the entries in the vector v are expressed as495v[0], v[1], . . . , v[L − 1].

500

The entries of a K × L matrix A over S are denoted as A[i, j], where 0 ≤ i < K and 0 ≤ j < L. The set of
all length-L vectors over S is denoted by SL . The set of all K × L matrices over S is denoted by SK×L . A
length-L vector can also be treated as an L × 1 matrix.

501

2.5

498
499

502
503

NTT Representation

The Number Theoretic Transform (NTT) is a specifc isomorphism between the rings Rq and Tq . Let
ζ = 1753 ∈ Zq , which is a 512th root of unity. If w ∈ Rq , thenNTT(w) = (w(ζ0 ), w(−ζ0 ), . . . w(ζ127 ), w(−ζ127 )) ∈ Tq ,

504
505
506

507
508
509

(2.1)

where ζi = ζ brv(128+i) . See section 8.5 for a discussion of the implementation of NTT and NTT−1 .
The motivation for using NTT is that multiplication is considerably faster in the ring Tq . Since NTT is an
isomorphism, for any a, b ∈ Rq ,NTT(ab) = NTT(a) ◦ NTT(b).
(2.2)
If A is a matrix with entries from Rq , then NTT(A) denotes the matrix computed via the entry-wise
application of NTT to A. The symbol ◦ is also used to denote matrix multiplication of matrices with entries
in Tq . Thus, NTT(AB) = NTT(A) ◦ NTT(B).

8FIPS 204 (D RAFT )

510

3.

M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

Overview of the ML-DSA Signature Scheme

514

ML-DSA is a digital signature scheme based on CRYSTALS-D ILITHIUM [5]. It consists of threemain 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 [9, 10] and bears
the most resemblance to the schemes proposed in [11, 12].

515

3.1

511
512
513

516
517
518
519

Security Properties

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

521

ML-DSA is also designed to satisfy additional security properties beyond unforgeability, which aredescribed in [6].

522

3.2

520

523
524
525
526
527
528

Computational Assumptions

Security for lattice-based digital signature schemes is typically related to two central problems: theLearning With Errors (LWE) problem and the Short Integer Solution (SIS) problem. The LWE problem[13] is to recover a vector s ∈ Znq given a set of random noisy linear equations satisfed by s. The SIS
problem is to fnd, for a given linear system over Zq of the form At = 0, a solution t ∈ Znq such that ∥t∥∞ issmall. For appropriate choices of parameters, these problems are intractable for the best known techniques(including Gaussian elimination).

532

When the module Znq in LWE and SIS is replaced by a module over a ring larger than Zq (such as Rq ),the resulting problems are called MLWE (Module Learning With Errors [14]) and MSIS (Module Short
Integer Solution). The security of ML-DSA is based on the MLWE problem over Rq and a nonstandard
variant of MSIS called SelfTargetMSIS [15].

533

3.3

529
530
531

534
535
536
537

The ML-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 verifer who knows g (the generator of a group inwhich discrete logs are believed to be diffcult) and the value y = gx , and a prover who knows g and x. Theinteractive protocol, where the prover demonstrates knowledge of x to the verifer, consists of three steps:539

1. Commitment: The prover generates a random positive integer r less than the order of g and commits
to its value by sending gr to the verifer

540

2. Challenge: The verifer sends a random positive integer c less than the order of g to the prover.

541

3. Response: The prover returns s = r − cx, and the verifer checks whether gs · yc = gr .

538

542
543
544
545

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

9

FIPS 204 (D RAFT )

546
547
548
549

M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

The basic idea of ML-DSA and similar lattice signature schemes is to build a signature scheme from an
K ×nanalogous interactive protocol, where a prover who knows matrices A ∈ ZK×L, S1 ∈ ZL×nqq , and S2 ∈ Zq
with short coeffcients, demonstrates knowledge of these matrices to a verifer who knows A and T ∈= AS1 + S2 . Such an interactive protocol would proceed as follows:
ZK×n
q

551

1. Commitment: The prover generates y ∈ ZLq with short coeffcients and commits to its value by
sending Ay to the verifer.

552

2. Challenge: The verifer sends a vector c ∈ Znq with short coeffcients to the prover.

550

553
554

555
556
557
558
559
560
561
562
563

564
565
566
567
568

569
570

571
572

573
574
575

576
577
578
579
580

581
582
583

3. Response: The prover returns z = y + S1 c, and the verifer checks that z has small coeffcients andthat Az − Tc ≈ Ay.
As written the above protocol has a security faw: The response z will be biased in a direction related tothe private value S1 . However, this faw 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. However, to correct the bias, thesigner applies rejection sampling to z: if coeffcients of z fall outside a specifed range, the signing process
is aborted, and the signer starts over from a new value of y. In the resulting “Fiat-Shamir with Aborts”
signature, the public key is (A, T) and the private key is (S1 , S2 )In the ML-DSA standard, a number of tweaks and modifcations are added to this basic framework forsecurity or effciency reasons:• To reduce key and signature size and to use fast NTT-based polynomial multiplication, ML-DSA
uses module-structured matrices. That is to say, relative to the basic scheme described above, it
replaces dimension-n × n blocks of matrices and dimension-n blocks of vectors with polynomials in, T ∈ ZqK×n , S1 ∈ ZqL×n , S2 ∈ ZqK×n , y ∈ ZLq , c ∈ Zqn , ML-DSA
the ring Rq . Thus, instead of A ∈ ZK×L
q
k
k
ℓ
ℓ
has A ∈ Rk×ℓ
q , t ∈ Rq , s1 ∈ Rq , s2 ∈ Rq , y ∈ Rq , c ∈ Rq .
• To further reduce the size of the public key, the matrix A is pseudorandomly derived from a 256-bit
public seed, ρ which is included in the ML-DSA public key in place of A.
• For a still further reduction in public key size, the ML-DSA public key substitutes for t a compressedvalue t0 , which drops the d low order bits of each coeffcient.
• To obtain beyond unforgeability (BUFF) properties noted in [6], ML-DSA does not sign the message
M directly, but rather signs a message representative µ obtained by hashing the concatenation of ahash tr of the public key and M.
• To reduce signature size, rather than including the commitment w = Ay in the signature, the MLDSA signature uses a rounded version w1 as a commitment, and includes only the hash, c̃, of w1
concatenated with µ.
To ensure that w1 can be reconstructed by the verifer from z and the compressed value t0 , thesignature must also include a hint h ∈ Rk2 computed by the signer using the signer’s private key.
In this document, we use the abbreviations ML-DSA-44, ML-DSA-65, and ML-DSA-87 to refer to
ML-DSA with the parameter choices given in Table 1. (In these abbreviations, the numerical suffx refers
to the dimension of the matrix A. For example, in ML-DSA-65, the matrix A is a 6 × 5 matrix over Rq .)10

FIPS 204 (D RAFT )

584

585
586
587

3.4

M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

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 verifcation algorithms in thisdocument. Guidance for key management is provided in the NIST SP 800-57 series [16, 17, 18].

592

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 certifcates involves assurances ofidentity and proof of possession. When a public-key certifcate is not available, users of digital signatures
should determine whether a public key needs to be bound to an identity. Methods for obtaining assurancesof identity and proof of possession are provided in [3].

593

3.5

588
589
590
591

Additional Requirements

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

596

3.5.1 Randomness Generation

594

597
598
599
600
601
602
603

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

608

Additionally, in the default “hedged” variant of Algorithm 2, implementing signing for ML-DSA, thevalue rnd is generated using an RBG. While this value should ideally be generated by an approved RBG,
other methods for generating fresh randomness may be used. The primary purpose of rnd is to facilitate
countermeasures to side-channel attacks and fault attacks on deterministic signatures, such as [22, 23, 24].1
For this purpose, even a weak RBG may be preferable to the fully deterministic variant of Algorithm 2.

609

3.5.2 Public-Key Validity and Signature Length Checks

604
605
606
607

615

Algorithm 3, implementing verifcation for ML-DSA, specifes the length of the signature σ and the public
key pk in terms of the parameters described in Table 1. If an implementation of ML-DSA can accept
inputs for σ or pk of any other length, it shall return false whenever the lengths of either of these inputs
differs from its specifed length. Checking the length of pk serves as a partial public-key validity check,and failing to do so may interfere with the security properties that ML-DSA is designed to have, like strong
unforgeability. ML-DSA is not designed to require any additional public-key validity checks.

616

3.5.3 Intermediate Values

610
611
612
613
614

617
618
619

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. For
some applications, including the verifcation of signatures that are used as bearer tokens (i.e., authentication
1 In addition, when signing is deterministic, there is leakage through timing side-channels of information about themessage (but not the private key). In cases where the signer does not want to reveal the message being signed,
hedged signatures should be used; see section 3.2 in [5].

11FIPS 204 (D RAFT )

620
621
622
623
624
625
626
627
628
629
630

M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

secrets) or the verifcation of signatures on plaintext messages that are intended to be confdential, data
used internally by verifcation algorithms is similarly sensitive. (Intermediate values of the verifcation
algorithm may reveal information about its inputs, i.e., the message, signature, and public key, and in some
applications security or privacy requires one or more of these inputs to be confdential.) Implementationsof ML-DSA shall, therefore, ensure that any potentially sensitive intermediate data is destroyed as soon as
it is no longer needed.
In certain situations, such as deterministic signing (described above), and the verifcation of confdential
messages and signatures (described above), additional care must be taken to protect implementations
against side-channel attacks or fault attacks. A cryptographic device may leak critical information throughside-channels that allows internal data or keying material to be extracted without breaking the cryptographic
primitives.

12

FIPS 204 (D RAFT )

631

4.

M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

Parameter Sets
Table 1. ML-DSA Parameter sets
Parameters(see sections 5 and 6 of this document)
q - modulus [see §5]
d - # of dropped bits from t [see §5]
τ - # of ±1’s in polynomial c [see §6]
λ - collision strength of c̃ [see §6]γ1 - coeffcient range of y [see §6]γ2 - low-order rounding range [see §6](k, ℓ) - dimensions of A [see §5]η - private key range [see §5]β = τ · η [see §6]ω - max # of 1’s in the hint h [see §6]� 
Challenge entropy log 256
τ + τ [see §6]
Repetitions (see explanation below)
Claimed security strength

632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655

Values assigned by each parameter set
ML-DSA-44 ML-DSA-65 ML-DSA-87
838041783804178380417
13
13
13
39
49
60
128
192
256
217
219
219
(q − 1)/88(q − 1)/32(q − 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 verifcation. 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 [4]. The names of the parameter sets are of the form “ML-DSA-kℓ,” where (k, ℓ)
are the dimensions of the matrix A.
These parameter sets were designed to meet certain security strength categories defned by NIST in its
original Call for Proposals [25]. These security strength categories are explained further in Appendix A.
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 [26].
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 [5]. For additional discussionof the security strength of MLWE-based cryptosystems, see [27].
The sizes of keys and signatures corresponding to each parameter set are given in Table 2. Note that certain
optimizations are possible, when storing ML-DSA public and private keys. If additional space is available,
one can pre-compute and store Â, to speed up signing and verifying. Alternatively, if one wants to reduce
the space needed for the private key, one can only store the 32-byte seed ξ , which is suffcient to generate
the other parts of the private key. For additional details, see Section 3.1 in [5].

13FIPS 204 (D RAFT )ML-DSA-44
ML-DSA-65
ML-DSA-87

M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

Private Key Public Key
2528
1312
4000
1952
4864
2592

Signature Size
2420
3293
4595

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

656

657
658
659
660

661
662

5.

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 begins by using an approved RBG to generate a 256-bit random seed ξ , which is expanded
as needed using an XOF (namely, SHAKE-256) to produce other random values. In particular:• A public random seed ρ. Using this seed, a polynomial matrix, A ∈ Rqk×ℓ is pseudorandomly
sampled2 from Rk×ℓ
q .

665

• A private random seed ρ ′ . Using this seed, the polynomial vectors s1 ∈ Rℓq and s2 ∈ Rkq are
pseudorandomly sampled from the subset of polynomial vectors whose coeffcients are short, (i.e.
in the range [−η, η]).

666

• A private random seed K for use during signing.

667

The core cryptographic operation computes the public value,

663
664

t = As1 + s2 .
668
669
670
671
672
673
674
675
676
677
678

The vector t together with the matrix A may be thought of as an expanded form of the public key. The
vector t is compressed in the actual public key by dropping the d least signifcant bits from each coeffcient,thus producing the polynomial vector t1 . This compression is an optimization for performance, not security.
The low order bits of t can be reconstructed from a small number of signatures and, therefore, need not be
regarded as secret.
The ML-DSA public key pk is a byte encoding of the public random seed ρ and the compressed polynomial
vector t1 .
The ML-DSA private key sk is a byte encoding of the public random seed ρ; a 256-bit private random seed
K for use during signing; a 512-bit hash of the public key, tr, for use during signing; the secret polynomial
vectors s1 and s2 ; and a polynomial vector t0 encoding the d least signifcant bits of each coeffcient of theuncompressed public-key polynomial t.

2 More precisely, since only the NTT form of A, Â ∈ T k×ℓ = NTT(A) is needed in subsequent calculations, the codeqactually computes Â as a pseudorandom sample over Tqk×ℓ , and the sampling of A = NTT−1 (Â) is only implicit (itcould be computed but is not).

14

FIPS 204 (D RAFT )M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

Algorithm 1 ML-DSA.KeyGen()
Generates a public-private key pair.
Output: Public key, pk ∈ B32+32k(bitlen (q−1)−d) ,and private key, sk ∈ B32+32+64+32·((ℓ+k)·bitlen (2η)+dk) .
1: ξ ← {0, 1}256▷ Choose random seed
′
256
512
256
2: (ρ, ρ , K ) ∈ {0, 1}
× {0, 1} × {0, 1} ← H(ξ , 1024)▷ Expand seed
3: Â ← ExpandA(ρ)▷ A is generated and stored in NTT representation as Â
4: (s1 , s2 ) ← ExpandS(ρ ′ )5: t ← NTT−1 (Â ◦ NTT(s1 )) + s2
▷ Compute t = As1 + s2
6: (t1 , t0 ) ← Power2Round(t, d)▷ Compress t
7: pk ← pkEncode(ρ, t1 )8: tr ← H(BytesToBits(pk), 512)
9: sk ← skEncode(ρ, K,tr, s1 , s2 , t0 )▷ K and tr are for use in signing
10: return (pk, sk)

679

680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705

6.

Signing

ML-DSA.Sign (Algorithm 2) takes as input a private key sk, encoded as a byte string, and a message,M, encoded as a bit string, and it outputs a signature encoded as a byte string. There are two versionsof the algorithm: “hedged” and “deterministic.” The default “hedged” version of ML-DSA.Sign uses
fresh randomness. In addition, for platforms where a random number generator is unavailable, an optional
deterministic variant is specifed. However, the lack of randomness in the deterministic variant makes
the risk of side-channel attacks more diffcult to mitigate. Therefore, this variant should not be used on
platforms where side-channel attacks are a concern and where they cannot be otherwise mitigated. (Seethe discussion in Section 3 for more details.)
Note that implementing the hedged variant only (without the deterministic variant) is suffcient to guarantee
interoperability. The same verifcation algorithm will work to verify signatures produced by either
variant, so implementing the deterministic variant in addition to the hedged variant does not enhanceinteroperability.
In both variants, the signer frst extracts the following from the private key: the public random seed ρ;
the 256-bit private random seed K; the 512-bit hash of the public key, tr; the secret polynomial vectors
s1 and s2 ; and the polynomial vector t0 encoding the d least signifcant bits of each coeffcient of theuncompressed public key polynomial t. ρ is then expanded to the same matrix A as in key generation.
Before the message, M, is signed, it is concatenated with the public-key hash tr and hashed down to a
512-bit message representative, µ, using the hash function H (see section 8.3).
The signer produces an additional 512-bit seed ρ ′ , for private randomness during each signing operation.
ρ ′ is computed as ρ ′ ← H(K||rnd||µ, 512). In the default “hedged” variant, rnd is the output of an RBG,
while in the deterministic variant rnd is a 256-bit string consisting entirely of zeroes. 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, where 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. The rejection sampling loop follows the Fiat-Shamir with aborts paradigm [9] and15

FIPS 204 (D RAFT )M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

708(aside from the rejection step) is similar in structure to Schnorr signatures [28] (e.g., EdDSA [29]). The
signer frst produces a “commitment” w1 . Then the signer pseudorandomly derives a “challenge” c from
w1 and the message representative µ. Finally, the signer computes a response z.

709

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

706
707

710
711
712

713
714

715
716
717
718

719
720

721
722
723
724

725
726
727
728
729

• Using the ExpandMask function (Algorithm 28), the seed ρ ′ and a counter κ, a polynomial vectory ∈ Rℓq is pseudorandomly sampled from the subset of polynomial vectors whose coeffcients aremoderately short (i.e. in the range [−γ1 + 1, γ1 ]).
• From y, the signer computes the commitment w1 by computing w = Ay and then rounding to a
nearby multiple of 2γ2 , using HighBits (Algorithm 31).
• w1 and µ are concatenated and hashed to produce the commitment hash c̃. This uses the function
w1Encode (Algorithm 22). Let c̃1 denote the frst 256 bits of c̃. The bit string c̃1 is used topseudorandomly sample a polynomial c ∈ Rq that has coeffcients in {−1, 0, 1} and Hamming
weight τ. The sampling is done with the function SampleInBall (Algorithm 23). 3• The signer computes the response z = y + cs1 and performs various validity checks. If any of thechecks fail, the signer will continue the rejection sampling loop.
• If the checks pass, the signer can compute a hint polynomial, h, which will allow the verifer toreconstruct w1 using the compressed public key (along with the other components of the signature).
This uses the function MakeHint (Algorithm 33). The signer will then output the fnal signature,
which is a byte encoding of the commitment hash c̃, the response z, and the hint h.
In addition, there is an alternative way of implementing the validity checks on z, and the computation of h,which is described in section 5.1 of [5]. This method may also be used in implementations of ML-DSA.
In Algorithm 2, 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., ⟨⟨cs1 ⟩⟩).

3 The length of c̃

1 is determined by the targeted security strength against signature forgery attacks, and the required
length is only 256 bits for 256 bits of classical security. The length of c̃ is determined by the desired security withrespect to the “message-bound signatures” property described in [6]. Here, a length of 2λ bits is required for λ bitsof classical security.

16

FIPS 204 (D RAFT )M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

Algorithm 2 ML-DSA.Sign(sk, M)
Generates a signature for a message M.
Input: Private key, sk ∈ B32+32+64+32·((ℓ+k)·bitlen (2η)+dk) and the message M ∈ {0, 1}∗ .
Output: Signature, σ ∈ B32+ℓ·32·(1+bitlen (γ1 −1))+ω +k .
1: (ρ, K,tr, s1 , s2 , t0 ) ← skDecode(sk)
2: ŝ1 ← NTT(s1 )3: ŝ2 ← NTT(s2 )4: t̂0 ← NTT(t0 )5: Â ← ExpandA(ρ)▷ A is generated and stored in NTT representation as Â
6: µ ← H(tr||M, 512)
▷ Compute message representative µ
7: rnd ← {0, 1}256▷ For the optional deterministic variant, substitute rnd ← {0}256
8: ρ ′ ← H(K||rnd||µ, 512)
▷ Compute private random seed
9: κ ← 0▷ Initialize counter κ
10: (z, h) ← ⊥11: while (z, h) = ⊥ do
▷ Rejection sampling loop′
12:y ← ExpandMask(ρ , κ)13:w ← NTT−1 (Â ◦ NTT(y))
14:
w1 ← HighBits(w)▷ Signer’s commitment15:c̃ ∈ {0, 1}2λ ← H(µ||w1Encode(w1 ), 2λ )▷ Commitment hash
256
2λ
−
256
16:
(c̃1 , c̃2 ) ∈ {0, 1} × {0, 1}← c̃▷ First 256 bits of commitment hash17:c ← SampleInBall(c̃1 )▷ Verifer’s challenge18:ĉ ← NTT(c)19:⟨⟨cs1 ⟩⟩ ← NTT−1 (ĉ ◦ ŝ1 )20:⟨⟨cs2 ⟩⟩ ← NTT−1 (ĉ ◦ ŝ2 )21:z ← y + ⟨⟨cs1 ⟩⟩▷ Signer’s response22:
r0 ← LowBits(w − ⟨⟨cs2 ⟩⟩)23:
if ||z||∞ ≥ γ1 − β or ||r0 ||∞ ≥ γ2 − β then (z, h) ← ⊥▷ Validity checks
24:
else
25:
⟨⟨ct0 ⟩⟩ ← NTT−1 (ĉ ◦ t̂0 )26:h ← MakeHint(−⟨⟨ct0 ⟩⟩, w − ⟨⟨cs2 ⟩⟩ + ⟨⟨ct0 ⟩⟩)▷ Signer’s hint27:
if ||⟨⟨ct0 ⟩⟩||∞ ≥ γ2 or the number of 1’s in h is greater than ω, then (z, h) ← ⊥28:
end if29:
end if30:
κ ← κ +ℓ
▷ Increment counter
31: end while
32: σ ← sigEncode(c̃, z mod± q, h)
33: return σ

17FIPS 204 (D RAFT )

730

731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748

7.

M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

Verifcation

The algorithm ML-DSA.Verify (Algorithm 3) takes as input a public key pk encoded as a byte string, amessage M encoded as a bit string, and a signature σ encoded as a byte string. ML-DSA.Verify requires
no randomness. It produces as output 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). Algorithm 3 specifes thelength of the signature σ and the public key pk in terms of the parameters described in section 1. If an
implementation of ML-DSA.Verify can accept inputs for σ or pk of any other length, it shall return false
whenever the length of either of these inputs differs from its specifed length.
The verifer frst extracts the public random seed ρ and the compressed polynomial vector t1 from thepublic key pk; and extracts the signer’s commitment hash c̃, response z, and hint h from the signature σ .
The verifer may fnd that the hint was not properly byte encoded, denoted by the symbol “⊥,” in whichcase the verifcation algorithm will immediately return false, indicating that the signature is invalid.
Assuming that the signature is successfully extracted from its byte encoding, the verifer pseudorandomly
derives A from ρ, as is done in key generation and signing, and creates a message representative µ, byhashing the concatenation of tr (the hash of the public key pk) and the message M.
The verifer then attempts to reconstruct the signer’s commitment (the polynomial vector w1 ) fromthe public key pk and the signature σ . In ML-DSA.Sign, w1 is computed by rounding w = Ay. In
ML-DSA.Verify, the reconstructed value of w1 is called w1′ , since it may have been computed in a different
way, in the case where the signature is invalid. This w′1 is computed through the following process:749• Derive the challenge polynomial c from the signer’s commitment hash c̃, as done in ML-DSA.Sign.

750• Use the signer’s response z to computew′Approx = Az − ct1 · 2d .

751

Note that assuming the signature was computed correctly, as in ML-DSA.Sign, it follows thatw = Ay = Az − ct + cs2 ≈ w′Approx = Az − ct1 · 2d ,

752

753

754
755
756
757
758
759

because c and s2 have small coeffcients, and t1 · 2d ≈ t .
• Use the signer’s hint h to obtain w′1 from w′Approx .
Finally, the verifer checks that the signer’s response z and the signer’s hint h are valid, and that thereconstructed w′1 is consistent with the signer’s commitment hash c̃. More precisely, the verifer checks
that all of the coeffcients of z are suffciently small (i.e., in the range [−(γ1 − β ), γ1 − β ]); that h contains
no more than ω nonzero coeffcients; and that c̃ matches the hash c̃′ of the message representative µconcatenated with w′1 (represented as a bit string). If all of these checks succeed, then ML-DSA.Verify
returns true. Otherwise it returns false.

18

FIPS 204 (D RAFT )M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

Algorithm 3 ML-DSA.Verify(pk, M, σ )Verifes a signature σ for a message M.
Input: Public key, pk ∈ B32+32k(bitlen (q−1)−d) and message M ∈ {0, 1}∗ .
Input: Signature, σ ∈ B32+ℓ·32·(1+bitlen (γ1 −1))+ω +k .
Output: Boolean
1: (ρ, t1 ) ← pkDecode(pk)
2: (c̃, z, h) ← sigDecode(σ )▷ Signer’s commitment hash c̃, response z and hint h
3: if h = ⊥ then return false▷ Hint was not properly encoded
4: end if
5: Â ← ExpandA(ρ)▷ A is generated and stored in NTT representation as Â
6: tr ← H(BytesToBits(pk), 512)
7: µ ← H(tr||M, 512)
▷ Compute message representative µ
8: (c̃1 , c̃2 ) ∈ {0, 1}256 × {0, 1}2λ −256 ← c̃
9: c ← SampleInBall(c̃1 )▷ Compute verifer’s challenge from c̃′ˆ ◦ NTT(z) − NTT(c) ◦ NTT(t1 · 2d ))10: wApprox← NTT−1 (A▷ w′Approx = Az − ct1 · 2d
11: w′1 ← UseHint(h, w′Approx )▷ Reconstruction of signer’s commitment′′
12: c̃ ← H(µ||w1Encode(w1 ), 2λ )▷ Hash it; this should match c̃
13: return [[ ||z||∞ < γ1 − β ]] and [[c̃ = c̃′ ]] and [[number of 1’s in h is ≤ ω]]

760

761
762
763
764
765
766
767
768
769
770

7.1

Prehash ML-DSA

For some cryptographic modules that generate ML-DSA signatures, hashing the message in ML-DSA.Sign(step 6 of Algorithm 2) may have unacceptable performance when the message M is large. For example, theplatform may require hardware support for hashing to achieve acceptable performance, but lack hardware
support for SHAKE256 specifcally. For some use cases, this may be addressed by signing a digest of themessage rather than signing the message directly.
In order to maintain the same level of security strength, the digest that is signed needs to be generated using
an approved hash function or extendable-output function (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].4 Note that verifcation of a signature created in this way will require the verify function
to generate a digest from the message in the same way to be used as input for the verifcation function.

4 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 (D RAFT )

771

8.

M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

Auxiliary Functions

773

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

774

8.1

772

775
776
777
778
779

Conversion Between Data Types

All keys and signatures in ML-DSA are communicated as byte strings. The goal in this subsection is toconstruct procedures for translating between byte strings and the various other algebraic objects defned insubsection 2.3.
Algorithms 4–7 are simple intermediate procedures for converting between bit strings, byte strings, andintegers.

Algorithm 4 IntegerToBits(x, α)Computes the base-2 representation of x mod 2α (using in little-endian order).
Input: A nonnegative integer x and a positive integer α.
Output: A bit string y of length α.
1: for i from 0 to α − 1 do
2:y[i] ← x mod 2
3:
x ← ⌊x/2⌋
4: end for5: return yAlgorithm 5 BitsToInteger(y)Computes the integer value expressed by a bit string (using little-endian order).
Input: A bit string y of length α.
Output: A nonnegative integer x.
1: x ← 0
2: for i from 1 to α do3:
x ← 2x + y[α − i]4: end for5: return x

20

FIPS 204 (D RAFT )M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

Algorithm 6 BitsToBytes(y)Converts a string of bits of length c into a string of bytes of length ⌈c/8⌉.
Input: A bit string y of length c.
Output: A byte string z.
1: z ← 0⌈c/8⌉
2: for i from 0 to c − 1 do
3:z [⌊i/8⌋] ← z [⌊i/8⌋] + y[i] · 2i mod 8
4: end for5: return z
Algorithm 7 BytesToBits(z)Converts a byte string into a bit string.
Input: A byte string z of length d.
Output: A bit string y.
1: for i from 0 to d − 1 do
2:for j from 0 to 7 do
3:y[8i + j] ← z[i] mod 2
4:z[i] ← ⌊z[i]/2⌋
5:
end for
6: end for7: return y
780
781
782
783
784

Algorithms 8–9 translate byte strings into coeffcients of polynomials in Rq . CoeffFromThreeBytes
uses a three-byte string to either generate an element of {0, 1, . . . , q − 1} or return the blank symbol ⊥.
CoefFromHalfByte 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, discussed in subsection 8.3.

Algorithm 8 CoefFromThreeBytes(b0 , b1 , b2 )Generates an element of {0, 1, 2, . . . , q − 1} ∪ {⊥}.
Input: Bytes b0 , b1 , b2 .
Output: An integer modulo q or ⊥.
1: if b2 > 127 then2:b2 ← b2 − 128
3: end if
4: z ← 216 · b2 + 28 · b1 + b0
5: if z < q then return z
6: else return ⊥7: end if▷ Set the top bit of b2 to zero21

FIPS 204 (D RAFT )M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

Algorithm 9 CoefFromHalfByte(b)Generates an element of {−η, −η + 1, . . . , η} ∪ {⊥}.
Input: Integer b ∈ {0, 1, . . . , 15}.
Output: An integer between −η and η, or ⊥.
1: if η = 2 and b < 15 then return 2 − (b mod 5)
2: else3:
if η = 4 and b < 9 then return 4 − b
4:else return ⊥5:
end if
6: end if

785
786
787
788
789

Algorithms 10–13 effciently translate an element w ∈ R into a byte string and vice versa under theassumption that the coeffcients of w are in a restricted range. SimpleBitPack assumes that wi ∈ [0, b]
for some positive integer b and packs w into a byte string of length 32 · bitlen b. BitPack allows for the
more general restriction wi ∈ [−a, b]. The BitPack algorithm works by merely subtracting w from theipolynomial ∑255
i=0 bX and then applying SimpleBitPack.

Algorithm 10 SimpleBitPack(w, b)
Encodes a polynomial w into a byte string.
Input: b ∈ N and w ∈ R such that the coeffcients of w are all in [0, b].
Output: A byte string of length 32 · bitlen b.
1: z ← ()▷ set z to the empty string
2: for i from 0 to 255 do
3:z ← z||IntegerToBits(wi , bitlen b)
4: end for5: return BitsToBytes(z)Algorithm 11 BitPack(w, a, b)
Encodes a polynomial w into a byte string.
Input: a, b ∈ N and w ∈ R such that the coeffcients of w are all in [−a, b].
Output: A byte string of length 32 · bitlen (a + b).
1: z ← ()▷ set z to the empty string
2: for i from 0 to 255 do
3:z ← z||IntegerToBits(b − wi , bitlen (a + b))
4: end for5: return BitsToBytes(z)
790
791
792
793
794

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

22

FIPS 204 (D RAFT )M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

Algorithm 12 SimpleBitUnpack(v, b)
Reverses the procedure SimpleBitPack.
Input: b ∈ N and a byte string v of length 32 · bitlen b.
Output: A polynomial w ∈ R, with coeffcients in [0, 2c − 1], where c = bitlen b.
When b + 1 is a power of 2, the coeffcients are in [0, b].
1: c ← bitlen b
2: z ← BytesToBits(v)
3: for i from 0 to 255 do
4:wi ← BitsToInteger((z[ic], z[ic + 1], . . . z[ic + c − 1]), c)
5: end for
6: return w
Algorithm 13 BitUnpack(v, a, b)
Reverses the procedure BitPack.
Input: a, b ∈ N and a byte string v of length 32 · bitlen (a + b).
Output: A polynomial w ∈ R, with coeffcients in [b − 2c + 1, b], where c = bitlen (a + b).
When a + b + 1 is a power of 2, the coeffcients are in [−a, b].
1: c ← bitlen (a + b)
2: z ← BytesToBits(v)
3: for i from 0 to 255 do
4:wi ← b − BitsToInteger((z[ic], z[ic + 1], . . . z[ic + c − 1]), c)
5: end for
6: return w

795
796
797
798
799
800
801
802
803

Algorithms 14–15 carry out byte-string-to-polynomial conversions for polynomials with sparse binary
coeffcients. In particular, the signing and verifcation algorithms (sections 6 and 7) make use of a “hint,”
which is a vector of polynomials h ∈ Rk2 such that the total number of coeffcients in h[0], h[1], . . . , h[k − 1]that are equal to 1 is no more than ω. This constraint enables encoding and decoding procedures that are
more effcient (although more complex) than BitPack and BitUnpack.
HintBitPack (h) outputs a byte string y of length ω + k. The last k bytes of y contain information about
how many nonzero coeffcients are present in each of the polynomials h[0], h[1], . . . , h[k − 1], and the frst
ω bytes of y contain information about exactly where those nonzero terms occur. HintBitUnpack reverses
the procedure performed by HintBitPack and recovers the vector h.

23

FIPS 204 (D RAFT )M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

Algorithm 14 HintBitPack(h)Encodes a polynomial vector h with binary coeffcients into a byte string.
Input: A polynomial vector h ∈ Rk2 such that at most ω of the coeffcients in h are equal to 1.
Output: A byte string y of length ω + k.
1: y ∈ Bω+k ← 0ω+k2: Index ← 0
3: for i from 0 to k − 1 do
4:
for j from 0 to 255 do
5:
if h[i] j ̸= 0 then6:y[Index] ← j▷ Store the locations of the nonzero coeffcients in h[i]7:Index ← Index + 1
8:
end if
9:end for10:y[ω + i] ← Index▷ Store the value of Index after processing h[i]11: end for
12: return yAlgorithm 15 HintBitUnpack(y)Reverses the procedure HintBitPack.
Input: A byte string y of length ω + k.
Output: A polynomial vector h ∈ Rk2 or ⊥.
1: h ∈ Rk2 ← 0k
2: Index ← 0
3: for i from 0 to k − 1 do
4:
if y[ω + i] < Index or y[ω + i] > ω then return ⊥5:
end if6:
while Index < y[ω + i] do
7:h[i]y[Index] ← 1
8:Index ← Index + 1
9:end while
10: end for
11: while Index < ω do12:
if y[Index] ̸= 0 then return ⊥13:
end if14:
Index ← Index + 1
15: end while
16: return h

804

805
806
807

8.2

Encodings of ML-DSA Keys and Signatures

Algorithms 16–21 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.

24

FIPS 204 (D RAFT )

808
809
810
811

M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

First, pkEncode and pkDecode translate ML-DSA public keys into byte strings, and vice versa. Note that,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 16 pkEncode(ρ, t1 )Encodes a public key for ML-DSA into a byte string.
Input:ρ ∈ {0, 1}256 , t1 ∈ Rk with coeffcients in [0, 2bitlen (q−1)−d − 1]).
Output: Public key pk ∈ B32+32k(bitlen (q−1)−d) .
1: pk ← BitsToBytes(ρ)
2: for i from 0 to k − 1 do
pk ← pk || SimpleBitPack (t1 [i], 2bitlen (q−1)−d − 1)3:
4: end for5: return pk
Algorithm 17 pkDecode(pk)Reverses the procedure pkEncode.
Input: Public key pk ∈ B32+32k(bitlen (q−1)−d) .
Output: ρ ∈ {0, 1}256 , t1 ∈ Rk with coeffcients in [0, 2bitlen (q−1)−d − 1]).
k
1: (y, z0 , . . . , zk−1 ) ∈ B32 × B32(bitlen (q−1)−d) ← pk
2: ρ ← BytesToBits(y)3: for i from 0 to k − 1 do
4:
t1 [i] ← SimpleBitUnpack(zi , 2bitlen (q−1)−d − 1)) ▷ This is always in the correct range
5: end for
6: return (ρ, t1 )25

FIPS 204 (D RAFT )

812
813
814

M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

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 input that comes from trusted sources.

Algorithm 18 skEncode(ρ, K,tr, s1 , s2 , t0 )Encodes a secret key for ML-DSA into a byte string.
Input: ρ ∈ {0, 1}256 , K ∈ {0, 1}256 , tr ∈ {0, 1}512 , s1 ∈ Rℓ with coeffcients in [−η, η],s2 ∈ Rk with coeffcients in [−η , η ], t0 ∈ Rk with coeffcients in [−2d −1 + 1, 2d −1 ].
Output: Private key, sk ∈ B32+32+64+32·((k+ℓ)·bitlen (2η)+dk) .
1: sk ← BitsToBytes(ρ) || BitsToBytes(K) || BitsToBytes(tr)2: for i from 0 to ℓ − 1 do
3:sk ← sk || BitPack (s1 [i], η, η)
4: end for
5: for i from 0 to k − 1 do
6:
sk ← sk || BitPack (s2 [i], η, η)
7: end for
8: for i from 0 to k − 1 do
9:sk ← sk || BitPack (t0 [i], 2d −1 − 1, 2d −1 )10: end for
11: return sk

26

FIPS 204 (D RAFT )M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

Algorithm 19 skDecode(sk)Reverses the procedure skEncode.
Input: Private key, sk ∈ B32+32+64+32·((ℓ+k)·bitlen (2η)+dk) .
Output: ρ ∈ {0, 1}256 , K ∈ {0, 1}256 , tr ∈ {0, 1}512 ,s1 ∈ Rℓ , s2 ∈ Rk , t0 ∈ Rk with coeffcients in [−2d−1 + 1, 2d−1 ].
1: ( f , g, h, y0 , . . . , yℓ−1 , z0 , . . . , zk−1 , w0 , . . . , wk−1 )ℓ∈ B32 × B32 × B64 × B32·bitlen (2η ) ×


k �
k
32·bitlen(2η)
B
× B32d ← sk
2: ρ ← BytesToBits( f )3: K ← BytesToBits(g)4: tr ← BytesToBits(h)5: for i from 0 to ℓ − 1 do
6:
s1 [i] ← BitUnpack(yi , η, η)▷ This may lie outside [−η, η], if input is malformed
7: end for
8: for i from 0 to k − 1 do
9:s2 [i] ← BitUnpack(zi , η, η)▷ This may lie outside [−η, η], if input is malformed
10: end for
11: for i from 0 to k − 1 do
12:
t0 [i] ← BitUnpack(wi , 2d −1 − 1, 2d−1 )▷ This is always in the correct range
13: end for
14: return (ρ, K,tr, s1 , s2 , t0 )27

FIPS 204 (D RAFT )

815
816
817
818

M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

Next, sigEncode and sigDecode translate ML-DSA signatures into byte strings, and vice versa. Note that,when verifying a signature, sigDecode might be run on input that comes from an untrusted source. Thus
care is required when using BitUnpack. As used here, BitUnpack always returns values in the correct
range.

Algorithm 20 sigEncode(c̃, z, h)
Encodes a signature into a byte string.
Input: c̃ ∈ {0, 1}2λ , z ∈ Rℓ with coeffcients in [−γ1 + 1, γ1 ], h ∈ Rk2 .
Output: Signature, σ ∈ Bλ /4+ℓ·32·(1+bitlen (γ1 −1))+ω+k .
1: σ ← BitsToBytes(c̃)
2: for i from 0 to ℓ − 1 do
3:σ ← σ || BitPack (z[i], γ1 − 1, γ1 )4: end for
5: σ ← σ || HintBitPack (h)6: return σ
Algorithm 21 sigDecode(σ )Reverses the procedure sigEncode.
Input: Signature, σ ∈ Bλ /4+ℓ·32·(1+bitlen (γ1 −1))+ω +k .
Output: c̃ ∈ {0, 1}2λ , z ∈ Rℓq with coeffcients in [−γ1 + 1, γ1 ], h ∈ Rk2 or ⊥.
1: (w, x0 , . . . , xℓ−1 , y) ∈ Bλ /4 × Bℓ·32·(1+bitlen (γ1 −1)) × Bω+k ← σ
2: c̃ ← BytesToBits(w)
3: for i from 0 to ℓ − 1 do
4:z[i] ← BitUnpack(xi , γ1 − 1, γ1 ) ▷ This is always in the correct range, as γ1 is a power of 2
5: end for
6: h ← HintBitUnpack(y)7: return (c̃, z, h)

819
820
821

Lastly, w1Encode (Algorithm 22) is a specifc subroutine that is used in ML-DSA.Sign (Algorithm 2).
Algorithm 22 encodes a polynomial vector w1 into a string of bits, so that it can be processed by the hashfunction, H.

Algorithm 22 w1Encode(w1 )Encodes a polynomial vector w1 into a bit string.
Input: w1 ∈ Rk with coeffcients in [0, (q − 1)/(2γ2 ) − 1].
Output: A bit string representation, w̃1 ∈ {0, 1}32k·bitlen ((q−1)/(2γ2 )−1) .
1: w̃1 ← ()2: for i from 0 to k − 1 do
3:w̃1 ← w̃1 || BytesToBits (SimpleBitPack (w1 [i], (q − 1)/(2γ2 ) − 1))
4: end for5: return w̃1
28

FIPS 204 (D RAFT )

822

823
824
825

8.3

M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

Hashing and Pseudorandom Sampling

The ML-DSA scheme makes use of two extendable-output functions (XOFs) that will be denoted by H
and H128 , each of which accepts a bit string v and a positive integer d and returns a length-d bit string. The
functions H and H128 shall be computed from the procedures in FIPS 202 [7] as follows:
H(v, d) ← SHAKE256(v, d),
H128 (v, d) ← SHAKE128(v, d).

826
827
828
829

The algorithm SHAKE256 is such that if c < d are positive integers and ρ ∈ {0, 1}∗ , then H(ρ, c) is exactly
equal to the frst c bits of H(ρ, d). The same is true of SHAKE128. For convenience, the expression
H(ρ)[k] may be used to denote the bit H(ρ, k + 1)[k] for any nonnegative integer k. Similarly, H(ρ)J jK
denotes the byte expressed by the bit stringH(ρ, 8( j + 1))[8 j], H(ρ, 8( j + 1))[8 j + 1], . . . , H(ρ, 8( j + 1))[8 j + 7]

830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847

The notation H(ρ)[k] is used in loops where an unknown number of bits of the form H(ρ)[k] will be needed
to compute a pseudorandom value (for the same ρ and consecutive, increasing values of k). It is expectedthat implementations will avoid recomputation by keeping track of the internal state of the SHAKE256
computation throughout the loop, and will only completely destroy that information once the the loop ends.
Similar implementation considerations apply when the XOF is H128 and when the output is parsed in bytes.
When H is used with a fxed length output, this standard sometimes refers to H as a hash function. Note
that, while H used with a fxed output length is a hash function, it is not an approved hash function forgeneral use. This standard only approves the use of H as a hash function where it is explicitly specifed aspart of the algorithms herein, or as part of a mathematically equivalent set of steps being performed inplace of the steps of these algorithms. In other contexts, the fact that H(ρ, c) is a prefx of H(ρ, d) for anyd > c, may interfere with desired security properties, but it is believed that when H is used as described inthis standard, it is overwhelmingly unlikely that H will be used with the same input string but a different
output length.
In addition, this subsection specifes various algorithms for generating algebraic objects pseudorandomly
from a seed ρ. The length of the bit string ρ varies depending on the algorithm.
The frst procedure to be defned is SampleInBall in Algorithm 23. Let Bτ denote the set of all polynomialsc ∈ Rq such that• Each coeffcient of c is either −1, 0, or 1, and849• Exactly τ of the coeffcients of c are nonzero.

851
852

(8.3)

(in little endian-order). The expressions H128 (ρ)[k] and H128 (ρ)J jK are similarly defned.

848

850

(8.1)
(8.2)

SampleInBall generates an element of Bτ pseudorandomly using the XOF of a seed ρ. The procedure isbased on the Fisher-Yates shuffe. The frst 8 bytes of H(ρ) are used to choose the signs of the nonzero
entries of c,5 and subsequent bytes of H(ρ) are used to choose the positions of those nonzero entries.

5 The parameter τ is always less than or equal to 64, and thus 8 bytes are suffcient to choose the signs for all τ

nonzero entries of c.

29

FIPS 204 (D RAFT )M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

Algorithm 23 SampleInBall(ρ)
Samples a polynomial c ∈ Rq with coeffcients from {−1, 0, 1} and Hamming weight τ.
Input: A seed ρ ∈ {0, 1}256
Output: A polynomial c in Rq .
1: c ← 0
2: k ← 8
3: for i from 256 − τ to 255 do
4:
while H(ρ)JkK > i do
5:k ← k+1
6:
end while7:j ← H(ρ)JkK
8:ci ← c j
c j ← (−1)H(ρ)[i+τ −256]9:10:k ← k+1
11: end for
12: return c

853
854
855
856
857
858
859

▷ j is a pseudorandom byte that is ≤ i

Algorithms 24–28 are the pseudorandom procedures RejNTTPoly, RejBoundedPoly, ExpandA, ExpandS,
and ExpandMask. Each generates elements of Rq or Tq under different input and output conditions.
RejNTTPoly and ExpandA make use of the more effcient XOF H128 , whereas the other three procedures
use the XOF H.
The procedure ExpandMask (Algorithm 28) generates a polynomial vector s in Rkq that disguises the secret
key in the Sign procedure (Algorithm 2). In addition to the seed ρ, ExpandMask also accepts an integer
input µ that is incorporated into the pseudorandom procedure that generates s.

Algorithm 24 RejNTTPoly(ρ)
Samples a polynomial ∈ Tq .
Input: A seed ρ ∈ {0, 1}272 .
Output: An element â ∈ Tq .
1: j ← 0
2: c ← 0
3: while j < 256 doâ[ j] ← CoefFromThreeBytes(H128 (ρ)JcK, H128 (ρ)Jc + 1K, H128 (ρ)Jc + 2K)4:c ← c+3
5:
6:
if â[ j] ≠ ⊥ then7:j ← j+1
end if8:
9: end while
10: return â

30

FIPS 204 (D RAFT )M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

Algorithm 25 RejBoundedPoly(ρ)
Samples an element a ∈ Rq with coeffcients in [−η, η] computed via rejection sampling from ρ.
Input: A seed ρ ∈ {0, 1}528 .
Output: A polynomial a ∈ Rq .
1: j ← 0
2: c ← 0
3: while j < 256 do
4:z ← H(ρ)JcK
5:z0 ← CoefFromHalfByte(z mod 16, η)
6:z1 ← CoefFromHalfByte(⌊z/16⌋, η)7:
if z0 ̸= ⊥ then8:a j ← z09:j ← j+1
10:
end if11:
if z1 ̸= ⊥ and j < 256 then12:a j ← z1
13:
j ← j+1
14:
end if15:c ← c+1
16: end while
17: return a

Algorithm 26 ExpandA(ρ)
Samples a k × ℓ matrix Â of elements of Tq .
Input: ρ ∈ {0, 1}256 .
Output: Matrix Â.
1: for r from 0 to k − 1 do
2:for s from 0 to ℓ − 1 do
3:Â[r, s] ← RejNTTPoly(ρ||IntegerToBits(s, 8)||IntegerToBits(r, 8))4:
end for
5: end for
6: return Â

31

FIPS 204 (D RAFT )M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

Algorithm 27 ExpandS(ρ)
Samples vectors s1 ∈ Rℓq and s2 ∈ Rkq , each with coeffcients in the interval [−η, η].
Input: ρ ∈ {0, 1}512
Output: Vectors s1 , s2 of polynomials in Rq .
1: for r from 0 to ℓ − 1 do
2:
s1 [r] ← RejBoundedPoly(ρ||IntegerToBits(r, 16))
3: end for
4: for r from 0 to k − 1 do
5:s2 [r] ← RejBoundedPoly(ρ||IntegerToBits(r + ℓ, 16))
6: end for7: return (s1 , s2 )Algorithm 28 ExpandMask(ρ, µ)Samples a vector s ∈ Rℓq such that each polynomial s j has coeffcients between −γ1 + 1 and γ1 .
Input: A bit string ρ ∈ {0, 1}512 and a nonnegative integer µ.
Output: Vector s ∈ Rℓq .
1: c ← 1 + bitlen (γ1 − 1)
▷ γ1 is always a power of 2
2: for r from 0 to ℓ − 1 do
3:n ← IntegerToBits(µ + r, 16)4:v ← (H(ρ||n)J32rcK, H(ρ||n)J32rc + 1K, . . . , H(ρ||n)J32rc + 32c − 1K)
5:s[r] ← BitUnpack(v, γ1 − 1, γ1 )6: end for7: return s

32

FIPS 204 (D RAFT )

860

861
862
863
864
865

866

8.4

M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

High Order / Low Order Bits and Hints

This specifcation uses the auxiliary functions Power2Round, Decompose, HighBits, LowBits, MakeHint,
and UseHint. This document explicitly defnes these functions where r ∈ Zq , r1 , r0 ∈ Z and h is a boolean(or equivalently an element of Z2 ). However, the specifcation also uses these functions where r, z ∈ Rkq ,r1 , r0 ∈ Rk and h ∈ Rk2 . In this case, the functions are applied coeffcientwise.
That is:• For r ∈ Rkq and d ∈ Z, defne (r1 , r0 ) ∈ (Rk )2 = Power2Round(r, d), so that:((r1 [i]) j , (r0 [i]) j ) = Power2Round((r[i]) j , d).

867• For r ∈ Rkq defne (r1 , r0 ) ∈ (Rk )2 = Decompose(r), so that:((r1 [i]) j , (r0 [i]) j ) = Decompose((r[i]) j ).

868

• For r ∈ Rkq defne r1 = HighBits (r), so that:(r1 [i]) j = HighBits((r[i]) j ).

869

• For r ∈ Rkq defne r0 = LowBits(r), so that:(r0 [i]) j = LowBits((r[i]) j ).

870

• For z, r ∈ Rkq defne h ∈ Rk2 = MakeHint(z, r), so that:(h[i]) j = MakeHint((z[i]) j ), (r[i]) j )).

871• For h ∈ Rk2 and r ∈ Rkq , defne r1 ∈ Rk = UseHint(h, r), so that:r1 [i] j = UseHint((h[i]) j ), (r[i]) j )).

872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887

These algorithms are used to support the key compression optimization of ML-DSA. The basic idea is
to drop the d low-order bits of each coeffcient of the polynomial vector t from the public key using thefunction Power2Round. However, in order to make this optimization work, additional information, calleda “hint”, needs to be provided in the signature to allow the verifer to reconstruct enough of the informationin the dropped public key bits to verify the signature. Hints are created during signing and used during
verifcation by the functions MakeHint and UseHint, respectively. In the verifcation of a valid signature,
the hint allows the verifer to recover w1 ∈ Rk , which represents w ∈ Rkq rounded to a nearby multipleof α = 2γ2 . The signer obtains w1 directly using the function HighBits, and the part rounded off, r0 , isobtained by LowBits. r0 is used by the signer in the rejection sampling procedure.
Power2Round decomposes an input r ∈ Zq into integers that represent the high- and low-order bits ofr mod q in the straightforward bitwise way, r mod q = r1 · 2d + r0 , where r0 = (r mod q) mod± 2d andr1 = (r mod q − r0 )/2d .
However, for the purpose of computations related to hints, this method of decomposing r has the undesirable
property that when r is close to q − 1 or 0, a small rounding error in r can cause r1 to change by more than
1 (even accounting for wrap-around). This is because unlike for other unequal pairs of values of r1 · 2d andr1′ · 2d , the distance between ⌊q/2d ⌋ · 2d and 0 may be very small.

33

FIPS 204 (D RAFT )

888

889

890
891

892
893
894

M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

To avoid this problem, this specifcation defnes Decompose, which is similar to Power2Round except:• r is generally decomposed as r mod q = r1 · α + r0 , where α = 2γ2 is a divisor of q − 1.
• If the straightforward rounding procedure would return (r1 = (q − 1)/α, r0 ∈ [−(α/2) + 1, α/2]),
Decompose instead returns (r1 = 0, r0 − 1).
The functions HighBits and LowBits– which only return r1 and r0 , respectively – and MakeHint andUseHint use Decompose. For additional discussion of the mathematical properties of these functions thatare relevant to the correctness and security of ML-DSA, see Section 2.4 in [5].

Algorithm 29 Power2Round(r)Decomposes r into (r1 , r0 ) such that r ≡ r1 2d + r0 mod q.
Input: r ∈ Zq .
Output: Integers (r1 , r0 ).
1: r+ ← r mod q
2: r0 ← r+�mod± 2d
3: return (r+ − r0 )/2d , r0
Algorithm 30 Decompose(r)Decomposes r into (r1 , r0 ) such that r ≡ r1 (2γ2 ) + r0 mod q.
Input: r ∈ Zq
Output: Integers (r1 , r0 ).
1: r+ ← r mod q
2: r0 ← r+ mod± (2γ2 )3: if r+ − r0 = q − 1 then4:
r1 ← 05:
r0 ← r 0 − 1
6: else r1 ← (r+ − r0 )/(2γ2 )7: end if
8: return (r1 , r0 )Algorithm 31 HighBits(r)Returns r1 from the output of Decompose (r)Input: r ∈ Zq
Output: Integer r1 .
1: (r1 , r0 ) ← Decompose(r)2: return r1

34

FIPS 204 (D RAFT )M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

Algorithm 32 LowBits(r)Returns r0 from the output of Decompose (r)Input: r ∈ Zq
Output: Integer r0 .
1: (r1 , r0 ) ← Decompose(r)2: return r0

Algorithm 33 MakeHint(z, r)
Compute hint bit indicating whether adding z to r alters the high bits of r.
Input: z, r ∈ Zq
Output: Boolean
1: r1 ← HighBits(r)2: v1 ← HighBits(r + z)
3: return [[r1 ̸= v1 ]]Algorithm 34 UseHint(h, r)
Returns the high bits of r adjusted according to hint h
Input:boolean h, r ∈ Zq
Output:r1 ∈ Z with 0 ≤ r1 ≤ q2−1
γ2
1: m ← (q − 1)/(2γ2 )2: (r1 , r0 ) ← Decompose(r)3: if h = 1 and r0 > 0 return (r1 + 1) mod m
4: if h = 1 and r0 ≤ 0 return (r1 − 1) mod m
5: return r1

35

FIPS 204 (D RAFT )

895

896
897
898
899
900
901
902
903
904
905
906
907

908
909
910

8.5

M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

NTT and NTT−1

The following algorithms implement the NTT and its inverse (NTT−1 ). Using the NTT is important for
effciency. There are other important optimizations that are not included in this standard. In particular,
mod and mod± are expensive operations whose use can be minimized by using Montgomery reduction(see Appendix B).
The NTT algorithm takes a polynomial w ∈ Rq as input and returns ŵ ∈ Tq . NTT−1 takes ŵ ∈ Tq as input
and returns w such that ŵ = NTT(w).
This document always distinguishes between elements of Rq and elements of Tq . However, the natural data
structure for both of these sets is as an integer array of size 256. This would allow for 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.
Recall that ζ = 1753 ∈ Zq , which is a 512th root of unity modulo q. On input w ∈ Rq , the algorithm
outputs(8.4)
NTT(w) = (w(ζ0 ), w(−ζ0 ), . . . w(ζ127 ), w(−ζ127 )) ∈ Tq ,where ζi = ζ brv(128+i) mod q. The values ζ brv(k) mod q for k = 1, . . . , 255 used in line 10 of Algorithm
35 and line 10 of Algorithm 36 are typically pre-computed. That optimization is not included in thisdocument.

Algorithm 35 NTT(w)Computes the Number-Theoretic Transform.
j
Input: polynomial w(X) = ∑255
j=0 w j X ∈ Rq .
Output: ŵ = (ŵ[0], . . . , ŵ[255]) ∈ Tq .
1: for j from 0 to 255 do
2:ŵ[ j] ← w j
3: end for
4: k ← 0
5: len ← 128
6: while len ≥ 1 do
7:start ← 08:
while start < 256 do
9:k ← k+1
10:
zeta ← ζ brv(k) mod q
11:
for j from start to start + len − 1 do
12:t ← zeta · ŵ[ j + len]13:ŵ[ j + len] ← ŵ[ j] − t
14:ŵ[ j] ← ŵ[ j] + t
15:
end for16:
start ← start + 2 · len
17:
end while18:
len ← ⌊len/2⌋
19: end while
20: return ŵ

36

FIPS 204 (D RAFT )M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

Algorithm 36 NTT−1 (ŵ)
Computes the inverse of the Number-Theoretic Transform.
Input: ŵ = (ŵ[0], . . . , ŵ[255]) ∈ Tq .
j
Output: polynomial w(X) = ∑255
j=0 w j X ∈ Rq .
1: for j from 0 to 255 do2:
w j ← ŵ[ j]3: end for
4: k ← 256
5: len ← 1
6: while len < 256 do
7:start ← 08:
while start < 256 do
9:k ← k−1
10:zeta ← −ζ brv(k) mod q
11:
for j from start to start + len − 1 do
12:t ← wj13:
w j ← t + w j+len
14:
w j+len ← t − w j+len
15:
w j+len ← zeta · w j+len
16:
end for17:
start ← start + 2 · len
18:
end while19:
len ← 2 · len
20: end while
21: f ← 8347681
22: for j from 0 to 255 do
23:
wj ← f ·wj
24: end for
25: return w

37▷ f = 256−1 mod q

FIPS 204 (D RAFT )

911

912
913
914

915
916
917

918
919
920

921
922
923
924

925
926
927
928

929
930
931

932
933
934

935
936
937

938
939
940

941
942

943
944

945
946
947

948
949
950

M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

References[1] National Institute of Standards and Technology. Digital signature standard (DSS). (U.S. Departmentof Commerce, Washington, DC), Federal Information Processing Standards Publication (FIPS) 186-5,
February 2023. https://doi.org/10.6028/NIST.FIPS.186-5.
[2] Elaine Barker. 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, March 2020. https://doi.org/10.6028/NIST.SP.800-175Br1.
[3] Elaine B. Barker. Recommendation for obtaining assurances for digital signature applications.
National Institute of Standards and Technology, Gaithersburg, MD. NIST Special Publication (SP)
800-89, November 2006. https://doi.org/10.6028/NIST.SP.800-89.
[4] Shi Bai, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, Peter Schwabe, Gregor
Seiler, and Damien Stehlé. CRYSTALS-Dilithium: Algorithm specifcations and supporting documentation. Submission to the NIST’s post-quantum cryptography standardization process, 2020.
https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions.
[5] Shi Bai, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, Peter Schwabe, Gregor
Seiler, and Damien Stehlé. CRYSTALS-Dilithium: Algorithm specifcations and supporting documentation (Version 3.1), 2021. https://pq-crystals.org/dilithium/data/dilithium-specifcation-round3-20210208.pdf.
[6] C. Cremers, S. Düzlü, R. Fiedler, C. Janson, and M. Fischlin. BUFFing signature schemes beyond
unforgeability and the case of post-quantum signatures. In 2021 IEEE Symposium on Security andPrivacy (SP), pages 1696–1714, Los Alamitos, CA, USA, may 2021. IEEE Computer Society.
[7] National Institute of Standards and Technology. SHA-3 standard: Permutation-based hash andextendable-output functions. (U.S. Department of Commerce, Washington, DC), Federal Information
Processing Standards Publication (FIPS) 202, August 2015. https://doi.org/10.6028/NIST.FIPS.202.
[8] National Institute of Standards and Technology. Secure hash standard (SHS). (U.S. Department ofCommerce, Washington, DC), Federal Information Processing Standards Publication (FIPS) 180-4,
August 2015. https://doi.org/10.6028/NIST.FIPS.180-4.
[9] Vadim Lyubashevsky. Fiat-Shamir with aborts: Applications to lattice and factoring-based signatures.
In Mitsuru Matsui, editor, Advances in Cryptology – ASIACRYPT 2009, pages 598–616, Berlin,
Heidelberg, 2009. Springer Berlin Heidelberg.
[10] Vadim Lyubashevsky. Lattice signatures without trapdoors. In EUROCRYPT, volume 7237 of Lecture
Notes in Computer Science, pages 738–755. Springer, 2012.
[11] Tim Güneysu, Vadim Lyubashevsky, and Thomas Pöppelmann. Practical lattice-based cryptography:
A signature scheme for embedded systems. In CHES, volume 7428, pages 530–547. Springer, 2012.
[12] Shi Bai and Steven D. Galbraith. An improved compression technique for signatures based onlearning with errors. In Josh Benaloh, editor, Topics in Cryptology – CT-RSA 2014, pages 28–47,
Cham, 2014. Springer International Publishing.
[13] Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In Proceedingsof the Thirty-Seventh Annual ACM Symposium on Theory of Computing, STOC ’05, page 84–93,
New York, NY, USA, 2005. Association for Computing Machinery.

38

FIPS 204 (D RAFT )

951
952

953
954
955
956

957
958
959

960
961
962
963

964
965
966
967

968
969
970
971

972
973
974
975

976
977
978
979

980
981

982
983
984

985
986
987

988
989
990

M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD[14] Adeline Langlois and Damien Stehlé. Worst-case to average-case reductions for module lattices.
Designs, Codes and Cryptography, 75(3):565–599, 2015.
[15] Eike Kiltz, Vadim Lyubashevsky, and Christian Schaffner. A concrete treatment of Fiat-Shamir
signatures in the quantum random-oracle model. In Jesper Buus Nielsen and Vincent Rijmen, editors,
Advances in Cryptology – EUROCRYPT 2018, pages 552–586, Cham, 2018. Springer International
Publishing.
[16] Elaine B. Barker. Recommendation for key management:part 1 - general. National Institute ofStandards and Technology, Gaithersburg, MD. NIST Special Publication (SP) 800-57 Part 1 Revision
5, May 2020. https://doi.org/10.6028/NIST.SP.800-57pt1r5.
[17] Elaine B. Barker and William C. Barker. Recommendation for key management: Part 2 - bestpractices for key management organizations. National Institute of Standards and Technology,
Gaithersburg, MD. NIST Special Publication (SP) 800-57 Part 2 Revision 1, May 2019. https://doi.org/10.6028/NIST.SP.800-57pt2r1.
[18] Elaine B. Barker and Quynh Dang. Recommendation for key management: Part 3 - applicationspecifc key management guidance. National Institute of Standards and Technology, Gaithersburg,
MD. NIST Special Publication (SP) 800-57 Part 3 Revision 1, May 2019. http://dx.doi.org/10.6028/NIST.SP.800-57pt3r1.
[19] Elaine B. Barker and John M. Kelsey. 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, June 2015. https://doi.org/10.6028/NIST.SP.
800-90Ar1.
[20] Meltem Sönmez Turan, Elaine B. Barker, John M. Kelsey, Kerry A. McKay, Mary L. Baish, andMike Boyle. Recommendation for the entropy sources used for random bit generation. (National
Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-90B,
January 2018. https://doi.org/10.6028/NIST.SP.800-90B.
[21] Elaine B. Barker, John M. Kelsey, Kerry McKay, Allen Roginsky, and Meltem Sönmez Turan.
Recommendation for random bit generator (RBG) constructions. (National Institute of Standards
and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-90C (Third Public Draft),
September 2022. https://csrc.nist.gov/publications/detail/sp/800-90c/draft.
[22] Leon Groot Bruinderink and Peter Pessl. Differential fault attacks on deterministic lattice signatures.
IACR Transactions on Cryptographic Hardware and Embedded Systems, pages 21–43, 2018.
[23] Damian Poddebniak, Juraj Somorovsky, Sebastian Schinzel, Manfred Lochter, and Paul Rösler.
Attacking deterministic signature schemes using fault attacks. In 2018 IEEE European Symposium
on Security and Privacy (EuroS&P), pages 338–352. IEEE, 2018.
[24] Niels Samwel, Lejla Batina, Guido Bertoni, Joan Daemen, and Ruggero Susella. Breaking ed25519
in wolfssl. In Topics in Cryptology–CT-RSA 2018: The Cryptographers’ Track at the RSA Conference
2018, San Francisco, CA, USA, April 16-20, 2018, Proceedings, pages 1–20. Springer, 2018.
[25] National Institute of Standards and Technology. Submission requirements and evaluation criteria forthe post-quantum cryptography standardization process, 2016. https://csrc.nist.gov/CSRC/media/Pro
jects/Post-Quantum-Cryptography/documents/call-for-proposals-final-dec-2016.pdf.

39

FIPS 204 (D RAFT )

991
992
993
994
995
996

997
998
999
1000
1001

1002
1003
1004

1005
1006

1007
1008
1009
1010

1011
1012
1013

M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD[26] Gorjan Alagic, Daniel Apon, David Cooper, Quynh Dang, Thinh Dang, John Kelsey, Jacob Lichtinger,
Yi-Kai Liu, Carl Miller, Dustin Moody, Rene Peralta, Ray Perlner, Angela Robinson, and Daniel
Smith-Tone. Status report on the third round of the NIST post-quantum cryptography standardization
process. Technical Report NIST Interagency or Internal Report (IR) 8413, National Institute ofStandards and Technology, Gaithersburg, MD, July 2022. https://doi.org/10.6028/NIST.IR.8413-upd
1.
[27] Robert Avanzi, Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M.
Schanck, Peter Schwabe, Gregor Seiler, and Damien Stehlé. CRYSTALS-Kyber algorithm specifcations and supporting documentation. 3rd Round submission to the NIST’s post-quantum cryptography
standardization process, 2020. https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-sub
missions.
[28] C. P. Schnorr. Effcient identifcation and signatures for smart cards. In Gilles Brassard, editor,
Advances in Cryptology — CRYPTO’ 89 Proceedings, pages 239–252, New York, NY, 1990. Springer
New York.
[29] Simon Josefsson and Ilari Liusvaara. Edwards-Curve Digital Signature Algorithm (EdDSA). RFC
8032, January 2017.
[30] Samuel Jaques, Michael Naehrig, Martin Roetteler, and Fernando Virdia. Implementing Grover
oracles for quantum key search on AES and LowMC. In Anne Canteaut and Yuval Ishai, editors,
Advances in Cryptology – EUROCRYPT 2020, pages 280–310, Cham, 2020. Springer International
Publishing.
[31] Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of theTwenty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’96, page 212–219, New
York, NY, USA, 1996. Association for Computing Machinery.

40

FIPS 204 (D RAFT )

1014

1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026

M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

Appendix A — Security Strength Categories
NIST understands that there are signifcant uncertainties in estimating the security strengths of postquantum cryptosystems. These uncertainties come from two sources: frst, the possibility that new
cryptanalytic attacks are discovered, based on classical or quantum computation; and second, our limited
ability to predict the performance characteristics of future quantum computers, such as their cost, speed,
and memory size.
In order to address these uncertainties, NIST proposed the following approach in its original Call for
Proposals [25]. Instead of defning the strength of an algorithm using precise estimates of the numberof “bits of security,” NIST defned a collection of broad security strength categories. Each category isdefned by a comparatively easy-to-analyze reference primitive whose security serves as a foor for a wide
variety of metrics that NIST deems potentially relevant to practical security. A given cryptosystem may
be instantiated using different parameter sets in order to ft into different categories. The goals of thisclassifcation are:1028

• To facilitate meaningful performance comparisons between various post-quantum algorithms by
ensuring – insofar as possible – that the parameter sets being compared provide comparable security1029• To allow NIST to make prudent future decisions regarding when to transition to longer keys

1027

1031

• To help submitters make consistent and sensible choices regarding what symmetric primitives to use
in padding mechanisms or other components of their schemes that require symmetric cryptography1032• To better understand the security/performance trade-offs involved in a given design approach

1030

1033
1034
1035
1036

1037
1038
1039

1040
1041
1042

1043
1044
1045

1046
1047
1048

1049
1050
1051

In accordance with the second and third goals above, NIST based its classifcation on the range of security
strengths offered by the existing NIST standards in symmetric cryptography, which NIST expects to offer
signifcant resistance to quantum cryptanalysis. In particular, NIST defned a separate category for each of
the following security requirements (listed in order of increasing strength):
1. Any attack that breaks the relevant security defnition must require computational resources comparable to or greater than those required for key search on a block cipher with a 128-bit key (e.g.,
AES-128).
2. Any attack that breaks the relevant security defnition must require computational resources comparable to or greater than those required for collision search on a 256-bit hash function (e.g., SHA-256/
SHA3-256).
3. Any attack that breaks the relevant security defnition must require computational resources comparable to or greater than those required for key search on a block cipher with a 192-bit key (e.g.,
AES-192).
4. Any attack that breaks the relevant security defnition must require computational resources comparable to or greater than those required for collision search on a 384-bit hash function (e.g., SHA-384/
SHA3-384).
5. Any attack that breaks the relevant security defnition must require computational resources comparable to or greater than those required for key search on a block cipher with a 256-bit key (e.g.,
AES-256).

41

FIPS 204 (D RAFT )M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

Table 3. NIST Security Strength Categories
Security Category

1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076

Corresponding Attack Type

Example1

Key search on block cipher with 128-bit key

AES-128

2

Collision search on 256-bit hash function

SHA3-2563

Key search on block cipher with 192-bit key

AES-192

4

Collision search on 384-bit hash function

SHA3-384

5

Key search on block cipher with 256-bit key

AES-256

When considering the fve categories, computational resources may be measured using a variety ofdifferent metrics (e.g., number of classical elementary operations, quantum circuit size). In order for acryptosystem to satisfy one of the above security requirements, any attack must require computational
resources comparable to or greater than the stated threshold with respect to all metrics that NIST deems to
be potentially relevant to practical security.
NIST intends to consider a variety of possible metrics that refect different predictions about the future
development of quantum and classical computing technology and the cost of different computing resources(such as the cost of accessing extremely large amounts of memory).6 NIST will also consider input fromthe cryptographic community regarding this question.
In an example metric provided to submitters, NIST suggested an approach where quantum attacks are
restricted to a fxed running time or circuit depth. Call this parameter MAXDEPTH. This restriction is motivated by the diffculty of running extremely long serial computations. Plausible values for MAXDEPTH
range from 240 logical gates (the approximate number of gates that presently envisioned quantum computing architectures are expected to serially perform in a year) through 264 logical gates (the approximate
number of gates that current classical computing architectures can perform serially in a decade), to no
more than 296 logical gates (the approximate number of gates that atomic scale qubits with speed-of-lightpropagation times could perform in a millennium). The most basic version of this cost metric ignores
costs associated with physically moving bits or qubits so that they are physically close enough to perform gate operations. This simplifcation may result in an underestimate of the cost of implementing
memory-intensive computations on real hardware.
The complexity of quantum attacks can then be measured in terms of circuit size. These numbers can becompared to the resources required to break AES and SHA-3. During the post-quantum standardization
process, NIST gave the following estimates for the classical and quantum gate counts7 for the optimal
key recovery and collision attacks on AES and SHA-3, respectively, where circuit depth is limited to
MAXDEPTH.8

6 See the discussion in [26, Appendix B].
7 Quantum circuit sizes are based on the work in [30].
8 NIST believes that the above estimates are accurate for the majority of values of MAXDEPTH that are relevant to its

security analysis, but the above estimates may understate the security of SHA for very small values of MAXDEPTH
and may understate the quantum security of AES for very large values of MAXDEPTH.

42

FIPS 204 (D RAFT )M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

Table 4. Estimated gate counts for the optimal key recovery and collision attacks on AES
and SHA-3

1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088

Algorithm

Estimated number of gates

AES-1282157 /MAXDEPTH quantum gates or 2143 classical gates

SHA3-2562146 classical gates

AES-192

2221 /MAXDEPTH quantum gates or 2207 classical gates

SHA3-384

2210 classical gates

AES-2562285 /MAXDEPTH quantum gates or 2272 classical gates

SHA3-512

2274 classical gates

It is worth noting that the security categories based on these reference primitives provide substantiallymore quantum security than a naïve analysis might suggest. For example, categories 1, 3, and 5 are defnedin terms of block ciphers, which can be broken using Grover’s algorithm [31] with a quadratic quantum
speedup. However, Grover’s algorithm requires a long-running serial computation, which is diffcult toimplement in practice. In a realistic attack, one has to run many smaller instances of the algorithm inparallel, which makes the quantum speedup less dramatic.
Finally, for attacks that use a combination of classical and quantum computation, one may use a cost metricthat rates logical quantum gates as being several orders of magnitude more expensive than classical gates.
Presently envisioned quantum computing architectures typically indicate that the cost per quantum gate
could be billions or trillions of times the cost per classical gate. However, especially when considering
algorithms that claim a high security strength (e.g., equivalent to AES-256 or SHA-384), it is likely prudent
to consider the possibility that this disparity will narrow signifcantly or even be eliminated.

43

FIPS 204 (D RAFT )

1089

1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102

M ODULE -L ATTICE -B ASED D IGITAL S IGNATURE S TANDARD

Appendix B — Montgomery Reduction
This document uses modular multiplication. This is an expensive operation that is, in practice, often
avoided. One way of achieving this is through the use of Montgomery multiplication. If a is an integer
modulo q, then its Montgomery form with multiplier 232 is r ≡ a · 232 mod q.
Suppose two integers a and b modulo q are in Montgomery form. Their product modulo q is c = a · b · 2−32 ,also in Montgomery form. If a and b have absolute value less than q, one can compute c by frst performing
the integer multiplication a · b and then “reducing” the product by multiplying by 2−32 modulo q. This lastoperation can be done effciently as follows.
The Montgomery_Reduce function takes as input an integer a with absolute value at most 231 q. It returns
an integer r with absolute value strictly less than q and such that r = a · 2−32 mod q. The output is inMontgomery form with multiplier 232 mod q. An implementation would typically use a 64-bit input andreturn a 32-bit output. The “modulo 232 ” operation simply extracts the 32 least signifcant bits of a 64-bit
value. The value (a − t · q) on line 3 is an integer divisible by 232 . Therefore, the division consists simplyof taking the most signifcant 32 bits of a 64-bit value.

Algorithm 37 Montgomery_Reduce(a)Converts from Montgomery form to regular form.
Input: integer a with −231 q ≤ a ≤ 231 q.
Output: r ≡ a · 2−32 mod q such that −q < r < q.
1: QINV ← 58728449
2: t ← ((a mod 232 ) · QINV ) mod 232
3: r ← (a − t · q)/232
4: return r
1103
1104
1105
1106
1107

▷ the inverse of q modulo 232

With this algorithm, the modular product of a and b is Montgomery_Reduce(a · b).
Converting an integer modulo q to Montgomery form by multiplying by 232 modulo q is an expensive
operation. When a sequence of modular operations is to be performed, as in Algorithms 35 and 36, theoperands are converted once to Montgomery form, the operations are performed, and the factor 232 is
extracted from the fnal results.

44