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 203
Title Module-Lattice-Based Key-Encapsulation Mechanism Standard
Publication Date August 2024
DOI https://doi.org/10.6028/NIST.FIPS.203
CSRC URL https://csrc.nist.gov/pubs/fips/203/final
Additional Information https://csrc.nist.gov/projects/post-quantum-cryptography/postquantum-cryptography-standardization

1

FIPS 203 (Draft)

2 Federal Information Processing Standards Publication
3

Module-Lattice-based
5 Key-Encapsulation
6 Mechanism Standard
4

7 Category: Computer Security

Subcategory: Cryptography

8 Information Technology Laboratory
9 National Institute of Standards and Technology
10 Gaithersburg, MD 20899-8900
11 This publication is available free of charge from:
12 https://doi.org/10.6028/NIST.FIPS.203.ipd
13 Published August 24, 2023

14

15 U.S. Department of Commerce
16 Gina M. Raimondo, Secretary
17 National Institute of Standards and Technology
18 Laurie E. Locascio, NIST Director and Under Secretary of Commerce for Standards and Technology

19

Foreword

20 The Federal Information Processing Standards Publication (FIPS) Series of the National Institute of
21 Standards and Technology is the offcial series of publications relating to standards and guidelines developed
22 under 15 U.S.C. 278g-3, and issued by the Secretary of Commerce under 40 U.S.C. 11331.
23 Comments concerning this Federal Information Processing Standard publication are welcomed and should
24 be submitted using the contact information in the “Inquiries and comments” clause of the announcement
25 section.
26

James A. St Pierre, Acting Director
Information Technology Laboratory

FIPS 203 (D RAFT )M ODULE -L ATTICE - BASED K EY-E NCAPSULATION M ECHANISM

27

Abstract

28
29
30
31
32

A key-encapsulation mechanism (or KEM) is a set of algorithms that, under certain conditions,can be used by two parties to establish a shared secret key over a public channel. A sharedsecret key that is securely established using a KEM can then be used with symmetric-key
cryptographic algorithms to perform basic tasks in secure communications, such as encryption
and authentication.

33
34
35
36

This standard specifes a key-encapsulation mechanism called ML-KEM. The security of
ML-KEM is related to the computational diffculty of the so-called Module Learning with Errors
problem. At present, ML-KEM is believed to be secure even against adversaries who possess aquantum computer.

37 This standard specifes three parameter sets for ML-KEM. In order of increasing security strength
38 (and decreasing performance), these parameter sets are ML-KEM-512, ML-KEM-768, and
39 ML-KEM-1024.
40 Keywords: computer security; cryptography; encryption; Federal Information Processing
41 Standards; lattice-based cryptography; key-encapsulation; post-quantum; public-key cryptography

FIPS 203 (D RAFT )M ODULE -L ATTICE - BASED K EY-E NCAPSULATION M ECHANISM

42

Federal Information Processing Standards Publication 203

43

Published: August 24, 2023

44

Announcing the45

Module-Lattice-based Key-Encapsulation
Mechanism Standard

46

47 Federal Information Processing Standards Publications (FIPS) are issued by the National Institute48 of Standards and Technology (NIST) under 15 U.S.C. 278g-3 and issued by the Secretary of
49 Commerce under 40 U.S.C. 11331.
50 1. Name of Standard. Module-Lattice-based Key-Encapsulation Mechanism Standard (ML51
KEM) (FIPS PUB 203).
52 2. Category of Standard. Computer Security. Subcategory. Cryptography.
53 3. Explanation. This standard specifes a set of algorithms for applications that require a secret
54
cryptographic key that is shared by two parties who can only communicate over a publicchannel. A cryptographic key (or simply "key") is represented in a computer as a string of bits.
55
56
A shared secret key is computed jointly by two parties (e.g., Party A and Party B) using a set
57
of rules and parameters. Under certain conditions, these rules and parameters ensure that both58
parties will produce the same key and that this shared key is secret from adversaries. Such a59
shared secret key can then be used with symmetric-key cryptographic algorithms (specifed
60
in other NIST standards) to perform tasks, such as encryption and authentication of digital
61
information.
62
63
64
65
66
67
68
69

While there are many methods for establishing a shared secret key, the particular method
described in this specifcation is a key-encapsulation mechanism (KEM). In a KEM, thecomputation of the shared secret key begins with Party A generating a decapsulation key andan encapsulation key. Party A keeps the decapsulation key private and makes the encapsulation
key available to Party B. Party B then uses Party A’s encapsulation key to generate one copyof a shared secret key along with an associated ciphertext. Party B then sends the ciphertext
to Party A over the same channel. Finally, Party A uses the ciphertext from Party B alongwith Party A’s private decapsulation key to compute another copy of the shared secret key.

70
71
72
73
74
75

The security of the particular KEM specifed here is related to the computational diffculty ofsolving certain systems of noisy linear equations, specifcally the so-called Module Learning
With Errors (MLWE) problem. At present, it is believed that this particular method of
establishing a shared secret key is secure even against adversaries who possess a quantum
computer. In the future, additional KEMs may be specifed and approved in FIPS publications
or in NIST Special Publications.

76 4. Approving Authority. Secretary of Commerce.
77 5. Maintenance Agency. Department of Commerce, National Institute of Standards and Tech78
nology, Information Technology Laboratory (ITL).

iFIPS 203 (D RAFT )M ODULE -L ATTICE - BASED K EY-E NCAPSULATION M ECHANISM

79 6. Applicability. Federal Information Processing Standards apply to information systems used
80
or operated by federal agencies or by a contractor of an agency or other organization on behalfof an agency. They do not apply to national security systems as defned in 44 U.S.C. 3552.
81
82
83
84
85
86

This standard must be implemented wherever the establishment of a shared secret key isrequired for federal applications, including the use of such a key with symmetric-key cryptographic algorithms, in accordance with applicable Offce of Management and Budget andagency policies. Federal agencies may also use alternative methods that NIST has indicatedare appropriate for this purpose.

87

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

88 7. Implementations. A key-encapsulation mechanism may be implemented in software,
frmware, hardware, or any combination thereof. A conforming implementation may replace89
the given sequence of steps in the top-level algorithms of ML-KEM (i.e., ML-KEM.KeyGen,
90
ML-KEM.Encaps, and ML-KEM.Decaps) with any equivalent process. In other words, dif91
ferent procedures that produce the correct output for every input are permitted. In particular,
92
conforming implementations are not required to use the same subroutines (of the aforemen93
tioned main algorithms) as are used in this specifcation.
94
95
96
97
98

NIST will develop a validation program to test implementations for conformance to thealgorithms in this standard. Information about validation programs is available at https://csrc.nist.gov/projects/cmvp. Example values for cryptographic algorithms are available athttps://csrc.nist.gov/projects/cryptographic-standards-and-guidelines/example-values.

99 8. Other Approved Security Functions. Implementations that comply with this standard shall
employ cryptographic algorithms that have been approved for protecting Federal Government100
sensitive information. Approved cryptographic algorithms and techniques include those that101
are either:102103(a) Specifed in a Federal Information Processing Standards (FIPS) publication,

104(b) Adopted in a FIPS or NIST recommendation, or

105(c) Specifed in the list of approved security functions for FIPS 140-3.

106 9. Export Control. Certain cryptographic devices and technical data regarding them are subject
to federal export controls. Exports of cryptographic modules that implement this standard107
and technical data regarding them must comply with all federal laws and regulations and108
be licensed by the Bureau of Industry and Security of the U.S. Department of Commerce.
109
Information about export regulations is available at https://www.bis.doc.gov.
110
111 10. Patents. NIST has entered into two patent license agreements to facilitate the adoption of
NIST’s announced selection of public-key encryption PQC algorithm CRYSTALS-K YBER.
112
NIST and the licensing parties share a desire, in the public interest, the licensed patents be
113
freely available to be practiced by any implementer of the ML-KEM algorithm as published by
114
NIST. ML-KEM is the name given to the algorithm in this standard derived from CRYSTALS115
KYBER. For a summary and extracts from the license, please see https://csrc.nist.gov/csrc/m116
edia/Projects/post-quantum-cryptography/documents/selected-algos-2022/nist-pqc-license117
summary-and-excerpts.pdf. Implementation of the algorithm specifed in the standard may be
118
covered by U.S. and foreign patents of which NIST is not aware.
119

ii

FIPS 203 (D RAFT )M ODULE -L ATTICE - BASED K EY-E NCAPSULATION M ECHANISM

120 11. Implementation Schedule. This standard becomes effective immediately upon fnal publica121tion.
122 12. Specifcations. Federal Information Processing Standards (FIPS) 203, Module-Lattice-based
123
Key-Encapsulation Mechanism Standard (affxed).
124 13. Qualifcations. In applications, the security guarantees of a KEM only hold under certain
conditions (see NIST SP 800-227 [1]). One such condition is the secrecy of several values,
125
including the randomness used by the two parties, the decapsulation key, and the shared secret126
key itself. Users shall, therefore, guard against the disclosure of these values.
127
128
129
130
131

While it is the intent of this standard to specify general requirements for implementing
ML-KEM algorithms, conformance to this standard does not ensure that a particular implementation is secure. It is the responsibility of the implementer to ensure that any module that
implements a key establishment capability is designed and built in a secure manner.

132
133
134
135

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

136
137
138

NIST will continue to follow developments in the analysis of the ML-KEM algorithm. As
with its other cryptographic algorithm standards, NIST will formally reevaluate this standard
every fve years.

139
140
141
142
143

Both this standard and possible threats that reduce the security provided through the use ofthis standard will undergo review by NIST as appropriate, taking into account newly available
analysis and technology. In addition, the awareness of any breakthrough in technology or
any mathematical weakness of the algorithm will cause NIST to reevaluate this standard andprovide necessary revisions.

144 14. Waiver Procedure. The Federal Information Security Management Act (FISMA) does
not allow for waivers to Federal Information Processing Standards (FIPS) that are made145
mandatory by the Secretary of Commerce.
146
147 15. 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 the148same website.
149
150 16. How to Cite this Publication. NIST has assigned NIST FIPS 203 ipd as the publication
identifer for this FIPS, per the NIST Technical Series Publication Identifer Syntax. NIST
151
recommends that it be cited as follows:
152
153
154
155
156

National Institute of Standards and Technology (2023) Module-Lattice-based KeyEncapsulation Mechanism Standard. (Department of Commerce, Washington,
D.C.), Federal Information Processing Standards Publication (FIPS) NIST FIPS
203 ipd. https://doi.org/10.6028/NIST.FIPS.203.ipd

157 17. Inquiries and Comments. Inquiries and comments about this FIPS may be submitted to
fps-203-comments@nist.gov.
158

iii

FIPS 203 (D RAFT )M ODULE -L ATTICE - BASED K EY-E NCAPSULATION M ECHANISM

159 Call for Patent Claims
160
161
162
163
164
165

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 bedirectly stated in this ITL Publication or by reference to another publication. This call also
includes disclosure, where known, of the existence of pending U.S. or foreign patent applications
relating to this ITL draft publication and of any relevant unexpired U.S. or foreign patents.

166 ITL may require from the patent holder, or a party authorized to make assurances on its behalf, in
167 written or electronic form, either:168
169a) assurance in the form of a general disclaimer to the effect that such party does not hold anddoes not currently intend holding any essential patent claim(s); or

170
171
172

b) 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:

173
174

(i) under reasonable terms and conditions that are demonstrably free of any unfair
discrimination; or

175
176

(ii) without compensation and under reasonable terms and conditions that are demonstrably free of any unfair discrimination.

177
178
179
180
181

Such assurance shall indicate that the patent holder (or third party authorized to make assuranceson its behalf) will include in any documents transferring ownership of patents subject to theassurance, provisions suffcient to ensure that the commitments in the assurance are binding on
the transferee, and that the transferee will similarly include appropriate provisions in the event of
future transfers with the goal of binding each successor-in-interest.

182 The assurance shall also indicate that it is intended to be binding on successors-in-interest
183 regardless of whether such provisions are included in the relevant transfer documents.
184 Such statements should be addressed to: fps-203-comments@nist.gov.

iv

FIPS 203 (D RAFT )M ODULE -L ATTICE - BASED K EY-E NCAPSULATION M ECHANISM

185

Federal Information Processing Standards Publication 203

186

Specifcation for the

187
188

Module-Lattice-based Key-Encapsulation
Mechanism Standard

189

Table of Contents

190 1

Introduction

1

191

1.1

Purpose and Scope

1

192

1.2

Context

1

193

1.3

Differences From the CRYSTALS-K YBER Submission

2

194 2

Glossary of Terms, Acronyms, and Mathematical Symbols

3

195

2.1

Terms and Defnitions

3

196

2.2

Acronyms

4

197

2.3

Mathematical Symbols

5

198

2.4

Interpreting the Pseudocode

6

199 3

Overview of the ML-KEM Scheme

11

200

3.1

Key-Encapsulation Mechanisms

11

201

3.2

The ML-KEM Scheme

12

202

3.3

Requirements for ML-KEM Implementations

14

203 4

Auxiliary Algorithms

16

204

4.1

Cryptographic Functions

16

205

4.2

General Algorithms
4.2.1 Conversion and Compression Algorithms
4.2.2 Sampling Algorithms
The Number-Theoretic Transform
4.3.1 Multiplication in the NTT Domain

17
17
19
21
23

206
207
208

4.3

209
210 5

The K-PKE Component Scheme

25

211

5.1

K-PKE Key Generation

25

212

5.2

K-PKE Encryption

26

213

5.3

K-PKE Decryption

28v

FIPS 203 (D RAFT )M ODULE -L ATTICE - BASED K EY-E NCAPSULATION M ECHANISM

