NIST FIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard

FIPS 203 Federal Information Processing Standards Publication

Module-Lattice-Based Key-Encapsulation Mechanism Standard Category: Computer Security

Subcategory: Cryptography

Information Technology Laboratory National Institute of Standards and Technology Gaithersburg, MD 20899-8900 This publication is available free of charge from: https://doi.org/10.6028/NIST.FIPS.203 Published August 13, 2024

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

Foreword The Federal Information Processing Standards (FIPS) Publication Series of the National Institute of Standards and Technology is the official series of publications relating to standards and guidelines developed under 15 U.S.C. 278g-3, and issued by the Secretary of Commerce under 40 U.S.C. 11331. Comments concerning this Federal Information Processing Standard publication are welcomed and should be submitted using the contact information in the “Inquiries and Comments” clause of the announcement section. Kevin M. Stine, Director Information Technology Laboratory

FIPS 203

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

Abstract A key-encapsulation mechanism (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 shared secret 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. This standard specifies a key-encapsulation mechanism called ML-KEM. The security of ML-KEM is related to the computational difficulty of the Module Learning with Errors problem. At present, ML-KEM is believed to be secure, even against adversaries who possess a quantum computer. This standard specifies three parameter sets for ML-KEM. In order of increasing security strength and decreasing performance, these are ML-KEM-512, ML-KEM-768, and ML-KEM-1024. Keywords: computer security; cryptography; encryption; Federal Information Processing Standards; key-encapsulation mechanism; lattice-based cryptography; post-quantum; public-key cryptography.

FIPS 203

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

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

Announcing the

Module-Lattice-Based Key-Encapsulation Mechanism Standard Federal Information Processing Standards (FIPS) publications are developed by the National Institute of Standards and Technology (NIST) under 15 U.S.C. 278g-3 and issued by the Secretary of Commerce under 40 U.S.C. 11331. 1. Name of Standard. Module-Lattice-Based Key-Encapsulation Mechanism Standard (FIPS 203). 2. Category of Standard. Computer Security. Subcategory. Cryptography. 3. Explanation. A cryptographic key (or simply “key”) is represented in a computer as a string of bits. A shared secret key is a cryptographic key that is computed jointly by two parties (e.g., Alice and Bob) using a set of algorithms. Under certain conditions, these algorithms ensure that both parties will produce the same key and that this key is secret from adversaries. Such a shared secret key can then be used with symmetric-key cryptographic algorithms (specified in other NIST standards) to perform tasks such as encryption and authentication of digital information. This standard specifies a set of algorithms for establishing a shared secret key. While there are many methods for establishing a shared secret key, the particular method described in this standard is a key-encapsulation mechanism (KEM). In a KEM, the computation of the shared secret key begins with Alice generating a decapsulation key and an encapsulation key. Alice keeps the decapsulation key private and makes the encapsulation key available to Bob. Bob then uses Alice’s encapsulation key to generate one copy of a shared secret key along with an associated ciphertext. Bob then sends the ciphertext to Alice. Finally, Alice uses the ciphertext from Bob along with Alice’s private decapsulation key to compute another copy of the shared secret key. The security of the particular KEM specified in this standard is related to the computational difficulty of solving certain systems of noisy linear equations, specifically the 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 specified and approved in FIPS publications or in NIST Special Publications. 4. Approving Authority. Secretary of Commerce. 5. Maintenance Agency. Department of Commerce, National Institute of Standards and Technology, Information Technology Laboratory (ITL). i

FIPS 203

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

6. Applicability. Federal Information Processing Standards apply to information systems used or operated by federal agencies or by a contractor of an agency or other organization on behalf of an agency. They do not apply to national security systems as defined in 44 U.S.C. 3552. This standard, or other FIPS or NIST Special Publications that specify alternative mechanisms, shall be used wherever the establishment of a shared secret key (or shared secret from which keying material can be generated) is required for federal applications, including the use of such a key with symmetric-key cryptographic algorithms, in accordance with applicable Office of Management and Budget and agency policies. The adoption and use of this standard are available to private and commercial organizations. 7. Implementations. A key-encapsulation mechanism may be implemented in software, firmware, hardware, or any combination thereof. For every computational procedure that is specified in this standard, a conforming implementation may replace the given set of steps with any mathematically equivalent set of steps. In other words, different procedures that produce the correct output for every input are permitted. NIST will develop a validation program to test implementations for conformance to the algorithms in this standard. Information about validation programs is available at https: //csrc.nist.gov/projects/cmvp. Example values will be available at https://csrc.nist.gov/proj ects/cryptographic-standards-and-guidelines/example-values. 8. Other Approved Security Functions. Implementations that comply with this standard shall employ cryptographic algorithms that have been approved for protecting Federal Government-sensitive information. Approved cryptographic algorithms and techniques include those that are either: (a) Specified in a Federal Information Processing Standards (FIPS) publication, (b) Adopted in a FIPS or NIST recommendation, or (c) Specified in the list of approved security functions in SP 800-140C. 9. Export Control. Certain cryptographic devices and technical data regarding them are subject to federal export controls. Exports of cryptographic modules that implement this standard and technical data regarding them must comply with all federal laws and regulations and be licensed by the Bureau of Industry and Security of the U.S. Department of Commerce. Information about export regulations is available at https://www.bis.doc.gov. 10. Patents. NIST has entered into two patent license agreements to facilitate the adoption of NIST’s announced selection of the PQC key-encapsulation mechanism CRYSTALS-KYBER. NIST and the licensing parties share a desire, in the public interest, the licensed patents be freely available to be practiced by any implementer of the ML-KEM algorithm as published by NIST. ML-KEM is the name given to the algorithm in this standard derived from CRYSTALS-KYBER. For a summary and extracts from the license, please see https://csrc.nist.gov/csrc/media/P rojects/post-quantum-cryptography/documents/selected-algos-2022/nist-pqc-license-sum mary-and-excerpts.pdf. Implementation of the algorithm specified in the standard may be covered by U.S. and foreign patents of which NIST is not aware.

ii

FIPS 203

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

11. Implementation Schedule. This standard becomes effective immediately upon final publication. 12. Specifications. Federal Information Processing Standards (FIPS) 203, Module-Lattice-Based Key-Encapsulation Mechanism Standard (affixed). 13. Qualifications. In applications, the security guarantees of a KEM only hold under certain conditions (see SP 800-227 [1]). One such condition is the secrecy of several values, including the randomness used by the two parties, the decapsulation key, and the shared secret key itself. Users shall, therefore, guard against the disclosure of these values. 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. 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. 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 five years. Both this standard and possible threats that reduce the security provided through the use of this 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 and provide necessary revisions. 14. Waiver Procedure. The Federal Information Security Management Act (FISMA) does not allow for waivers to Federal Information Processing Standards (FIPS) that are made mandatory by the Secretary of Commerce. 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 the same website. 16. How to Cite This Publication. NIST has assigned NIST FIPS 203 as the publication identifier for this FIPS, per the NIST Technical Series Publication Identifier Syntax. NIST recommends that it be cited as follows: National Institute of Standards and Technology (2024) Module-Lattice-Based KeyEncapsulation Mechanism Standard. (Department of Commerce, Washington, D.C.), Federal Information Processing Standards Publication (FIPS) NIST FIPS 203. https://doi.org/10.6028/NIST.FIPS.203 17. Inquiries and Comments. Inquiries and comments about this FIPS may be submitted to fips-203-comments@nist.gov.

iii

FIPS 203

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

Federal Information Processing Standards Publication 203 Specification for the

Module-Lattice-Based Key-Encapsulation Mechanism Standard Table of Contents 1 Introduction

1

1.1

Purpose and Scope

1

1.2

Context

1

2 Terms, Acronyms, and Notation

2

2.1

Terms and Definitions

2

2.2

Acronyms

4

2.3

Mathematical Symbols

5

2.4

Interpreting the Pseudocode 2.4.1 Data Types 2.4.2 Loop Syntax 2.4.3 Arithmetic With Arrays of Integers 2.4.4 Representations of Algebraic Objects 2.4.5 Arithmetic With Polynomials and NTT Representations 2.4.6 Matrices and Vectors 2.4.7 Arithmetic With Matrices and Vectors 2.4.8 Applying Algorithms to Arrays, Examples

6 7 7 7 8 9 9 10 11

3 Overview of the ML-KEM Scheme

12

3.1

Key-Encapsulation Mechanisms

12

3.2

The ML-KEM Scheme

13

3.3

Requirements for ML-KEM Implementations

15

4 Auxiliary Algorithms

18

4.1

Cryptographic Functions

18

4.2

General Algorithms 4.2.1 Conversion and Compression Algorithms 4.2.2 Sampling Algorithms The Number-Theoretic Transform

20 20 22 24

4.3

iv

FIPS 203

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

4.3.1

Multiplication in the NTT Domain

5 The K-PKE Component Scheme

27 28

5.1

K-PKE Key Generation

28

5.2

K-PKE Encryption

29

5.3

K-PKE Decryption

31

6 Main Internal Algorithms

32

6.1

Internal Key Generation

32

6.2

Internal Encapsulation

32

6.3

Internal Decapsulation

33

7 The ML-KEM Key-Encapsulation Mechanism

35

7.1

ML-KEM Key Generation

35

7.2

ML-KEM Encapsulation

36

7.3

ML-KEM Decapsulation

37

8 Parameter Sets

39

References

41

Appendix A — Precomputed Values for the NTT

44

Appendix B — SampleNTT Loop Bounds

46

Appendix C — Differences From the CRYSTALS-KYBER Submission

47

C.1

Differences Between CRYSTALS-KYBER and FIPS 203 Initial Public Draft

47

C.2

Changes From FIPS 203 Initial Public Draft

47

v

FIPS 203

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

List of Tables Table 1 Table 2 Table 3 Table 4

Decapsulation failure rates for ML-KEM Approved parameter sets for ML-KEM Sizes (in bytes) of keys and ciphertexts of ML-KEM While-loop limits and probabilities of occurrence for SampleNTT

15 39 39 46

List of Figures Figure 1

A simple view of key establishment using a KEM

12

List of Algorithms Algorithm 1 Algorithm 2 Algorithm 3 Algorithm 4 Algorithm 5 Algorithm 6 Algorithm 7 Algorithm 8 Algorithm 9 Algorithm 10 Algorithm 11 Algorithm 12 Algorithm 13 Algorithm 14 Algorithm 15 Algorithm 16 Algorithm 17 Algorithm 18 Algorithm 19 Algorithm 20 Algorithm 21

ForExample() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . SHAKE128example(str1 , … , str𝑚 , 𝑏1 , … , 𝑏ℓ ) . . . . . . . . . . . . . BitsToBytes(𝑏) . . . . . . . . . . . . . . . . . . . . . . . . . . . . BytesToBits(𝐵) . . . . . . . . . . . . . . . . . . . . . . . . . . . . ByteEncode𝑑 (𝐹 ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . ByteDecode𝑑 (𝐵) . . . . . . . . . . . . . . . . . . . . . . . . . . . . SampleNTT(𝐵) . . . . . . . . . . . . . . . . . . . . . . . . . . . . SamplePolyCBD𝜂 (𝐵) . . . . . . . . . . . . . . . . . . . . . . . . . NTT(𝑓) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . NTT−1 (𝑓)̂ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . MultiplyNTTs(𝑓,̂ 𝑔)̂ . . . . . . . . . . . . . . . . . . . . . . . . . . BaseCaseMultiply(𝑎0 , 𝑎1 , 𝑏0 , 𝑏1 , 𝛾) . . . . . . . . . . . . . . . . . . K-PKE.KeyGen(𝑑) . . . . . . . . . . . . . . . . . . . . . . . . . . . K-PKE.Encrypt(ekPKE , 𝑚, 𝑟) . . . . . . . . . . . . . . . . . . . . . . . K-PKE.Decrypt(dkPKE , 𝑐) . . . . . . . . . . . . . . . . . . . . . . . . ML-KEM.KeyGen_internal(𝑑, 𝑧) . . . . . . . . . . . . . . . . . . . . ML-KEM.Encaps_internal(ek, 𝑚) . . . . . . . . . . . . . . . . . . . ML-KEM.Decaps_internal(dk, 𝑐) . . . . . . . . . . . . . . . . . . . . ML-KEM.KeyGen() . . . . . . . . . . . . . . . . . . . . . . . . . . . ML-KEM.Encaps(ek) . . . . . . . . . . . . . . . . . . . . . . . . . . ML-KEM.Decaps(dk, 𝑐) . . . . . . . . . . . . . . . . . . . . . . . .

vi

8 19 20 20 22 22 23 23 26 26 27 27 29 30 31 32 33 34 35 37 38

FIPS 203

1.

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

Introduction

1.1 Purpose and Scope This standard specifies the Module-Lattice-Based Key-Encapsulation Mechanism (ML-KEM). A key-encapsulation mechanism (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 a particular type of key establishment scheme. Other NIST-approved key establishment schemes are specified in NIST Special Publication (SP) 800-56A, Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm-Based Cryptography [2], and SP 800-56B, Recommendation for Pair-Wise Key Establishment Schemes Using Integer Factorization Cryptography [3]. The key establishment schemes specified in SP 800-56A and SP 800-56B are vulnerable to attacks that use sufficiently-capable quantum computers. ML-KEM is an approved alternative that is presently believed to be secure, even against adversaries in possession of a large-scale fault-tolerant quantum computer. ML-KEM is derived from the round-three version of the CRYSTALS-KYBER KEM [4], a submission in the NIST Post-Quantum Cryptography Standardization project. For the differences between ML-KEM and CRYSTALS-KYBER, see Appendix C. This standard specifies the algorithms and parameter sets of the ML-KEM scheme. It aims to provide sufficient information to implement ML-KEM in a manner that can pass validation (see https://csrc.nist.gov/projects/cryptographic- module- validation- program). For general definitions and properties of KEMs, including requirements for the secure use of KEMs in applications, see SP 800-227 [1]. This standard specifies three parameter sets for ML-KEM that offer different trade-offs in security strength versus performance. All three parameter sets of ML-KEM are approved to protect sensitive, non-classified communication systems of the U.S. Federal Government.

1.2 Context 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 signature schemes whose security depends on the difficulty of solving the integer factorization and discrete logarithm problems (both over finite fields and elliptic curves). As a result, in 2016, NIST initiated a public Post-Quantum Cryptography (PQC) Standardization process to select quantum-resistant public-key cryptographic algorithms. A total of 82 candidate algorithms were submitted to NIST for consideration. After three rounds of evaluation and analysis, NIST selected the first four algorithms for standardization. These algorithms are intended to protect sensitive U.S. Government information well into the foreseeable future, including after the advent of cryptographically-relevant quantum computers. This standard specifies a variant of the selected algorithm CRYSTALS-KYBER, a lattice-based key-encapsulation mechanism (KEM) designed by Peter Schwabe, Roberto Avanzi, Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John Schanck, Gregor Seiler, Damien Stehlé, and Jintai Ding [4]. Throughout this standard, the KEM specified here will be referred to as ML-KEM, as it is based on the Module Learning With Errors assumption. 1

FIPS 203

2.

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

Terms, Acronyms, and Notation

2.1 Terms and Definitions approved

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

(KEM) ciphertext

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

cryptographic module

The set of hardware, software, and/or firmware that implements approved cryptographic functions (including key generation) that are contained within the cryptographic boundary of the module.

decapsulation

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

decapsulation key

A cryptographic key produced by a KEM during key generation and used during the decapsulation process. The decapsulation key must be kept private and must be destroyed after it is no longer needed. (See Section 3.3.)

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.

destroy

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

encapsulation

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

encapsulation key

A cryptographic key produced by a KEM during key generation and used during the encapsulation process. The encapsulation key can be made public. (See Section 3.3.)

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.

equivalent process

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

fresh random value An output that was produced by a random bit generator and has not been previously used. 2

FIPS 203

hash function

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

A function on bit strings in which the length of the output is fixed. Approved hash functions (such as those specified in FIPS 180 [5] and FIPS 202 [6]) are designed to satisfy the following properties: 1. (One-way) It is computationally infeasible to find any input that maps to any new pre-specified output. 2. (Collision-resistant) It is computationally infeasible to find any two distinct inputs that map to the same output.

input checking

Examination of a potential input to an algorithm for the purpose of determining whether it conforms to certain requirements.

key

A bit string that is used in conjunction with a cryptographic algorithm, such as the encapsulation and decapsulation keys (of a KEM), the shared secret key (produced by a KEM), and the encryption and decryption keys (of a PKE). (See Section 3.3.)

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.

key establishment

A procedure that results in secret keying material that is shared among different parties.

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.

little-endian

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

party

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

pseudorandom

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

public channel

A communication channel between two parties. Such a channel can be observed and possibly also corrupted by third parties.

3

FIPS 203

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

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.

shared secret

A secret value that has been computed during a key-establishment scheme, is known by both participants, and is used as input to a keyderivation method to produce keying material.

shared secret key

A shared secret that can be used directly as a cryptographic key in symmetric-key cryptography. It does not require additional key derivation. The shared secret key must be kept private and must be destroyed when no longer needed.

security category

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

security strength

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

shall

Used to indicate a requirement of this standard.

should

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

2.2 Acronyms AES

Advanced Encryption Standard

CBD

Centered Binomial Distribution

FIPS

Federal Information Processing Standard

KEM

Key-Encapsulation Mechanism

LWE

Learning with Errors

MLWE

Module Learning with Errors

NIST

National Institute of Standards and Technology

NISTIR

NIST Interagency or Internal Report

NTT

Number-Theoretic Transform

PKE

Public-Key Encryption

PQC

Post-Quantum Cryptography

PRF

Pseudorandom Function

RBG

Random Bit Generator

SHA

Secure Hash Algorithm 4

FIPS 203

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

SHAKE

Secure Hash Algorithm KECCAK

SP

Special Publication

XOF

Extendable-Output Function

2.3 Mathematical Symbols 𝑛

Denotes the integer 256 throughout this document.

𝑞

Denotes the prime integer 3329 = 28 ⋅ 13 + 1 throughout this document.

𝜁

Denotes the integer 17, which is a primitive 𝑛-th root of unity modulo 𝑞.

𝔹

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

ℚ

The set of rational numbers.

ℤ

The set of integers.

ℤ𝑚

The ring of integers modulo 𝑚 (i.e., the set {0, 1, … , 𝑚 − 1} equipped with the operations of addition and multiplication modulo 𝑚.)

ℤ𝑛𝑚

The set of 𝑛-tuples over ℤ𝑚 equipped with ℤ𝑚 -module structure. As a data type, this is the set of length-𝑛 arrays whose entries are in ℤ𝑚 .

𝑅𝑞

The ring ℤ𝑞 [𝑋]/(𝑋 𝑛 + 1) consisting of polynomials of the form 𝑓 = 𝑓0 + 𝑓1 𝑋 + ⋯ + 𝑓255 𝑋 255 , where 𝑓𝑗 ∈ ℤ𝑞 for all 𝑗. The ring operations are addition and multiplication modulo 𝑋 𝑛 + 1.

𝑇𝑞

The image of 𝑅𝑞 under the number-theoretic transform. Its elements are called “NTT representations” of polynomials in 𝑅𝑞 . (See Section 4.3.)

D𝜂 (𝑅𝑞 )

A certain distribution of polynomials in 𝑅𝑞 with small coefficients, from which noise is sampled. The distribution is parameterized by 𝜂 ∈ {2, 3}. (See Section 4.2.2.)

𝑆∗

If 𝑆 is a set, this denotes the set of finite-length tuples (or arrays) of elements from the set 𝑆, including the empty tuple (or empty array).

𝑆𝑘

If 𝑆 is a set, this denotes the set of 𝑘-tuples (or length-𝑘 arrays) of elements from the set 𝑆.

𝑓𝑗

The coefficient of 𝑋 𝑗 of a polynomial 𝑓 = 𝑓0 + 𝑓1 𝑋 + ⋯ + 𝑓255 𝑋 255 ∈ 𝑅𝑞 .

𝑓̂

The element of 𝑇𝑞 that is equal to the NTT representation of a polynomial 𝑓 ∈ 𝑅𝑞 . (See Sections 2.4.4 and 4.3.)

𝐯𝑇 , 𝐀𝑇

The transpose of a row or column vector 𝐯. In general, the transpose of a matrix 𝐀.

5

FIPS 203

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

∘

Denotes linear-algebraic composition with coefficients in 𝑅𝑞 or 𝑇𝑞 (e.g., 𝐀 ∘ 𝐯 denotes the vector resulting from applying matrix 𝐀 to vector 𝐯). (See Section 2.4.7.)

×𝑇𝑞

Denotes the operation on coefficient arrays that implements product in the ring 𝑇𝑞 . (See Sections 2.4.5 and 4.3.1.)

𝐴‖𝐵

The concatenation of two arrays or bit strings 𝐴 and 𝐵.

𝐵[𝑖]

The entry at index 𝑖 in the array 𝐵. All arrays have indices that begin at zero.

𝐵[𝑘 ∶ 𝑚]

The subarray (𝐵[𝑘], 𝐵[𝑘 + 1], … , 𝐵[𝑚 − 1]) of the array 𝐵.

|𝐵|

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

⌈𝑥⌉

The ceiling of 𝑥 (i.e., the smallest integer greater than or equal to 𝑥).

⌊𝑥⌋

The floor of 𝑥 (i.e., the largest integer less than or equal to 𝑥).

⌈𝑥⌋

The rounding of 𝑥 to the nearest integer. If 𝑥 = 𝑦 + 1/2 for some 𝑦 ∈ ℤ, then ⌈𝑥⌋ = 𝑦 + 1.

∶=

Denotes that the left-hand side is defined to be the expression on the righthand side.

𝑟 mod 𝑚

The unique integer 𝑟′ in {0, 1, … , 𝑚 − 1} such that 𝑚 divides 𝑟 − 𝑟′ .

BitRev7 (𝑟)

Bit reversal of a seven-bit integer 𝑟. Specifically, if 𝑟 = 𝑟0 + 2𝑟1 + 4𝑟2 + ⋯ + 64𝑟6 with 𝑟𝑖 ∈ {0, 1}, then BitRev7 (𝑟) = 𝑟6 + 2𝑟5 + 4𝑟4 + ⋯ + 64𝑟0 .

𝑠←𝑥

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

$

𝑠 ←− 𝔹ℓ

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

⊥

A symbol indicating failure or the lack of output from an algorithm.

2.4 Interpreting the Pseudocode This section outlines the conventions of the pseudocode used to describe the algorithms in this standard. All algorithms are understood to have access to two global integer constants: 𝑛 = 256 and 𝑞 = 3329. There are also five global integer variables: 𝑘, 𝜂1 , 𝜂2 , 𝑑𝑢 , and 𝑑𝑣 . All other variables are local. The five global variables are set to particular values when a parameter set is selected (see Section 8). When algorithms in this specification invoke other algorithms as subroutines, all arguments (i.e., inputs) are passed by value. In other words, a copy of the inputs is created, and the subroutine is invoked with the copy. There is no “passing by reference.” Pseudocode assignments are performed using the symbol “←.” For example, the statement 𝑧 ← 𝑦 means that the variable 𝑧 is assigned the value of variable 𝑦. Pseudocode comparisons 6

FIPS 203

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

are performed via the symbol “==.” For example, the expression 𝑥 == 𝑤 is a boolean value that is TRUE if and only if the variables 𝑥 and 𝑤 have the same value. In regular text (i.e., outside of the pseudocode), a different convention is applied. There, the “=” symbol is used both for assigning values and for comparisons, in keeping with standard mathematical notation. When emphasis is needed, assignments will be made with “∶=” instead. Variables will always have a valid value that is appropriate to their data type, with two exceptions: 1. The outputs of a random bit generator (RBG) have the byte array data type but are also allowed to have the special value NULL. This value indicates that randomness generation failed. This can only occur in ML-KEM.KeyGen and ML-KEM.Encaps. 2. The outputs of ML-KEM.KeyGen and ML-KEM.Encaps have the byte array data type but are also allowed to have the special value ⊥. When ML-KEM.KeyGen or ML-KEM.Encaps return the value ⊥, this indicates that the algorithm failed due to a failure of randomness generation. 2.4.1 Data Types For variables that represent the input or output of an algorithm, the data type (e.g., 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 is determined the first 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. In addition to standard atomic data types (e.g., bits, bytes) and data structures (e.g., arrays), integers modulo 𝑚 (i.e., elements of ℤ𝑚 ) will also be used as an abstract data type. It is implicit that reduction modulo 𝑚 takes place whenever an assignment is made to a variable in ℤ𝑚 . For example, for 𝑧 ∈ ℤ𝑚 and integers 𝑥 and 𝑦, the statement 𝑧 ← 𝑥+𝑦

(2.1)

means that 𝑧 is assigned the value 𝑥 + 𝑦 mod 𝑚. The pseudocode is agnostic regarding how an integer modulo 𝑚 is represented in actual implementations or how modular reduction is computed. 2.4.2

Loop Syntax

The pseudocode will make use of both “while” and “for” loops. The “while” syntax is selfexplanatory. In the case of “for” loops, the syntax will be in the style of the programming language C. Two simple examples are given in Algorithm 1. The standard mathematical expression (e.g., ∑𝑛𝑖←1 (𝑖 + 3)) will be used for simple summations instead of a “for” loop. 2.4.3 Arithmetic With Arrays of Integers This standard makes extensive use of arrays of integers modulo 𝑚 (i.e., elements of ℤℓ𝑚 ). In a typical case, the relevant values are 𝑚 = 𝑞 = 3329 and ℓ = 𝑛 = 256. Arithmetic with arrays in 7

FIPS 203

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

Algorithm 1 ForExample() Performs two simple “for” loops. 1: for (𝑖 ← 0; 𝑖 < 10; 𝑖 ++) 2: 𝐴[𝑖] ← 𝑖 3: end for 4: 𝑗 ← 0 5: for (𝑘 ← 256; 𝑘 > 1; 𝑘 ← 𝑘/2) 6: 𝐵[𝑗] ← 𝑘 7: 𝑗 ← 𝑗+1 8: end for

▷ 𝐴 is an integer array of length 10 ▷ 𝐴 now has the value (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)

▷ 𝐵 is an integer array of length 8 ▷ 𝐵 now has the value (256, 128, 64, 32, 16, 8, 4, 2)

ℓ . The statements ℤℓ𝑚 will be done as follows. Let 𝑎 ∈ ℤ𝑚 and 𝑋, 𝑌 ∈ ℤ𝑚

𝑍 ← 𝑎⋅𝑋 𝑊 ← 𝑋 +𝑌

(2.2) (2.3)

will result in two arrays 𝑍, 𝑊 ∈ ℤℓ𝑚 , with the property that 𝑍[𝑖] = 𝑎 ⋅ 𝑋[𝑖] and 𝑊 [𝑖] = 𝑋[𝑖] + 𝑌 [𝑖] for all 𝑖. Multiplication of arrays in ℤℓ𝑚 will only be meaningful when 𝑚 = 𝑞 and ℓ = 𝑛 = 256, in which case it corresponds to multiplication in a particular ring. This operation will be described in (2.8). 2.4.4

Representations of Algebraic Objects

An essential operation in ML-KEM is the number-theoretic transform (NTT), which maps a polŷ an isomorphic ring 𝑇 . The rings 𝑅 nomial 𝑓 in a certain ring 𝑅𝑞 to its “NTT representation” 𝑓 in 𝑞 𝑞 and 𝑇𝑞 and the NTT are discussed in detail in Section 4.3. This standard will represent elements of 𝑅𝑞 and 𝑇𝑞 in pseudocode using arrays of integers modulo 𝑞 as follows. An element 𝑓 of 𝑅𝑞 is a polynomial of the form 𝑓 = 𝑓0 + 𝑓1 𝑋 + ⋯ + 𝑓255 𝑋 255 ∈ 𝑅𝑞

(2.4)

and will be represented in pseudocode by the array (𝑓0 , 𝑓1 , … , 𝑓255 ) ∈ ℤ256 𝑞 ,

(2.5)

whose entries contain the coefficients of 𝑓. Overloading notation, the array in (2.5) will also be denoted by 𝑓. The 𝑖-th entry of the array 𝑓 will thus contain the 𝑖-th coefficient of the polynomial 𝑓 (i.e., 𝑓[𝑖] = 𝑓𝑖 ). An element (sometimes called “NTT representation”) 𝑔 ̂ of 𝑇𝑞 is a tuple of 128 polynomials, each of degree at most one. Specifically, 𝑔 ̂ = (𝑔0,0 ̂ + 𝑔0,1 ̂ 𝑋, 𝑔1,0 ̂ + 𝑔1,1 ̂ 𝑋, … , 𝑔127,0 ̂ + 𝑔127,1 ̂ 𝑋) ∈ 𝑇𝑞 .

8

(2.6)

FIPS 203

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

Such an algebraic object will be represented in pseudocode by the array (𝑔0,0 ̂ , 𝑔0,1 ̂ , 𝑔1,0 ̂ , 𝑔1,1 ̂ ̂ ̂ , … , 𝑔127,0 , 𝑔127,1 ) ∈ ℤ256 𝑞 .

(2.7)

Overloading notation, the array in (2.7) will also be denoted by 𝑔.̂ In this case, the mapping between array entries and coefficients is 𝑔[2𝑖] ̂ = 𝑔𝑖,0 ̂ and 𝑔[2𝑖 ̂ + 1] = 𝑔𝑖,1 ̂ for 𝑖 ∈ {0, 1, … , 127}. Converting between a polynomial 𝑓 ∈ 𝑅𝑞 and its NTT representation 𝑓 ̂ ∈ 𝑇𝑞 will be done via the algorithms NTT (Algorithm 9) and NTT−1 (Algorithm 10). These algorithms act on arrays of coefficients, as described above, and satisfy 𝑓 ̂ = NTT(𝑓) and 𝑓 = NTT−1 (𝑓)̂. 2.4.5

Arithmetic With Polynomials and NTT Representations

The algebraic operations of addition and scalar multiplication in 𝑅𝑞 and 𝑇𝑞 are done coordinatewise. For example, if 𝑎 ∈ ℤ𝑞 and 𝑓 ∈ 𝑅𝑞 , the 𝑖-th coefficient of the polynomial 𝑎 ⋅ 𝑓 ∈ 𝑅𝑞 is equal to 𝑎 ⋅ 𝑓𝑖 mod 𝑞. In pseudocode, elements of both 𝑅𝑞 and 𝑇𝑞 are represented by coefficient arrays (i.e., elements of ℤ256 𝑞 ). The algebraic operations of addition and scalar multiplication are thus performed by addition and scalar multiplication of the corresponding coefficient arrays, as in (2.3) and (2.2). For example, the addition of two NTT representations in pseudocode is ̂ 𝑔,̂ where ℎ,̂ 𝑓,̂ 𝑔 ̂ ∈ ℤ256 are coefficient arrays. performed by a statement of the form ℎ̂ ← 𝑓 + 𝑞 The algebraic operations of multiplication in 𝑅𝑞 and 𝑇𝑞 are treated as follows. For efficiency reasons, multiplication in 𝑅𝑞 will not be used. The algebraic meaning of multiplication in 𝑇𝑞 is discussed in Section 4.3.1. In pseudocode, it will be performed by the algorithm MultiplyNTTs (Algorithm 11). Specifically, if 𝑓,̂ 𝑔 ̂ ∈ ℤ256 are a pair of arrays (each representing the NTT of some 𝑞 polynomial), then ̂ ℎ̂ ← 𝑓 × 𝑇𝑞 𝑔 ̂

ℎ̂ ← MultiplyNTTs(𝑓,̂ 𝑔)̂ .

means

(2.8)

The result is an array ℎ̂ ∈ ℤ256 𝑞 . 2.4.6

Matrices and Vectors

In addition to arrays of integers modulo 𝑞, the pseudocode will also make use of arrays whose 256 3 entries are themselves elements of ℤ256 𝑞 . For example, an element 𝐯 ∈ (ℤ𝑞 ) will be a lengththree array whose entries 𝐯[0], 𝐯[1], and 𝐯[2] are themselves elements of ℤ256 (i.e., arrays). One 𝑞 can think of each of these entries as representing a polynomial in 𝑅𝑞 so that 𝐯 itself represents an element of the module 𝑅𝑞3 . When arrays are used to represent matrices and vectors whose entries are elements of 𝑅𝑞 , they will be denoted with bold letters (e.g., 𝐯 for vectors and 𝐀 for matrices). When arrays are used to represent matrices and vectors whose entries are elements of 𝑇𝑞 , they will be denoted with a “hat” (e.g., 𝐯̂ and 𝐀̂). 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. Converting between matrices over 𝑅𝑞 and matrices over 𝑇𝑞 will be done coordinate-wise. For 9

FIPS 203

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

𝑘 example, if 𝐯 ∈ (ℤ256 𝑞 ) , then the statement

𝐯̂ ← NTT(𝐯)

(2.9)

𝑘 will result in 𝐯̂ ∈ (ℤ256 ̂ = NTT(𝐯[𝑖]) for all 𝑖. This involves running NTT a total 𝑞 ) such that 𝐯[𝑖] of 𝑘 times.

2.4.7

Arithmetic With Matrices and Vectors

The following describes how to perform arithmetic with matrices over 𝑅𝑞 and 𝑇𝑞 with vectors as a special case. Addition and scalar multiplication are performed coordinate-wise, so the addition of matrices over 𝑅𝑞 and 𝑇𝑞 is straightforward. In the case of 𝑇𝑞 , scalar multiplication is done via (2.8). For 𝑘 example, if 𝑓 ̂ ∈ ℤ256 and 𝐮,̂ 𝐯̂ ∈ (ℤ256 𝑞 𝑞 ) , then 𝐰̂ ← 𝑓 ⋅̂ 𝐮̂ 𝐳̂ ← 𝐮̂ + 𝐯̂

(2.10) (2.11)

𝑘 ̂ will result in 𝐰,̂ 𝐳̂ ∈ (ℤ256 ̂ =𝑓× ̂ and 𝐳[𝑖] ̂ = 𝐮[𝑖] ̂ + 𝐯[𝑖] ̂ for all 𝑖. Here, the 𝑞 ) satisfying 𝐰[𝑖] 𝑇𝑞 𝐮[𝑖] multiplication and addition of individual entries are performed using the appropriate arithmetic for coefficient arrays of elements of 𝑇𝑞 (i.e., as in (2.3)).

It will also be necessary to multiply matrices with entries in 𝑇𝑞 , which is done by using standard matrix multiplication with the base-case multiplication (i.e., multiplication of individual entries) being multiplication in 𝑇𝑞 . If 𝐀̂ and 𝐁̂ are two matrices with entries in 𝑇𝑞 , their matrix product ̂ Some example pseudocode statements involving matrix multiplication will be denoted 𝐀̂ ∘ 𝐁. are given in (2.12), (2.13), and (2.14). In these examples, 𝐀̂ is a 𝑘 × 𝑘 matrix, while 𝐮̂ and 𝐯̂ are vectors of length 𝑘. All three of these objects are represented in pseudocode by arrays: a 𝑘 × 𝑘 array for 𝐀̂ and length-𝑘 arrays for 𝐮̂ and 𝐯̂ . The entries of 𝐀̂, 𝐮̂ , and 𝐯̂ are elements of ℤ256 𝑞 . In (2.12) and (2.13), the pseudocode statement on the left produces a new length-𝑘 vector whose entries are specified on the right. In (2.14), the pseudocode statement on the left computes a dot product. The result is in the base ring (i.e., 𝑇𝑞 ) and is represented by an element 𝑧 ̂ of ℤ256 𝑞 . 𝑘−1

𝐰̂ ← 𝐀̂ ∘ 𝐮̂

̂ 𝑗] ×𝑇 𝐮[𝑗] 𝐰[𝑖] ̂ = ∑ 𝐀[𝑖, ̂ 𝑞

(2.12)

𝑗=0 𝑘−1

𝐲̂ ← 𝐀̂ ⊺ ∘ 𝐮̂

̂ 𝑖] ×𝑇 𝐮[𝑗] 𝐲[𝑖] ̂ = ∑ 𝐀[𝑗, ̂ 𝑞

(2.13)

𝑗=0 𝑘−1

𝑧 ̂ ← 𝐮̂ ⊺ ∘ 𝐯̂

𝑧 ̂ = ∑ 𝐮[𝑗] ̂ ×𝑇𝑞 𝐯[𝑗] ̂

(2.14)

𝑗=0

The multiplication ×𝑇𝑞 of individual entries above is performed using MultiplyNTTs, as described in (2.8).

10

FIPS 203

2.4.8

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

Applying Algorithms to Arrays, Examples

In the previous examples, arithmetic over ℤ𝑚 was extended to arithmetic with arrays over ℤ𝑚 and then further extended to arithmetic with matrices whose entries are themselves arrays over ℤ𝑚 . Similarly, algorithms defined with a given data type as input will be applied to arrays and matrices over that data type. When the pseudocode invokes such an algorithm on an array or matrix input, it is implied that the algorithm is invoked repeatedly and applied to each entry of the input. For example, consider the function Compress𝑑 ∶ ℤ𝑞 → ℤ2𝑑 defined in Section 4. It can be invoked on an array input 𝐹 ∈ ℤ256 with the statement 𝑞 𝐾 ← Compress𝑑 (𝐹 ) .

(2.15)

The result will be an array 𝐾 ∈ ℤ256 such that 𝐾[𝑖] = Compress𝑑 (𝐹 [𝑖]) for every 𝑖 ∈ {0, 1, … , 255}. 2𝑑 The computation (2.15) involves running the Compress algorithm 256 times. For a second example, consider the algorithm NTT defined in Section 4.3. It takes an array 𝑓 ∈ ℤ256 (representing an element of 𝑅𝑞 ) as input and outputs another array 𝑓 ̂ ∈ ℤ256 (representing 𝑞 𝑞 256 𝑘 an element of 𝑇𝑞 ). If the NTT algorithm is invoked on a vector 𝐬 ∈ (ℤ𝑞 ) (representing an element of 𝑅𝑞𝑘 ) with the pseudocode statement 𝐬 ̂ ← NTT(𝐬) ,

(2.16)

𝑘 ̂ = NTT(𝐬[𝑖]) for all 𝑖 ∈ {0, 1, … , 𝑘 − 1}. The vector the result is a vector 𝐬 ̂ ∈ (ℤ256 𝑞 ) such that 𝐬[𝑖] 𝑘 𝐬̂ represents an element of 𝑇𝑞 . The computation (2.16) involves running the NTT algorithm 𝑘 times.

For a third example, consider line 2 of K-PKE.Encrypt in Section 5.2: 𝐭̂ ← ByteDecode12 (ekPKE [0 ∶ 384𝑘]) .

(2.17)

ByteDecode12 is defined to receive a byte array of length 32 ⋅ 12 = 384 as input and produce an integer array in ℤ256 as output. The computation (2.17) is run on the first 384𝑘 bytes of 𝑞 𝑘 byte array ekPKE and results in 𝐭̂ ∈ (ℤ256 𝑞 ) . ByteDecode12 will thus be applied 𝑘 times, once for ̂ ∈ ℤ256 each subarray ekPKE [384 ⋅ 𝑗, 384 ⋅ (𝑗 + 1)], and will result in an integer array 𝐭[𝑗] such that 𝑞 ̂𝐭[𝑗] = ByteDecode (ekPKE [384 ⋅ 𝑗, 384 ⋅ (𝑗 + 1)]) for each 𝑗 from 0 to 𝑘 − 1. 12

11

FIPS 203

3.

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

Overview of the ML-KEM Scheme

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

3.1 Key-Encapsulation Mechanisms The following is a high-level overview of key-encapsulation mechanisms (KEMs). For details, see SP 800-227 [1]. A KEM is a cryptographic scheme that, under certain conditions, can be used to establish a shared secret key between two communicating parties. This shared secret key can then be used for symmetric-key cryptography. A KEM consists of three algorithms and a collection of parameter sets. The three algorithms are: 1. A probabilistic key generation algorithm denoted by KeyGen 2. A probabilistic ”encapsulation” algorithm denoted by Encaps 3. A deterministic ”decapsulation” algorithm denoted by Decaps The collection of parameter sets is used to select a trade-off between security and efficiency. Each parameter set in the collection is a list of specific (typically numerical) values, one for each parameter required by the three algorithms.

Alice

Bob

KeyGen

decapsulation key

Decaps

encapsulation key

ciphertext

Encaps

Alice’s copy of the shared secret key

Bob’s copy of the shared secret key

𝐾′

𝐾

Figure 1. A simple view of key establishment using a KEM

12

FIPS 203

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

In the typical application, a KEM is used to establish a shared secret key between two parties (here referred to as Alice and Bob) as described in Figure 1. Alice begins by running KeyGen in order to generate a (public) encapsulation key and a (private) decapsulation key. Upon obtaining Alice’s encapsulation key, Bob runs the Encaps algorithm, which produces Bob’s copy 𝐾 of the shared secret key along with an associated ciphertext. Bob sends the ciphertext to Alice, and Alice completes the process by running the Decaps algorithm using her decapsulation key and the ciphertext. This final step produces Alice’s copy 𝐾 ′ of the shared secret key. After completing this process, Alice and Bob would like to conclude that their outputs satisfy 𝐾 ′ = 𝐾 and that this value is a secure, random, shared secret key. However, these properties only hold if certain important conditions are satisfied, as discussed in SP 800-227 [1].

3.2 The ML-KEM Scheme ML-KEM is a key-encapsulation mechanism based on CRYSTALS-KYBER [4], a scheme that was initially described in [8]. The following is a brief and informal description of the computational assumption underlying ML-KEM and how the ML-KEM scheme is constructed. The computational assumption. The security of ML-KEM is based on the presumed hardness of the so-called Module Learning with Errors (MLWE) problem [9], which is 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 in module lattices [9]. This motivates the name of the scheme ML-KEM. In the LWE problem, the input is a set of random “noisy” linear equations in some secret variables 𝑥 ∈ ℤ𝑛𝑞 , and the task is to recover 𝑥. The noise in the equations is such that standard algorithms (e.g., Gaussian elimination) are intractable. The LWE problem naturally lends itself to cryptographic applications. For example, if 𝑥 is interpreted as a secret key, then one can encrypt a one-bit plaintext value by sampling either an approximately correct linear equation (if the plaintext is zero) or a far-from-correct linear equation (if the plaintext is one). Plausibly, only a party in possession of 𝑥 can 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. The MLWE problem is similar to the LWE problem. An important difference is that, in MLWE, ℤ𝑛𝑞 is replaced by a certain module 𝑅𝑞𝑘 , which is constructed by taking the 𝑘-fold Cartesian product of a certain polynomial ring 𝑅𝑞 . In particular, the secret in the MLWE problem is an element 𝐱 of the module 𝑅𝑞𝑘 . The ring 𝑅𝑞 is discussed in detail in Section 4.3. The ML-KEM construction. At a high level, the construction of the scheme ML-KEM proceeds in two steps. First, the ideas discussed previously are used to construct a public-key encryption (PKE) scheme from the MLWE problem. Second, this PKE scheme is converted into a key-encapsulation mechanism using the so-called Fujisaki-Okamoto (FO) transform [11, 12]. Due to certain properties of the FO transform, the resulting KEM provides security in a significantly more general attack model than the PKE scheme. As a result, ML-KEM is believed to satisfy so-called IND-CCA2 security [1, 4, 13, 14]. 13

FIPS 203

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

The specification of the ML-KEM algorithms in this standard will follow the same pattern. Specifically, this standard will first describe a public-key encryption scheme called K-PKE (in Section 5) and then use the algorithms of K-PKE as subroutines when describing the algorithms of ML-KEM (in Sections 6 and 7). The cryptographic transformation from K-PKE to ML-KEM is crucial for achieving IND-CCA2 security. The scheme K-PKE is not IND-CCA2-secure and shall not be used as a stand-alone scheme (see Section 3.3). A notable feature of ML-KEM is the use of the number-theoretic transform (NTT). The NTT ̂ linear polynomials. converts a polynomial 𝑓 ∈ 𝑅𝑞 to an alternative representation as a vector 𝑓 of Working with NTT representations enables significantly faster multiplication of polynomials. Other operations (e.g., addition, rounding, and sampling) can be done in either representation. ML-KEM satisfies the essential KEM property of correctness. This means that in the absence of corruption or interference, the process in Figure 1 will result in 𝐾 ′ = 𝐾 with overwhelming probability. ML-KEM also comes with a proof of asymptotic theoretical security in a certain heuristic model [4]. Each of the parameter sets of ML-KEM comes with an associated security strength that was estimated based on current cryptanalysis (see Section 8 for details). Parameter sets and algorithms. Recall that a KEM consists of algorithms KeyGen, Encaps, and Decaps, along with a collection of parameter sets. In the case of ML-KEM, the three aforementioned algorithms are: 1. ML-KEM.KeyGen (Algorithm 19) 2. ML-KEM.Encaps (Algorithm 20) 3. ML-KEM.Decaps (Algorithm 21) These algorithms are described and discussed in detail in Section 7. ML-KEM comes equipped with three parameter sets: • ML-KEM-512 (security category 1) • ML-KEM-768 (security category 3) • ML-KEM-1024 (security category 5) These parameter sets are described and discussed in detail in Section 8. The security categories 1-5 are defined in SP 800-57, Part 1 [7]. Each parameter set assigns a particular numerical value to five integer variables: 𝑘, 𝜂1 , 𝜂2 , 𝑑𝑢 , and 𝑑𝑣 . The values of these variables in each parameter set are given in Table 2 of Section 8. In addition to these five variable parameters, there are also two constants: 𝑛 = 256 and 𝑞 = 3329. Decapsulation failures. Provided that all inputs are well-formed and randomness generation is successful, the key establishment procedure of ML-KEM will never explicitly fail, meaning that both ML-KEM.Encaps and ML-KEM.Decaps will each output a 256-bit value. Moreover, if no corruption or interference is present, the two 256-bit values produced by ML-KEM.Encaps and ML-KEM.Decaps will be equal with overwhelming probability (i.e., 𝐾 ′ will equal 𝐾 in the process described in Figure 1). The event that 𝐾 ′ ≠ 𝐾 under these conditions is called a decapsulation 14

FIPS 203

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

failure. Formally, the decapsulation failure probability is defined to be the probability (conditioned on no RGB failures) that the process 1. (ek, dk) ← ML-KEM.KeyGen() 2. (𝑐, 𝐾) ← ML-KEM.Encaps(ek) 3. 𝐾 ′ ← ML-KEM.Decaps(dk, 𝑐)

(3.1) (3.2) (3.3)

results in 𝐾 ′ ≠ 𝐾. The probability is taken over uniformly random seeds 𝑑, 𝑧 (sampled in ML-KEM.KeyGen) and 𝑚 (sampled in ML-KEM.Encaps) and under the heuristic assumption that hash functions and XOFs behave like uniformly random functions. The decapsulation failure rates for ML-KEM are listed in Table 1. For details, see Theorem 1 in [8] and the scripts in [15]. Table 1. Decapsulation failure rates for ML-KEM Parameter set ML-KEM-512 ML-KEM-768 ML-KEM-1024

Decapsulation failure rate 2−138.8 2−164.8 2−174.8

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, which 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 are sometimes referred to as “private keys.” In order to reduce confusion, this standard will not use the terms “public key” or “private key.” Instead, keys will be referred to only using the more specific terms, i.e., one of “encapsulation key”, “decapsulation key”, “encryption key”, “decryption key”, and “shared secret key”.

3.3 Requirements for ML-KEM Implementations This section describes several requirements for cryptographic modules that implement ML-KEM. Implementation requirements specific to particular algorithms will be described in later sections. Additional requirements, including requirements for using ML-KEM in specific applications, are given in SP 800-227 [1]. While conforming implementations must adhere to all of these requirements, adherence does not guarantee that the result will be secure (see Point 13 in the announcement). 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 13), K-PKE.Encrypt (Algorithm 14), and K-PKE.Decrypt (Algorithm 15) are not approved for use as a public-key encryption scheme. 15

FIPS 203

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

Controlled access to internal functions. The key-encapsulation mechanism ML-KEM makes use of internal, “derandomized” functions ML-KEM.KeyGen_internal, ML-KEM.Encaps_internal, and ML-KEM.Decaps_internal, specified in Section 6. The interfaces for these functions should not be made available to applications other than for testing purposes. In particular, the sampling of random values required for key generation (as specified in ML-KEM.KeyGen) and encapsulation (as specified in ML-KEM.Encaps) shall be performed by the cryptographic module. Equivalent implementations. For every algorithm that is specified in this standard, a conforming implementation may replace the given set of steps with any mathematically equivalent set of steps. In other words, the specified algorithm may be replaced with a different procedure that produces the correct output for every input (where “input” includes the specified input as well as all parameter values and all randomness). Approved usage of the shared secret key. If randomness generation is successful, the values 𝐾 and 𝐾 ′ returned by ML-KEM.Encaps and ML-KEM.Decaps, respectively, are always 256-bit values. Under appropriate conditions (see Sections 3.1 and 3.2, and SP 800-227 [1]), these values match (i.e., 𝐾 ′ = 𝐾) and can be used directly as a shared secret key for symmetric cryptography. If further key derivation is needed, the final symmetric keys shall be derived from this 256-bit shared secret key in an approved manner, as specified in SP 800-108 and SP 800-56C [16, 17]. As discussed in Section 3.2, ML-KEM is an IND-CCA2-secure KEM. However, a combined KEM that includes ML-KEM as a component might not meet IND-CCA2 security. Implementers should assess the security of any procedure in which the key derivation methods of SP 800-56C are applied to ML-KEM in combination with another key establishment procedure. More guidance regarding combined KEMs is given in SP 800-227 [1]. Randomness generation. Two algorithms in this standard require the generation of randomness as an internal step: ML-KEM.KeyGen and ML-KEM.Encaps. In pseudocode, this randomness $ generation is denoted by a statement of the form 𝑚 ←− 𝔹32 . A fresh string of random bytes must be generated for every such invocation. These random bytes shall be generated using an approved RBG, as prescribed in SP 800-90A, SP 800-90B, and SP 800-90C [18, 19, 20]. Moreover, this RBG shall have a security strength of at least 128 bits for ML-KEM-512, at least 192 bits for ML-KEM-768, and at least 256 bits for ML-KEM-1024. Input checking. The algorithms ML-KEM.Encaps and ML-KEM.Decaps require input checking. Implementers shall ensure that ML-KEM.Encaps and ML-KEM.Decaps are only executed on inputs that have been checked, as described in Section 7. Destruction of intermediate values. Data used in intermediate computation steps of KEM algorithms could be used by an adversary to compromise security. Therefore, implementers shall ensure that intermediate data is destroyed as soon as it is no longer needed. In particular, for ML-KEM.KeyGen, ML-KEM.Encaps, and ML-KEM.Decaps, only the designated output can be retained in memory after the algorithm terminates. All other data shall be destroyed prior to 16

FIPS 203

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

the algorithm terminating. There are two exceptions to this rule: 1. The seed (𝑑, 𝑧) generated in steps 1 and 2 of ML-KEM.KeyGen can be stored for later expansion using ML-KEM.KeyGen_internal. As this seed can be used to compute the decapsulation key, it is sensitive data and shall be treated with the same safeguards as a decapsulation key (see SP 800-227 [1]). 2. The matrix 𝐀̂ generated in steps 3-7 of K-PKE.KeyGen (as a subroutine of ML-KEM.KeyGen) can be stored so that it need not be recomputed in later operations (e.g., ML-KEM.Decaps). The same matrix 𝐀̂ is also generated in steps 4-8 of K-PKE.Encrypt (as a subroutine of ML-KEM.Encaps or ML-KEM.Decaps); it can also then be stored. In either case, the matrix 𝐀̂ is data that is easily computed from the public encapsulation key and thus does not require any special protections. No floating-point arithmetic. Implementations of ML-KEM shall not use floating-point arithmetic, as rounding errors in floating-point operations may lead to incorrect results in some cases. In all pseudocode in this standard in which division is performed (e.g., 𝑥/𝑦) and 𝑦 may not divide 𝑥, either ⌊𝑥/𝑦⌋, ⌈𝑥/𝑦⌉, or ⌈𝑥/𝑦⌋ is used. All of these can be computed without floating-point arithmetic, as ordinary integer division 𝑥/𝑦 computes ⌊𝑥/𝑦⌋, and ⌈𝑥/𝑦⌉ = ⌊(𝑥 + 𝑦 − 1)/𝑦⌋ for non-negative integers 𝑥 and positive integers 𝑦.

17

FIPS 203

4.

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

Auxiliary Algorithms

4.1 Cryptographic Functions The algorithms specified 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 [6]. They will be used as follows. SHA3-256 and SHA3-512 are hash functions with one variable-length input and one fixed-length output. In this standard, invocations of these functions on an input 𝑀 will be denoted by SHA3-256(𝑀 ) and SHA3-512(𝑀 ), respectively. The inputs and outputs for both SHA3-256 and SHA3-512 are always byte arrays. SHAKE128 and SHAKE256 are XOFs with one variable-length input and one variable-length output. This standard will adhere to the following conventions [6]: • The inputs and outputs for both SHAKE128 and SHAKE256 are always byte arrays. • When invoking SHAKE128 or SHAKE256, desired output length is always specified in bits. For example, the expression 𝑟 ∶= SHAKE128(𝑀 , 8 ⋅ 64)

(4.1)

implies that 𝑀 is an array of bytes and that 𝑟 is an array of 64 bytes. The aforementioned functions play several different roles in the algorithms specified in this standard and will only be invoked using the wrapper functions defined below. Importantly, these wrappers will avoid any potential “byte array” versus “bit-length” confusion by only working with bytes and byte array lengths. Pseudorandom function (PRF). The function PRF takes a parameter 𝜂 ∈ {2, 3}, one 32-byte input, and one 1-byte input. It produces one (64 ⋅ 𝜂)-byte output. It will be denoted by PRF ∶ {2, 3} × 𝔹32 × 𝔹 → 𝔹64𝜂 ,

(4.2)

PRF𝜂 (𝑠, 𝑏) ∶= SHAKE256(𝑠‖𝑏, 8 ⋅ 64 ⋅ 𝜂) ,

(4.3)

and it shall be instantiated as

where 𝜂 ∈ {2, 3}, 𝑠 ∈ 𝔹32 , and 𝑏 ∈ 𝔹. Note that 𝜂 is only used to specify the desired output length and not to perform domain separation. Hash functions. The specification will also make use of three hash functions H, J and G, which are defined as follows. The functions H and J each take one variable-length input and produce one 32-byte output. They will be denoted by H ∶ 𝔹∗ → 𝔹32 and J ∶ 𝔹∗ → 𝔹32 , respectively, and shall be instantiated as H(𝑠) ∶= SHA3-256(𝑠)

and 18

J(𝑠) ∶= SHAKE256(𝑠, 8 ⋅ 32)

(4.4)

FIPS 203

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

where 𝑠 ∈ 𝔹∗ . The function G takes one variable-length input and produces two 32-byte outputs. It will be denoted by G ∶ 𝔹∗ → 𝔹32 × 𝔹32 . The two outputs of G will be denoted by (𝑎, 𝑏) ← G(𝑐), where 𝑎, 𝑏 ∈ 𝔹32 , 𝑐 ∈ 𝔹∗ , and G(𝑐) = 𝑎‖𝑏. The function G shall be instantiated as G(𝑐) ∶= SHA3-512(𝑐) .

(4.5)

eXtendable-Output Function (XOF). This standard uses a XOF wrapper defined in terms of the incremental API for SHAKE128 in SP 800-185 [21]. This SHAKE128 API consists of three functions: • ctx ← SHAKE128.Init() Initializes a XOF “context” ctx. • ctx ← SHAKE128.Absorb(ctx, str) Injects data to be used in the “absorbing” phase of SHAKE128 and updates the context accordingly. • (ctx, 𝐵) ← SHAKE128.Squeeze(ctx, 8 ⋅ 𝑧) Extracts 𝑧 output bytes produced during the “squeezing” phase of SHAKE128 and updates the context accordingly. While the above functions are constructed using the Keccak-𝑓 permutation rather than the XOF SHAKE128 directly, they are defined so that a single SHAKE128 call of the form output ← SHAKE128(str1 ‖ … ‖str𝑚 , 8𝑏1 + … + 8𝑏ℓ )

(4.6)

is equivalent to performing Algorithm 2. This equivalence holds whether or not |str𝑖 | and 𝑏𝑗 are multiples of the SHAKE128 block length. Algorithm 2 SHAKE128example(str1 , … , str𝑚 , 𝑏1 , … , 𝑏ℓ ) Performs a sequence of absorbing operations followed by a sequence of squeezing operations. Input: byte arrays str1 , … , str𝑚 . Input: positive integers 𝑏1 , … , 𝑏ℓ . ℓ Output: a byte array of length ∑𝑗=1 𝑏𝑗 . 1: ctx ← SHAKE128.Init() ▷ initialize context 2: for (𝑖 ← 1; 𝑖 ≤ 𝑚; 𝑖 ++) 3: ctx ← SHAKE128.Absorb(ctx, str𝑖 ) ▷ absorb byte array str𝑖 4: end for 5: for (𝑗 ← 1; 𝑗 ≤ ℓ; 𝑗 ++) 6: (ctx, out𝑗 ) ← SHAKE128.Squeeze(ctx, 8 ⋅ 𝑏𝑗 ) ▷ squeeze 𝑏𝑗 -many bytes 7: end for 8: output ← out1 ‖ … ‖outℓ ▷ return the concatenation of all the results

In this standard, the incremental API for SHAKE128 will only be invoked through a wrapper XOF, 19

FIPS 203

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

which is defined as follows. 1. XOF.Init() = SHAKE128.Init(). 2. XOF.Absorb(ctx, str) = SHAKE128.Absorb(ctx, str). 3. XOF.Squeeze(ctx, ℓ) = SHAKE128.Squeeze(ctx, 8 ⋅ ℓ). Note that XOF.Squeeze requires the input length to be specified in bytes. This is consistent with the convention that all wrapper functions treat inputs and outputs as byte arrays and measure the lengths of all such arrays in terms of bytes.

4.2 General Algorithms This section specifies a number of algorithms that will be used as subroutines in ML-KEM. 4.2.1

Conversion and Compression Algorithms

This section specifies several algorithms for converting between bit arrays, byte arrays, and arrays of integers modulo 𝑚. It also specifies a certain operation for compressing integers modulo 𝑞, and the corresponding decompression operation. Algorithm 3 BitsToBytes(𝑏) Converts a bit array (of a length that is a multiple of eight) into an array of bytes. Input: bit array 𝑏 ∈ {0, 1}8⋅ℓ . Output: byte array 𝐵 ∈ 𝔹ℓ . 1: 𝐵 ← (0, … , 0) 2: for (𝑖 ← 0; 𝑖 < 8ℓ; 𝑖 ++) 3: 𝐵 [⌊𝑖/8⌋] ← 𝐵 [⌊𝑖/8⌋] + 𝑏[𝑖] ⋅ 2𝑖 mod 8 4: end for 5: return 𝐵 Algorithm 4 BytesToBits(𝐵) Performs the inverse of BitsToBytes, converting a byte array into a bit array. Input: byte array 𝐵 ∈ 𝔹ℓ . Output: bit array 𝑏 ∈ {0, 1}8⋅ℓ . 1: 𝐶 ← 𝐵 2: for (𝑖 ← 0; 𝑖 < ℓ; 𝑖 ++) 3: for (𝑗 ← 0; 𝑗 < 8; 𝑗 ++) 4: 𝑏[8𝑖 + 𝑗] ← 𝐶[𝑖] mod 2 5: 𝐶[𝑖] ← ⌊𝐶[𝑖]/2⌋ 6: end for 7: end for 8: return 𝑏

▷ copy 𝐵 into array 𝐶 ∈ 𝔹ℓ

20

FIPS 203

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

Converting between bits and bytes. The algorithms BitsToBytes (Algorithm 3) and BytesToBits (Algorithm 4) convert between bit arrays and byte arrays. The inputs to BitsToBytes and the outputs of BytesToBits are bit arrays, with each segment of eight bits representing a byte in little-endian order. As an example, the 8-bit string 11010001 corresponds to the byte 20 + 21 + 23 + 27 = 139. Compression and decompression. Recall that 𝑞 = 3329, and that the bit length of 𝑞 is 12. For 𝑑 < 12, define Compress𝑑 ∶ ℤ𝑞 ⟶ ℤ2𝑑 𝑥 ⟼ ⌈(2𝑑 /𝑞) ⋅ 𝑥⌋ mod 2𝑑 . Decompress𝑑 ∶ ℤ2𝑑 ⟶ ℤ𝑞

(4.7) (4.8)

𝑦 ⟼ ⌈(𝑞/2𝑑 ) ⋅ 𝑦⌋ . The input and output types of these functions are integers modulo 𝑚 (see Section 2.4.1). Division and rounding in the computation of these functions are performed in the set of rational numbers. Floating-point computations shall not be used. The Compress and Decompress algorithms satisfy two important properties. First, decompression followed by compression preserves the input. That is, Compress𝑑 (Decompress𝑑 (𝑦)) = 𝑦 for all 𝑦 ∈ ℤ2𝑑 and all 𝑑 < 12. Second, if 𝑑 is large (i.e., close to 12), compression followed by decompression does not significantly alter the value. Encoding and decoding. The algorithms ByteEncode (Algorithm 5) and ByteDecode (Algorithm 6) will be used for conversion between integers modulo 𝑚 and bytes. The algorithm ByteEncode converts an array of 𝑛 = 256 integers modulo 𝑚 into a corresponding array of bytes. ByteDecode performs the inverse operation, converting an array of bytes into an array of integers modulo 𝑚. Specifying the modulus 𝑚 is done as described below. For the following description, it is convenient to view ByteDecode and ByteEncode as converting between integers and bits. The conversion between bits and bytes is straightforward and done using BitsToBytes and BytesToBits. The valid range of values for the parameter 𝑑 is 1 ≤ 𝑑 ≤ 12. Bit arrays are divided into 𝑑-bit segments. The operations are performed in two different ways, depending on the value of 𝑑: • For 𝑑 satisfying 1 ≤ 𝑑 ≤ 11, the conversion is one-to-one. ByteDecode𝑑 converts each 𝑑-bit segment of its input into one integer modulo 2𝑑 , while ByteEncode𝑑 performs the inverse operation. • For 𝑑 = 12, ByteDecode12 produces integers modulo 𝑞 as output, while ByteEncode12 receives integers modulo 𝑞 as input. Specifically, ByteDecode12 converts each 12-bit segment of its input into an integer modulo 212 = 4096 and then reduces the result modulo 𝑞. This is no longer a one-to-one operation. Indeed, some 12-bit segments could correspond to an integer greater than 𝑞 − 1 = 3328 but less than 4096. However, this cannot occur for arrays produced by ByteEncode12 . These aspects of ByteDecode12 and 21

FIPS 203

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

ByteEncode12 will be important when considering checking of the ML-KEM encapsulation key in Section 7. Algorithm 5 ByteEncode𝑑 (𝐹 ) Encodes an array of 𝑑-bit integers into a byte array for 1 ≤ 𝑑 ≤ 12. 𝑑 Input: integer array 𝐹 ∈ ℤ256 𝑚 , where 𝑚 = 2 if 𝑑 < 12, and 𝑚 = 𝑞 if 𝑑 = 12. Output: byte array 𝐵 ∈ 𝔹32𝑑 . 1: for (𝑖 ← 0; 𝑖 < 256; 𝑖 ++) 2: 𝑎 ← 𝐹 [𝑖] ▷ 𝑎 ∈ ℤ𝑚 3: for (𝑗 ← 0; 𝑗 < 𝑑; 𝑗 ++) 4: 𝑏[𝑖 ⋅ 𝑑 + 𝑗] ← 𝑎 mod 2 ▷ 𝑏 ∈ {0, 1}256⋅𝑑 5: 𝑎 ← (𝑎 − 𝑏[𝑖 ⋅ 𝑑 + 𝑗])/2 ▷ note 𝑎 − 𝑏[𝑖 ⋅ 𝑑 + 𝑗] is always even 6: end for 7: end for 8: 𝐵 ← BitsToBytes(𝑏) 9: return 𝐵

Algorithm 6 ByteDecode𝑑 (𝐵) Decodes a byte array into an array of 𝑑-bit integers for 1 ≤ 𝑑 ≤ 12. Input: byte array 𝐵 ∈ 𝔹32𝑑 . 𝑑 Output: integer array 𝐹 ∈ ℤ256 𝑚 , where 𝑚 = 2 if 𝑑 < 12 and 𝑚 = 𝑞 if 𝑑 = 12. 1: 𝑏 ← BytesToBits(𝐵) 2: for (𝑖 ← 0; 𝑖 < 256; 𝑖 ++) 𝑑−1 3: 𝐹 [𝑖] ← ∑𝑗←0 𝑏[𝑖 ⋅ 𝑑 + 𝑗] ⋅ 2𝑗 mod 𝑚 4: end for 5: return 𝐹 4.2.2

Sampling Algorithms

The algorithms of ML-KEM require two sampling subroutines that are specified in Algorithms 7 and 8. Both of these algorithms can be used to convert a stream of uniformly random bytes into a sample from some desired distribution. In this standard, these algorithms will be invoked with a stream of pseudorandom bytes as the input. It follows that the output will then be a sample from a distribution that is computationally indistinguishable from the desired distribution. Uniform sampling of NTT representations. The algorithm SampleNTT (Algorithm 7) converts a seed together with two indexing bytes into a polynomial in the NTT domain. If the seed is uniformly random, the resulting polynomial will be drawn from a distribution that is computationally indistinguishable from the uniform distribution on 𝑇𝑞 . The output of SampleNTT is an array in ℤ256 that contains the coefficients of the sampled element of 𝑇𝑞 (see Section 2.4.4). See 𝑞 Appendix B for a note on (optionally) safely bounding the algorithm’s while-loop iterations. 22

FIPS 203

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

Algorithm 7 SampleNTT(𝐵) Takes a 32-byte seed and two indices as input and outputs a pseudorandom element of 𝑇𝑞 . Input: byte array 𝐵 ∈ 𝔹34 . Output: array 𝑎̂ ∈ ℤ256 𝑞 . 1: ctx ← XOF.Init() 2: ctx ← XOF.Absorb(ctx, 𝐵) 3: 𝑗 ← 0 4: while 𝑗 < 256 do 5: (ctx, 𝐶) ← XOF.Squeeze(ctx, 3) 6: 𝑑1 ← 𝐶[0] + 256 ⋅ (𝐶[1] mod 16) 7: 𝑑2 ← ⌊𝐶[1]/16⌋ + 16 ⋅ 𝐶[2] 8: if 𝑑1 < 𝑞 then 9: 𝑎[𝑗] ̂ ← 𝑑1 10: 𝑗 ← 𝑗+1 11: end if 12: if 𝑑2 < 𝑞 and 𝑗 < 256 then 13: 𝑎[𝑗] ̂ ← 𝑑2 14: 𝑗 ← 𝑗+1 15: end if 16: end while 17: return 𝑎̂

▷ a 32-byte seed along with two indices ▷ the coefficients of the NTT of a polynomial ▷ input the given byte array into XOF

▷ get a fresh 3-byte array 𝐶 from XOF ▷ 0 ≤ 𝑑1 < 212 ▷ 0 ≤ 𝑑2 < 212 ▷ 𝑎̂ ∈ ℤ256 𝑞

Sampling from the centered binomial distribution. ML-KEM makes use of a special distribution D𝜂 (𝑅𝑞 ) of polynomials in 𝑅𝑞 with small coefficients. Such polynomials are sometimes referred to as “errors” or “noise.” The distribution is parameterized by an integer 𝜂 ∈ {2, 3}. To sample a polynomial from D𝜂 (𝑅𝑞 ), each of its coefficients is independently sampled from a certain centered binomial distribution (CBD) on ℤ𝑞 . The algorithm SamplePolyCBD (Algorithm 8) samples the coefficient array of a polynomial 𝑓 ∈ 𝑅𝑞 according to the distribution D𝜂 (𝑅𝑞 ), provided that Algorithm 8 SamplePolyCBD𝜂 (𝐵) Takes a seed as input and outputs a pseudorandom sample from the distribution D𝜂 (𝑅𝑞 ). Input: byte array 𝐵 ∈ 𝔹64𝜂 . Output: array 𝑓 ∈ ℤ256 𝑞 . 1: 𝑏 ← BytesToBits(𝐵) 2: for (𝑖 ← 0; 𝑖 < 256; 𝑖 ++) 𝜂−1 3: 𝑥 ← ∑𝑗←0 𝑏[2𝑖𝜂 + 𝑗]

▷ the coefficients of the sampled polynomial

▷0≤𝑥≤𝜂

𝜂−1

𝑦 ← ∑𝑗←0 𝑏[2𝑖𝜂 + 𝜂 + 𝑗] 5: 𝑓[𝑖] ← 𝑥 − 𝑦 mod 𝑞 6: end for 7: return 𝑓 4:

▷0≤𝑦≤𝜂 ▷ 0 ≤ 𝑓[𝑖] ≤ 𝜂 or 𝑞 − 𝜂 ≤ 𝑓[𝑖] ≤ 𝑞 − 1

23

FIPS 203

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

its input is a stream of uniformly random bytes.

4.3 The Number-Theoretic Transform The Number-Theoretic Transform (NTT) can be viewed as a specialized, exact version of the discrete Fourier transform. In the case of ML-KEM, the NTT is used to improve the efficiency of multiplication in the ring 𝑅𝑞 . Recall that 𝑅𝑞 is the ring ℤ𝑞 [𝑋]/(𝑋 𝑛 + 1) of polynomials of the form 𝑓 = 𝑓0 + 𝑓1 𝑋 + ⋯ + 𝑓255 𝑋 255 (where 𝑓𝑗 ∈ ℤ𝑞 for all 𝑗), with the ring operations defined by arithmetic modulo 𝑋 𝑛 + 1. The ring 𝑅𝑞 is isomorphic to another ring 𝑇𝑞 , which is a direct sum of 128 quadratic extensions of ℤ𝑞 . The NTT is a computationally efficient isomorphism between these two rings. When a ̂ polynomial 𝑓 ∈ 𝑅𝑞 is input, the NTT outputs an element 𝑓 ̂ ∶= NTT(𝑓) of the ring 𝑇𝑞 , where 𝑓 is called the “NTT representation” of 𝑓. The isomorphism property implies that ̂ 𝑓 ×𝑅𝑞 𝑔 = NTT−1 (𝑓 × ̂ 𝑇𝑞 𝑔),

(4.9)

where ×𝑅𝑞 and ×𝑇𝑞 denote multiplication in 𝑅𝑞 and 𝑇𝑞 , respectively. Moreover, since 𝑇𝑞 is a product of 128 rings that each consist of polynomials of degree at most one, the operation ×𝑇𝑞 is much more efficient than the operation ×𝑅𝑞 . For these reasons, the NTT is considered to be an integral part of ML-KEM and not merely an optimization. As the rings 𝑅𝑞 and 𝑇𝑞 have a vector space structure over ℤ𝑞 , the most natural abstract data type to represent elements from either of these rings is ℤ𝑛𝑞 . For this reason, the choice of data structure for the inputs and outputs of NTT and NTT−1 are length-𝑛 arrays of integers modulo 𝑞. These arrays are understood to represent elements of 𝑇𝑞 or 𝑅𝑞 , respectively (see Section 2.4.4). Algorithms 9 and 10 describe an efficient means of computing NTT and NTT−1 in place. However, to clarify the distinction between the algebraic objects before and after the conversion, the algorithms are written with explicit inputs and outputs. This is consistent with this standard’s convention that all inputs are passed by copy. The mathematical structure of the NTT. In ML-KEM, 𝑞 is the prime 3329 = 28 ⋅ 13 + 1, and 𝑛 = 256. There are 128 primitive 256-th roots of unity and no primitive 512-th roots of unity in ℤ𝑞 . Note that 𝜁 = 17 ∈ ℤ𝑞 is a primitive 256-th root of unity modulo 𝑞. Thus, 𝜁 128 ≡ −1. Define BitRev7 (𝑖) to be the integer represented by bit-reversing the unsigned 7-bit value that corresponds to the input integer 𝑖 ∈ {0, … , 127}. The polynomial 𝑋 256 + 1 factors into 128 polynomials of degree 2 modulo 𝑞 as follows: 127

𝑋 256 + 1 = ∏ (𝑋 2 − 𝜁 2BitRev7 (𝑖)+1 ) .

(4.10)

𝑖=0

Therefore, 𝑅𝑞 ∶= ℤ𝑞 [𝑋]/(𝑋 256 + 1) is isomorphic to a direct sum of 128 quadratic extension

24

FIPS 203

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

fields of ℤ𝑞 , denoted 𝑇𝑞 . Specifically, this ring has the structure 127

𝑇𝑞 ∶= ⨁ ℤ𝑞 [𝑋]/ (𝑋 2 − 𝜁 2BitRev7 (𝑖)+1 ) .

(4.11)

𝑖=0

Thus, the NTT representation 𝑓 ̂ ∈ 𝑇𝑞 of a polynomial 𝑓 ∈ 𝑅𝑞 is the vector that consists of the corresponding residues of degree at most one: 𝑓 ̂ ∶= (𝑓 mod (𝑋 2 − 𝜁 2BitRev7 (0)+1 ), … , 𝑓 mod (𝑋 2 − 𝜁 2BitRev7 (127)+1 )) .

(4.12)

As discussed in Section 2.4.4, the algorithms in this standard represent 𝑓 ̂ as an array of 256 integers modulo 𝑞. Specifically, ̂ + 𝑓[2𝑖 ̂ + 1]𝑋, 𝑓 mod (𝑋 2 − 𝜁 2BitRev7 (𝑖)+1 ) = 𝑓[2𝑖]

(4.13)

for 𝑖 from 0 to 127. The ML-KEM NTT algorithms. An algorithm for the ML-KEM NTT is described in Algorithm 9. An algorithm for the inverse operation (NTT−1 ) is described in Algorithm 10. These two algorithms will be used to transform elements of 𝑅𝑞 to elements of 𝑇𝑞 (using NTT) and vice versa (using NTT−1 ). In addition, as discussed in Section 2.4.8, these algorithms represent the coordinatewise transformation of structures over those rings. Specifically, they map matrices/vectors with entries in 𝑅𝑞 to matrices/vectors with entries in 𝑇𝑞 (using NTT) and vice versa (using NTT−1 ). The values 𝜁 BitRev7 (𝑖) mod 𝑞 for 𝑖 = 1, … , 127 used in line 5 of Algorithm 9 and line 5 of Algorithm 10 may be precomputed into an array. This array is given in Appendix A.

25

FIPS 203

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

Algorithm 9 NTT(𝑓) ̂ the given polynomial 𝑓 ∈ 𝑅 . Computes the NTT representation 𝑓 of 𝑞 Input: array 𝑓 ∈ ℤ256 ▷ the coefficients of the input polynomial 𝑞 . 256 ̂ Output: array 𝑓 ∈ ℤ𝑞 . ▷ the coefficients of the NTT of the input polynomial 1: 𝑓 ̂ ← 𝑓 ▷ will compute in place on a copy of input array 2: 𝑖 ← 1 3: for (len ← 128; len ≥ 2; len ← len/2) 4: for (start ← 0; start < 256; start ← start + 2 ⋅ len) zeta ← 𝜁 BitRev7 (𝑖) mod 𝑞 5: 6: 𝑖 ← 𝑖+1 7: for (𝑗 ← start; 𝑗 < start + len; 𝑗 ++) ̂ + len] 8: 𝑡 ← zeta ⋅ 𝑓[𝑗 ▷ steps 8-10 done modulo 𝑞 ̂ ̂ 9: 𝑓[𝑗 + len] ← 𝑓[𝑗] − 𝑡 ̂ ← 𝑓[𝑗] ̂ +𝑡 10: 𝑓[𝑗] 11: end for 12: end for 13: end for 14: return 𝑓 ̂

Algorithm 10 NTT−1 (𝑓)̂ Computes the polynomial 𝑓 ∈ 𝑅𝑞 that corresponds to the given NTT representation 𝑓 ̂ ∈ 𝑇𝑞 . Input: array 𝑓 ̂ ∈ ℤ256 ▷ the coefficients of input NTT representation 𝑞 . 256 ▷ the coefficients of the inverse NTT of the input Output: array 𝑓 ∈ ℤ𝑞 . 1: 𝑓 ← 𝑓 ̂ ▷ will compute in place on a copy of input array 2: 𝑖 ← 127 3: for (len ← 2; len ≤ 128; len ← 2 ⋅ len) 4: for (start ← 0; start < 256; start ← start + 2 ⋅ len) zeta ← 𝜁 BitRev7 (𝑖) mod 𝑞 5: 6: 𝑖 ← 𝑖−1 7: for (𝑗 ← start; 𝑗 < start + len; 𝑗 ++) 8: 𝑡 ← 𝑓[𝑗] 9: 𝑓[𝑗] ← 𝑡 + 𝑓[𝑗 + len] ▷ steps 9-10 done modulo 𝑞 10: 𝑓[𝑗 + len] ← zeta ⋅ (𝑓[𝑗 + len] − 𝑡) 11: end for 12: end for 13: end for 14: 𝑓 ← 𝑓 ⋅ 3303 mod 𝑞 ▷ multiply every entry by 3303 ≡ 128−1 mod 𝑞 15: return 𝑓

26

FIPS 203

4.3.1

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

Multiplication in the NTT Domain

The addition and scalar multiplication of elements of 𝑇𝑞 can be done using the corresponding coordinate-wise arithmetic operations on the coefficient arrays (see Section 2.4.5). This section describes how to do the remaining ring operation (i.e., multiplication in 𝑇𝑞 ). Recall from (4.12) that 𝑓 ̂ ∈ 𝑇𝑞 is a vector of 128 degree-one residues modulo quadratic polynomials. Algebraically, multiplication in the ring 𝑇𝑞 consists of independent multiplication in each of the 128 coordinates with respect to the quadratic modulus of that coordinate. Specifically, ̂ the 𝑖-th coordinate in 𝑇𝑞 of the product ℎ̂ = 𝑓 × 𝑇𝑞 𝑔 ̂ is determined by the calculation ̂ + 𝑓[2𝑖 ̂ + 1]𝑋)(𝑔[2𝑖] ̂ ̂ + 1]𝑋 = (𝑓[2𝑖] ℎ[2𝑖] + ℎ[2𝑖 ̂ + 𝑔[2𝑖 ̂ + 1]𝑋) mod (𝑋 2 − 𝜁 2BitRev7 (𝑖)+1 ). (4.14) Algorithm 11 MultiplyNTTs(𝑓,̂ 𝑔)̂ Computes the product (in the ring 𝑇𝑞 ) of two NTT representations. and 𝑔 ̂ ∈ ℤ256 ▷ the coefficients of two NTT representations Input: Two arrays 𝑓 ̂ ∈ ℤ256 𝑞 𝑞 . 256 ̂ ▷ the coefficients of the product of the inputs Output: An array ℎ ∈ ℤ𝑞 . 1: for (𝑖 ← 0; 𝑖 < 128; 𝑖 ++) ̂ ̂ + 1], 𝑔[2𝑖], ̂ ̂ + 1]) ← BaseCaseMultiply(𝑓[2𝑖], ̂ ̂ + 1], 𝜁 2BitRev7 (𝑖)+1 ) 2: (ℎ[2𝑖], ℎ[2𝑖 𝑓[2𝑖 𝑔[2𝑖 3: end for 4: return ℎ̂ Thus, one can compute the product of two elements of 𝑇𝑞 using the algorithm MultiplyNTTs (Algorithm 11), which uses BaseCaseMultiply (Algorithm 12) as a subroutine. The values 𝜁 2BitRev7 (𝑖)+1 used in Algorithm 11 may be precomputed and stored in an array (see Appendix A). MultiplyNTTs also enables linear-algebraic arithmetic with matrices and vectors whose entries are in 𝑇𝑞 (see Section 2.4.7). Algorithm 12 BaseCaseMultiply(𝑎0 , 𝑎1 , 𝑏0 , 𝑏1 , 𝛾) Computes the product of two degree-one polynomials with respect to a quadratic modulus. Input: 𝑎0 , 𝑎1 , 𝑏0 , 𝑏1 ∈ ℤ𝑞 . Input: 𝛾 ∈ ℤ𝑞 . Output: 𝑐0 , 𝑐1 ∈ ℤ𝑞 . 1: 𝑐0 ← 𝑎0 ⋅ 𝑏0 + 𝑎1 ⋅ 𝑏1 ⋅ 𝛾 2: 𝑐1 ← 𝑎0 ⋅ 𝑏1 + 𝑎1 ⋅ 𝑏0 3: return (𝑐0 , 𝑐1 )

▷ the coefficients of 𝑎0 + 𝑎1 𝑋 and 𝑏0 + 𝑏1 𝑋 ▷ the modulus is 𝑋 2 − 𝛾 ▷ the coefficients of the product of the two polynomials ▷ steps 1-2 done modulo 𝑞

27

FIPS 203

5.

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

The K-PKE Component Scheme

This section describes the component scheme K-PKE. As discussed in Section 3.3, K-PKE is not approved for use in a stand-alone fashion. It serves only as a collection of subroutines for use in the algorithms of the approved scheme ML-KEM, as described in Section 7. K-PKE consists of three algorithms: 1. Key generation (K-PKE.KeyGen) 2. Encryption (K-PKE.Encrypt) 3. Decryption (K-PKE.Decrypt) When K-PKE is instantiated as part of ML-KEM, K-PKE inherits the parameter set selected for ML-KEM. Each parameter set specifies numerical values for each parameter. While 𝑛 is always 256 and 𝑞 is always 3329, the values of the remaining parameters 𝑘, 𝜂1 , 𝜂2 , 𝑑𝑢 , and 𝑑𝑣 vary among the three parameter sets. Parameters and parameter sets are described in Section 8. The algorithms in this section do not perform any input checking because they are only invoked as subroutines of the main ML-KEM algorithms. The algorithms of ML-KEM themselves do perform input checking as needed. Each of the algorithms of K-PKE 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 𝑅𝑞 . In the actual algorithm, most of the computations occur in the NTT domain in order to improve the efficiency of multiplication. The relevant vectors and matrices will then have entries in 𝑇𝑞 . Linear-algebraic arithmetic with such vectors and matrices (e.g., line 18 of K-PKE.KeyGen) is performed as described in Sections 2.4.7 and 4.3.1. The encryption and decryption keys of K-PKE are also stored in the NTT form.

5.1 K-PKE Key Generation The key generation algorithm K-PKE.KeyGen of K-PKE (Algorithm 13) receives a seed as input and outputs an encryption key ekPKE and a decryption key dkPKE . As is typically the case for public-key encryption, the encryption key can be made public, while the decryption key and the randomness must remain private. 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, the decryption key and seed of K-PKE.KeyGen must remain private as they can be used to perform decapsulation in ML-KEM. The matrix 𝐀̂ generated in steps 3-7 of K-PKE.KeyGen can be stored, as specified in Section 3.3. This allows later operations to use 𝐀̂ directly rather than re-expanding it from the public seed 𝜌. Informal description. The decryption key of K-PKE.KeyGen is a length-𝑘 vector 𝐬 of elements of 𝑅𝑞 (i.e., 𝐬 ∈ 𝑅𝑞𝑘 ). Roughly speaking, 𝐬 is a set of secret variables, while the encryption key is a collection of “noisy” linear equations (𝐀, 𝐀𝐬 + 𝐞) in the secret variables 𝐬. The rows of the matrix 𝐀 form the equation coefficients. This matrix is generated pseudorandomly using XOF with only a seed stored in the encryption key. The secret 𝐬 and the “noise” 𝐞 are sampled from 28

FIPS 203

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

Algorithm 13 K-PKE.KeyGen(𝑑) Uses randomness to generate an encryption key and a corresponding decryption key. Input: randomness 𝑑 ∈ 𝔹32 . Output: encryption key ekPKE ∈ 𝔹384𝑘+32 . Output: decryption key dkPKE ∈ 𝔹384𝑘 . 1: (𝜌, 𝜎) ← G(𝑑‖𝑘) ▷ expand 32+1 bytes to two pseudorandom 32-byte seeds1 2: 𝑁 ← 0 𝑘×𝑘 ̂ (ℤ256 3: for (𝑖 ← 0; 𝑖 < 𝑘; 𝑖 ++) ▷ generate matrix 𝐀∈ 𝑞 ) 4: for (𝑗 ← 0; 𝑗 < 𝑘; 𝑗 ++) ̂ 𝑗] ← SampleNTT(𝜌‖𝑗‖𝑖) 5: 𝐀[𝑖, ▷ 𝑗 and 𝑖 are bytes 33 and 34 of the input 6: end for 7: end for 𝑘 8: for (𝑖 ← 0; 𝑖 < 𝑘; 𝑖 ++) ▷ generate 𝐬 ∈ (ℤ256 𝑞 ) 9: 𝐬[𝑖] ← SamplePolyCBD𝜂 (PRF𝜂1 (𝜎, 𝑁 )) ▷ 𝐬[𝑖] ∈ ℤ256 sampled from CBD 𝑞 1 10: 𝑁 ← 𝑁 +1 11: end for 𝑘 12: for (𝑖 ← 0; 𝑖 < 𝑘; 𝑖 ++) ▷ generate 𝐞 ∈ (ℤ256 𝑞 ) 13: 𝐞[𝑖] ← SamplePolyCBD𝜂 (PRF𝜂1 (𝜎, 𝑁 )) ▷ 𝐞[𝑖] ∈ ℤ256 sampled from CBD 𝑞 1 14: 𝑁 ← 𝑁 +1 15: end for 16: 𝐬 ̂ ← NTT(𝐬) ▷ run NTT 𝑘 times (once for each coordinate of 𝐬) ▷ run NTT 𝑘 times 17: 𝐞̂ ← NTT(𝐞) ̂ ̂ 18: 𝐭 ← 𝐀 ∘ 𝐬 ̂ + 𝐞̂ ▷ noisy linear system in NTT domain ̂ ̂ 19: ekPKE ← ByteEncode12 (𝐭)‖𝜌 ▷ run ByteEncode12 𝑘 times, then append 𝐀-seed 20: dkPKE ← ByteEncode12 (𝐬)̂ ▷ run ByteEncode12 𝑘 times 21: return (ekPKE , dkPKE ) centered binomial distributions using randomness expanded from another seed 𝜎 via PRF. Once 𝐀, 𝐬, and 𝐞 are generated, the computation of the final part 𝐭 = 𝐀𝐬 + 𝐞 of the encryption key takes place. The results are appropriately encoded into byte arrays and output. In K-PKE.KeyGen, the choice of parameter set affects the length of the secret 𝐬 (via the parameter 𝑘) and, as a consequence, the sizes of the noise vector 𝐞 and the pseudorandom matrix 𝐀. The choice of parameter set also affects the noise distribution (via the parameter 𝜂1 ) used to sample the entries of 𝐬 and 𝐞.

5.2 K-PKE Encryption The encryption algorithm K-PKE.Encrypt of K-PKE (Algorithm 14) takes an encryption key ekPKE , a 32-byte plaintext 𝑚, and randomness 𝑟 as input and produces a single output: a ciphertext 𝑐. 1 Byte 33 of the input to G is the module dimension 𝑘 ∈ {2, 3, 4} ⊂ 𝔹. This is included to establish domain separation

between the three parameter sets. For implementations that use the seed in place of the private key, this ensures that the expansion will produce an unrelated key if the seed is mistakenly expanded using a parameter set other than the originally intended one.

29

FIPS 203

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

The matrix 𝐀̂ generated in steps 4-8 of K-PKE.Encrypt can be stored, as specified in Section 3.3. This allows later operations to use 𝐀̂ directly rather than re-expanding it from the public seed 𝜌. Algorithm 14 K-PKE.Encrypt(ekPKE , 𝑚, 𝑟) Uses the encryption key to encrypt a plaintext message using the randomness 𝑟. Input: encryption key ekPKE ∈ 𝔹384𝑘+32 . Input: message 𝑚 ∈ 𝔹32 . Input: randomness 𝑟 ∈ 𝔹32 . Output: ciphertext 𝑐 ∈ 𝔹32(𝑑𝑢 𝑘+𝑑𝑣 ) . 1: 𝑁 ← 0 𝑘 2: 𝐭̂ ← ByteDecode12 (ekPKE [0 ∶ 384𝑘]) ▷ run ByteDecode12 𝑘 times to decode 𝐭̂ ∈ (ℤ256 𝑞 ) 3: 𝜌 ← ekPKE [384𝑘 ∶ 384𝑘 + 32] ▷ extract 32-byte seed from ekPKE 𝑘×𝑘 ++ 4: for (𝑖 ← 0; 𝑖 < 𝑘; 𝑖 ) ▷ re-generate matrix 𝐀̂ ∈ (ℤ256 sampled in Alg. 13 𝑞 ) 5: for (𝑗 ← 0; 𝑗 < 𝑘; 𝑗 ++) ̂ 𝑗] ← SampleNTT(𝜌‖𝑗‖𝑖) 6: 𝐀[𝑖, ▷ 𝑗 and 𝑖 are bytes 33 and 34 of the input 7: end for 8: end for 𝑘 9: for (𝑖 ← 0; 𝑖 < 𝑘; 𝑖 ++) ▷ generate 𝐲 ∈ (ℤ256 𝑞 ) 10: 𝐲[𝑖] ← SamplePolyCBD𝜂 (PRF𝜂1 (𝑟, 𝑁 )) ▷ 𝐲[𝑖] ∈ ℤ256 sampled from CBD 𝑞 1 11: 𝑁 ← 𝑁 +1 12: end for 𝑘 13: for (𝑖 ← 0; 𝑖 < 𝑘; 𝑖 ++) ▷ generate 𝐞𝟏 ∈ (ℤ256 𝑞 ) 256 14: 𝐞𝟏 [𝑖] ← SamplePolyCBD𝜂 (PRF𝜂2 (𝑟, 𝑁 )) ▷ 𝐞𝟏 [𝑖] ∈ ℤ𝑞 sampled from CBD 2 15: 𝑁 ← 𝑁 +1 16: end for 17: 𝑒2 ← SamplePolyCBD𝜂 (PRF𝜂 (𝑟, 𝑁 )) ▷ sample 𝑒2 ∈ ℤ256 from CBD 𝑞 2 2 18: 𝐲̂ ← NTT(𝐲) ▷ run NTT 𝑘 times −1 ⊺ ̂ 19: 𝐮 ← NTT (𝐀 ∘ 𝐲) ̂ + 𝐞𝟏 ▷ run NTT−1 𝑘 times 20: 𝜇 ← Decompress1 (ByteDecode1 (𝑚)) −1 ̂ ∘ 𝐲)̂ + 𝑒2 + 𝜇 21: 𝑣 ← NTT (𝐭⊺ ▷ encode plaintext 𝑚 into polynomial 𝑣 22: 𝑐1 ← ByteEncode𝑑 (Compress𝑑 (𝐮)) ▷ run ByteEncode𝑑 and Compress𝑑 𝑘 times 𝑢 𝑢 𝑢 𝑢 23: 𝑐2 ← ByteEncode𝑑 (Compress𝑑 (𝑣)) 𝑣 𝑣 24: return 𝑐 ← (𝑐1 ‖𝑐2 )

Informal description. The algorithm K-PKE.Encrypt begins by extracting the vector 𝐭 and the seed from the encryption key. The seed is then expanded to re-generate the matrix 𝐀 in the same manner as was done in K-PKE.KeyGen. If 𝐭 and 𝐀 are derived correctly from an encryption key produced by K-PKE.KeyGen, then they are equal to their corresponding values in K-PKE.KeyGen. Recall from the description of key generation that the pair (𝐀, 𝐭 = 𝐀𝐬 + 𝐞) can be thought of as a system of noisy linear equations in the secret variables 𝐬. One can generate an additional noisy linear equation in the same secret variables — without knowing 𝐬 — by picking a random linear 30

FIPS 203

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

combination of the noisy equations in the system (𝐀, 𝐭). One can then encode information in the “constant term” (i.e., the entry that is a linear combination of entries of 𝐭) of such a combined equation. This information can then be deciphered by a party in possession of 𝐬. For example, one could encode a single bit by deciding whether or not to significantly alter the constant term, thus making either a nearly correct equation that corresponds to the decrypted bit value of 0 or a far-from-correct equation that corresponds to the decrypted bit value of 1. In the case of K-PKE, the constant term is a polynomial with 256 coefficients, so one can encode more information: one bit in each coefficient. To this end, K-PKE.Encrypt proceeds by generating a vector 𝐲 ∈ 𝑅𝑞𝑘 and noise terms 𝐞𝟏 ∈ 𝑅𝑞𝑘 and 𝑒2 ∈ 𝑅𝑞 , all of which are sampled from the centered binomial distribution using pseudorandomness expanded via PRF from the input randomness 𝑟. One then computes the “new noisy equation,” which is (up to some details) (𝐀⊺ 𝐲 + 𝐞1 , 𝐭⊺ 𝐲 + 𝑒2 ). An appropriate encoding 𝜇 of the input message 𝑚 is then added to the latter term in the pair. Finally, the resulting pair (𝐮, 𝑣) is compressed, serialized into a byte array, and output as the ciphertext.

5.3 K-PKE Decryption The decryption algorithm K-PKE.Decrypt of K-PKE (Algorithm 15) takes a decryption key dkPKE and a ciphertext 𝑐 as input, requires no randomness, and outputs a plaintext 𝑚. Informal description. The algorithm K-PKE.Decrypt begins by recovering a pair (𝐮′ , 𝑣′ ) from the ciphertext 𝑐 (see the description of K-PKE.Encrypt). Here, one can think of 𝐮′ as the coefficients of the equation and 𝑣′ as the constant term. The decryption key dkPKE contains the vector of secret variables 𝐬. The decryption algorithm can thus use the decryption key to compute the true constant term 𝑣 = 𝐬⊺ 𝐮′ and calculate 𝑣′ − 𝑣. The decryption algorithm ends by decoding the plaintext message 𝑚 from 𝑣′ − 𝑣 and outputting 𝑚. Algorithm 15 K-PKE.Decrypt(dkPKE , 𝑐) Uses the decryption key to decrypt a ciphertext. Input: decryption key dkPKE ∈ 𝔹384𝑘 . Input: ciphertext 𝑐 ∈ 𝔹32(𝑑𝑢 𝑘+𝑑𝑣 ) . Output: message 𝑚 ∈ 𝔹32 . 1: 𝑐1 ← 𝑐[0 ∶ 32𝑑𝑢 𝑘] 2: 𝑐2 ← 𝑐[32𝑑𝑢 𝑘 ∶ 32(𝑑𝑢 𝑘 + 𝑑𝑣 )] 3: 𝐮′ ← Decompress𝑑 (ByteDecode𝑑 (𝑐1 )) ▷ run Decompress𝑑 and ByteDecode𝑑 𝑘 times 𝑢 𝑢 𝑢 𝑢 4: 𝑣′ ← Decompress𝑑 (ByteDecode𝑑 (𝑐2 )) 𝑣 𝑣 5: 𝐬 ̂ ← ByteDecode12 (dkPKE ) ▷ run ByteDecode12 𝑘 times −1 ⊺ ′ ′ 6: 𝑤 ← 𝑣 − NTT (𝐬 ̂ ∘ NTT(𝐮 )) ▷ run NTT 𝑘 times; run NTT−1 once 7: 𝑚 ← ByteEncode1 (Compress1 (𝑤)) ▷ decode plaintext 𝑚 from polynomial 𝑣 8: return 𝑚

31

FIPS 203

6.

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

Main Internal Algorithms

This section specifies three algorithms: ML-KEM.KeyGen_internal, ML-KEM.Encaps_internal, and ML-KEM.Decaps_internal. These three algorithms are all deterministic, meaning that their output is completely determined by their input. No randomness is sampled inside of these algorithms. These three algorithms will be used to construct ML-KEM in Section 7. The algorithms in this section make use of the parameters 𝑛, 𝑞, 𝑘, 𝑑𝑢 , and 𝑑𝑣 . The subroutines they invoke additionally make use of the parameters 𝜂1 and 𝜂2 . While 𝑛 is always 256 and 𝑞 is always 3329, the remaining parameters vary among the possible parameter sets (see Section 8). The interfaces specified in this section will be used to test ML-KEM implementations through the Cryptographic Algorithm Validation Program (CAVP). The key generation function in this section may also be used to re-expand a key from a seed (see Section 3.3), including when obtaining assurance of private key possession via regeneration. As prescribed in Section 3.3, the interfaces specified in this section should not be made available to applications other than for testing purposes, and the random seeds (as specified in ML-KEM.KeyGen and ML-KEM.Encaps in Section 7) shall be generated by the cryptographic module.

6.1 Internal Key Generation The algorithm ML-KEM.KeyGen_internal (Algorithm 16) accepts two random seeds as input, and produces an encapsulation key and a decapsulation key. Informal description. The core subroutine of ML-KEM.KeyGen_internal is the key generation algorithm of K-PKE (Algorithm 13). The encapsulation key is simply the encryption key of K-PKE. The decapsulation key consists of the decryption key of K-PKE, the encapsulation key, a hash of the encapsulation key, and a random 32-byte value. This random value will be used in the ”implicit rejection” mechanism of the internal decapsulation algorithm (Algorithm 18). Algorithm 16 ML-KEM.KeyGen_internal(𝑑, 𝑧) Uses randomness to generate an encapsulation key and a corresponding decapsulation key. Input: randomness 𝑑 ∈ 𝔹32 . Input: randomness 𝑧 ∈ 𝔹32 . Output: encapsulation key ek ∈ 𝔹384𝑘+32 . Output: decapsulation key dk ∈ 𝔹768𝑘+96 . 1: (ekPKE , dkPKE ) ← K-PKE.KeyGen(𝑑) 2: ek ← ekPKE 3: dk ← (dkPKE ‖ek‖H(ek)‖𝑧) 4: return (ek, dk)

▷ run key generation for K-PKE ▷ KEM encaps key is just the PKE encryption key ▷ KEM decaps key includes PKE decryption key

6.2 Internal Encapsulation The algorithm ML-KEM.Encaps_internal (Algorithm 17) accepts an encapsulation key and a random byte array as input and outputs a ciphertext and a shared key. 32

FIPS 203

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

Algorithm 17 ML-KEM.Encaps_internal(ek, 𝑚) Uses the encapsulation key and randomness to generate a key and an associated ciphertext. Input: encapsulation key ek ∈ 𝔹384𝑘+32 . Input: randomness 𝑚 ∈ 𝔹32 . Output: shared secret key 𝐾 ∈ 𝔹32 . Output: ciphertext 𝑐 ∈ 𝔹32(𝑑𝑢 𝑘+𝑑𝑣 ) . 1: (𝐾, 𝑟) ← G(𝑚‖H(ek)) 2: 𝑐 ← K-PKE.Encrypt(ek, 𝑚, 𝑟) 3: return (𝐾, 𝑐)

▷ derive shared secret key 𝐾 and randomness 𝑟 ▷ encrypt 𝑚 using K-PKE with randomness 𝑟

Informal description. The core subroutine of ML-KEM.Encaps_internal is the encryption algorithm of K-PKE, which is used to encrypt a random value 𝑚 into a ciphertext 𝑐. A copy of the shared secret key 𝐾 and the randomness used during encryption are derived from 𝑚 and the encapsulation key ek via hashing. Specifically, H is applied to ek, and the result is concatenated with 𝑚 and then hashed using G. Finally, the algorithm outputs the shared secret key 𝐾 and the ciphertext 𝑐.

6.3 Internal Decapsulation The algorithm ML-KEM.Decaps_internal (Algorithm 18) accepts a decapsulation key and a ciphertext as input, does not use any randomness, and outputs a shared secret key. Informal description. The algorithm ML-KEM.Decaps_internal begins by parsing out the components of the decapsulation key dk of ML-KEM. These components are an (encryption key, decryption key) pair for K-PKE, a hash value ℎ, and a random value 𝑧. The decryption key of K-PKE is then used to decrypt the input ciphertext 𝑐 to get a plaintext 𝑚′ . The decapsulation algorithm then re-encrypts 𝑚′ and computes a candidate shared secret key 𝐾 ′ in the same manner as should have been done in encapsulation. Specifically, 𝐾 ′ and the encryption randomness 𝑟′ are computed by hashing 𝑚′ and the encryption key of K-PKE, and a ciphertext 𝑐′ is generated by encrypting 𝑚′ using randomness 𝑟′ . Finally, decapsulation checks whether the resulting ciphertext 𝑐′ matches the provided ciphertext 𝑐. If it does not, the algorithm performs an “implicit rejection”: the value of 𝐾 ′ is changed to a hash of 𝑐 together with the random value 𝑧 stored in the ML-KEM secret key (see the discussion of decapsulation failures in Section 3.2). In either case, decapsulation outputs the resulting shared secret key 𝐾 ′ . The “implicit reject” flag computed in step 9 (by comparing 𝑐 and 𝑐′ ) is a secret piece of intermediate data. As specified in the requirements in Section 3.3, this flag shall be destroyed prior to ML-KEM.Decaps_internal terminating. In particular, returning the value of the flag as an output in any form is not permitted.

33

FIPS 203

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

Algorithm 18 ML-KEM.Decaps_internal(dk, 𝑐) Uses the decapsulation key to produce a shared secret key from a ciphertext. Input: decapsulation key dk ∈ 𝔹768𝑘+96 . Input: ciphertext 𝑐 ∈ 𝔹32(𝑑𝑢 𝑘+𝑑𝑣 ) . Output: shared secret key 𝐾 ∈ 𝔹32 . 1: dkPKE ← dk[0 ∶ 384𝑘] ▷ extract (from KEM decaps key) the PKE decryption key 2: ekPKE ← dk[384𝑘 ∶ 768𝑘 + 32] ▷ extract PKE encryption key 3: ℎ ← dk[768𝑘 + 32 ∶ 768𝑘 + 64] ▷ extract hash of PKE encryption key 4: 𝑧 ← dk[768𝑘 + 64 ∶ 768𝑘 + 96] ▷ extract implicit rejection value 5: 𝑚′ ← K-PKE.Decrypt(dkPKE , 𝑐) ▷ decrypt ciphertext ′ ′ ′ 6: (𝐾 , 𝑟 ) ← G(𝑚 ‖ℎ) 7: 𝐾̄ ← J(𝑧‖𝑐) 8: 𝑐′ ← K-PKE.Encrypt(ekPKE , 𝑚′ , 𝑟′ ) ▷ re-encrypt using the derived randomness 𝑟′ 9: if 𝑐 ≠ 𝑐 ′ then 10: 𝐾 ′ ← 𝐾̄ ▷ if ciphertexts do not match, “implicitly reject” 11: end if 12: return 𝐾 ′

34

FIPS 203

7.

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

The ML-KEM Key-Encapsulation Mechanism

This section describes the three main algorithms of the ML-KEM scheme: 1. Key generation (ML-KEM.KeyGen) 2. Encapsulation (ML-KEM.Encaps) 3. Decapsulation (ML-KEM.Decaps) To instantiate ML-KEM, one must select a parameter set. Each parameter set is associated with a particular 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 of Section 8. Each parameter set assigns specific numerical values to the individual parameters 𝑛, 𝑞, 𝑘, 𝜂1 , 𝜂2 , 𝑑𝑢 , and 𝑑𝑣 . While 𝑛 is always 256 and 𝑞 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 is selected appropriately for the desired application. Moreover, implementers shall ensure that the parameter set used in any particular invocation of ML-KEM.Encaps or ML-KEM.Decaps matches the parameter set associated to the provided inputs.

7.1 ML-KEM Key Generation The key generation algorithm ML-KEM.KeyGen for ML-KEM (Algorithm 19) accepts no input, generates randomness internally, and produces an encapsulation key and a decapsulation key. While the encapsulation key can be made public, the decapsulation key shall remain private. The seed (𝑑, 𝑧) generated in steps 1 and 2 of ML-KEM.KeyGen can be stored for later expansion using ML-KEM.KeyGen_internal (see Section 3.3). As the seed can be used to compute the decapsulation key, it is sensitive data and shall be treated with the same safeguards as a decapsulation key (see SP 800-227 [1]). Algorithm 19 ML-KEM.KeyGen() Generates an encapsulation key and a corresponding decapsulation key. Output: encapsulation key ek ∈ 𝔹384𝑘+32 . Output: decapsulation key dk ∈ 𝔹768𝑘+96 . $ 1: 𝑑 ← ▷ 𝑑 is 32 random bytes (see Section 3.3) − 𝔹32 $ 32 2: 𝑧 ← ▷ 𝑧 is 32 random bytes (see Section 3.3) −𝔹 3: if 𝑑 == NULL or 𝑧 == NULL then 4: return ⊥ ▷ return an error indication if random bit generation failed 5: end if 6: (ek, dk) ← ML-KEM.KeyGen_internal(𝑑, 𝑧) ▷ run internal key generation algorithm 7: return (ek, dk) Secure key establishment depends on the use of key pairs that have been properly generated via ML-KEM.KeyGen. If the owner of a KEM key pair did not generate the key pair but instead received it from a trusted third party or other source, the owner may optionally perform certain 35

FIPS 203

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

checks on the key pair. While these checks can detect certain corruptions, they do not guarantee that the key pair was properly generated. Key pair check. To check a candidate key pair1 (ek, dk), perform the following checks: 1. (Seed consistency) If a seed (𝑑, 𝑧) is available, run ML-KEM.KeyGen_internal(𝑑, 𝑧), and verify that the output is equal to (ek, dk). 2. (Encapsulation key check) Check ek as specified in Section 7.2. 3. (Decapsulation key check) Check dk as specified in Section 7.3. 4. (Pair-wise consistency) Perform the following steps: $

i. Generate an array of 32 random bytes by performing 𝑚 ←− 𝔹32 . ii. Perform (𝐾, 𝑐) ← ML-KEM.Encaps_internal(ek, 𝑚). iii. Perform 𝐾 ′ ← ML-KEM.Decaps_internal(dk, 𝑐). iv. Reject unless 𝐾 == 𝐾 ′ . It is important to note that this checking process does not guarantee that the key pair is a properly produced output of ML-KEM.KeyGen.

7.2 ML-KEM Encapsulation The encapsulation algorithm ML-KEM.Encaps of ML-KEM (Algorithm 20) accepts an encapsulation key as input, generates randomness internally, and outputs a ciphertext and a shared key. This algorithm requires input checking, as specified below. Encapsulation key check. To check a candidate encapsulation key ek, perform the following: 1. (Type check) If ek is not an array of bytes of length 384𝑘 + 32 for the value of 𝑘 specified by the relevant parameter set, then input checking failed. 2. (Modulus check) Perform the computation test ← ByteEncode12 (ByteDecode12 (ek[0 ∶ 384𝑘]))

(7.1)

(see Section 4.2.1). If test ≠ ek[0 ∶ 384𝑘], then input checking failed. This check ensures that the integers encoded in the public key are in the valid range [0, 𝑞 − 1]. If both checks pass, then ML-KEM.Encaps can be run with input ek ∶= ek. It is important to note that this checking process does not guarantee that ek is a properly produced output of ML-KEM.KeyGen. ML-KEM.Encaps shall not be run with an encapsulation key that has not been checked as above. However, checking of the encapsulation key need not be performed by the encapsulating party, 1 In discussions of input checking, the “low overline” in the notation indicates that the input has not yet been

checked (e.g., ek has not yet been checked, while ek has passed the check).

36

FIPS 203

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

nor with every execution of ML-KEM.Encaps. Instead, assurance that these checks have been performed can be acquired through other means (see SP 800-227 [1]). Algorithm 20 ML-KEM.Encaps(ek) Uses the encapsulation key to generate a shared secret key and an associated ciphertext. Checked input: encapsulation key ek ∈ 𝔹384𝑘+32 . Output: shared secret key 𝐾 ∈ 𝔹32 . Output: ciphertext 𝑐 ∈ 𝔹32(𝑑𝑢 𝑘+𝑑𝑣 ) . $ 1: 𝑚 ← ▷ 𝑚 is 32 random bytes (see Section 3.3) − 𝔹32 2: if 𝑚 == NULL then 3: return ⊥ ▷ return an error indication if random bit generation failed 4: end if 5: (𝐾, 𝑐) ← ML-KEM.Encaps_internal(ek, 𝑚) ▷ run internal encapsulation algorithm 6: return (𝐾, 𝑐)

7.3 ML-KEM Decapsulation The decapsulation algorithm ML-KEM.Decaps of ML-KEM (Algorithm 21) accepts a decapsulation key and an ML-KEM ciphertext as input, does not use any randomness, and outputs a shared secret. This algorithm requires input checking, as specified below. Decapsulation input check. To check a candidate decapsulation key dk and ciphertext 𝑐, perform the following checks: 1. (Ciphertext type check) If 𝑐 is not a byte array of length 32(𝑑𝑢 𝑘 + 𝑑𝑣 ) for the values of 𝑑𝑢 , 𝑑𝑣 , and 𝑘 specified by the relevant parameter set, then input checking has failed. 2. (Decapsulation key type check) If dk is not a byte array of length 768𝑘 + 96 for the value of 𝑘 specified by the relevant parameter set, then input checking has failed. 3. (Hash check) Perform the computation test ← H(dk[384𝑘 ∶ 768𝑘 + 32])) .

(7.2)

If test ≠ dk[768𝑘 + 32 ∶ 768𝑘 + 64], then input checking has failed. If all of the above checks pass, then ML-KEM.Decaps can be run with inputs dk ∶= dk and 𝑐 ∶= 𝑐. It is important to note that this checking process does not guarantee that dk is a properly produced output of ML-KEM.KeyGen, nor that 𝑐 is a properly produced output of ML-KEM.Encaps. ML-KEM.Decaps shall not be run with a decapsulation key or a ciphertext unless both have been checked. However, checking of the decapsulation key need not be performed by the decapsulating party, nor with every execution of ML-KEM.Decaps. Instead, assurance that this check has been performed can be acquired through other means (see SP 800-227 [1]). Ciphertext checking shall be performed with every execution of ML-KEM.Decaps.

37

FIPS 203

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

Algorithm 21 ML-KEM.Decaps(dk, 𝑐) Uses the decapsulation key to produce a shared secret key from a ciphertext. Checked input: decapsulation key dk ∈ 𝔹768𝑘+96 . Checked input: ciphertext 𝑐 ∈ 𝔹32(𝑑𝑢 𝑘+𝑑𝑣 ) . Output: shared secret key 𝐾 ∈ 𝔹32 . 1: 𝐾 ′ ← ML-KEM.Decaps_internal(dk, 𝑐) 2: return 𝐾 ′

38

▷ run internal decapsulation algorithm

FIPS 203

8.

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

Parameter Sets

ML-KEM is equipped with three parameter sets, each of the which comprises five individual parameters: 𝑘, 𝜂1 , 𝜂2 , 𝑑𝑢 , and 𝑑𝑣 . There are also two constants: 𝑛 = 256 and 𝑞 = 3329. The following is a brief and informal description of the roles played by the variable parameters in the algorithms of K-PKE and ML-KEM. See Section 5 for details. • The parameter 𝑘 determines the dimensions of the matrix 𝐀̂ that appears in K-PKE.KeyGen and K-PKE.Encrypt. It also determines the dimensions of vectors 𝐬 and 𝐞 in K-PKE.KeyGen and the dimensions of vectors 𝐲 and 𝐞1 in K-PKE.Encrypt. • The parameter 𝜂1 is required to specify the distribution for generating the vectors 𝐬 and 𝐞 in K-PKE.KeyGen and the vector 𝐲 in K-PKE.Encrypt. • The parameter 𝜂2 is required to specify the distribution for generating the vectors 𝐞1 and 𝑒2 in K-PKE.Encrypt. • The parameters 𝑑𝑢 and 𝑑𝑣 serve as parameters and inputs for the functions Compress, Decompress, ByteEncode, and ByteDecode in K-PKE.Encrypt and K-PKE.Decrypt. This standard approves the parameter sets given in Table 2. Each parameter set is associated with a required security strength for randomness generation (see Section 3.3). The sizes of the ML-KEM keys and ciphertexts for each parameter set are summarized in Table 3. Table 2. Approved parameter sets for ML-KEM

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

𝑛 256 256 256

𝑞 𝑘 3329 2 3329 3 3329 4

𝜂1 3 2 2

𝜂2 2 2 2

𝑑𝑢 10 10 11

𝑑𝑣 4 4 5

required RBG strength (bits) 128 192 256

Table 3. Sizes (in bytes) of keys and ciphertexts of 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

A parameter set name can also be said to denote a (parameter-free) KEM. Specifically, ML-KEM-𝑥 can be used to denote the parameter-free KEM that results from instantiating the scheme ML-KEM with the parameter set ML-KEM-𝑥. The three parameter sets included in Table 2 were designed to meet certain security strength categories defined by NIST in its original Call for Proposals [4, 22]. These security strength categories are explained further in SP 800-57, Part 1 [7]. Using this approach, security strength is not described by a single number, such as “128 bits of security.” Instead, each ML-KEM parameter set is claimed to be at least as secure as a generic 39

FIPS 203

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

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 or hash function when those computational resources are estimated using any realistic model of computation. Different models of computation can be more or less realistic and, accordingly, lead to more or less accurate estimates of security strength. Some commonly studied models are discussed in [23]. Concretely, ML-KEM-512 is claimed to be in security category 1, ML-KEM-768 is claimed to be in security category 3, and ML-KEM-1024 is claimed to be in security category 5. For additional discussion of the security strength of MLWE-based cryptosystems, see [4]. 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, or objects such as keys or ciphertexts may be unacceptably large). NIST recommends using ML-KEM-768 as the default parameter set, as it provides a large security margin at a reasonable performance cost. In cases where this is impractical or even higher security is required, other parameter sets may be used.

40

FIPS 203

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

References [1] National Institute of Standards and Technology (2024) Recommendations for keyencapsulation mechanisms, (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-227. [Forthcoming; will be available at https://csrc.nist.gov/publications]. [2] Barker EB, Chen L, Roginsky AL, Vassilev A, Davis R (2018) Recommendation for pair-wise key-establishment schemes using discrete logarithm cryptography (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-56A Revision 3. https://doi.org/10.6028/NIST.SP.800-56Ar3. [3] Barker EB, Chen L, Roginsky AL, Vassilev A, Davis R, Simon S (2019) Recommendation for pair-wise key-establishment using integer factorization cryptography (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-56B Revision 2. https://doi.org/10.6028/NIST.SP.800-56Br2. [4] Avanzi R, Bos J, Ducas L, Kiltz E, Lepoint T, Lyubashevsky V, Schanck JM, Schwabe P, Seiler G, Stehlé D (2020) CRYSTALS-Kyber algorithm specifications and supporting documentation, Third-round submission to the NIST’s post-quantum cryptography standardization process. Available at https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cry ptography-standardization/round-3-submissions. [5] National Institute of Standards and Technology (2015) Secure hash standard (SHS), (U.S. Department of Commerce, Washington, DC), Federal Information Processing Standards Publication (FIPS) 180-4. https://doi.org/10.6028/NIST.FIPS.180-4. [6] National Institute of Standards and Technology (2015) SHA-3 standard: Permutation-based hash and extendable-output functions, (U.S. Department of Commerce, Washington, DC), Federal Information Processing Standards Publication (FIPS) 202. https://doi.org/10.6028/ NIST.FIPS.202. [7] Barker EB (2020) Recommendation for key management: Part 1 - General, (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-57 Part 1, Rev. 5 [or as amended]. https://doi.org/10.6028/NIST.SP.800-57pt1r5. [8] Bos J, Ducas L, Kiltz E, Lepoint T, Lyubashevsky V, Schanck JM, Schwabe P, Seiler G, Stehlé D (2018) CRYSTALS-Kyber: A CCA-secure module-lattice-based KEM. 2018 IEEE European Symposium on Security and Privacy (EuroS&P), pp 353–367. https://doi.org/10.1109/Euro SP.2018.00032. [9] Langlois A, Stehlé D (2015) Worst-case to average-case reductions for module lattices. Designs, Codes and Cryptography 75(3):565–599. https://doi.org/10.1007/s10623-014-9 938-4. [10] Regev O (2005) On lattices, learning with errors, random linear codes, and cryptography. Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing STOC ’05 (Association for Computing Machinery, New York, NY, USA), pp 84––93. https://doi.org/ 10.1145/1060590.1060603.

41

FIPS 203

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

[11] Fujisaki E, Okamoto T (2013) Secure integration of asymmetric and symmetric encryption schemes. Journal of Cryptology 26:80–101. https://doi.org/10.1007/s00145-011-9114-1. [12] Hofheinz D, Hövelmanns K, Kiltz E (2017) A modular analysis of the Fujisaki-Okamoto transformation. Theory of Cryptography, eds Kalai Y, Reyzin L (Springer International Publishing, Cham), pp 341–371. https://doi.org/10.1007/978-3-319-70500-2_12. [13] Katz J, Lindell Y (2020) Introduction to Modern Cryptography (Chapman & Hall/CRC), 3rd Ed. [14] Almeida JB, Olmos SA, Barbosa M, Barthe G, Dupressoir F, Grégoire B, Laporte V, Léchenet JC, Low C, Oliveira T, Pacheco H, Quaresma M, Schwabe P, Strub PY (2024) Formally verifying Kyber episode V: Machine-checked IND-CCA security and correctness of ML-KEM in EasyCrypt, Cryptology ePrint Archive, Paper 2024/843. Available at https://eprint.iacr.org/2024/843. [15] Ducas L, Schanck J (2021) Security estimation scripts for Kyber and Dilithium, Github repository. Available at https://github.com/pq-crystals/security-estimates. [16] Chen L (2022) Recommendation for key derivation using pseudorandom functions, (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-108r1-upd1, Includes updates as of February 2, 2024. https://doi.org/10.6028/NIST.SP. 800-108r1-upd1. [17] Barker EB, Chen L, Davis R (2020) Recommendation for key-derivation methods in keyestablishment schemes (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-56C Revision 2. https://doi.org/10.6028/NIST.SP.800-56C r2. [18] Barker EB, Kelsey JM (2015) Recommendation for random number generation using deterministic random bit generators, (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-90A, Rev. 1. https://doi.org/10.6028/NIST.SP. 800-90Ar1. [19] Sönmez Turan M, Barker EB, Kelsey JM, McKay KA, Baish ML, Boyle M (2018) Recommendation for the entropy sources used for random bit generation, (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-90B. https://doi.org/10.6028/NIST.SP.800-90B. [20] Barker E, Kelsey J, McKay K, Roginsky A, Turan MS (2024) Recommendation for random bit generator (RBG) constructions, (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-90C 4pd. https://doi.org/10.6028/NIST.SP.80 0-90C.4pd. [21] Kelsey J, Chang S, Perlner R (2016) SHA-3 Derived Functions: cSHAKE, KMAC, TupleHash and ParallelHash, (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-185 [or as amended]. https://doi.org/10.6028/NIST.SP.800-1 85. [22] National Institute of Standards and Technology (2016) Submission requirements and evaluation criteria for the post-quantum cryptography standardization process. Available at https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/call-f or-proposals-final-dec-2016.pdf. 42

FIPS 203

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

[23] Alagic G, Apon D, Cooper D, Dang Q, Dang T, Kelsey J, Lichtinger J, Liu YK, Miller C, Moody D, Peralta R, Perlner R, Robinson A, Smith-Tone D (2022) Status report on the third round of the NIST post-quantum cryptography standardization process (National Institute of Standards and Technology, Gaithersburg, MD), NIST Interagency or Internal Report (IR) 8413. https://doi.org/10.6028/NIST.IR.8413-upd1. [24] CRYSTALS-Kyber submission team (2023) “Discussion about Kyber’s tweaked FO transform”, PQC-Forum Post. Available at https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/W FRDl8DqYQ4. [25] CRYSTALS-Kyber submission team (2023) “Kyber decisions, part 2: FO transform”, PQCForum Post. Available at https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/C0D3W 1KoINY/m/99kIvydoAwAJ.

43

FIPS 203

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

Appendix A — Precomputed Values for the NTT The following 128 numbers are the values of 𝜁 BitRev7 (𝑖) mod 𝑞 for 𝑖 ∈ {0, … , 127}. These numbers are used in Algorithms 9 and 10. {1

1729

2580

3289

2642

630

1897

848

1062

1919

193

797

2786

3260

569

1746

296

2447

1339

1476

3046

56

2240

1333

1426

2094

535

2882

2393

2879

1974

821

289

331

3253

1756

1197

2304

2277

2055

650

1977

2513

632

2865

33

1320

1915

2319

1435

807

452

1438

2868

1534

2402

2647

2617

1481

648

2474

3110

1227

910

17

2761

583

2649

1637

723

2288

1100

1409

2662

3281

233

756

2156

3015

3050

1703

1651

2789

1789

1847

952

1461

2687

939

2308

2437

2388

733

2337

268

641

1584

2298

2037

3220

375

2549

2090

1645

1063

319

2773

757

2099

561

2466

2594

2804

1092

403

1026

1143

2150

2775

886

1722

1212

1874

1029

2110

2935

885

2154 }

44

FIPS 203

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

When implementing Algorithm 11, the values 𝜁 2BitRev7 (𝑖)+1 mod 𝑞 need to be computed. The following array contains these values for 𝑖 ∈ {0, … , 127}: { 17

-17

2761

-2761

583

-583

2649

-2649

1637

-1637

723

-723

2288

-2288

1100

-1100

1409

-1409

2662

-2662

3281

-3281

233

-233

756

-756

2156

-2156

3015

-3015

3050

-3050

1703

-1703

1651

-1651

2789

-2789

1789

-1789

1847

-1847

952

-952

1461

-1461

2687

-2687

939

-939

2308

-2308

2437

-2437

2388

-2388

733

-733

2337

-2337

268

-268

641

-641

1584

-1584

2298

-2298

2037

-2037

3220

-3220

375

-375

2549

-2549

2090

-2090

1645

-1645

1063

-1063

319

-319

2773

-2773

757

-757

2099

-2099

561

-561

2466

-2466

2594

-2594

2804

-2804

1092

-1092

403

-403

1026

-1026

1143

-1143

2150

-2150

2775

-2775

886

-886

1722

-1722

1212

-1212

1874

-1874

1029

-1029

2110

-2110

2935

-2935

885

-885

2154

-2154 }

45

FIPS 203

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

Appendix B — SampleNTT Loop Bounds In SampleNTT (Algorithm 7), the algorithm repeatedly generates byte arrays from the XOF to create an element of 𝑇𝑞 . If a generated byte array value is out of bounds for a coefficient of 𝑇𝑞 , the algorithm tries again until all 256 coefficients are created. On average, this while loop will resolve within a reasonable number of iterations. However, there may be cases in which the generated byte arrays are consistently out of bounds and the algorithm may run for a higher number of iterations. Implementations should not bound this loop, if at all possible. An incorrect limit will cause interoperability errors, and the chances for SampleNTT to iterate longer become exponentially rare. If an implementation does bound the number of iterations of SampleNTT, it shall not use a limit lower than those presented in Table 4. The calculated probability of SampleNTT exceeding the limit is included and calculated under standard assumptions about the output distributions of XOFs and hash functions. Table 4. While-loop limits and probabilities of occurrence for SampleNTT Number of iterations

Probability of reaching limit

280

2−261

If a limit is used and the number of iterations exceeds the limit, then the algorithm shall destroy all intermediate results. If a return value or exception is produced, it shall be the same value for any execution in which the maximum number of iterations is exceeded.

46

FIPS 203

MODULE-LATTICE-BASED KEY-ENCAPSULATION MECHANISM

Appendix C — Differences From the CRYSTALS-Kyber Submission This appendix lists the differences between CRYSTALS-KYBER (as described in [4]) and the ML-KEM scheme (specified in this document) that result in differing input-output behavior of the main algorithms (i.e., KeyGen, Encaps, Decaps). Since a conforming implementation need only match the input-output behavior of these three algorithms (see “Implementations” and Section 3.3 below), the list 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), nor any differences in presentation between this standard and [4].

C.1 Differences Between CRYSTALS-Kyber and FIPS 203 Initial Public Draft • In the third-round specification [4], the shared secret key was treated as a variable-length value whose length depended on how it would be used in the relevant application. In this specification, the length of the shared secret key is fixed to 256 bits. It can be used directly in applications as a symmetric key, or symmetric keys can be derived from it, as specified in Section 3.3. • The ML-KEM.Encaps and ML-KEM.Decaps algorithms in this specification use a different variant of the Fujisaki-Okamoto transform (see [24, 25]) than the third-round specification [4]. Specifically, ML-KEM.Encaps no longer includes a hash of the ciphertext in the derivation of the shared secret, and ML-KEM.Decaps has been adjusted to match this change. • In the third-round specification [4], the initial randomness 𝑚 in the ML-KEM.Encaps algorithm was first hashed before being used. Specifically, between lines 1 and 2 in Algorithm 20, there was an additional step that performed the operation 𝑚 ← 𝐻(𝑚). The purpose of this step was to safeguard against the use of flawed randomness generation processes. As this standard requires the use of NIST-approved randomness generation, this step is unnecessary and is not performed in ML-KEM. • This specification includes explicit input checking steps that were not part of the third-round specification [4]. For example, ML-KEM.Encaps requires that the byte array containing the encapsulation key correctly decodes to an array of integers modulo 𝑞 without any modular reductions.

C.2 Changes From FIPS 203 Initial Public Draft The differences between CRYSTALS-KYBER and ML-KEM as described in Appendix C were included in the initial public draft (ipd) of FIPS 203, which was posted on August 24, 2023. Based on comments submitted on the draft ML-KEM, domain separation was added to K-PKE.KeyGen to prevent the misuse of keys generated to target one security level from being used for a different security level when saving a key as a seed. Additionally, FIPS 203 ipd had inadvertently swapped the indices of matrix 𝐀̂ in K-PKE.KeyGen and K-PKE.Encrypt. This was changed back in the final version of ML-KEM to match CRYSTALS-KYBER. 47

Related documents

• NIST FIPS 198-1: The Keyed-Hash Message Authentication Code (HMAC)#2812
• Coherent File Distribution Protocol#133543
• CircLS: Compiling Lattice Surgery to Physical Circuits with Dynamic Allocation#1049958
• MHOT: Height-Optimized Authenticated Data Structure for Blockchain State Commitment#271813
• NIST SP 800-56Cr2: Recommendation for Key-Derivation Methods in Key-Establishment Schemes#3020