214 6

The ML-KEM Key-Encapsulation Mechanism

29

215

6.1

ML-KEM Key Generation

29

216

6.2

ML-KEM Encapsulation

30

217

6.3

ML-KEM Decapsulation

31

218 7

Parameter Sets

33

219 References

35

220 Appendix A — Security Strength Categories

37

vi

FIPS 203 (D RAFT )M ODULE -L ATTICE - BASED K EY-E NCAPSULATION M ECHANISM

221

List of Tables

222
223
224
225
226
227

Table 1 Decapsulation failure rates for ML-KEM
Table 2 Approved parameter sets for ML-KEM
Table 3 Sizes (in bytes) of keys and ciphertexts of ML-KEM
Table 4 NIST Security Strength Categories
Table 5 Estimates for classical and quantum gate counts for the optimal key recovery
and collision attacks on AES and SHA-3

228

List of Figures

229

Figure 1

A simple view of key establishment using a KEM

39

11

List of Algorithms

230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247

14
33
33
38

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

ForExample . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
BitsToBytes(b) . . . . . . . . . . . . . . . . . . . . . . . . . . . .
BytesToBits(B) . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ByteEncoded (F) . . . . . . . . . . . . . . . . . . . . . . . . . . .
ByteDecoded (B) . . . . . . . . . . . . . . . . . . . . . . . . . . . .
SampleNTT(B) . . . . . . . . . . . . . . . . . . . . . . . . . . . .
SamplePolyCBDη (B) . . . . . . . . . . . . . . . . . . . . . . . . .
NTT( f ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
NTT−1 ( fˆ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
MultiplyNTTs( fˆ, ĝ) . . . . . . . . . . . . . . . . . . . . . . . . . .
BaseCaseMultiply(a0 , a1 , b0 , b1 , γ) . . . . . . . . . . . . . . . . . .
K-PKE.KeyGen() . . . . . . . . . . . . . . . . . . . . . . . . . . .
K-PKE.Encrypt(ekPKE , m, r) . . . . . . . . . . . . . . . . . . . . .
K-PKE.Decrypt(dkPKE , c) . . . . . . . . . . . . . . . . . . . . . .
ML-KEM.KeyGen() . . . . . . . . . . . . . . . . . . . . . . . . .
ML-KEM.Encaps(ek) . . . . . . . . . . . . . . . . . . . . . . . .
ML-KEM.Decaps(c, dk) . . . . . . . . . . . . . . . . . . . . . . .

vii

7
17
18
19
19
20
20
22
23
24
24
26
27
28
29
30
32

FIPS 203 (D RAFT )M ODULE -L ATTICE - BASED K EY-E NCAPSULATION M ECHANISM

248

1. Introduction

249

1.1

250
251
252
253
254
255
256

This standard specifes the Module-Lattice-based Key-Encapsulation Mechanism, or ML-KEM.
A key-encapsulation mechanism (or KEM) is a set of algorithms that can be used to establish
a shared secret key between two parties communicating over a public channel. A KEM is aparticular type of key establishment scheme. Current NIST-approved key establishment schemes
are specifed in NIST SP-800-56A, Recommendation for Pair-Wise Key-Establishment Schemes
Using Discrete Logarithm-Based Cryptography [2], and NIST SP-800-56B, Recommendation for
Pair-Wise Key Establishment Schemes Using Integer Factorization Cryptography [3].

257
258
259
260
261
262
263

It is well-known that the key establishment schemes specifed in NIST SP-800-56A and NIST
SP-800-56B are vulnerable to attacks using suffciently capable quantum computers. ML-KEM
is an approved alternative that is presently believed to be secure even against adversaries
in possession of a quantum computer. ML-KEM is derived from the round-three versionof the CRYSTALS-K YBER KEM [4], a submission in the NIST post-quantum cryptography
standardization project. For the differences between ML-KEM and CRYSTALS-K YBER, see
Section 1.3.

264
265
266
267
268

This standard specifes the algorithms and parameter sets of the ML-KEM scheme. It aims toprovide suffcient information for implementing ML-KEM in a manner that can pass validation(see https://csrc.nist.gov/projects/cryptographic-module-validation-program). For general
defnitions and properties of KEMs, including requirements for the secure use of KEMs inapplications, see NIST SP 800-227 [1].

269
270
271
272

This standard specifes three parameter sets for ML-KEM. These parameter sets offer different trade-offs in security strength versus performance. All three parameter sets of ML-KEM
are approved to protect sensitive, non-classifed communication systems of the U.S. Federal
Government.

273

1.2

274
275
276
277
278
279
280
281

Over the past several years, there has been steady progress toward building quantum computers.
If large-scale quantum computers are realized, the security of many commonly used public-key
cryptosystems will be at risk. This would include key-establishment schemes and digital signatureschemes that are based on integer factorization and discrete logarithms (both over fnite felds andelliptic curves). As a result, in 2016, the National Institute of Standards and Technology (NIST)
initiated a public process to select quantum-resistant public-key cryptographic algorithms forstandardization. A total of 82 candidate algorithms were submitted to NIST for consideration forstandardization.

282
283
284
285
286
287

After three rounds of evaluation and analysis, NIST selected the frst four algorithms to standardize as a result of the Post-Quantum Cryptography (PQC) Standardization process. Thesealgorithms are intended to protect sensitive U.S. Government information well into the foreseeable future, including after the advent of quantum computers. This standard specifes a variantof the selected algorithm CRYSTALS-K YBER, a lattice-based key-encapsulation mechanism(KEM) [4]. Throughout this standard, the KEM specifed here will be referred to as ML-KEM,

Purpose and Scope

Context

1

FIPS 203 (D RAFT )M ODULE -L ATTICE - BASED K EY-E NCAPSULATION M ECHANISM

288 as it is based on the so-called Module Learning With Errors assumption.
289

1.3

Differences From the CRYSTALS-K YBER Submission

290
291
292
293
294
295
296
297
298

Below is a list of all scheme differences between CRYSTALS-K YBER (as described in [4]) andthe ML-KEM scheme specifed in this document. The list consists only of those differences that
result in differing input-output behavior of the main algorithms (i.e., KeyGen, Encaps, Decaps) of
CRYSTALS-K YBER and ML-KEM. Recall that a conforming implementation need only matchthe input-output behavior of these three algorithms (see “Implementations” above, and Section 3.3
below). Consequently, the list below does not include any of the numerous differences in how
the main algorithms actually produce outputs from inputs (e.g., via different computational steps
or different subroutines). The list below also does not include any differences in presentation
between this standard and [4].

299
300
301
302
303

• In the third-round specifcation [4], the shared secret key was treated as a variable-length
value whose length depends on how this key would be used in the relevant application. In
this specifcation, the length of the shared secret key is fxed to 256 bits. In this specifcation,
this key can be used directly in applications as a symmetric key; alternatively, symmetrickeys can be derived from this key, as specifed in Section 3.3.

304
305
306
307
308

• The ML-KEM.Encaps and ML-KEM.Decaps algorithms in this specifcation use a different variant of the Fujisaki-Okamoto transform (see [5, 6]) than the third-round specifcation [4]. Specifcally, ML-KEM.Encaps no longer includes a hash of the ciphertext inthe derivation of the shared secret, and ML-KEM.Decaps has been adjusted to match thischange.

309
310
311
312
313
314

• In the third-round specifcation [4], the initial randomness m in the ML-KEM.Encaps
algorithm was frst hashed before being used. Specifcally, between lines 1 and 2 inAlgorithm 16, there was an additional step that performed the operation m ← H(m). The
purpose of this step was to safeguard against the use of fawed randomness generation
processes. As this standard requires the use of NIST-approved randomness generation, thisstep is unnecessary and is not performed in ML-KEM.

315
316
317
318

• This specifcation includes explicit input validation steps that were not part of the thirdround specifcation [4]. For example, ML-KEM.Encaps requires that the byte array
containing the encapsulation key correctly decodes to an array of integers modulo q without
any modular reductions.

2FIPS 203 (D RAFT )M ODULE -L ATTICE - BASED K EY-E NCAPSULATION M ECHANISM

2. Glossary of Terms, Acronyms, and Mathematical Sym320 bols
319

321

2.1

Terms and Defnitions

322
323
324
325

approved

FIPS-approved and/or NIST-recommended. An algorithm or techniquethat is either 1) specifed in a FIPS or NIST recommendation, 2) adopted
in a FIPS or NIST recommendation, or 3) specifed in a list of NISTapproved security functions.

326
327
328

decapsulation

The process of applying the Decaps algorithm of a KEM. This algorithm accepts a KEM ciphertext and the decapsulation key as input andproduces a shared secret key as output.

329
330
331

decapsulation key

A cryptographic key produced by a KEM during key generation andused during the decapsulation process. The decapsulation key must be
kept private, and must be destroyed after it is no longer needed.

332
333
334

decryption key

A cryptographic key that is used with a PKE in order to decrypt ciphertexts into plaintexts. The decryption key must be kept private, and must
be destroyed after it is no longer needed.

335
336

destroy

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

337
338
339

encapsulation

The process of applying the Encaps algorithm of a KEM. This algorithm
accepts private randomness and the encapsulation key as input andproduces a shared secret key and an associated ciphertext as output.

340
341
342

encapsulation key

A cryptographic key produced by a KEM during key generation andused during the encapsulation process. The encapsulation key can bemade public.

343
344

encryption key

A cryptographic key that is used with a PKE in order to encrypt plaintexts into ciphertexts. The encryption key can be made public.

345
346
347

equivalent process

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

348
349
350

hash function

A function on bit strings in which the length of the output is fxed.
Approved hash functions relevant to this standard are specifed in FIPS
202 [7].

351
352

KEM ciphertext

A bit string that is produced by encapsulation and used as an input todecapsulation.

353
354
355
356

key

A bit string that is used in conjunction with a cryptographic algorithm.
Examples applicable to this standard include: the encapsulation anddecapsulation keys (of a KEM), the shared secret key (produced by aKEM), and the encryption and decryption keys (of a PKE).
3FIPS 203 (D RAFT )M ODULE -L ATTICE - BASED K EY-E NCAPSULATION M ECHANISM

357
358
359

key-encapsulation
mechanism (KEM)

A set of three cryptographic algorithms (KeyGen, Encaps, and Decaps)that can be used by two parties to establish a shared secret key over a
public channel.

360
361
362
363

key pair

A set of two keys with the property that one key can be made public
while the other key must be kept private. In this standard, this could
refer to either the (encapsulation key, decapsulation key) key pair of a
KEM, or the (encryption key, decryption key) key pair of a PKE.

364
365
366

party

An individual (person), organization, device, or process. In this specifcation, there are two parties (Party A and Party B, or Alice and Bob),and they jointly perform the key establishment process using a KEM.

367
368
369
370
371
372

pseudorandom

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

373
374

public channel

A communication channel between two parties; such a channel can beobserved and possibly also corrupted by third parties.

375
376
377

public-key
encryption scheme(PKE)

A set of three cryptographic algorithms (KeyGen, Encrypt, and Decrypt)
that can be used by two parties to send secret data over a public channel.
Also known as an asymmetric encryption scheme.

378
379
380

shared secret key

The fnal result of a KEM key establishment process. It is a cryptographic key that can be used for symmetric-key cryptography. It must
be kept private, and it must be destroyed when no longer needed.

381
382

security category

A number associated with the security strength of a post-quantum cryptographic algorithm as specifed by NIST (see Appendix A, Table 4).

383
384

security strength

A number associated with the amount of work that is required to breaka cryptographic algorithm or system.

385

shall

Used to indicate a requirement of this standard.

386
387
388

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

389
390

2.2

Acronyms

391

AES

Advanced Encryption Standard

392

CBD

Centered Binomial Distribution

393

FIPS

Federal Information Processing Standard
4

FIPS 203 (D RAFT )M ODULE -L ATTICE - BASED K EY-E NCAPSULATION M ECHANISM

394

KEM

Key-encapsulation Mechanism

395

LWE

Learning With Errors

396

MLWE

Module Learning with Errors

397

NIST

National Institute of Standards and Technology

398

NISTIRNIST Interagency or Internal Report

399

NTT

Number-Theoretic Transform

400

PKE

Public-Key Encryption

401

PQC

Post-Quantum Cryptography

402

PRF

Pseudorandom Function

403

RBG

Random Bit Generator

404

SHA

Secure Hash Algorithm

405

SHAKE

Secure Hash Algorithm K ECCAK

406

SP

Special Publication

407

XOF

Extendable-Output Function

408
409

2.3

Mathematical Symbols

410
411

S∗

If S is a set, this denotes the set of fnite-length tuples (or arrays) of elementsfrom the set S, including the empty tuple (or empty array).

412
413

Sk

If S is a set, this denotes the set of k-tuples (or length-k arrays) of elementsfrom the set S.

414
415

BitRev7 (r)Bit reversal of a seven-bit integer r. Specifcally, if r = r0 + 2r1 + 4r2 + · · · +64r6 with ri ∈ {0, 1}, then BitRev7 (r) = r6 + 2r5 + 4r4 + · · · + 64r0 .

416
417

fˆ

The element of Tq that is equal to the NTT representation of a polynomialf ∈ Rq (see Section 4.3).

418

Q

The set of rational numbers.

419
420

Zm

The ring of integers modulo m, i.e., the set {0, 1, . . . , m − 1} equipped withthe operations of addition and multiplication modulo m.

421

Z

The set of integers.

422

vT , ATThe transpose of a row or column v; also, the transpose of a matrix A.

423

fj

The coeffcient of X j of a polynomial f = f0 + f1 X + · · · + f255 X 255 ∈ Rq .

424

r mod mThe unique integer r′ in {0, 1, . . . , m − 1} such that m divides r − r′ .

5FIPS 203 (D RAFT )M ODULE -L ATTICE - BASED K EY-E NCAPSULATION M ECHANISM

425
426
427

r mod± m

For m even (respectively, odd), this denotes the unique integer r′ such that−m/2 < r′ ≤ m/2 (respectively, −(m−1)/2 ≤ r′ ≤ (m−1)/2) and m divides
r − r′ .

428
429

|B|

If B is a number, this denotes the absolute value of B. If B is an array, thisdenotes its length.

430

⌈x⌉

The ceiling of x, i.e., the smallest integer greater than or equal to x.

431
432

⌈x⌋

The rounding of x to the nearest integer; if x = y + 1/2 for some y ∈ Z, then⌈x⌋ = y + 1.

433

⌊x⌋

The foor of x, i.e., the largest integer less than or equal to x.

434

B

The set {0, 1, . . . , 255} of unsigned 8-bit integers (bytes).

435

A∥B

The concatenation of two arrays or bit strings A and B.

436

B[i]

The entry at index i in the array B. All arrays have indices that begin at zero.

437

B[k : m]The subarray (B[k], B[k + 1], . . . , B[m − 1]) of the array B.

438nDenotes the integer 256 throughout this document.

439

qDenotes the prime integer 3329 = 28 · 13 + 1 throughout this document.

440
441
442

Rq

The ring Zq [X]/(X n + 1) consisting of polynomials of the form f = f0 +f1 X + · · · + f255 X 255 where f j ∈ Zq for all j, equipped with addition andmultiplication modulo X n + 1.

443
444

s←x

In pseudocode, this notation means that the variable s is assigned the valueof the expression x.

445
446
447

$
Bℓ
s ←−

In pseudocode, this notation means that the variable s is assigned the value ofan array of ℓ random bytes. The bytes must be generated using randomness
from an approved RBG (see Section 3.3).

448
449

Tq

The image of Rq under the number-theoretic transform. Its elements arecalled “NTT representations” of polynomials in Rq (see Section 4.3).

450

2.4

Interpreting the Pseudocode

451
452
453
454
455

This section outlines the conventions of the pseudocode used to describe the algorithms in thisstandard. All algorithms are understood to have access to two global integer constants: n = 256
and q = 3329. There are also fve global integer variables: k, η 1 , η 2 , du and dv . All other variables
are local. The fve global variables are set to particular values when a parameter set is selected(see Section 7).

456 When algorithms in this specifcation invoke other algorithms as subroutines, all arguments
457 (inputs) are passed by value. In other words, a copy of the inputs is created, and the subroutine is
458 invoked with the copie. There is no “passing by reference.”459
460 Data types. For variables that represent the input or output of an algorithm, the data type (e.g.,

6

FIPS 203 (D RAFT )M ODULE -L ATTICE - BASED K EY-E NCAPSULATION M ECHANISM

461
462
463
464
465

bit, byte, array of bits) will be explicitly described at the start of the algorithm. For most local
variables in the pseudocode, the data type is easily deduced from context. For all other variables,
the data type will be declared in a comment. In a single algorithm, the data type of a variable isdetermined the frst time that the variable is used and will not be changed. Variable names can
and will be reused across different algorithms, including with different data types.

466
467
468
469

In addition to standard atomic data types (e.g., bits, bytes) and data structures (e.g., arrays),integers modulo m (i.e., elements of Zm ) will also be used as an abstract data type. It is implicit
that reduction modulo m takes place whenever an assignment is made to a variable in Zm . For
example, for z ∈ Zm and any integers x, y, the statementz ← x+y(2.1)

470 means that z is assigned the value x + y mod m. The pseudocode is agnostic regarding how an
471 integer modulo m is represented in actual implementations or how modular reduction is computed.
472
473 Loop syntax. The pseudocode will make use of both “while” and “for” loops. The “while” syntax
474 is self-explanatory. In the case of “for” loops, the syntax will be in the style of the programming
475 language C. Two simple examples are given in Algorithm 1.

Algorithm 1 ForExample
Performs two simple “for” loops.
1: for (i ← 0; i < 10; i ++)2:
A[i] ← i
3: end for
4: j ← 0
5: for (k ← 256; k > 1; k ← k/2)
6:
B[ j] ← k7:
j ← j+1
8: end for▷ A is an integer array of length 10▷ A now has the value (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)▷ B is an integer array of length 8▷ B now has the value (256, 128, 64, 32, 16, 8, 4, 2)

Arithmetic with arrays of integers. This standard makes extensive use of arrays of integers
modulo m (i.e., elements of Zℓm ). In a typical case, the relevant values are m = q and ℓ = n = 256.
Arithmetic with arrays in Zℓm will be done as follows. Let a ∈ Zm and X,Y ∈ Zℓm . The statements
Z ← a·X
W ← X +Y
476
477
478
479

will result in two arrays Z,W ∈ Zℓm , with the property that Z[i] = a · X[i] and W [i] = X[i] +Y [i]for all i. Multiplication of arrays in Zℓm will only be meaningful when m = q and ℓ = n = 256, in
which case it corresponds to multiplication in a particular ring. This operation will be describedin (2.2) below.

480
481 Representations of algebraic objects. An essential operation in ML-KEM is the number-

7

FIPS 203 (D RAFT )

482
483
484
485

M ODULE -L ATTICE - BASED K EY-E NCAPSULATION M ECHANISM

theoretic transform (NTT), which maps a polynomial f in a certain ring Rq to its “NTT representation” fˆ in a different ring Tq . The rings Rq and Tq and the NTT are discussed in detail in
Section 4.3. This standard will represent elements of Rq and elements of Tq in pseudocode usingarrays of integers modulo q, as follows.
An element f of Rq is a polynomial of the formf = f0 + f1 X + · · · + f255 X 255 ∈ Rq
and will be represented in pseudocode by the array( f0 , f1 , . . . , f255 ) ∈ Z256q

486 whose entries contain the coeffcients of f . Abusing notation somewhat, this array will also be
487 denoted by f . The i-th entry of the array f will thus contain the i-th coeffcient of the polynomial
488 f (i.e., f [i] = fi ).

An element (sometimes called “NTT representation”) ĝ of Tq is a tuple of 128 polynomials, eachof degree at most one. Specifcally,ĝ = (ĝ0,0 + ĝ0,1 X, ĝ1,0 + ĝ1,1 X, . . . , ĝ127,0 + ĝ127,1 X) ∈ Tq .
Such an algebraic object will be represented in pseudocode by the array(ĝ0,0 , ĝ0,1 , ĝ1,0 , ĝ1,1 , . . . , ĝ127,0 , ĝ127,1 ) ∈ Z256q .
489 Abusing notation somewhat, this array will also be denoted by ĝ. In this case, the mapping
490 between array entries and coeffcients is ĝ[2i] = ĝi,0 and ĝ[2i + 1] = ĝi,1 for i ∈ {0, 1, . . . , 127}.
491 Converting between a polynomial f ∈ Rq and its NTT representation fˆ ∈ Tq will be done via the492 algorithms NTT (Algorithm 8) and NTT−1 (Algorithm 9). These algorithms act on arrays of
493 coeffcients, as described above, and satisfy fˆ = NTT( f ) and f = NTT−1 ( fˆ).
494
495
496
497
498
499
500
501
502

Arithmetic with polynomials and NTT representations. The algebraic operations of additionand scalar multiplication in Rq and Tq are done coordinate-wise. For example, if a ∈ Zq and f ∈ Rq ,the i-th coeffcient of the polynomial a · f ∈ Rq is equal to a · fi mod q. In pseudocode, elementsof both Rq and Tq are represented by coeffcient arrays (i.e., elements of Z256q ), as described above.
The algebraic operations of addition and scalar multiplication are thus performed by addition andscalar multiplication of the corresponding coeffcient arrays. For example, the addition of two
NTT representations in pseudocode is performed by a statement of the form ĥ ← fˆ + ĝ, whereĥ, fˆ, ĝ ∈ Z256
q are coeffcient arrays.

503
504
505
506

The algebraic operations of multiplication in Rq and Tq are treated as follows. For effciency
reasons, multiplication in Rq will not be used. The algebraic meaning of multiplication in Tq is
discussed in Section 4.3.1. In pseudocode, it will be performed by the algorithm MultiplyNTTs(Algorithm 10). Specifcally, if fˆ, ĝ ∈ Z256
q are a pair of arrays (each representing the NTT of

8

FIPS 203 (D RAFT )M ODULE -L ATTICE - BASED K EY-E NCAPSULATION M ECHANISM

507 some polynomial), thenĥ ← fˆ ×Tq ĝĥ ← MultiplyNTTs( fˆ, ĝ) .

means

(2.2)

508 The result is an array hˆ ∈ Z256
q .
509
510
511
512
513
514

Matrices and vectors. In addition to arrays of integers modulo q, the pseudocode will also make256 3
use of arrays whose entries are themselves elements of Z256
q . For example, an element v ∈ (Zq )will be a length-three array whose entries v[0], v[1] and v[2] are themselves elements of Z256
q (i.e.,arrays). One can think of each of these entries as representing a polynomial in Rq , so that v itself
represents an element of the module R3q .

515
516
517
518
519
520

When arrays are used to represent matrices and vectors whose entries are elements of Rq , they
will be denoted with bold letters (e.g., v for vectors and A for matrices). When arrays are used
to represent matrices and vectors whose entries are elements of Tq , they will be denoted with a“hat” (e.g., v̂ and Â). Unless an explicit transpose operation is performed, it is understood that
vectors are column vectors. One can then view vectors as the special case of matrices with only
one column.

521 Converting between matrices over Rq and matrices over Tq will be done coordinate-wise. Specifk×ℓ , then the statement
522 cally, if A ∈ (Z256q )Â ← NTT(A)k×ℓ such that Â[i, j] = NTT(A[i, j]) for all i, j. This involves runningˆ ∈ (Z256
523 will result in Aq )524 NTT a total of k · ℓ times. Note that the case of vectors corresponds to ℓ = 1.

525
526 Arithmetic with matrices and vectors. The following describes how to perform arithmetic with
527 matrices while continuing to view vectors as a special case of matrices.

Addition and scalar multiplication is performed coordinate-wise. Addition of matrices over Rq
and Tq is then straightforward. In the case of Tq , scalar multiplication is done via (2.2). Forkˆ ∈ (Z256
example, if fˆ ∈ Z256
q and û, vq ) , thenŵ ← fˆ · ûẑ ← û + v̂kˆ
528 will result in ŵ, ẑ ∈ (Z256q ) satisfying ŵ[i] = f ×Tq û[i] and ẑ[i] = û[i] + v̂[i] for all i. Note that529 the multiplication and addition of individual entries here is performed using the appropriate
530 arithmetic for coeffcient arrays of elements of Tq .

It will also be necessary to multiply matrices with entries in Tq . This is done using standard
matrix multiplication with the base-case multiplication (i.e., multiplication of individual entries)
being multiplication in Tq . If Â and B̂ are two matrices with entries in Tq , their matrix productwill be denoted Â ◦ B̂. Some example pseudocode statements involving matrix multiplication are
given below. In these examples, Â is a k × k matrix, while û and v̂ are vectors of length k. All
9FIPS 203 (D RAFT )M ODULE -L ATTICE - BASED K EY-E NCAPSULATION M ECHANISM

three of these objects are represented in pseudocode by arrays: a k × k array for Â and length-karrays for û and v̂. The entries of Â, û, and v̂ are elements of Z256
q . The frst two pseudocode
statements below produce a new length-k vector whose entries are specifed on the right-handside. The third pseudocode statement computes a dot product; the result is therefore in the basering (i.e., Tq ), and is represented by an element zˆ of Z256q .
k−1ŵ ← Â ◦ uˆŵ[i] = ∑ Â[i, j] ×Tq û[ j]
j=0

k−1

ŷ ← Â⊺ ◦ ûŷ[i] = ∑ Â[ j, i] ×Tq û[ j]
j=0

k−1

ẑ ← û⊺ ◦ v̂ẑ = ∑ û[ j] ×Tq v̂[ j]j=0531 The multiplication ×Tq of individual entries above is performed using MultiplyNTTs, as described
532 in (2.2) above.
533
534
535
536
537
538

Applying algorithms to arrays. The conventions of coordinate-wise arithmetic described above
will also be extended to algorithms that act on (and/or produce) an atomic data type. Whenthe pseudocode invokes such an algorithm on an array input, it is implied that the algorithm isinvoked repeatedly for each entry of the array. For example, the function Compressd : Zq → Z2d
defned in Section 4 can be invoked on an array input F ∈ Z256
q with the statement
K ← Compressd (F) .

(2.3)

and K[i] = Compressd (F[i]) for every i. This computation
539 The result will be that K ∈ Z2562d
540 involves running the Compress algorithm 256 times.

10

FIPS 203 (D RAFT )

541

3.

M ODULE -L ATTICE - BASED K EY-E NCAPSULATION M ECHANISM

Overview of the ML-KEM Scheme

542 This section gives a high-level overview of the ML-KEM scheme.
543

3.1

Key-Encapsulation Mechanisms

544 The following is a brief and informal overview of key-encapsulation mechanisms (or KEMs). For
545 more details, see NIST SP 800-227 [1].
546 A key-encapsulation mechanism (or KEM) is a set of algorithms that can be used, under certain
547 conditions, to establish a shared secret key between two communicating parties. This shared
548 secret key can then be used for symmetric-key cryptography.
549 A KEM consists of three algorithms and a collection of parameter sets. The three algorithms are:550

• a key generation algorithm denoted by KeyGen;

551• an "encapsulation" algorithm denoted by Encaps;

552• a "decapsulation" algorithm denoted by Decaps.

553 The collection of parameter sets is used to select a trade-off between security and effciency.
554 Each parameter set in the collection is a list of specifc numerical values, one for each parameter
555 required by the above algorithms.

KeyGenencapsulation key

Encapsdecapsulation key

ciphertext

Bob’s copy of theshared secret key

DecapsAlice’s copy of theshared secret key

Figure 1. A simple view of key establishment using a KEM
556 A KEM can be used to establish a shared secret key between two parties (see Figure 1) referred
557 to here as Alice and Bob. Alice begins by running KeyGen in order to generate a (public)
558 encapsulation key and a (private) decapsulation key. Upon obtaining Alice’s encapsulation key,

11

FIPS 203 (D RAFT )

559
560
561
562

M ODULE -L ATTICE - BASED K EY-E NCAPSULATION M ECHANISM

Bob runs the Encaps algorithm; this produces Bob’s copy KB of the shared secret key along withan associated ciphertext. Bob sends the ciphertext to Alice, and Alice completes the process byrunning the Decaps algorithm using her decapsulation key and the ciphertext; this step produces
Alice’s copy KA of the shared secret key.

563 After completing the process above, Alice and Bob would like to conclude that their individual
564 outputs satisfy KA = KB and that this value is a secure, random, shared secret key. However, these565 properties only hold under certain important assumptions, as discussed in NIST SP 800-227 [1].
566

3.2

The ML-KEM Scheme

567 ML-KEM is a key-encapsulation mechanism based on CRYSTALS-K YBER [4], a scheme
568 that was initially described in [8]. The following is a brief and informal description of the569 computational assumption underlying ML-KEM, and how the ML-KEM scheme is constructed.
570
571
572
573
574
575

The computational assumption. The security of ML-KEM is based on the presumed diffcultyof solving the so-called Module Learning with Errors (MLWE) problem [9], a generalization of
the Learning with Errors (LWE) problem introduced by Regev in 2005 [10]. The hardness of the
MLWE problem is itself based on the presumed hardness of certain computational problems inmodule lattices [9]. This motivates the name of the scheme ML-KEM.

576
577
578
579
580
581
582
583
584

In the LWE problem, the input is a set of random “noisy" linear equations in some secretvariables x ∈ Znq , and the task is to recover x. The noise in the equations is such that standard
algorithms (e.g., Gaussian elimination) are intractable. The LWE problem lends itself naturally tocryptographic applications. For example, if x is interpreted as a secret key, then one can encrypt a
one-bit value by sampling either an approximately correct linear equation (if the bit value is zero)or a far-from-correct linear equation (if the bit value is one). Plausibly, only a party in possessionof x can then distinguish these two cases. Encryption can then be delegated to another party by
publishing a large collection of noisy linear equations, which can be combined appropriately by
the encrypting party. The result is an asymmetric encryption scheme.

585 At a high level, the MLWE problem poses the same task as LWE but with Znq replaced with the
586 module Rkq constructed by taking the k-fold Cartesian product of a certain polynomial ring Rq for
587 some integer k > 1. In particular, the secret is now an element x of the module Rkq .
588
589
590
591
592
593
594
595

The ML-KEM construction. At a high level, the ML-KEM construction proceeds in two
steps. First, the idea mentioned above is used to construct a public-key encryption schemefrom the MLWE problem. Second, this public-key encryption scheme is converted into a
key-encapsulation mechanism using the so-called Fujisaki-Okamoto (FO) transform [11, 12].
In addition to producing a KEM, the FO transform is also intended to provide security in asignifcantly more general adversarial attack model. As a result, ML-KEM is believed to satisfy
so-called IND-CCA security [1, 4, 13].

596
597
598
599

The specifcation of the ML-KEM algorithms in this standard will follow the above pattern.
Specifcally, this standard will frst describe a public-key encryption scheme called K-PKE andthen use the algorithms of K-PKE as subroutines when describing the algorithms of ML-KEM.
The cryptographic transformation from K-PKE to ML-KEM is crucial for achieving full security.
12

FIPS 203 (D RAFT )M ODULE -L ATTICE - BASED K EY-E NCAPSULATION M ECHANISM

600 The scheme K-PKE is not suffciently secure and shall not be used as a stand-alone scheme (see601 Section 3.3).
602
603
604
605

A notable feature of ML-KEM is the use of the number-theoretic transform (NTT). The NTT
converts a polynomial f ∈ Rq to an alternative representation as a vector fˆ of linear polynomials.
Although NTT representations enable fast multiplication, other operations such as rounding andsampling must be applied to standard polynomial representations.

606
607
608
609

ML-KEM satisfes the key properties of KEM correctness, and a proof of asymptotic theoreticalsecurity (in a certain heuristic model) is known [4]. Each of the parameter sets of ML-KEM
comes with an associated security strength, which was estimated based on current cryptanalysis(see Section 7 for details).

610
611 Parameter sets and algorithms. Recall that a KEM consists of algorithms KeyGen, Encaps,
612 and Decaps, together with a collection of parameter sets. In the case of ML-KEM, the three
613 aforementioned algorithms are:614

• ML-KEM.KeyGen (Algorithm 15);615

• ML-KEM.Encaps (Algorithm 16);616

• ML-KEM.Decaps (Algorithm 17).

617 These algorithms are described and discussed in detail in Section 6.
618 ML-KEM comes equipped with three parameter sets:619• ML-KEM-512 (security category 1);

620• ML-KEM-768 (security category 3);621• ML-KEM-1024 (security category 5).

622
623
624
625
626

These parameter sets are described and discussed in detail in Section 7; the security categories
1-5 are defned in Appendix A. Each parameter set assigns a particular numerical value to fve
integer variables: k, η 1 , η 2 , du , and dv . The values of these variables in each parameter set are
given in Table 2 of Section 7. In addition to these fve variable parameters, there are also two
constants: n = 256 and q = 3329.

627
628
629
630
631
632
633
634
635
636

Decapsulation failures. Provided all inputs are well-formed, the key establishment procedure of
ML-KEM will never explicitly fail. Specifcally, the ML-KEM.Encaps and ML-KEM.Decaps
algorithms will always output a value with the same data type as a shared secret key, and will never
output an error or failure symbol. However, it is possible (though extremely unlikely) that theprocess will fail in the sense that Alice (via ML-KEM.Decaps) and Bob (via ML-KEM.Encaps)
will produce different outputs, even though both of them are behaving honestly and no adversarial
interference is present. In this case, Alice and Bob clearly did not succeed in producing a sharedsecret key. This event is called a decapsulation failure. The decapsulation failure probability isdefned to be the probability that the process637

1. (ek, dk) ← ML-KEM.KeyGen()
13

FIPS 203 (D RAFT )M ODULE -L ATTICE - BASED K EY-E NCAPSULATION M ECHANISM

638

2. (c, K) ← ML-KEM.Encaps(ek)639

3. K ′ ← ML-KEM.Decaps(c, dk)

640 results in K ̸= K ′ (i.e., the encapsulated key is different from the decapsulated key). Estimates for
641 the decapsulation failure probability (or rate) for each of the ML-KEM parameter sets are given
642 in Table 1 (see [4]).

Table 1. Decapsulation failure rates for ML-KEM
Parameter set
ML-KEM-512
ML-KEM-768
ML-KEM-1024

Decapsulation failure rate
2−139
2−164
2−174

643
644
645
646
647
648
649
650
651
652

A note on terminology for keys. A KEM involves three different types of keys: encapsulation
keys, decapsulation keys, and shared secret keys. ML-KEM is built on top of the component
public-key encryption scheme K-PKE, and K-PKE has two additional key types: encryption
keys and decryption keys. In the literature, encapsulation keys and encryption keys are sometimes
referred to as “public keys,” while decapsulation keys and decryption keys can sometimes bereferred to as “private keys.” In order to reduce confusion, this standard will not use the terms“public key” and “private key.” Instead, keys will be referred to using the more specifc terms
above (i.e., encapsulation key, decapsulation key, encryption key, decryption key, or shared secret
key).

653

3.3

Requirements for ML-KEM Implementations

654 This section describes several requirements for implementing the algorithms of ML-KEM.
655 Requirements for using ML-KEM in specifc applications are given in NIST SP 800-227 [1].
656
657
658
659
660
661

K-PKE is only a component. The public-key encryption scheme K-PKE described in Section
5 shall not be used as a stand-alone cryptographic scheme. Instead, the algorithms that comprise
K-PKE may only be used as subroutines in the algorithms of ML-KEM. In particular, the algorithms K-PKE.KeyGen (Algorithm 12), K-PKE.Encrypt (Algorithm 13), and K-PKE.Decrypt(Algorithm 14) are not approved for use as a public-key encryption scheme.

662
663
664
665
666

Equivalent implementations. Each of the three top-level algorithms (i.e., ML-KEM.KeyGen,
ML-KEM.Encaps, and ML-KEM.Decaps) defnes a particular mathematical operation, mapping
any given input to a corresponding output. For example, the operation defned by the algorithm
ML-KEM.Encaps takes one byte array as input and produces two byte arrays as output.

667
668
669
670

In this standard, the three operations defned by ML-KEM.KeyGen, ML-KEM.Encaps, and
ML-KEM.Decaps are described using particular sequences of computational steps. A conforming implementation can replace each of these sequences with a different sequence of steps,
provided that the resulting operation is an equivalent process to the one specifed in this standard.
14

FIPS 203 (D RAFT )M ODULE -L ATTICE - BASED K EY-E NCAPSULATION M ECHANISM

671 For example, a conforming implementation of the encapsulation operation must have the property
672 that, for any parameter set and any input byte array ek, the distribution of output byte arrays is
673 identical to the distribution ML-KEM.Encaps(ek) as specifed in this standard.
674
675
676
677
678
679
680

Approved usage of the shared secret key. The output of the encapsulation and decapsulation
algorithms of ML-KEM is always a 256-bit value. Under appropriate conditions (see above; seealso NIST SP 800-227 [1]), this output is a shared secret key K. This shared secret key K canbe used directly as a key for symmetric cryptography. When key derivation is needed, the fnal
symmetric key(s) shall be derived from this 256-bit shared secret key K in an approved manner,as specifed in NIST SP 800-108 [14].

681
682
683
684
685
686
687
688
689

Randomness generation. Three algorithms in this standard require the generation of randomness:
K-PKE.KeyGen, ML-KEM.KeyGen, and ML-KEM.Encaps. In pseudocode, the step in which$
this randomness is generated is denoted by a pseudocode statement of the form m ←−B32 . A fresh
string of random bytes must be generated for every such invocation. These random bytes shallbe generated using an approved RBG, as prescribed in NIST SP 800-90A, NIST SP 800-90B,
and NIST SP 800-90C [15, 16, 17]. Moreover, the RBG used shall have a security strength of atleast 128 bits for ML-KEM-512, at least 192 bits for ML-KEM-768, and at least 256 bits for
ML-KEM-1024.

690
691
692
693
694
695
696
697

Input validation. The algorithms ML-KEM.Encaps and ML-KEM.Decaps require input validation. Implementers shall ensure that ML-KEM.Encaps and ML-KEM.Decaps are only
executed on validated inputs, as described in Section 6. As discussed above, implementers canchoose to implement the top-level algorithms (i.e., ML-KEM.Encaps, ML-KEM.Decaps, or
ML-KEM.KeyGen) using any equivalent process; the validation of inputs is considered part ofthis process. A conforming implementation shall be equivalent to frst validating the input, andthen running the appropriate algorithm.

698
699 Destruction of intermediate values. Data used internally by KEM algorithms in intermediate
700 computation steps could be used by an adversary to compromise security. Implementers shall,
701 therefore, ensure that such intermediate data is destroyed as soon as it is no longer needed.
702
703 No foating-point arithmetic. Implementations of ML-KEM should not use foating-point
704 arithmetic. All division and rounding steps in the algorithms of ML-KEM can be performed
705 within the set of rational numbers.

15

FIPS 203 (D RAFT )M ODULE -L ATTICE - BASED K EY-E NCAPSULATION M ECHANISM

706

4.

Auxiliary Algorithms

707

4.1

Cryptographic Functions

708
709
710
711

The algorithms specifed in this publication require the use of several cryptographic functions.
Each function shall be instantiated by means of an approved hash function or an approved
eXtendable-Output function (XOF), as prescribed below. The relevant hash functions and XOFs
are described in detail in FIPS 202 [7]. They will be used as follows.

712 SHA3-256 and SHA3-512 are hash functions with variable-length input and fxed-length output.
713 In this standard, invocations of these functions on an input M will be denoted by SHA3-256(M)714 and SHA3-512(M), respectively.
715
716
717
718
719
720
721
722

SHAKE128 and SHAKE256 are XOFs with variable-length input and variable-length output.
Invocations of these functions on an input M will be denoted in two different ways, dependingon whether the desired output length ℓ (in bytes) is known at invocation time. If ℓ is known at
invocation time, the invocation will be denoted by SHAKE128(M, ℓ) or SHAKE256(M, ℓ). For
SHAKE128, the output length will sometimes not be known at invocation time; in those cases,
the invocation will be denoted by SHAKE128(M) and the hashing routine will behave like a byte
stream that provides pseudorandom bytes (by performing additional “squeezing” rounds [7]) until
no more bytes are needed.

723 The above functions will play several different roles in the algorithms specifed in this standard.
724 It will be convenient to assign a specifc notation to each of these roles, as follows.
725
726 Pseudorandom function (PRF). The function PRF takes a parameter η ∈ {2, 3}, one 32-byte
727 input, and one 1-byte input. It produces one (64 · η )-byte output. It will be denoted by PRF :728 {2, 3} × B32 × B → B64η , and it shall be instantiated as

PRFη (s, b) := SHAKE256(s∥b, 64 · η ) ,(4.1)

729 where η ∈ {2, 3}, s ∈ B32 , and b ∈ B. Here, η is only used to specify the desired output length
730 and not to perform domain separation. Note that the output length parameter for SHAKE256 is
731 specifed in bytes.
732
733 eXtendable-output function (XOF). The function XOF takes one 32-byte input and two 1734 byte inputs. It produces a variable-length output. This function will be denoted by XOF :735 B32 × B × B → B∗ , and it shall be instantiated as

XOF(ρ, i, j) := SHAKE128(ρ∥i∥ j) ,
736
737
738
739

(4.2)

where ρ ∈ B32 , i ∈ B, and j ∈ B. The function XOF will only be invoked to provide a streamof pseudorandom bytes for the sampling algorithm SampleNTT (Algorithm 6). As SampleNTT
performs rejection sampling, the total number of needed bytes will not be known at the time thatXOF is invoked.

740

16

FIPS 203 (D RAFT )M ODULE -L ATTICE - BASED K EY-E NCAPSULATION M ECHANISM

741 Three hash functions. The specifcation will also make use of three hash function instantiations
742 H, J, and G, as follows.
743 The functions H and J each take one variable-length input and produce one 32-byte output. They744 will be denoted by H : B∗ → B32 and J : B∗ → B32 , respectively, and shall be instantiated as

H(s) := SHA3-256(s)andJ(s) := SHAKE256(s, 32)(4.3)

745 where s ∈ B∗ .
746 The function G takes a variable-length input and produces two 32-byte outputs. It will be denoted
747 by G : B∗ → B32 × B32 . The two outputs of G will be denoted by, e.g., (a, b) ← G(c), where
748 a, b ∈ B32 , c ∈ B∗ , and G(c) = a∥b. The function G shall be instantiated as

G(c) := SHA3-512(c) .

(4.4)

749
750
751

4.2

General Algorithms

752 This section specifes a number of algorithms that will be used as subroutines in the main
753 ML-KEM algorithms. For a discussion of how to interpret the pseudocode of these algorithms,
754 see Section 2.4.
755 4.2.1

Conversion and Compression Algorithms

756 This section specifes several algorithms for converting between bit arrays, byte arrays, and arrays757 of integers modulo m. it also specifes a certain compression operation for integers modulo q, as
758 well as the corresponding decompression operation.
759
760 Converting between bits and bytes. Algorithms 2 and 3 convert between bit arrays and byte
761 arrays. The inputs to BitsToBytes and the outputs of BytesToBits are bit arrays, with each762 segment of 8 bits representing a byte in little-endian order.

Algorithm 2 BitsToBytes(b)Converts a bit string (of length a multiple of eight) into an array of bytes.
Input: bit array b ∈ {0, 1}8·ℓ .
Output: byte array B ∈ Bℓ .
1: B ← (0, . . . , 0)
2: for (i ← 0; i < 8ℓ; i ++)3:
B [⌊i/8⌋] ← B [⌊i/8⌋] + b[i] · 2i mod 8
4: end for5: return B

17

FIPS 203 (D RAFT )M ODULE -L ATTICE - BASED K EY-E NCAPSULATION M ECHANISM

Algorithm 3 BytesToBits(B)Performs the inverse of BitsToBytes, converting a byte array into a bit array.
Input: byte array B ∈ Bℓ .
Output: bit array b ∈ {0, 1}8·ℓ .
1: for (i ← 0; i < ℓ; i ++)2:for ( j ← 0; j < 8; j ++)3:b[8i + j] ← B[i] mod 2
4:
B[i] ← ⌊B[i]/2⌋
5:
end for
6: end for7: return bCompression and decompression. Recall that q = 3329, and note that the bit length of q is 12.
For d < 12, defne
Compressd : Zq −→ Z2d

(4.5)

d

x 7−→ ⌈(2 /q) · x⌋ .
Decompressd : Z2d −→ Zq

(4.6)

d

y 7−→ ⌈(q/2 ) · y⌋ .
763 Note that the input and output types of these functions are integers modulo m (see discussion
764 of types in Section 2.4). Division and rounding in the computation of the above functions are
765 performed in the set of rational numbers. Floating-point computations should not be used.
766
767
768
769
770
771

Informally, Compress discards low-order bits of the input, and Decompress adds low-order bits
set to zero. These algorithms satisfy two important properties. First, decompression followedby compression preserves the input, that is, Compressd (Decompressd (y)) = y for all y ∈ Zq andall d < 12. Second, if d is large (i.e., close to 12) — meaning that the number of discarded
bits is small — compression followed by decompression does not signifcantly alter the value.
Specifcally,[Decompressd (Compressd (x)) − x] mod± q ≤ ⌈q/2d+1 ⌋(4.7)

772 for all x ∈ Zq and all d < 12.
773
774
775
776
777
778

Encoding and decoding. The algorithms ByteEncode (Algorithm 4) and ByteDecode (Algorithm5) will be used for serialization and deserialization of arrays of integers modulo m. All serialized
arrays will be of length n = 256. ByteEncoded serializes an array of d-bit integers into an arrayof 32 · d bytes. ByteDecoded performs the corresponding deserialization operation, converting anarray of 32 · d bytes into an array of d-bit integers.

779 For the following discussion, it is convenient to view ByteDecode and ByteEncode as converting
780 between integers and bits. (The conversion between bits and bytes is straightforward and done
781 using BitsToBytes and BytesToBits.)

18

FIPS 203 (D RAFT )M ODULE -L ATTICE - BASED K EY-E NCAPSULATION M ECHANISM

782
783
784
785

The valid range of values for the parameter d is 1 ≤ d ≤ 12. Bit arrays are divided into d-bit
segments. In the case where 1 ≤ d ≤ 11, ByteDecoded converts each d-bit segment of the input
into one integer modulo 2d , and ByteEncoded performs the inverse operation. In this case, theconversion is one-to-one.

786
787
788
789
790
791
792

The case d = 12 is treated differently. In this case, ByteEncode12 receives integers modulo q
as input, and ByteDecode12 produces integers modulo q as output. ByteDecode12 converts each12-bit segment of the input into an integer modulo 212 = 4096, and then reduces the result modulo
q. This is no longer a one-to-one operation. Indeed, some 12-bit segments could correspond to an
integer greater than q = 3329 but less than 4096; however, this cannot occur for arrays produced
by ByteEncode12 . These aspects of ByteDecode12 and ByteEncode12 will be important when
considering validation of the ML-KEM encapsulation key in Section 6.
Algorithm 4 ByteEncoded (F)Encodes an array of d-bit integers into a byte array, for 1 ≤ d ≤ 12.
dInput: integer array F ∈ Z256
m , where m = 2 if d < 12 and m = q if d = 12.
Output: byte array B ∈ B32d .
1: for (i ← 0; i < 256; i ++)2:
a ← F[i]▷ a ∈ Z2d3:for ( j ← 0; j < d; j ++)4:b[i · d + j] ← a mod 2▷ b ∈ {0, 1}256·d5:a ← (a − b[i · d + j])/2▷ note a − b[i · d + j] is always even.
6:
end for
7: end for
8: B ← BitsToBytes(b)9: return B

Algorithm 5 ByteDecoded (B)Decodes a byte array into an array of d-bit integers, for 1 ≤ d ≤ 12.
Input: byte array B ∈ B32d .
d
Output: integer array F ∈ Z256
m , where m = 2 if d < 12 and m = q if d = 12.
1: b ← BytesToBits(B)
2: for (i ← 0; i < 256; i ++)−1j3:
F[i] ← ∑dj=
0 b[i · d + j] · 2 mod m
4: end for5: return F
793 4.2.2
794
795
796
797
798

Sampling Algorithms

The algorithms of ML-KEM require two sampling subroutines that are specifed in Algorithms 6
and 7. Both of these algorithms can be used to convert a stream of uniformly random bytes into asample from some desired distribution. In this standard, these algorithms will be invoked with astream of pseudorandom bytes as the input. It follows that the output will then be a sample froma distribution that is computationally indistinguishable from the desired distribution.
19

FIPS 203 (D RAFT )

799
800
801
802
803

M ODULE -L ATTICE - BASED K EY-E NCAPSULATION M ECHANISM

Uniform sampling of NTT representations. The algorithm SampleNTT (Algorithm 6) converts
a stream of bytes into a polynomial in the NTT domain. If the input stream consists of uniformly
random bytes, then the result will be drawn uniformly at random from Tq . The output is an arrayin Z256
q that contains the coeffcients of the sampled element of Tq (see Section 2.4).
Algorithm 6 SampleNTT(B)
If the input is a stream of uniformly random bytes, the output is a uniformly random element of Tq .
Input: byte stream B ∈ B∗ .
Output: array aˆ ∈ Z256q .
1: i ← 0
2: j ← 0
3: while j < 256 do
4:
d1 ← B[i] + 256 · (B[i + 1] mod 16)
5:
d2 ← ⌊B[i + 1]/16⌋ + 16 · B[i + 2]
6:
if d1 < q then7:â[ j] ← d1
8:j ← j+1
9:
end if10:
if d2 < q and j < 256 then11:â[ j] ← d2
12:j ← j+1
13:
end if14:i ← i+3
15: end while
16: return â▷ the coeffcients of the NTT of a polynomial▷ aˆ ∈ Z256
q

Algorithm 7 SamplePolyCBDη (B)
If the input is a stream of uniformly random bytes, outputs a sample from the distribution Dη (Rq ).
Input: byte array B ∈ B64η .
Output: array f ∈ Z256q .
1: b ← BytesToBits(B)
2: for (i ← 0; i < 256; i ++)η −1
3:x ← ∑ j=0 b[2iη + j]

▷ the coeffcients of the sampled polynomialη −1y ← ∑ j=0 b[2iη + η + j]
5:f [i] ← x − y mod q
6: end for7: return f
4:▷ f ∈ Z256q

804
805 Sampling from the centered binomial distribution. ML-KEM makes use of a special distri806 bution Dη (Rq ) of polynomials in Rq with small coeffcients. Such polynomials will sometimes

20

FIPS 203 (D RAFT )M ODULE -L ATTICE - BASED K EY-E NCAPSULATION M ECHANISM

807
808
809
810
811

be referred to as “errors” or “noise.” The distribution is parameterized by an integer η ∈ {2, 3}.
To sample a polynomial from Dη (Rq ), each of its coeffcients is independently sampled from acertain centered binomial distribution (CBD) on Zq . The algorithm SamplePolyCBD (Algorithm7) samples the coeffcient array of a polynomial f ∈ Rq according to the distribution Dη (Rq ),provided that its input is a stream of uniformly random bytes.

812

4.3

813
814
815
816
817

The number-theoretic transform (or NTT) can be viewed as a specialized, exact version of thediscrete Fourier transform. In the case of ML-KEM, the NTT is used to improve the effciency ofmultiplication in the ring Rq . Recall that Rq is the ring Zq [X]/(X n + 1) consisting of polynomialsof the form f = f0 + f1 X + · · · + f255 X 255 where f j ∈ Zq for all j, equipped with arithmetic
modulo X n + 1.

818
819
820
821

The ring Rq is naturally isomorphic to another ring, denoted Tq , which is a direct sum of 128
quadratic extensions of Zq . The NTT is a computationally effcient isomorphism between these
two rings. On input a polynomial f ∈ Rq , the NTT outputs an element fˆ := NTT( f ) of the ring
Tq , where fˆ is called the “NTT representation” of f . The isomorphism property implies that

The Number-Theoretic Transformf ×Rq g = NTT−1 ( fˆ ×Tq ĝ),
822
823
824
825

(4.8)

where ×Rq and ×Tq denote multiplication in Rq and Tq , respectively. Moreover, since Tq is a
product of 128 rings, each consisting of degree-one polynomials, the operation ×Tq is much more
effcient than the operation ×Rq . For these reasons, the NTT is considered to be an integral partof ML-KEM and not merely an optimization.

826 As the rings Rq and Tq have a vector space structure over Zq , the most natural abstract data type
827 to represent elements from either of these rings is Znq . For this reason, the choice of data structure
828
829
830
831
832
833

for the inputs and outputs of NTT and NTT−1 are length-n arrays of integers modulo q; thesearrays are understood to represent elements of Tq or Rq , respectively (see Section 2.4). Both NTT
and NTT−1 can be computed in-place. In fact, Algorithms 8 and 9 demonstrate an effcient meansof computing NTT and NTT−1 in-place. However, for clarity in understanding the distinctionof the algebraic objects before and after the conversion, the algorithms are written with explicit
inputs and outputs.

834
835
836
837
838

The mathematical structure of a simple NTT. Recall that, in ML-KEM, q is the prime
3329 = 28 · 13 + 1 and n = 256. There are 128 primitive 256-th roots of unity and no primitive
512-th roots of unity in Zq . Note that ζ = 17 ∈ Zq is a primitive 256-th root of unity modulo q.
Thus ζ 128 ≡ −1.

839 Defne BitRev7 (i) to be the integer represented by bit-reversing the unsigned 7-bit value that
840 corresponds to the input integer i ∈ {0, . . . , 127}.
841 The polynomial X 256 + 1 factors into 128 polynomials of degree 2 modulo q as follows:127 X 256 + 1 = ∏ X 2 − ζ 2BitRev7 (k)+1 .
k=0

21

(4.9)

FIPS 203 (D RAFT )M ODULE -L ATTICE - BASED K EY-E NCAPSULATION M ECHANISM

842 Therefore, Rq := Zq [X]/(X 256 + 1) is isomorphic to a direct sum of 128 quadratic extension felds
843 of Zq , denoted Tq . Specifcally, this ring has the structure

Tq :=

127
M



Zq [X]/ X 2 − ζ 2BitRev7 (k)+1 .

(4.10)

k=0

844 Thus, the NTT representation fˆ ∈ Tq of a polynomial f ∈ Rq is the vector that consists of the845 corresponding degree one residues:fˆ := f mod (X 2 − ζ 2BitRev7 (0)+1 ), . . . , f mod (X 2 − ζ 2BitRev7 (127)+1 ) .

(4.11)

846 In the algorithms below, fˆ is stored as an array of 256 integers modulo q. Specifcally,f mod (X 2 − ζ 2BitRev7 (i)+1 ) = fˆ[2i] + fˆ[2i + 1]X.
847 for i from 0 to 127.

Algorithm 8 NTT( f )Computes the NTT representation fˆ of the given polynomial f ∈ Rq .
▷ the coeffcients of the input polynomial
Input: array f ∈ Z256
q .
256
ˆ
Output: array f ∈ Zq .
▷ the coeffcients of the NTT of the input polynomial
1: fˆ ← f
▷ will compute NTT in-place on a copy of input array
2: k ← 1
3: for (len ← 128; len ≥ 2; len ← len/2)
4:for (start ← 0; start < 256; start ← start + 2 · len)zeta ← ζ BitRev7 (k) mod q
5:6:k ← k+1
7:
for ( j ← start; j < start + len; j ++)8:t ← zeta · fˆ[ j + len]▷ steps 8-10 done modulo qˆˆ9:f [ j + len] ← f [ j] − t
10:fˆ[ j] ← fˆ[ j] + t
11:
end for12:
end for
13: end for
14: return fˆ

848
849
850
851
852
853
854

The ML-KEM NTT algorithms. An algorithm for the NTT is described in Algorithm 8. An
algorithm for the Inverse-NTT is described in Algorithm 9. These two algorithms are overloadedin this standard. First, they represent the transformation used to map elements of Rq to elementsof Tq (using NTT) and vice versa (using NTT−1 ). Second, they represent the coordinate-wisetransformation of structures over those rings; specifcally, they map matrices/vectors with entries
in Rq to matrices/vectors with entries in Tq (using NTT) and vice versa (using NTT−1 ).
22

FIPS 203 (D RAFT )M ODULE -L ATTICE - BASED K EY-E NCAPSULATION M ECHANISM

Algorithm 9 NTT−1 ( fˆ)Computes the polynomial f ∈ Rq corresponding to the given NTT representation fˆ ∈ Tq .
▷ the coeffcients of input NTT representation
Input: array fˆ ∈ Z256
q .
Output: array f ∈ Z256
▷ the coeffcients of the inverse-NTT of the input
q .
1: f ← fˆ▷ will compute in-place on a copy of input array
2: k ← 127
3: for (len ← 2; len ≤ 128; len ← 2 · len)4:for (start ← 0; start < 256; start ← start + 2 · len)zeta ← ζ BitRev7 (k) mod q
5:k ← k−16:
7:
for ( j ← start; j < start + len; j ++)8:t ← f [ j]9:f [ j] ← t + f [ j + len]▷ steps 9-10 done modulo q
10:
f [ j + len] ← zeta · ( f [ j + len] − t)11:
end for12:
end for
13: end for
14: f ← f · 3303 mod q▷ multiply every entry by 3303 ≡ 128−1 mod q
15: return f

855 4.3.1

Multiplication in the NTT Domain

856 As discussed in Section 2.4, addition and scalar multiplication of elements of Tq is straightforward:
857 it can be done using the corresponding coordinate-wise arithmetic operations on the coeffcient
858 arrays. This section describes how to do the remaining ring operation (i.e., multiplication in Tq ).
859
860
861
862

Recall from (4.11) that fˆ ∈ Tq is a vector of 128 degree one residues modulo quadratic polynomials.
Algebraically, multiplication in the ring Tq consists of independent multiplication in each of the
128 coordinates with respect to the quadratic modulus of that coordinate. Specifcally, the i-thcoordinate in Tq of the product ĥ = fˆ ×Tq ĝ is determined by the calculationˆˆ + 1]X = ( fˆ[2i] + fˆ[2i + 1]X)(ĝ[2i] + ĝ[2i + 1]X) mod (X 2 − ζ 2BitRev7 (i)+1 ). (4.12)h[2i]+ h[2i

863
864
865
866

Thus, one can compute the product of two elements of Tq using the algorithm MultiplyNTTs(Algorithm 10). Note that MultiplyNTTs uses BaseCaseMultiply (Algorithm 11) as a subroutine.
As discussed in Section 2.4, MultiplyNTTs enables one to perform linear-algebraic arithmetic
operations with matrices and vectors with entries in Tq .

23

FIPS 203 (D RAFT )M ODULE -L ATTICE - BASED K EY-E NCAPSULATION M ECHANISM

Algorithm 10 MultiplyNTTs( fˆ, ĝ)Computes the product (in the ring Tq ) of two NTT representations.
256▷ the coeffcients of two NTT representations
Input: Two arrays fˆ ∈ Z256
q and ĝ ∈ Zq .
256
ˆ
Output: An array h ∈ Zq .
▷ the coeffcients of the product of the inputs
1: for (i ← 0; i < 128; i ++)2:(ĥ[2i], ĥ[2i + 1]) ← BaseCaseMultiply( fˆ[2i], fˆ[2i + 1], ĝ[2i], ĝ[2i + 1], ζ 2BitRev7 (i)+1 )3: end for
4: return ĥAlgorithm 11 BaseCaseMultiply(a0 , a1 , b0 , b1 , γ)Computes the product of two degree-one polynomials with respect to a quadratic modulus.
Input: a0 , a1 , b0 , b1 ∈ Zq .
Input: γ ∈ Zq .
Output: c0 , c1 ∈ Zq .
1: c0 ← a0 · b0 + a1 · b1 · γ
2: c1 ← a0 · b1 + a1 · b0
3: return c0 , c1

▷ the coeffcients of a0 + a1 X and b0 + b1 X
▷ the modulus is X 2 − γ▷ the coeffcients of the product of the two polynomials▷ steps 1-2 done modulo q24

FIPS 203 (D RAFT )

867

5.

M ODULE -L ATTICE - BASED K EY-E NCAPSULATION M ECHANISM

The K-PKE Component Scheme

868 This section describes the component scheme K-PKE. As discussed in Section 3.3, K-PKE is869 not approved for use in a stand-alone fashion. It serves only as a collection of subroutines for
870 use in the algorithms of the approved scheme ML-KEM, as described in Section 6.
871 K-PKE consists of three algorithms:872

1. Key generation (K-PKE.KeyGen);873

2. Encryption (K-PKE.Encrypt);874

3. Decryption (K-PKE.Decrypt).

875
876
877
878
879

When K-PKE is instantiated as part of ML-KEM, K-PKE inherits the parameter set selected
for ML-KEM. Each parameter set specifes numerical values for each parameter. While n isalways 256 and q is always 3329, the values of the remaining parameters k, η 1 , η 2 , du , and dv vary
among the three parameter sets. The individual parameters and the parameter sets are describedin Section 7.

880
881
882
883

The algorithms in this section do not perform any input validation. This is because they are
only invoked as subroutines of the main ML-KEM algorithms. The algorithms of ML-KEM
do perform input validation as needed; they also ensure that all inputs to K-PKE algorithms(invoked as subroutines) will be valid.

884
885
886
887
888
889
890

Each of the algorithms of K-PKE below is accompanied by a brief, informal description in text.
For simplicity, this description is written in terms of vectors and matrices whose entries are
elements of Rq . In the actual algorithm, most of the computations occur in the NTT domain inorder to improve the effciency of multiplication. The relevant vectors and matrices will thenhave entries in Tq . Linear-algebraic arithmetic with such vectors and matrices (see, e.g., line 19of K-PKE.KeyGen) is performed as described in Sections 2.4 and 4.3.1. The encryption anddecryption key of K-PKE are also stored in the NTT form.

891

5.1

892
893
894
895
896
897
898
899

The key generation algorithm K-PKE.KeyGen of K-PKE (Algorithm 12) takes no input, requires
randomness, and outputs an encryption key ekPKE and a decryption key dkPKE . From the typicalpoint of view of public-key encryption, the encryption key can be made public, while thedecryption key and the randomness must remain private. This will be the case in the context
of this standard as well. Indeed, the encryption key of K-PKE will serve as the encapsulation
key of ML-KEM (see ML-KEM.KeyGen below) and can thus be made public; meanwhile, thedecryption key and randomness of K-PKE.KeyGen must remain private as they can be used toperform decapsulation in ML-KEM.

900
901
902
903
904
905

Informal description. The decryption key of K-PKE.KeyGen is a length-k vector s of elementsof Rq , i.e., s ∈ Rkq . Roughly speaking, s is a set of secret variables, while the encryption key is acollection of “noisy” linear equations (A, As + e) in the secret variables s. The rows of the matrix
A form the equation coeffcients. This matrix is generated pseudorandomly using XOF, with
only the seed stored in the encryption key. The secret s and the “noise” e are sampled from the

K-PKE Key Generation

25

FIPS 203 (D RAFT )M ODULE -L ATTICE - BASED K EY-E NCAPSULATION M ECHANISM

Algorithm 12 K-PKE.KeyGen()
Generates an encryption key and a corresponding decryption key.
Output: encryption key ekPKE ∈ B384k+32 .
Output: decryption key dkPKE ∈ B384k .
$1: d ←− B32
2: (ρ, σ ) ← G(d)3: N ← 0
4: for (i ← 0; i < k; i ++)5:for ( j ← 0; j < k; j ++)6:Â[i, j] ← SampleNTT(XOF(ρ, i, j))7:
end for
8: end for
9: for (i ← 0; i < k; i ++)10:s[i] ← SamplePolyCBDη 1 (PRFη 1 (σ , N))
11:
N ← N +1
12: end for
13: for (i ← 0; i < k; i ++)▷ d is 32 random bytes (see Section 3.3)
▷ expand to two pseudorandom 32-byte seedsk×kˆ (Z256▷ generate matrix A∈q )▷ each entry of Â uniform in NTT domain▷ generate s ∈ (Zq256 )k▷ s[i] ∈ Z256
q sampled from CBD▷ generate e ∈ (Zq256 )k▷ e[i] ∈ Z256
q sampled from CBD

14:e[i] ← SamplePolyCBDη 1 (PRFη 1 (σ , N))
15:
N ← N +1
16: end for
17: ŝ ← NTT(s)▷ NTT is run k times (once for each coordinate of s)
18: ê ← NTT(e)▷ NTT is run k times
19: t̂ ← Â ◦ ŝ + ê
▷ noisy linear system in NTT domain
20: ekPKE ← ByteEncode12 (t̂)∥ρ▷ ByteEncode12 is run k times; include seed for Â
21: dkPKE ← ByteEncode12 (ŝ)▷ ByteEncode12 is run k times
22: return (ekPKE , dkPKE )906 centered binomial distribution using randomness expanded from a seed via PRF. Once A and s
907 and e are generated, the computation of the fnal part t = As + e of the encryption key takes place.
908
909
910
911

In K-PKE.KeyGen, the choice of parameter set affects the length of the secret s (via the parameterk) and, as a consequence, the sizes of the noise vector e and the pseudorandom matrix A. The
choice of parameter set also affects the noise distribution (via the parameter η 1 ) used to sample
the entries of s and e.

912

5.2

913
914
915
916
917

The encryption algorithm K-PKE.Encrypt of K-PKE (Algorithm 13) takes an encryption key
ekPKE and a plaintext m as input, requires randomness r, and outputs a ciphertext c. While many algorithms specifed in this document require randomness, only the description of K-PKE.Encryptinterprets this randomness as part of the input. This is because ML-KEM will need to invoke
K-PKE.Encrypt with a specifc choice of randomness (see Algorithm 16 for details).

K-PKE Encryption

918

26

FIPS 203 (D RAFT )

919
920
921
922
923

M ODULE -L ATTICE - BASED K EY-E NCAPSULATION M ECHANISM

Informal description. The algorithm K-PKE.Encrypt begins by extracting the vector t andthe seed from the encryption key. The seed is then expanded to re-generate the matrix A, inthe same manner as was done in K-PKE.KeyGen. If t and A are derived correctly from an
encryption key produced by K-PKE.KeyGen, then they are equal to their corresponding valuesin K-PKE.KeyGen.
Algorithm 13 K-PKE.Encrypt(ekPKE , m, r)
Uses the encryption key to encrypt a plaintext message using the randomness r.
Input: encryption key ekPKE ∈ B384k+32 .
Input: message m ∈ B32 .
Input: encryption randomness r ∈ B32 .
Output: ciphertext c ∈ B32(du k+dv ) .
1: N ← 0
2: t̂ ← ByteDecode12 (ekPKE [0 : 384k])
3: ρ ← ekPKE [384k : 384k + 32]
4: for (i ← 0; i < k; i ++)5:for ( j ← 0; j < k; j ++)6:Â[i, j] ← SampleNTT(XOF(ρ, i, j))7:
end for
8: end for
9: for (i ← 0; i < k; i ++)10:r[i] ← SamplePolyCBDη 1 (PRFη 1 (r, N))
11:
N ← N +1
12: end for
13: for (i ← 0; i < k; i ++)14:
e1 [i] ← SamplePolyCBDη 2 (PRFη 2 (r, N))
15:
N ← N +1
16: end for
17: e2 ← SamplePolyCBDη (PRFη 2 (r, N))2
18: r̂ ← NTT(r)19: u ← NTT−1 (Â⊺ ◦ r̂) + e1
20: µ ← Decompress1 (ByteDecode1 (m)))
21: v ← NTT−1 (t̂⊺ ◦ r̂) + e2 + µ
22: c1 ← ByteEncodedu (Compressdu (u))
23: c2 ← ByteEncodedv (Compressdv (v))
24: return c ← (c1 ∥c2 )

924
925
926
927
928
929
930

▷ extract 32-byte seed from ekPKE
ˆ (Zq256 )k×k
▷ re-generate matrix A∈▷ generate r ∈ (Zq256 )k▷ r[i] ∈ Z256
q sampled from CBD▷ generate e1 ∈ (Zq256 )k▷ e1 [i] ∈ Z256
q sampled from CBD▷ sample e2 ∈ Z256
q from CBD▷ NTT is run k times▷ NTT−1 is run k times▷ encode plaintext m into polynomial v.
▷ ByteEncodedu is run k times

Recall from the description of key generation that the pair (A, t = As + e) can be thought of as asystem of noisy linear equations in the secret variables s. One can generate an additional noisy
linear equation in the same secret variables — without knowing s — by picking a random linear
combination of the noisy equations in the system (A, t). One can then encode information in the“constant term” (i.e., the entry which is a linear combination of entries of t) of such a combined
equation. This information can then be deciphered by a party in possession of s. For example,
one could encode a single bit by deciding whether or not to signifcantly alter the constant term,
27

FIPS 203 (D RAFT )M ODULE -L ATTICE - BASED K EY-E NCAPSULATION M ECHANISM

931
932
933
934

thus making either a nearly correct equation (corresponding to the decrypted bit value of 0) or a
far-from-correct equation (corresponding to the decrypted bit value of 1). In the case of K-PKE,
the constant term is a polynomial with 256 coeffcients, so one can encode more information: one
bit in each coeffcient.

935
936
937
938
939
940

To this end, K-PKE.Encrypt proceeds by generating a vector r ∈ Rkq and noise terms e1 ∈ Rkq ande2 ∈ Rq , all of which are sampled from the centered binomial distribution using pseudorandomness
expanded (via PRF) from the input randomness r. One then computes the “new noisy equation”
which is (up to some details) computed by (u, v) ← (A⊺ r + e1 , t⊺ r + e2 ). An appropriate encodingµ of the input message m is then added to the term t⊺ r + e2 . Finally, the pair (u, v) is compressed,
serialized into a byte array, and output as the ciphertext.

941

5.3

K-PKE Decryption

942 The decryption algorithm K-PKE.Decrypt of K-PKE (Algorithm 14) takes a decryption key
943 dkPKE and a ciphertext c as input, requires no randomness, and outputs a plaintext m.
944
945
946
947
948
949
950

Informal description. The algorithm K-PKE.Decrypt begins by computing the “noisy equation”(u, v) underlying the ciphertext c, as discussed in the description of K-PKE.Encrypt. Here, one
can think of u as the coeffcients of the equation and v as the constant term. Recall that thedecryption key dkPKE contains the vector of secret variables s. The decryption algorithm can thus
use the decryption key to compute the true constant term v′ = s⊺ u and then calculate v − v′ . The
decryption algorithm ends by decoding the plaintext message m from v − v′ and outputting m.
Algorithm 14 K-PKE.Decrypt(dkPKE , c)Uses the decryption key to decrypt a ciphertext.
Input: decryption key dkPKE ∈ B384k .
Input: ciphertext c ∈ B32(du k+dv ) .
Output: message m ∈ B32 .
1: c1 ← c[0 : 32du k]
2: c2 ← c[32du k : 32(du k + dv )]3: u ← Decompressdu (ByteDecodedu (c1 ))4: v ← Decompressdv (ByteDecodedv (c2 ))5: ŝ ← ByteDecode12 (dkPKE )6: w ← v − NTT−1 (ŝ⊺ ◦ NTT(u))
7: m ← ByteEncode1 (Compress1 (w))
8: return m▷ ByteDecodedu invoked k times▷ NTT−1 and NTT invoked k times▷ decode plaintext m from polynomial v

28

FIPS 203 (D RAFT )

951

6.

M ODULE -L ATTICE - BASED K EY-E NCAPSULATION M ECHANISM

The ML-KEM Key-Encapsulation Mechanism

952 The ML-KEM scheme consists of three algorithms:953

1. Key generation (ML-KEM.KeyGen)

954

2. Encapsulation (ML-KEM.Encaps)

955

3. Decapsulation (ML-KEM.Decaps)

956
957
958
959
960
961
962
963
964

To instantiate ML-KEM, one must select a parameter set, each of which is associated with aparticular trade-off between security and performance. The three possible parameter sets are called
ML-KEM-512, ML-KEM-768, and ML-KEM-1024 and are described in detail in Table 2 ofSection 7. Each parameter set assigns specifc numerical values to the individual parameters n,
q, k, η 1 , η 2 , du , and dv . While n is always 256 and q is always 3329, the remaining parameters
vary among the three parameter sets. Implementers shall ensure that the three algorithms of
ML-KEM listed above are only invoked with a valid parameter set, and that this parameter set isselected appropriately for the desired application. In addition, the algorithms ML-KEM.Encaps
and ML-KEM.Decaps require validation of inputs, as discussed below.

965

6.1

ML-KEM Key Generation

966 The key generation algorithm ML-KEM.KeyGen for ML-KEM (Algorithm 15) accepts no input,
967 requires randomness, and produces an encapsulation key and a decapsulation key. While the968 encapsulation key can be made public, the decapsulation key must remain private.
969
970
971
972
973
974
975

Informal description. The core subroutine of ML-KEM.KeyGen is the key generation algorithmof K-PKE (Algorithm 12). The ML-KEM encapsulation key is simply the encryption key of
K-PKE. The ML-KEM decapsulation key is comprised of the decryption key of K-PKE, theencapsulation key, a hash of the encapsulation key, and a pseudorandom 32-byte value. Thisrandom value will be used in the "implicit rejection" mechanism of the decapsulation algorithm(Algorithm 17).
Algorithm 15 ML-KEM.KeyGen()
Generates an encapsulation key and a corresponding decapsulation key.
Output: Encapsulation key ek ∈ B384k+32 .
Output: Decapsulation key dk ∈ B768k+96 .
$1: z ←− B32
2: (ekPKE , dkPKE ) ← K-PKE.KeyGen()
3: ek ← ekPKE
4: dk ← (dkPKE ∥ek∥H(ek)∥z)
5: return (ek, dk)▷ z is 32 random bytes (see Section 3.3)
▷ run key generation for K-PKE▷ KEM encaps key is just the PKE encryption key▷ KEM decaps key includes PKE decryption key

29

FIPS 203 (D RAFT )

976

6.2

M ODULE -L ATTICE - BASED K EY-E NCAPSULATION M ECHANISM

ML-KEM Encapsulation

977 The encapsulation algorithm ML-KEM.Encaps of ML-KEM (Algorithm 16) accepts an encap978 sulation key as input, requires randomness, and outputs a ciphertext and a shared key.
979
e to ML-KEM.Encaps, perform the following
980 Input validation. To validate a given input1 ek
981 checks.
982
983

e is not an array of bytes of length 384k + 32 for the value of k specifed
1. (Type check.) If ek
by the relevant parameter set, the input is invalid.

984
985

e )). If
2. (Modulus check.) Perform the computation ek ← ByteEncode12 (ByteDecode12 (eke , the input is invalid. (See Section 4.2.1.)
ek =
̸ ek

986
987
988
989

If either of the above checks declare the input to be invalid, then ML-KEM.Encaps shall not be
e . Instead, application-appropriate steps shall be taken to abort. If both
performed with input ekof the above checks pass (i.e., none of them declare the input to be invalid), then the input ise.
considered valid and ML-KEM.Encaps can be performed with input ek = ek

e is an actual
990 It is important to note that the above input validation process does not ensure that ek
991 output of ML-KEM.KeyGen. In fact, the ability to ensure that (without using the decapsulation
992 key) would violate the security assumption.
993
994
995
996
997

Recall that, as discussed in Section 3.3, implementations are only required to correctly reproduce
the input-output behavior of the top-level algorithms. In the case of ML-KEM.Encaps, thismeans that an implementation can perform any process that is equivalent to executing checks 1
and 2 above and then running Algorithm 16. (For example, the second check could be performed
during the execution of ByteDecode12 in line 2 of K-PKE.Encrypt.)
Algorithm 16 ML-KEM.Encaps(ek)Uses the encapsulation key to generate a shared key and an associated ciphertext.
Validated input: encapsulation key ek ∈ B384k+32 .
Output: shared key K ∈ B32 .
Output: ciphertext c ∈ B32(du k+dv ) .
$1: m ←− B32
2: (K, r) ← G(m∥H(ek))
3: c ← K-PKE.Encrypt(ek, m, r)
4: return (K, c)▷ m is 32 random bytes (see Section 3.3)
▷ derive shared secret key K and randomness r▷ encrypt m using K-PKE with randomness r

998
999 Informal description. The core subroutine of ML-KEM.Encaps is the encryption algorithm of1000 K-PKE, which is used to encrypt a random value m into a ciphertext c. A copy of the shared
1001 secret K and the randomness used during encryption are derived from m and the encapsulation

1 In discussions of input validation, the tilde in the notation indicates that the input might not be properly formed,

e for a candidate encapsulation key input, as opposed to ek for a valid input.
e.g., ek

30

FIPS 203 (D RAFT )M ODULE -L ATTICE - BASED K EY-E NCAPSULATION M ECHANISM

1002 key ek via hashing. Specifcally, H is applied to ek, and the result is concatenated with m and then1003 hashed using G. The algorithm completes by outputting the ciphertext c and the shared secret K.
1004

6.3

ML-KEM Decapsulation

1005 The decapsulation algorithm ML-KEM.Decaps of ML-KEM (Algorithm 16) accepts a decap1006 sulation key and a ML-KEM ciphertext as input, does not use any randomness, and outputs a1007 shared secret.
1008
e (candidate1009 Input validation. To validate a given pair of inputs ce (candidate ciphertext) and dk
1010 decapsulation key) to ML-KEM.Decaps, perform the following checks.
1011
1012

1. (Ciphertext type check.) If ce is not a byte array of length 32(du k + dv ) for the values of du ,dv , and k specifed by the relevant parameter set, the input is invalid.

1013
1014

e is not a byte array of length 768k + 96 for the value
2. (Decapsulation key type check.) If dk
of k specifed by the relevant parameter set, the input is invalid.

1015
1016
1017
1018

If either of the above checks declares the input to be invalid, then ML-KEM.Decaps shall note ). Instead, application-appropriate steps shall be taken to abort.
be performed with input (ce, dk
If both of the checks pass (i.e., neither one declares the input to be invalid), then the input ise ).
considered valid and ML-KEM.Decaps can be performed with input (c, dk) = (ce, dk

1019
1020
1021
1022
1023

e may be appropriate. For
For some applications, further validation of the decapsulation key dk
e was generated by a third party, users may want to ensure that the four
instance, in cases where dk
e have the correct relationship with each other, as in line 4 of ML-KEM.KeyGen.
components of dk
In all cases, implementers shall validate the inputs to ML-KEM.Decaps in a manner that is
appropriate for their application.

1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036

Informal description. The algorithm ML-KEM.Decaps begins by parsing out the componentsof the decapsulation key dk of ML-KEM. These components are an (encryption key, decryptionkey) pair for K-PKE, a hash value h, and a random value z. The decryption key of K-PKE isthen used to decrypt the input ciphertext c to get a plaintext m′ . The decapsulation algorithm thenre-encrypts m′ and computes a candidate shared secret key K ′ in the same manner as should havebeen done in encapsulation. Specifcally, K ′ and the encryption randomness r′ are computed byhashing m′ and the encryption key of K-PKE, and a ciphertext c′ is generated by encrypting m′using randomness r′ . Finally, decapsulation checks whether the resulting ciphertext c′ matches
the provided ciphertext c. If it does not, the algorithm performs an “implicit rejection”: the valueof K ′ is changed to a hash of c together with the random value z stored in the ML-KEM secretkey (see the discussion on decapsulation failures in Section 3.2). In either case, decapsulation
outputs the resulting shared secret key K ′ .

1037
1038

31

FIPS 203 (D RAFT )M ODULE -L ATTICE - BASED K EY-E NCAPSULATION M ECHANISM

Algorithm 17 ML-KEM.Decaps(c, dk)
Uses the decapsulation key to produce a shared key from a ciphertext.
Validated input: ciphertext c ∈ B32(du k+dv ) .
Validated input: decapsulation key dk ∈ B768k+96 .
Output: shared key K ∈ B32 .
1: dkPKE ← dk[0 : 384k]▷ extract (from KEM decaps key) the PKE decryption key
2: ekPKE ← dk[384k : 768k + 32]▷ extract PKE encryption key
3: h ← dk[768k + 32 : 768k + 64]▷ extract hash of PKE encryption key
4: z ← dk[768k + 64 : 768k + 96]▷ extract implicit rejection value
5: m′ ← K-PKE.Decrypt(dkPKE , c)
▷ decrypt ciphertext′′′
6: (K , r ) ← G(m ∥h)
7: K̄ ← J(z∥c, 32)
8: c′ ← K-PKE.Encrypt(ekPKE , m′ , r′ )▷ re-encrypt using the derived randomness r′
9: if c =
̸ c′ then10:
K ′ ← K̄▷ if ciphertexts do not match, “implicitly reject”
11: end if
12: return K ′
1039
1040

32

FIPS 203 (D RAFT )M ODULE -L ATTICE - BASED K EY-E NCAPSULATION M ECHANISM

1041

7.

Parameter Sets

1042
1043
1044
1045

ML-KEM is equipped with three parameter sets. Each of the three parameter sets is comprisedof fve individual parameters: k, η 1 , η 2 , du , and dv . There are also two constants: n = 256 andq = 3329. The following is a brief and informal description of the roles played by the variable
parameters in the algorithms of K-PKE (and hence in ML-KEM). See Section 5 for details.

1046
1047

• The parameter k determines the dimensions of the vectors s and e in K-PKE.KeyGen, as
well as the dimensions of the matrix Â and the vectors r, e1 , and e2 in K-PKE.Encrypt.

1048
1049

• The parameter η 1 is required for specifying the distribution for generating the vectors s ande in K-PKE.KeyGen and the vector r in K-PKE.Encrypt.

1050
1051

• The parameter η 2 is required for specifying the distribution for generating the vectors e1
and e2 in K-PKE.Encrypt.

1052
1053

• The parameters du and dv serve as parameters and inputs for the functions Compress,
Decompress, ByteEncode, and ByteDecode in K-PKE.Encrypt and K-PKE.Decrypt.

1054 This standard approves the parameter sets given in Table 2. Each parameter set is associated1055 with a required security strength for randomness generation (see Section 3.3). The sizes of the1056 ML-KEM keys and ciphertexts for each parameter set are summarized in Table 3.

ML-KEM-512
ML-KEM-768
ML-KEM-1024nq
256 3329
256 3329
256 3329

k
2
3
4

η1

η2

3
2
2

2
2
2

du
10
10
11

dv
4
4
5

required RBG strength (bits)
128
192
256

Table 2. Approved parameter sets for ML-KEM

ML-KEM-512
ML-KEM-768
ML-KEM-1024

encapsulation key
800
1184
1568

decapsulation key
1632
2400
3168

ciphertext
768
1088
1568

shared secret key
32
32
32

Table 3. Sizes (in bytes) of keys and ciphertexts of ML-KEM
1057 A parameter set name can also be said to denote a (parameter-free) KEM. Specifcally, ML-KEM-x
1058 can be used to denote the parameter-free KEM that results from instantiating the scheme
1059 ML-KEM with the parameter set ML-KEM-x.
1060 The three parameter sets included in Table 2 were designed to meet certain security strength
1061 categories defned by NIST in its original Call for Proposals [4, 18]. These security strength1062 categories are explained further in Appendix A.
1063 Using this approach, security strength is not described by a single number, such as “128 bits of1064 security.” Instead, each ML-KEM parameter set is claimed to be at least as secure as a generic

33

FIPS 203 (D RAFT )

1065
1066
1067
1068
1069
1070
1071

M ODULE -L ATTICE - BASED K EY-E NCAPSULATION M ECHANISM

block cipher with a prescribed key size or a generic hash function with a prescribed output
length. More precisely, it is claimed that the computational resources needed to break ML-KEM
are greater than or equal to the computational resources needed to break the block cipher orhash function, when these computational resources are estimated using any realistic model ofcomputation. Different models of computation can be more or less realistic and, accordingly,
lead to more or less accurate estimates of security strength. Some commonly studied models are
discussed in [19].

1072 Concretely, ML-KEM-512 is claimed to be in security category 1, ML-KEM-768 is claimed
1073 to be in security category 3, and ML-KEM-1024 is claimed to be in security category 5. For
1074 additional discussion of the security strength of MLWE-based cryptosystems, see [4].
1075
1076
1077
1078
1079
1080

Selecting an appropriate parameter set. When initially establishing cryptographic protections
for data, the strongest possible parameter set should be used. This has a number of advantages,
including reducing the likelihood of costly transitions to higher-security parameter sets in the
future. At the same time, it should be noted that some parameter sets might have adverse
performance effects for the relevant application (e.g., the algorithm may be unacceptably slow).

1081 NIST recommends using ML-KEM-768 as the default parameter set, as it provides a large
1082 security margin at a reasonable performance cost. In cases where this is impractical or where
1083 even higher security is required, other parameter sets may be used.

34

FIPS 203 (D RAFT )M ODULE -L ATTICE - BASED K EY-E NCAPSULATION M ECHANISM

1084

References

1085
1086

[1] NIST. Special Publication 800-227: Recommendations for key-encapsulation mechanisms,
2024.

1087
1088
1089
1090

[2] Elaine B. Barker, Lily Chen, Allen L. Roginsky, Apostol Vassilev, and Richard Davis.
Recommendation for pair-wise key-establishment schemes using discrete logarithm cryptography. Technical Report Special Publication 800-56A Revision 3, U.S. Department ofCommerce, Washington, D.C., April 2018.

1091
1092
1093
1094

[3] Elaine B. Barker, Lily Chen, Allen L. Roginsky, Apostol Vassilev, Richard Davis, andScott Simon. Recommendation for pair-wise key-establishment using integer factorization
cryptography. Technical Report Special Publication 800-56B Revision 2, U.S. Departmentof Commerce, Washington, D.C., March 2019.

1095
1096
1097
1098
1099

[4] 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. Third-round submission to the
NIST’s post-quantum cryptography standardization process, 2020. https://csrc.nist.gov/proj
ects/post-quantum-cryptography/round-3-submissions.

1100
1101
1102

[5] CRYSTALS-Kyber submission team. “Discussion about Kyber’s tweaked FO transform”.
Forum post on pqc-forum, available at https://groups.google.com/a/list.nist.gov/g/pqcforum/c/WFRDl8DqYQ4, 2023.

1103
1104
1105

[6] CRYSTALS-Kyber submission team. “Kyber decisions, part 2: FO transform”. Forum poston pqc-forum, available at https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/C0D3
W1KoINY/m/99kIvydoAwAJ, 2023.

1106
1107
1108
1109

[7] National Institute of Standards and Technology. SHA-3 standard: Permutation-basedhash and extendable-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.

1110
1111
1112
1113

[8] Joppe Bos, Léo Ducas, Eike Kiltz, T Lepoint, Vadim Lyubashevsky, John M. Schanck,
Peter Schwabe, Gregor Seiler, and Damien Stehlé. CRYSTALS-Kyber: A CCA-securemodule-lattice-based KEM. In 2018 IEEE European Symposium on Security and Privacy(EuroS&P), pages 353–367, 2018.

1114
1115

[9] Adeline Langlois and Damien Stehlé. Worst-case to average-case reductions for module
lattices. Designs, Codes and Cryptography, 75(3):565–599, 2015.

1116 [10] Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In
1117
Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, STOC
’05, page 84–93, New York, NY, USA, 2005. Association for Computing Machinery.
1118
1119 [11] Eiichiro Fujisaki and Tatsuaki Okamoto. Secure integration of asymmetric and symmetricencryption schemes. Journal of Cryptology, 26:80–101, 2013.
1120

35

FIPS 203 (D RAFT )M ODULE -L ATTICE - BASED K EY-E NCAPSULATION M ECHANISM

1121 [12] Dennis Hofheinz, Kathrin Hövelmanns, and Eike Kiltz. A modular analysis of the Fujisaki1122
Okamoto transformation. In Yael Kalai and Leonid Reyzin, editors, Theory of Cryptography,
pages 341–371, Cham, 2017. Springer International Publishing.
1123
1124 [13] Jonathan Katz and Yehuda Lindell. Introduction to Modern Cryptography. Chapman &Hall/CRC, third edition, 2020.
1125
1126 [14] Lily Chen. Recommendation for key derivation using pseudorandom functions. (National
Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP)1127
800-108 Rev. 1, August 2022. https://doi.org/10.6028/NIST.SP.800-108r1.
1128
1129 [15] Elaine B. Barker and John M. Kelsey. Recommendation for random number generation
using deterministic random bit generators. (National Institute of Standards and Technology,
1130
Gaithersburg, MD), NIST Special Publication (SP) 800-90A, Rev. 1, June 2015. https:
1131//doi.org/10.6028/NIST.SP.800-90Ar1.
1132
1133 [16] Meltem Sönmez Turan, Elaine B. Barker, John M. Kelsey, Kerry A. McKay, Mary L.
Baish, and Mike Boyle. Recommendation for the entropy sources used for random bit1134
generation. (National Institute of Standards and Technology, Gaithersburg, MD), NIST
1135
Special Publication (SP) 800-90B, January 2018. https://doi.org/10.6028/NIST.SP.800-90B.
1136
1137 [17] Elaine B. Barker, John M. Kelsey, Kerry McKay, Allen Roginsky, and Meltem Sönmez
Turan. Recommendation for random bit generator (RBG) constructions. (National Institute1138
of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-90C
1139(Third Public Draft), September 2022. https://csrc.nist.gov/publications/detail/sp/8001140
90c/draft.
1141
1142 [18] National Institute of Standards and Technology. Submission requirements and evaluation
criteria for the post-quantum cryptography standardization process, 2016. https://csrc.nist.
1143
gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/call-for-proposals1144
fnal-dec-2016.pdf.
1145
1146 [19] 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
1147
Robinson, and Daniel Smith-Tone. Status report on the third round of the NIST post1148
quantum cryptography standardization process. Technical Report NIST Interagency or
1149
Internal Report (IR) 8413, National Institute of Standards and Technology, Gaithersburg,
1150
MD, July 2022.
1151
1152 [20] 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
1153
Ishai, editors, Advances in Cryptology – EUROCRYPT 2020, pages 280–310, Cham, 2020.
1154
Springer International Publishing.
1155
1156 [21] Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedingsof the Twenty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’96, page1157
212–219, New York, NY, USA, 1996. Association for Computing Machinery.
1158

36

FIPS 203 (D RAFT )M ODULE -L ATTICE - BASED K EY-E NCAPSULATION M ECHANISM

1159

Appendix A — Security Strength Categories

1160
1161
1162
1163
1164

NIST understands that there are signifcant uncertainties in estimating the security strengths of
post-quantum cryptosystems. These uncertainties come from two sources: frst, the possibility
that new quantum algorithms will be discovered, leading to new cryptanalytic attacks; and second,
our limited ability to predict the performance characteristics of future quantum computers, suchas their cost, speed, and memory size.

1165
1166
1167
1168
1169
1170
1171

In order to address these uncertainties, NIST proposed the following approach in its original Callfor Proposals [18]. Instead of defning the strength of an algorithm using precise estimates of
the number of “bits of security,” NIST defned a collection of broad security strength categories.
Each category is defned by a comparatively easy-to-analyze reference primitive, whose security
will serve as a foor for a wide variety of metrics that NIST deems potentially relevant to practicalsecurity. A given cryptosystem may be instantiated using different parameter sets in order to ft
into different categories. The goals of this classifcation are:

1172
1173
1174

• To facilitate meaningful performance comparisons between various post-quantum algorithms by ensuring – insofar as possible – that the parameter sets being compared provide
comparable security

1175• To allow NIST to make prudent future decisions regarding when to transition to longer keys

1176
1177
1178

• 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 cryptography1179• To better understand the security/performance trade-offs involved in a given design approach

1180
1181
1182
1183
1184

In accordance with the second and third goals above, NIST based its classifcation on the rangeof 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):

1185
1186
1187

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

1188
1189
1190

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

1191
1192
1193

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

1194
1195
1196

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

1197

5. Any attack that breaks the relevant security defnition must require computational resources
37

FIPS 203 (D RAFT )

1198
1199

M ODULE -L ATTICE - BASED K EY-E NCAPSULATION M ECHANISM

comparable to or greater than those required for key search on a block cipher with a 256-bit
key (e.g., AES-256).
Table 4. NIST Security Strength Categories
Security Category

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

1200
1201
1202
1203
1204

Here, computational resources may be measured using a variety of different metrics (e.g., numberof classical elementary operations, quantum circuit size). In order for a cryptosystem to satisfy oneof 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 potentiallyrelevant to practical security.

1205
1206
1207
1208

NIST intends to consider a variety of possible metrics, refecting 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).2 NIST
will also consider input from the cryptographic community regarding this question.

1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220

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 light propagation times could perform in amillennium). The most basic version of this cost metric ignores costs associated with physicallymoving bits or qubits so 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.

1221
1222
1223
1224

The complexity of quantum attacks can then be measured in terms of circuit size. These numbers
can be compared 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
counts3 for the optimal key recovery and collision attacks on AES and SHA-3, respectively, where

2 See the discussion in [19, Appendix B].
3 Quantum circuit sizes are based on the work in [20].

38FIPS 203 (D RAFT )M ODULE -L ATTICE - BASED K EY-E NCAPSULATION M ECHANISM

1225 circuit depth is limited to MAXDEPTH]4 .

Table 5. Estimates for classical and quantum gate counts for the optimal key recovery andcollision attacks on AES and SHA-3
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

1226
1227
1228
1229
1230
1231

It is worth noting that the security categories based on these reference primitives provide substantially more quantum security than a naïve analysis might suggest. For example, categories 1, 3,
and 5 are defned in terms of block ciphers, which can be broken using Grover’s algorithm [21],with a quadratic quantum speedup. However, Grover’s algorithm requires a long-running serial
computation, which is diffcult to implement in practice. In a realistic attack, one has to run manysmaller instances of the algorithm in parallel, which makes the quantum speedup less dramatic.

1232
1233
1234
1235
1236
1237
1238

Finally, for attacks that use a combination of classical and quantum computation, one may
use a cost metric that rates logical quantum gates as being several orders of magnitude more
expensive than classical gates. Presently envisioned quantum computing architectures typicallyindicate that the cost per quantum gate could be billions or trillions of times the cost per classicalgate. However, especially when considering algorithms claiming a high security strength (e.g.,
equivalent to AES-256 or SHA-384), it is likely prudent to consider the possibility that thisdisparity will narrow signifcantly or even be eliminated.

4 NIST believes 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.

39