NIST FIPS 204: Module-Lattice-Based Digital Signature Standard

FIPS 204 Federal Information Processing Standards Publication

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

Subcategory: Cryptography

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

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

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

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

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

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

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

Announcing the Module-Lattice-Based Digital Signature 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 Digital Signature Standard (FIPS 204). 2. Category of Standard. Computer Security. Subcategory. Cryptography. 3. Explanation. This standard specifies ML-DSA, a lattice-based digital signature algorithm for applications that require a digital signature rather than a written signature. Additional digital signature schemes are specified and approved in other NIST Special Publications and FIPS publications (e.g., FIPS 186-5 [1]). A digital signature is represented in a computer as a string of bits and computed using a set of rules and parameters that allow the identity of the signatory and the integrity of the data to be verified. Digital signatures may be generated on both stored and transmitted data. Signature generation uses a private key to generate a digital signature. Signature verification uses a public key that corresponds to but is not the same as the private key. Each signatory possesses a key-pair composed of a private key and a corresponding public key. Public keys may be known by the public, but private keys must be kept secret. Anyone can verify the signature by employing the signatory’s public key. Only the user who possesses the private key can generate a signature that can be verified by the corresponding public key. The digital signature is provided to the intended verifier along with the signed data. The verifying entity verifies the signature by using the claimed signatory’s public key. Similar procedures may be used to generate and verify signatures for both stored and transmitted data. This standard specifies several parameter sets for ML-DSA that are approved for use. Additional parameter sets may be specified and approved in future NIST Special Publications. 4. Approving Authority. Secretary of Commerce. 5. Maintenance Agency. Department of Commerce, National Institute of Standards and Technology, Information Technology Laboratory (ITL). 6. Applicability. This standard is applicable to all federal departments and agencies for the protection of sensitive unclassified information that is not subject to section 2315 of Title 10, United States Code, or section 3502 (2) of Title 44, United States Code. Either this standard, FIPS 205, FIPS 186-5, or NIST Special Publication 800-208 shall be used in designing and implementing public-key-based signature systems that federal departments and agencies operate or that are operated for them under contract. In the future, additional digital signature schemes may be specified and approved in FIPS or NIST Special Publications. The adoption and use of this standard are available to private and commercial organizations.

i

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

7. Applications. A digital signature algorithm allows an entity to authenticate the integrity of signed data and the identity of the signatory. The recipient of a signed message can use a digital signature as evidence in demonstrating to a third party that the signature was, in fact, generated by the claimed signatory. This is known as non-repudiation since the signatory cannot easily repudiate the signature at a later time. A digital signature algorithm is intended for use in electronic mail, electronic funds transfer, electronic data interchange, software distribution, data storage, and other applications that require data integrity assurance and data origin authentication. 8. Implementations. A digital signature algorithm may be implemented in software, firmware, hardware, or any combination thereof. NIST will develop a validation program to test implementations for conformance to the algorithm in this standard. 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. Information about validation programs is available at https://csrc.nist.gov/projects/cmvp. Examples for digital signature algorithms are available at https://csrc.nist.gov/projects/cryptographic-standards -and-guidelines/example-values. Agencies are advised that digital signature key pairs shall not be used for other purposes. 9. Other Approved Security Functions. Digital signature implementations that comply with this standard shall employ cryptographic algorithms that have been approved for protecting Federal Governmentsensitive information. Approved cryptographic algorithms and techniques include those that 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. 10. Export Control. Certain cryptographic devices and technical data regarding them are subject to federal export controls. Exports of cryptographic modules that implement this standard and technical data regarding them must comply with these federal regulations and be licensed by the Bureau of Industry and Security of the U.S. Department of Commerce. Information about export regulations is available at https://www.bis.doc.gov. 11. Patents. The algorithm in this standard may be covered by U.S. or foreign patents. 12. Implementation Schedule. This standard becomes effective immediately upon final publication. 13. Specifications. Federal Information Processing Standards (FIPS) 204, Module-Lattice-Based Digital Signature Standard (affixed). 14. Qualifications. The security of a digital signature system depends on maintaining the secrecy of the signatory’s private keys. Signatories shall, therefore, guard against the disclosure of their private keys. While it is the intent of this standard to specify general security requirements for generating digital signatures, conformance to this standard does not ensure that a particular implementation is secure. It is the responsibility of an implementer to ensure that any module that implements a digital signature capability is designed and built in a secure manner. Similarly, the use of a product containing an implementation that conforms to this standard does 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.

ii

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

Since a standard of this nature must be flexible enough to adapt to advancements and innovations in science and technology, this standard will be reviewed every five years in order to assess its adequacy. 15. Waiver Procedure. The Federal Information Security Management Act (FISMA) does not allow for waivers to Federal Information Processing Standards (FIPS) that are made mandatory by the Secretary of Commerce. 16. Where to Obtain Copies of the Standard. This publication is available by accessing https://csrc.nist. gov/publications. Other computer security publications are available at the same website. 17. How to Cite This Publication. NIST has assigned NIST FIPS 204 as the publication identifier for this FIPS, per the NIST Technical Series Publication Identifier Syntax. NIST recommends that it be cited as follows: National Institute of Standards and Technology (2024) Module-Lattice-Based Digital Signature Standard. (Department of Commerce, Washington, D.C.), Federal Information Processing Standards Publication (FIPS) NIST FIPS 204. https://doi.org/10.6028/NIST.FIPS.204 18. Inquiries and Comments. Inquiries and comments about this FIPS may be submitted to fips-204comments@nist.gov.

iii

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

Federal Information Processing Standards Publication 204 Specification for the

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

1

1.1

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

1

1.2

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

1

2 Glossary of Terms, Acronyms, and Symbols

2

2.1

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

2

2.2

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

5

2.3

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

5

2.4

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

7 7 7 8

2.5

3 Overview of the ML-DSA Signature Scheme

9

3.1

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

9

3.2

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

9

3.3

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

9

3.4

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

11

3.5

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

11

3.6

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

12 12 12 12 13 13

3.7

4 Parameter Sets

15

5 External Functions

17

5.1

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

17

5.2

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

17

5.3

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

18

iv

FIPS 204

5.4

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

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

6 Internal Functions

18 19 22

6.1

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

22

6.2

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

23

6.3

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

25

7 Auxiliary Functions

28

7.1

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

28

7.2

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

33

7.3

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

36

7.4

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

39

7.5

NTT and NTT−1

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42

7.6

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

45

References

47

Appendix A — Montgomery Multiplication

50

Appendix B — Zetas Array

51

Appendix C — Loop Bounds

52

Appendix D — Differences from the CRYSTALS-DILITHIUM Submission

54

D.1

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

D.2

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

D.3

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

v

54

54

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

List of Tables Table 1 Table 2 Table 3

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

15 16 52

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

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

vi

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

FIPS 204

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

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

vii

41 41 43 44 44 45 45 45 46 46 50

FIPS 204

1.

Introduction

1.1

Purpose and Scope

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

This standard defines a digital signature scheme, which includes a method for digital signature generation that can be used for the protection of binary data (commonly called a “message”) and a method for the verification and validation of those digital signatures. NIST Special Publication (SP) 800-175B [2], Guideline for Using Cryptographic Standards in the Federal Government: Cryptographic Mechanisms, includes a general discussion of digital signatures. This standard specifies the mathematical steps that need to be performed for key generation, signature generation, and signature verification. In order for digital signatures to be valid, additional assurances are required, such as assurance of identity and of private key possession. SP 800-89, Recommendation for Obtaining Assurances for Digital Signature Applications [3], specifies the required assurances and the methods for obtaining them. The digital signature scheme approved in this standard is the Module-Lattice-Based Digital Signature Algorithm (ML-DSA), which is based on the Module Learning With Errors problem [4]. ML-DSA is believed to be secure, even against adversaries in possession of a large-scale fault-tolerant quantum computer. In particular, ML-DSA is believed to be strongly unforgeable, which implies that the scheme can be used to detect unauthorized modifications to data and to authenticate the identity of the signatory (one bound to the possession of the private-key). In addition, a signature generated by this scheme can be used as evidence in demonstrating to a third party that the signature was, in fact, generated by the claimed signatory. The latter property is known as non-repudiation since the signatory cannot easily repudiate the signature at a later time. This standard gives algorithms for ML-DSA key generation, signature generation, and signature verification (Section 5), and for supporting algorithms used by them (Section 7). ML-DSA is standardized with three possible parameter sets, each of which corresponds to a different security strength. Section 4 describes the global parameters used by these algorithms and enumerates the parameter sets for ML-DSA that are approved by this standard. ML-DSA can be used in place of other digital signature schemes specified in NIST FIPS and Special Publications (e.g., FIPS 186-5, Digital Signature Standard (DSS) [1]).

1.2

Context

Over the past several years, there has been steady progress toward building quantum computers. The security of many commonly used public-key cryptosystems will be at risk if large-scale quantum computers are ever realized. This would include key-establishment schemes and digital signatures that are based on integer factorization and discrete logarithms (both over finite fields and elliptic curves). As a result, in 2016, NIST initiated a public Post-Quantum Cryptography (PQC) Standardization process to select quantumresistant public-key cryptographic algorithms for standardization. A total of 82 candidate algorithms were submitted to NIST for consideration. After three rounds of evaluation and analysis, NIST selected the first four algorithms for standardization. ML-DSA is derived from one of the selected schemes, CRYSTALS-DILITHIUM [5, 6], and is intended to protect sensitive U.S. Government information well into the foreseeable future, including after the advent of cryptographically relevant quantum computers. For the differences between ML-DSA and CRYSTALSDILITHIUM, see Appendix D.

1

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

2.

Glossary of Terms, Acronyms, and Symbols

2.1

Terms and Definitions

approved

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

assurance of possession

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

asymmetric cryptography

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

bit string

An ordered sequence of zeros and ones.

byte

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

byte string

An ordered sequence of bytes.

certificate

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

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

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

destroy

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

digital signature

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

entity

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

equivalent process

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

eXtendable-Output Function (XOF)

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

2

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

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. fresh random value

A previously unused output of a random bit generator.

hash function

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

hash value

See message digest.

key

A parameter used in conjunction with a cryptographic algorithm that determines its operation. Examples of cryptographic algorithms applicable to this standard include: 1. The computation of a digital signature from data 2. The verification of a digital signature

key pair

A public key and its corresponding private key.

little-endian

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

message

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

message digest

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

non-repudiation

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

owner

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

party

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

public-key infrastructure (PKI)

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

3

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

private key

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

pseudorandom

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

public key

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

security category

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

security strength

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

seed

A bit string used as input to a pseudorandom process.

shall

Used to indicate a requirement of this standard.

should

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

signatory

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

signature generation

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

signature validation

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

signature verification

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

signed data

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

trusted third party (TTP)

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

verifier

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

4

FIPS 204

2.2

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

Acronyms

AES

Advanced Encryption Standard

API

Application Programming Interface

DER

Distinguished Encoding Rules

FIPS

Federal Information Processing Standard

ML-DSA

Module-Lattice-Based Digital Signature Algorithm

MLWE

Module Learning With Errors

NIST

National Institute of Standards and Technology

NIST IR

NIST Interagency or Internal Report

NTT

Number Theoretic Transform

OID

Object Identifier

PQC

Post-Quantum Cryptography

RBG

Random Bit Generator

SHA

Secure Hash Algorithm

SHAKE

Secure Hash Algorithm KECCAK

SP

Special Publication

SUF-CMA

Strongly existentially UnForgeable under Chosen Message Attack

XOF

eXtendable-Output Function

2.3

Mathematical Symbols

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

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

𝔹

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

ℕ

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

ℤ

The ring of integers.

ℤ𝑚

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

ℤ𝑛 𝑚

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

𝑅

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

𝑅𝑚

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

5

FIPS 204

1

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD 255

𝐵𝜏

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

Π

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

𝑇𝑞

The ring Π255 𝑗=0 ℤ𝑞 .

𝐴×𝐵

Cartesian product of two sets 𝐴, 𝐵.

[𝑎, 𝑏]

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

bitlen 𝑎

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

BitRev8 (𝑟)

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

0x

Prefix to an integer written in hexadecimal representation.

log2 𝑥

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

mod

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

mod±

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

⌊𝑥⌋

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

⌈𝑥⌉

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

‖⋅‖∞

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

𝑎!

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

(𝑎𝑏)

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

𝑠←𝑥

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

𝑠 ← 𝔹ℓ

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

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

6

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

𝑥∈𝑆←𝑦

Type casting. The variable 𝑥 is assigned a value in a set 𝑆 that is constructed from the value of an expression 𝑦 in a possibly different set 𝑇. The set 𝑇 and the mapping from 𝑇 to 𝑆 are not explicitly specified, but they should be obvious from the context in which this statement appears.

[[𝑎 < 𝑏]]

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

⟨⟨𝑓(𝑥)⟩⟩

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

𝑎||𝑏

Concatenation of two bit or byte strings 𝑎 and 𝑏.

𝑎∘𝑏

Multiplication of 𝑎 and 𝑏 in the ring 𝑇𝑞 .

𝑎 ⋅ 𝑏 or 𝑎𝑏

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

𝑎+𝑏

Addition of 𝑎 and 𝑏.

𝑎/𝑏

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

⊥

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

2.4

Notation

2.4.1

Rings

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

2.4.2

Vectors and Matrices

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

7

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

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

2.5

NTT Representation

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

(2.1)

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

8

FIPS 204

3.

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

Overview of the ML-DSA Signature Scheme

ML-DSA is a digital signature scheme based on CRYSTALS-DILITHIUM [6]. It consists of three main algorithms: ML-DSA.KeyGen (Algorithm 1), ML-DSA.Sign (Algorithm 2), and ML-DSA.Verify (Algorithm 3). The ML-DSA scheme uses the Fiat-Shamir With Aborts construction [10, 11] and bears the most resemblance to the schemes proposed in [12, 13]. This document also defines a closely related but domain-separated signature scheme, HashML-DSA, which differs from ML-DSA in that it includes an additional pre-hashing step before signing. It consists of three main algorithms: ML-DSA.KeyGen (Algorithm 1), which is the same key generation algorithm used for ML-DSA; HashML-DSA.Sign (Algorithm 4); and HashML-DSA.Verify (Algorithm 5).

3.1

Security Properties

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

3.2

Computational Assumptions

Security for lattice-based digital signature schemes is typically related to the Learning With Errors (LWE) problem and the short integer solution (SIS) problem. The LWE problem [15] is to recover a vector 𝐬 ∈ ℤ𝑛 𝑞 given a set of random “noisy” linear equations2 satisfied by 𝐬. The SIS problem is to find a non-zero solution 𝐭 ∈ ℤ𝑛 𝑞 for a given linear system over ℤ𝑞 of the form 𝐀𝐭 = 𝟎 such that ‖𝐭‖∞ is small. For appropriate choices of parameters, these problems are intractable for the best known techniques, including Gaussian elimination. When the module ℤ𝑛 𝑞 in LWE and SIS is replaced by a module over a ring larger than ℤ𝑞 (e.g., 𝑅𝑞 ), the resulting problems are called Module Learning With Errors (MLWE) [4] and Module Short Integer Solution (MSIS). The security of ML-DSA is based on the MLWE problem over 𝑅𝑞 and a nonstandard variant of MSIS called SelfTargetMSIS [16].

3.3

ML-DSA Construction

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

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

9

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

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

10

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

• To reduce signature size, rather than including the commitment 𝐰Approx = 𝐀𝐲+𝐲2 in the signature, the ML-DSA signature uses a rounded version of 𝐰 = 𝐀𝐲 as a commitment 𝐰1 and includes only the hash 𝑐 ̃ of 𝐰1 ||𝜇. • To ensure that 𝐰1 can be reconstructed by the verifier from 𝐳 and the compressed value 𝐭1 , the signature must also include a hint 𝐡 ∈ 𝑅2𝑘 computed by the signer using the signer’s private key. • Additionally, to ensure correctness, a second stage of rejection sampling must be included (Line 28 of Algorithm 7) In this document, the abbreviations ML-DSA-44, ML-DSA-65, and ML-DSA-87 are used to refer to ML-DSA with the parameter choices given in Table 1. In these abbreviations, the numerical suffix refers to the dimension of the matrix 𝐀. For example, in ML-DSA-65, the matrix 𝐀 is a 6 × 5 matrix over 𝑅𝑞 .

3.4

Hedged and Deterministic Signing

For ML-DSA to be secure, the signer’s commitment value 𝐲 must not be used to sign more than one message, and it must not be easily guessed by an attacker. This requires randomness. In principle, the randomness leading to 𝐲 can be produced either with the use of fresh randomness at signing time or pseudorandomly from the message being signed and a precomputed random value included in the signer’s private key. By default, this standard specifies the signing algorithm to use both types of randomness. This is referred to as the “hedged” variant of the signing procedure. The use of fresh randomness during signing helps mitigate side-channel attacks, while the use of precomputed randomness protects against the possibility that there may be flaws in the random number generator used by the signer at signing time. This document also permits a fully deterministic variant of the signing procedure in case the signer has no access to a fresh source of randomness at signing time. However, the lack of randomness in the deterministic variant makes the risk of side-channel attacks (particularly fault attacks) more difficult to mitigate. Therefore, this variant should not be used on platforms where side-channel attacks are a concern and where they cannot be otherwise mitigated. Only implementing the hedged variant (i.e., without the deterministic variant) is sufficient to guarantee interoperability. The same verification algorithm will work to verify signatures produced by either variant, so implementing the deterministic variant in addition to the hedged variant does not enhance interoperability. The hedged and deterministic signing procedure differ only at line 5 of Algorithm 2 and line 5 of Algorithm 4.

3.5

Use of Digital Signatures

Secure key management is an essential requirement for the use of digital signatures. This is contextdependent and involves more than the key generation, signing, and signature verification algorithms in this document. Guidance for key management is provided in the SP 800-57 series [9, 17, 18]. Digital signatures are most useful when bound to an identity. Binding a public key to an identity requires proof of possession of the private key. In the PKI context, issuing certificates involves assurances of identity and proof of possession. When a public-key certificate is not available, users of digital signatures should determine whether a public key needs to be bound to an identity. Methods for obtaining assurances of identity and proof of possession are provided in [3].

11

FIPS 204

3.6

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

Additional Requirements

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

3.6.1

Randomness Generation

Algorithm 1, implementing key generation for ML-DSA, uses an RBG to generate the 256-bit random seed 𝜉. The seed 𝜉 shall be a fresh (i.e., not previously used) random value generated using an approved RBG, as prescribed in SP 800-90A, SP 800-90B, and SP 800-90C [19, 20, 21]. Moreover, the RBG used shall have a security strength of at least 192 bits for ML-DSA-65 and 256 bits for ML-DSA-87. For ML-DSA-44, the RBG should have a security strength of at least 192 bits and shall have a security strength of at least 128 bits. If an approved RBG with at least 128 bits of security but less than 192 bits of security is used, then the claimed security strength of ML-DSA-44 is reduced from category 2 to category 1. Additionally, the value 𝑟𝑛𝑑 is generated using an RBG in the default “hedged” variants of Algorithms 2 and 4 for ML-DSA and HashML-DSA signing, respectively. While this value should ideally be generated by an approved RBG, other methods for generating fresh random values may be used. The primary purpose of 𝑟𝑛𝑑 is to facilitate countermeasures to side-channel attacks and fault attacks on deterministic signatures, such as [22, 23, 24].3 For this purpose, even a weak RBG may be preferable to the fully deterministic variants of Algorithms 2 and 4.

3.6.2

Public-Key and Signature Length Checks

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

3.6.3

Intermediate Values

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

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

12

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

using ML-DSA.KeyGen_internal. As the seed can be used to compute the private key, it is sensitive data and shall be treated with the same safeguards as a private key. 2. The matrix 𝐀̂ generated in step 3 of ML-DSA.KeyGen_internal can be stored so that it need not be recomputed in later operations. Likewise, the matrix 𝐀̂ generated in step 5 of the verification algorithm ML-DSA.Verify_internal can also be stored. In either case, the matrix 𝐀̂ is data that is easily computed from the public key and does not require any special protections. In certain situations (e.g., deterministic signing and the verification of confidential messages and signatures), additional care must be taken to protect implementations against side-channel attacks or fault attacks. A cryptographic device may leak critical information through side channels, which allows internal data or keying material to be extracted without breaking the cryptographic primitives.

3.6.4

No Floating-Point Arithmetic

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

3.7

Use of Symmetric Cryptography

This standard makes use of the functions SHAKE256 and SHAKE128, as defined in FIPS 202 [7]. While FIPS 202 specifies these functions as inputting and outputting bit strings, most implementations treat inputs and outputs as byte strings. This standard will always call these functions with an output length of a multiple of eight bits and treat the output of these functions as a byte string, which will be the same byte string that would result from taking the bit string expected from a literal reading of FIPS 202 and processing it with BitsToBytes. However, to allow the signing of messages that are not a whole number of bytes, this document will overload SHAKE256 so that its input may be a bit string but will usually be a byte string. The following equivalence will hold for any byte string str and integer ℓ ≥ 1: SHAKE256(str, 8ℓ) = SHAKE256(BytesToBits(str), 8ℓ). In addition to using a mostly byte-oriented variant of the API defined in FIPS 202 for SHAKE256 and SHAKE128, this standard sometimes makes use of the incremental API defined in SP 800-185 [25]. This API consists of three functions for each variant of SHAKE. These functions can be used to absorb a sequence of arbitrary-length strings and squeeze a sequence of arbitrary-length strings. These functions perform buffering to handle any incomplete data blocks while absorbing or squeezing. For example, for SHAKE256: • ctx ← SHAKE256.Init() Initializes a hash function context. • ctx ← SHAKE256.Absorb(ctx, str) Injects data to be used in the absorbing phase of SHAKE256 and updates context ctx.

13

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

• (ctx, out) ← SHAKE256.Squeeze(ctx, 8ℓ) Extracts ℓ output bytes produced during the squeezing phase of SHAKE256 and updates context ctx. While the above functions are specified in terms of the Keccak-𝑓 permutation rather than the eXtendableOutput Function (XOF), SHAKE256, they are defined so that any series of commands of the following form: 1. ctx ← SHAKE256.Init() 2. For 𝑖 = 1 to 𝑚: ctx ← SHAKE256.Absorb(ctx, str𝑖 ) 3. For 𝑗 = 1 to 𝑘: (ctx, out𝑗 ) ← SHAKE256.Squeeze(ctx, 8𝑏𝑗 ) 4. output ← out1 || … ||out𝑘 will yield the same output as a single SHAKE256 call: output ← SHAKE256(str1 || … ||str𝑚 , 8𝑏1 + … + 8𝑏𝑘 ). This equivalence holds whether or not |str𝑖 | and 𝑏𝑗 are multiples of the SHAKE256 block length. Since all outputs of SHAKE128 and SHAKE256 in this document give a whole number of bytes, the wrapper functions H and G are defined as follows: 1. H(str, ℓ) = SHAKE256(str, 8ℓ) 2. G(str, ℓ) = SHAKE128(str, 8ℓ) 3. H.Init() = SHAKE256.Init() 4. G.Init() = SHAKE128.Init() 5. H.Absorb(ctx, str) = SHAKE256.Absorb(ctx, str) 6. G.Absorb(ctx, str) = SHAKE128.Absorb(ctx, str) 7. H.Squeeze(ctx, ℓ) = SHAKE256.Squeeze(ctx, 8ℓ) 8. G.Squeeze(ctx, ℓ) = SHAKE128.Squeeze(ctx, 8ℓ) In addition to SHAKE128 and SHAKE256, HashML-DSA.Sign and HashML-DSA.Verify may call other approved hash functions for pre-hashing. The pseudocode in this standard also treats these functions as returning a byte string as output while supporting either a bit string or a byte string as input. Here, it should be noted that the hash functions defined in [8] use different rules (i.e., big-endian ordering) to relate bits, bytes, and words.

14

FIPS 204

4.

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

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

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

Three ML-DSA parameter sets are included in Table 1. Each parameter set assigns values for all of the parameters used in the ML-DSA algorithms for key generation, signing, and verification. For informational purposes, some parameters used in the analysis of these algorithms are also included in the table. In particular, “repetitions” refers to the expected number of repetitions of the main loop in the signing algorithm from eq. 5 in [5]. The names of the parameter sets are of the form “ML-DSA-𝑘ℓ,” where (𝑘, ℓ) are the dimensions of the matrix 𝐀. These parameter sets were designed to meet certain security strength categories defined by NIST in its original Call for Proposals [26]. These security strength categories are explained further in SP 800-57, Part 1 [9]. Using this approach, security strength is not described by a single number, such as “128 bits of security.” Instead, each ML-DSA parameter set is claimed to be at least as secure as a generic block cipher with a prescribed key size or a generic hash function with a prescribed output length. More precisely, it is claimed that the computational resources needed to break ML-DSA are greater than or equal to the computational resources needed to break the block cipher or hash function when these computational resources are estimated using any realistic model of computation. Different models of computation can be more or less realistic and, accordingly, lead to more or less accurate estimates of security strength. Some commonly studied models are discussed in [27]. Concretely, the parameter set ML-DSA-44 is claimed to be in security strength category 2, ML-DSA-65 is claimed to be in category 3, and ML-DSA-87 is claimed to be in category 5 [6]. For additional discussion of the security strength of MLWE-based cryptosystems, see [28]. The sizes of keys and signatures that correspond to each parameter set are given in Table 2. Certain optimizations are possible when storing ML-DSA public and private keys. If additional space is available, one can precompute and store 𝐀̂ to speed up signing and verifying. Alternatively, if one wants to reduce

15

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

the space needed for the private key, one can store only the 32-byte seed 𝜉, which is sufficient to generate the other parts of the private key. For additional details, see Section 3.1 in [6].

Table 2. Sizes (in bytes) of keys and signatures of ML-DSA Private Key ML-DSA-44 2560 ML-DSA-65 4032 ML-DSA-87 4896

Public Key 1312 1952 2592

16

Signature Size 2420 3309 4627

FIPS 204

5.

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

External Functions

The signing, verifying, and key generation functions can be split into “external” and “internal” components to simplify APIs and Cryptographic Algorithm Validation Program (CAVP) testing. The external components generate randomness and perform various checks before calling their internal counterparts. The internal components are deterministic and can assume that the external components did not encounter error conditions. The distinction between external and internal functions also simplifies the presentation of algorithms for signing and verification by grouping the operations that are shared between ML-DSA.Sign and HashML-DSA.Sign in ML-DSA.Sign_internal and grouping the operations that are shared between ML-DSA.Verify and HashML-DSA.Verify in ML-DSA.Verify_internal.

5.1

ML-DSA Key Generation

The key generation algorithm ML-DSA.KeyGen takes no input and outputs a public key and a private key, which are both encoded as byte strings. The algorithm uses an approved RBG to generate a 256-bit (32-byte) random seed 𝜉 that is given as input to ML-DSA.KeyGen_internal (Algorithm 6), which produces the public and private keys.

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

5.2

ML-DSA Signing

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

4

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

17

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

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

5.3

ML-DSA Verifying

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

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

5.4

Pre-Hash ML-DSA

For some cryptographic modules that generate ML-DSA signatures, hashing the message in step 6 of ML-DSA.Sign_internal may result in unacceptable performance if the message 𝑀 is large. For example,

18

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

the platform may require hardware support for hashing to achieve acceptable performance but lack hardware support for SHAKE256 specifically. For some use cases, this may be addressed by signing a digest of the message along with some domain separation information rather than signing the message directly. This version of ML-DSA is known as “pre-hash” ML-DSA or HashML-DSA . In general, the “pure” ML-DSA version is preferred. While key generation for HashML-DSA is the same as for ML-DSA, it is not the same for the signing algorithm HashML-DSA.Sign or the verification algorithm HashML-DSA.Verify. Like ML-DSA, the signing algorithm of HashML-DSA takes the content to be signed, the private key, and a context as input, as well as a hash function or XOF that is to be used to pre-hash the content to be signed. The context string has a maximum length of 255 bytes. By default, the context is the empty string, though applications may specify the use of a non-empty context string. The identifier for a signature (e.g., the object identifier [OID]) should indicate whether the signature is a ML-DSA signature or a pre-hash HashML-DSA signature. In the case of pre-hash signatures, the identifier should also indicate the hash function or XOF used to compute the pre-hash. 5 While a single key pair may be used for both ML-DSA and HashML-DSA signatures, it is recommended that each key pair only be used for one version or the other. If a non-empty context string is to be used, this should either be indicated by the signature’s identifier or by the application with which the signature is being used. If the default “hedged” variant of is used, the 32-byte random value 𝑟𝑛𝑑 shall be generated by the cryptographic module that generates the signature (i.e., that runs ML-DSA.Sign_internal). However, all other steps of signing may be performed outside of the cryptographic module that generates the signature. In the case of pre-hashing, the hash or XOF of the content to be signed must be computed within a FIPS 140-validated cryptographic module, but it may be a different cryptographic module than the one that generates the signature. If the content to be signed is large, hashing of the content is often performed at the application level. For example, in the Cryptographic Message Syntax [29], a digest of the content may be computed, and that digest is signed along with other attributes. If the content is not hashed at the application level, the pre-hash version of ML-DSA signing may be used. In order to maintain the same level of security strength when the content is hashed at the application level or using HashML-DSA , the digest that is signed needs to be generated using an approved hash function or XOF (e.g., from FIPS 180 [8] or FIPS 202 [7]) that provides at least 𝜆 bits of classical security strength against both collision and second preimage attacks [7, Table 4].6 The verification of a signature that is created in this way will require the verify function to generate a digest from the message in the same way to be used as input for the verification function.

5.4.1

HashML-DSA Signing and Verifying

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

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

19

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

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

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

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

Algorithm 5 presents the signature verification for HashML-DSA . This function constructs 𝑀 ′ in the same way as Algorithm 4 and passes the resulting 𝑀 ′ to Algorithm ML-DSA.Verify_internal for verification. As with the pre-hash signature generation, 𝑀 ′ may be constructed outside of the cryptographic module that performs ML-DSA.Verify_internal. However, in the case of HashML-DSA , the hash or XOF of the content must be computed within a FIPS 140-validated cryptographic module, which may be a different cryptographic module than the one that performs ML-DSA.Verify_internal. As noted in Section 5.4, the identifier associated with the signature should indicate whether ML-DSA or

20

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

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

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

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

21

FIPS 204

6.

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

Internal Functions

This section describes the functions for ML-DSA key generation, signature generation, and signature verification. Where randomness is required, the random values are provided as inputs to the functions. The interfaces specified in this section will be used when testing of ML-DSA implementations is performed through the CAVP. Other than for testing purposes, the interfaces for key generation and signature generation specified in this section should not be made available to applications, as any random values required for key generation and signature generation shall be generated by the cryptographic module. Section 5 provides guidance on the interfaces to be made available to applications.7

6.1

ML-DSA Key Generation (Internal)

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

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

22

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

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

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

6.2

ML-DSA Signing (Internal)

ML-DSA.Sign_internal (Algorithm 7) outputs a signature encoded as a byte string. It takes a private key 𝑠𝑘 encoded as a byte string, a formatted message 𝑀 ′ encoded as a bit string, and a 32-byte string 𝑟𝑛𝑑 as input. There are two ways that a signing algorithm can use ML-DSA.Sign_internal: “hedged” and “deterministic.” The default “hedged” variants of ML-DSA.Sign and HashML-DSA.Sign use a fresh random value for 𝑟𝑛𝑑, while the optional deterministic variants use the constant byte string {0}32 (see Section 3). In both variants, the signer first extracts the following from the private key: the public random seed 𝜌, the 32-byte private random seed 𝐾, the 64-byte hash of the public key 𝑡𝑟, the secret polynomial vectors 𝐬1 and 𝐬2 , and the polynomial vector 𝐭0 encoding the 𝑑 least significant bits of each coefficient of the uncompressed public-key polynomial 𝐭. 𝜌 is then expanded to the same matrix 𝐀 as in key generation. Before the message 𝑀 is signed, it is concatenated with the public-key hash 𝑡𝑟 and hashed down to a 64-byte message representative 𝜇 using H. The signer produces an additional 64-byte seed 𝜌″ for private randomness during each signing operation. 𝜌″ is computed as 𝜌″ ← H(𝐾||𝑟𝑛𝑑||𝜇, 64). In the default hedged variant, 𝑟𝑛𝑑 is the output of an RBG, while in the deterministic variant, 𝑟𝑛𝑑 is a 32-byte string that consists entirely of zeros. This is the only difference between the deterministic and hedged variant of ML-DSA.Sign. The main part of the signing algorithm consists of a rejection sampling loop in which each iteration of the loop either produces a valid signature or an invalid signature whose release would leak information about the private key. The loop is repeated until a valid signature is produced, which can then be encoded as a byte string and output.10 The rejection sampling loop follows the Fiat-Shamir With Aborts paradigm [10] 10

Implementations may limit the number of iterations in this loop to not exceed a finite maximum value. If this

23

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

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

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

24

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

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

6.3

ML-DSA Verifying (Internal)

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

25

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

required for ML-DSA.Verify_internal. It produces a Boolean value (i.e., a value that is true if the signature is valid with respect to the message and public key and false if the signature is invalid) as output. Algorithm 8 specifies the lengths of the signature 𝜎 and the public key 𝑝𝑘 in terms of the parameters described in Table 1. If an implementation of ML-DSA.Verify_internal can accept inputs for 𝜎 or 𝑝𝑘 of any other length, it shall return false whenever the length of either of these inputs differs from its specified length. The verifier first extracts the public random seed 𝜌 and the compressed polynomial vector 𝐭1 from the public key 𝑝𝑘 and then extracts the signer’s commitment hash 𝑐,̃ response 𝐳, and hint 𝐡 from the signature 𝜎. The verifier may find that the hint was not properly byte-encoded, denoted by the symbol “⊥,” in which case the verification algorithm will immediately return false to indicate that the signature is invalid. Assuming that the signature is successfully extracted from its byte encoding, the verifier pseudorandomly derives 𝐀 from 𝜌, as is done in key generation and signing, and creates a message representative 𝜇 by hashing the concatenation of 𝑡𝑟 (i.e., the hash of the public key 𝑝𝑘) and the message 𝑀. The verifier then attempts to reconstruct the signer’s commitment (i.e., the polynomial vector 𝐰1 ) from the public key 𝑝𝑘 and the signature 𝜎. In ML-DSA.Sign_internal, 𝐰1 is computed by rounding 𝐰 = 𝐀𝐲. In ML-DSA.Verify_internal, the reconstructed value of 𝐰1 is called 𝐰′1 since it may have been computed in a different way if the signature is invalid. This 𝐰′1 is computed through the following process: • Derive the challenge polynomial 𝑐 from the signer’s commitment hash 𝑐,̃ just as similarly is done in ML-DSA.Sign_internal. • Use the signer’s response 𝐳 to compute 𝐰′Approx = 𝐀𝐳 − 𝑐𝐭1 ⋅ 2𝑑 . Assuming the signature was computed correctly, as in ML-DSA.Sign_internal, it follows that 𝐰 = 𝐀𝐲 = 𝐀𝐳 − 𝑐𝐭 + 𝑐𝐬2 ≈ 𝐰′Approx = 𝐀𝐳 − 𝑐𝐭1 ⋅ 2𝑑 because 𝑐 and 𝐬2 have small coefficients, and 𝐭1 ⋅ 2𝑑 ≈ 𝐭 . • Use the signer’s hint 𝐡 to obtain 𝐰′1 from 𝐰′Approx . Finally, the verifier checks that the signer’s response 𝐳 and the signer’s hint 𝐡 are valid and that the reconstructed 𝐰′1 is consistent with the signer’s commitment hash 𝑐.̃ More precisely, the verifier checks that all of the coefficients of 𝐳 are sufficiently small (i.e., in the range (−(𝛾1 − 𝛽), 𝛾1 − 𝛽)), 𝐡 contains no more than 𝜔 nonzero coefficients, and 𝑐 ̃matches the hash 𝑐′̃ of the message representative 𝜇 concatenated with 𝐰′1 (represented as a byte string). If all of these checks succeed, then ML-DSA.Verify_internal returns true. Otherwise, it returns false.

26

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

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

27

FIPS 204

7.

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

Auxiliary Functions

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

7.1

Conversion Between Data Types

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

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

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

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

▷ convert the byte 𝑧[𝑖] into 8 bits

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

Algorithm 14 CoeffFromThreeBytes(𝑏0 , 𝑏1 , 𝑏2 ) Generates an element of {0, 1, 2, … , 𝑞 − 1} ∪ {⊥}. Input: Bytes 𝑏0 , 𝑏1 , 𝑏2 . Output: An integer modulo 𝑞 or ⊥. 1: 𝑏2′ ← 𝑏2 2: if 𝑏2′ > 127 then 3: 𝑏2′ ← 𝑏2′ − 128 4: end if 5: 𝑧 ← 216 ⋅ 𝑏2′ + 28 ⋅ 𝑏1 + 𝑏0 6: if 𝑧 < 𝑞 then return 𝑧 7: else return ⊥ 8: end if

▷ set the top bit of 𝑏2′ to zero ▷ 0 ≤ 𝑧 ≤ 223 − 1 ▷ rejection sampling

29

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

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

▷ rejection sampling from {−2, … , 2} ▷ rejection sampling from {−4, … , 4}

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

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

30

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

Algorithm 18 SimpleBitUnpack(𝑣, 𝑏) Reverses the procedure SimpleBitPack. Input: 𝑏 ∈ ℕ and a byte string 𝑣 of length 32 ⋅ bitlen 𝑏. Output: A polynomial 𝑤 ∈ 𝑅 with coefficients in [0, 2𝑐 − 1], where 𝑐 = bitlen 𝑏. When 𝑏 + 1 is a power of 2, the coefficients are in [0, 𝑏]. 1: 𝑐 ← bitlen 𝑏 2: 𝑧 ← BytesToBits(𝑣) 3: for 𝑖 from 0 to 255 do 4: 𝑤𝑖 ← BitsToInteger((𝑧[𝑖𝑐], 𝑧[𝑖𝑐 + 1], … 𝑧[𝑖𝑐 + 𝑐 − 1]), 𝑐) 5: end for 6: return 𝑤 Algorithm 19 BitUnpack(𝑣, 𝑎, 𝑏) Reverses the procedure BitPack. Input: 𝑎, 𝑏 ∈ ℕ and a byte string 𝑣 of length 32 ⋅ bitlen (𝑎 + 𝑏). Output: A polynomial 𝑤 ∈ 𝑅 with coefficients in [𝑏 − 2𝑐 + 1, 𝑏], where 𝑐 = bitlen (𝑎 + 𝑏). When 𝑎 + 𝑏 + 1 is a power of 2, the coefficients are in [−𝑎, 𝑏]. 1: 𝑐 ← bitlen (𝑎 + 𝑏) 2: 𝑧 ← BytesToBits(𝑣) 3: for 𝑖 from 0 to 255 do 4: 𝑤𝑖 ← 𝑏 − BitsToInteger((𝑧[𝑖𝑐], 𝑧[𝑖𝑐 + 1], … 𝑧[𝑖𝑐 + 𝑐 − 1]), 𝑐) 5: end for 6: return 𝑤 Algorithms 20 and 21 carry out byte-string-to-polynomial conversions for polynomials with sparse binary coefficients. In particular, the signing and verification algorithms (Sections 6.2 and 6.3) make use of a “hint,” which is a vector of polynomials 𝐡 ∈ 𝑅2𝑘 such that the total number of coefficients in 𝐡[0], 𝐡[1], … , 𝐡[𝑘−1] that are equal to 1 is no more than 𝜔. This constraint enables encoding and decoding procedures that are more efficient (although more complex) than BitPack and BitUnpack. HintBitPack (𝐡) outputs a byte string 𝑦 of length 𝜔 + 𝑘. The last 𝑘 bytes of 𝑦 contain information about how many nonzero coefficients are present in each of the polynomials 𝐡[0], 𝐡[1], … , 𝐡[𝑘 − 1], and the first 𝜔 bytes of 𝑦 contain information about exactly where those nonzero terms occur. HintBitUnpack reverses the procedure performed by HintBitPack and recovers the vector 𝐡.

31

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

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

FIPS 204

7.2

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

Encodings of ML-DSA Keys and Signatures

Algorithms 22–27 translate keys and signatures for ML-DSA into byte strings. These procedures take certain sequences of algebraic objects, encode them consecutively into byte strings, and perform the respective decoding procedures. First, pkEncode and pkDecode translate ML-DSA public keys into byte strings and vice versa. When verifying a signature, pkDecode might be run on an input that comes from an untrusted source. Thus, care is required when using SimpleBitUnpack. As used here, SimpleBitUnpack always returns values in the correct range.

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

1: (𝜌, 𝑧0 , … , 𝑧𝑘−1 ) ∈ 𝔹32 × (𝔹32(bitlen (𝑞−1)−𝑑) ) ← 𝑝𝑘 2: for 𝑖 from 0 to 𝑘 − 1 do 3: 𝐭1 [𝑖] ← SimpleBitUnpack(𝑧𝑖 , 2bitlen (𝑞−1)−𝑑 − 1) 4: end for 5: return (𝜌, 𝐭1 )

▷ This is always in the correct range

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

33

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

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

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

×

32𝑑 𝑘

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

34

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

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

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

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

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

35

FIPS 204

7.3

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

Pseudorandom Sampling

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

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

▷ ℎ is a bit string of length 64

▷ rejection sampling in {0, … , 𝑖} ▷ 𝑗 is a pseudorandom byte that is ≤ 𝑖

Algorithms 30–34 are the pseudorandom procedures RejNTTPoly, RejBoundedPoly, ExpandA, ExpandS, and ExpandMask. Each generates elements of 𝑅 or 𝑇𝑞 under different input and output conditions. RejNTTPoly and ExpandA make use of the more efficient XOF G, whereas the other three procedures use the XOF H. The procedure ExpandMask (Algorithm 34) generates a polynomial vector 𝐲 in 𝑅𝑘 that disguises the secret key in the ML-DSA.Sign_internal procedure (Algorithm 7). In addition to the seed 𝜌, ExpandMask also accepts an integer input 𝜇 that is incorporated into the pseudorandom procedure that generates 𝐬.

12

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

36

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

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

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

37

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

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

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

▷ seed depends on 𝑟

▷ seed depends on 𝑟 + ℓ

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

▷ 𝛾1 is always a power of 2 ▷ seed depends on 𝜇 + 𝑟

FIPS 204

7.4

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

High-Order and Low-Order Bits and Hints

This specification uses the auxiliary functions Power2Round, Decompose, HighBits, LowBits, MakeHint, and UseHint and explicitly defines these functions, where 𝑟 ∈ ℤ𝑞 , 𝑟1 , 𝑟0 ∈ ℤ, and ℎ is a Boolean (or equivalently an element of ℤ2 ). However, this specification also uses these functions where 𝐫, 𝐳 ∈ 𝑅𝑞𝑘 , 𝐫1 , 𝐫0 ∈ 𝑅𝑘 , and 𝐡 ∈ 𝑅2𝑘 . In this case, the functions are applied coefficientwise to the polynomials in the vectors. In particular: • For 𝐫 ∈ 𝑅𝑞𝑘 , define (𝐫1 , 𝐫0 ) ∈ (𝑅𝑘 )2 = Power2Round(𝐫) so that: ((𝐫1 [𝑖])𝑗 , (𝐫0 [𝑖])𝑗 ) = Power2Round((𝐫[𝑖])𝑗 ). • For 𝐫 ∈ 𝑅𝑞𝑘 , define (𝐫1 , 𝐫0 ) ∈ (𝑅𝑘 )2 = Decompose(𝐫) so that: ((𝐫1 [𝑖])𝑗 , (𝐫0 [𝑖])𝑗 ) = Decompose((𝐫[𝑖])𝑗 ). • For 𝐫 ∈ 𝑅𝑞𝑘 , define 𝐫1 = HighBits (𝐫) so that: (𝐫1 [𝑖])𝑗 = HighBits((𝐫[𝑖])𝑗 ). • For 𝐫 ∈ 𝑅𝑞𝑘 , define 𝐫0 = LowBits(𝐫) so that: (𝐫0 [𝑖])𝑗 = LowBits((𝐫[𝑖])𝑗 ). • For 𝐳, 𝐫 ∈ 𝑅𝑞𝑘 , define 𝐡 ∈ 𝑅2𝑘 = MakeHint(𝐳, 𝐫) so that: (𝐡[𝑖])𝑗 = MakeHint((𝐳[𝑖])𝑗 , (𝐫[𝑖])𝑗 ). • For 𝐡 ∈ 𝑅2𝑘 and 𝐫 ∈ 𝑅𝑞𝑘 , define 𝐫1 ∈ 𝑅𝑘 = UseHint(𝐡, 𝐫) so that: 𝐫1 [𝑖]𝑗 = UseHint((𝐡[𝑖])𝑗 , (𝐫[𝑖])𝑗 ). These algorithms are used to support the key compression optimization of ML-DSA. They involve dropping the 𝑑 low-order bits of each coefficient of the polynomial vector 𝐭 from the public key using the function Power2Round. However, in order to make this optimization work, additional information called a “hint” needs to be provided in the signature to allow the verifier to reconstruct enough of the information in the dropped public-key bits to verify the signature. Hints are created during signing and used during verification by the functions MakeHint and UseHint, respectively. In the verification of a valid signature, the hint allows the verifier to recover 𝐰1 ∈ 𝑅𝑘 , which represents 𝐰 ∈ 𝑅𝑞𝑘 rounded to a nearby multiple of 𝛼 = 2𝛾2 . The signer directly obtains 𝐰1 using the function HighBits, and the part rounded off (i.e., 𝐫0 ) is obtained by LowBits. 𝐫0 is used by the signer in the rejection sampling procedure. Power2Round decomposes an input 𝑟 ∈ ℤ𝑞 into integers that represent the high- and low-order bits of 𝑟 mod 𝑞 in the straightforward bitwise way, 𝑟 mod 𝑞 = 𝑟1 ⋅ 2𝑑 + 𝑟0 , where 𝑟0 = (𝑟 mod 𝑞) mod± 2𝑑 and 𝑟1 = (𝑟 mod 𝑞 − 𝑟0 )/2𝑑 . However, for the purpose of computations related to hints, this method of decomposing 𝑟 has the undesirable property that when 𝑟 is close to 𝑞 − 1 or 0, a small rounding error in 𝑟 can cause 𝑟1 to change by more than 1, even accounting for wrap-around. In contrast to other unequal pairs of values of 𝑟1 ⋅ 2𝑑 and 𝑟1′ ⋅ 2𝑑 , the distance (mod𝑞) between ⌊𝑞/2𝑑 ⌋ ⋅ 2𝑑 and 0 may be very small.

39

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

To avoid this problem, this specification defines Decompose, which is similar to Power2Round except: • 𝑟 is generally decomposed as 𝑟 mod 𝑞 = 𝑟1 ⋅ 𝛼 + 𝑟0 , where 𝛼 = 2𝛾2 is a divisor of 𝑞 − 1. • If the straightforward rounding procedure would return (𝑟1 = (𝑞 − 1)/𝛼, 𝑟0 ∈ [−(𝛼/2) + 1, 𝛼/2]), Decompose instead returns (𝑟1 = 0, 𝑟0 − 1). The functions HighBits and LowBits — which only return 𝑟1 and 𝑟0 , respectively — and MakeHint and UseHint use Decompose. For additional discussion of the mathematical properties of these functions that are relevant to the correctness and security of ML-DSA, see Section 2.4 in [6].

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

40

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

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

Algorithm 39 MakeHint(𝑧, 𝑟) Computes hint bit indicating whether adding 𝑧 to 𝑟 alters the high bits of 𝑟. Input: 𝑧, 𝑟 ∈ ℤ𝑞 . Output: Boolean. 1: 𝑟1 ← HighBits(𝑟) 2: 𝑣1 ← HighBits(𝑟 + 𝑧) 3: return [[𝑟1 ≠ 𝑣1 ]]

Algorithm 40 UseHint(ℎ, 𝑟) Returns the high bits of 𝑟 adjusted according to hint ℎ. Input: Boolean ℎ, 𝑟 ∈ ℤ𝑞 . Output: 𝑟1 ∈ ℤ with 0 ≤ 𝑟1 ≤ 𝑞−1 2𝛾 . 2

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

41

FIPS 204

7.5

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

NTT and NTT−1

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

42

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

Algorithm 41 NTT(𝑤) Computes the NTT. 255

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

43

▷ 𝑧 ← 𝜁 BitRev8 (𝑚) mod 𝑞

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

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

▷ 𝑧 ← −𝜁 BitRev8 (𝑚) mod 𝑞

▷ 𝑓 = 256−1 mod 𝑞

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

FIPS 204

7.6

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

Arithmetic Under NTT

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

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

45

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

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

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

46

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

References [1] National Institute of Standards and Technology (2023) Digital signature standard (DSS), (U.S. Department of Commerce, Washington, DC), Federal Information Processing Standards Publication (FIPS) 186-5. https://doi.org/10.6028/NIST.FIPS.186-5. [2] Barker E (2020) Guideline for using cryptographic standards in the federal government: Cryptographic mechanisms, (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-175B, Rev. 1 [or as amended]. https://doi.org/10.6028/NIST.SP.800-175Br1. [3] Barker E (2006) Recommendation for obtaining assurances for digital signature applications, National Institute of Standards and Technology, Gaithersburg, MD. NIST Special Publication (SP) 800-89 [or as amended]. https://doi.org/10.6028/NIST.SP.800-89. [4] Langlois A, Stehlé D (2015) Worst-case to average-case reductions for module lattices. Designs, Codes and Cryptography 75(3):565–599. https://doi.org/10.1007/s10623-014-9938-4. [5] Bai S, Ducas L, Kiltz E, Lepoint T, Lyubashevsky V, Schwabe P, Seiler G, Stehlé D (2020) CRYSTALSDilithium: Algorithm specifications and supporting documentation, Submission to the NIST’s postquantum cryptography standardization process. Available at https://csrc.nist.gov/Projects/post-qua ntum-cryptography/post-quantum-cryptography-standardization/round-3-submissions. [6] Bai S, Ducas L, Kiltz E, Lepoint T, Lyubashevsky V, Schwabe P, Seiler G, Stehlé D (2021) CRYSTALSDilithium: Algorithm specifications and supporting documentation (Version 3.1). Available at https: //pq-crystals.org/dilithium/data/dilithium-specification-round3-20210208.pdf. [7] National Institute of Standards and Technology (2015) SHA-3 standard: Permutation-based hash and extendable-output functions, (U.S. Department of Commerce, Washington, DC), Federal Information Processing Standards Publication (FIPS) 202. https://doi.org/10.6028/NIST.FIPS.202. [8] National Institute of Standards and Technology (2015) Secure hash standard (SHS), (U.S. Department of Commerce, Washington, DC), Federal Information Processing Standards Publication (FIPS) 180-4. https://doi.org/10.6028/NIST.FIPS.180-4. [9] Barker E (2020) Recommendation for key management: Part 1 - general, (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-57 Part 1, Rev. 5 [or as amended]. https://doi.org/10.6028/NIST.SP.800-57pt1r5. [10] Lyubashevsky V (2009) Fiat-Shamir with aborts: Applications to lattice and factoring-based signatures. Advances in Cryptology – ASIACRYPT 2009, ed Matsui M (Springer Berlin Heidelberg, Berlin, Heidelberg), pp 598–616. https://doi.org/10.1007/978-3-642-10366-7_35. [11] Lyubashevsky V (2012) Lattice signatures without trapdoors. EUROCRYPT (Springer), Lecture Notes in Computer Science, Vol. 7237, pp 738–755. https://doi.org/10.1007/978-3-642-29011-4_43. [12] Güneysu T, Lyubashevsky V, Pöppelmann T (2012) Practical lattice-based cryptography: A signature scheme for embedded systems. CHES (Springer), Vol. 7428, pp 530–547. https://doi.org/10.1007/97 8-3-642-33027-8_31. [13] Bai S, Galbraith SD (2014) An improved compression technique for signatures based on learning with errors. Topics in Cryptology – CT-RSA 2014, ed Benaloh J (Springer International Publishing, Cham), pp 28–47. https://doi.org/10.1007/978-3-319-04852-9_2.

47

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

[14] Cremers C, Düzlü S, Fiedler R, Janson C, Fischlin M (2021) BUFFing signature schemes beyond unforgeability and the case of post-quantum signatures. 2021 IEEE Symposium on Security and Privacy (SP) (IEEE Computer Society, Los Alamitos, CA, USA), pp 1696–1714. https://doi.org/10.110 9/SP40001.2021.00093. [15] Regev O (2005) On lattices, learning with errors, random linear codes, and cryptography. Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing STOC ’05 (Association for Computing Machinery, New York, NY, USA), p 84–93. https://doi.org/10.1145/1060590.1060603. [16] Kiltz E, Lyubashevsky V, Schaffner C (2018) A concrete treatment of Fiat-Shamir signatures in the quantum random-oracle model. Advances in Cryptology – EUROCRYPT 2018, eds Nielsen JB, Rijmen V (Springer International Publishing, Cham), pp 552–586. https://doi.org/10.1007/978-3-319-78372 -7_18. [17] Barker E, Barker W (2019) Recommendation for key management: Part 2 - best practices for key management organizations, National Institute of Standards and Technology, Gaithersburg, MD. NIST Special Publication (SP) 800-57 Part 2, Rev. 1. https://doi.org/10.6028/NIST.SP.800-57pt2r1. [18] Barker E, Dang Q (2019) Recommendation for key management: Part 3 - application-specific key management guidance, National Institute of Standards and Technology, Gaithersburg, MD. NIST Special Publication (SP) 800-57 Part 3, Rev. 1. http://doi.org/10.6028/NIST.SP.800-57pt3r1. [19] Barker E, Kelsey J (2015) Recommendation for random number generation using deterministic random bit generators, (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-90A, Rev. 1. https://doi.org/10.6028/NIST.SP.800-90Ar1. [20] Sönmez Turan M, Barker E, Kelsey J, McKay K, Baish M, Boyle M (2018) Recommendation for the entropy sources used for random bit generation, (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-90B. https://doi.org/10.6028/NIST.SP.800-90B. [21] Barker E, Kelsey J, McKay K, Roginsky A, Turan MS (2024) Recommendation for random bit generator (RBG) constructions, (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-90C 4pd. https://doi.org/10.6028/NIST.SP.800-90C.4pd. [22] Bruinderink LG, Pessl P (2018) Differential fault attacks on deterministic lattice signatures. IACR Transactions on Cryptographic Hardware and Embedded Systems (3):21–43. https://doi.org/10.131 54/tches.v2018.i3.21-43. [23] Poddebniak D, Somorovsky J, Schinzel S, Lochter M, Rösler P (2018) Attacking deterministic signature schemes using fault attacks. 2018 IEEE European Symposium on Security and Privacy (EuroS&P) (IEEE), pp 338–352. https://doi.org/10.1109/EuroSP.2018.00031. [24] Samwel N, Batina L, Bertoni G, Daemen J, Susella R (2018) Breaking ed25519 in wolfssl. Topics in Cryptology–CT-RSA 2018: The Cryptographers’ Track at the RSA Conference 2018, San Francisco, CA, USA, April 16-20, 2018, Proceedings (Springer), pp 1–20. https://doi.org/10.1007/978-3-319-76953 -0_1. [25] Kelsey J, Chang S, Perlner R (2016) SHA-3 Derived Functions: cSHAKE, KMAC, TupleHash and ParallelHash, (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-185 [or as amended]. https://doi.org/10.6028/NIST.SP.800-185. [26] National Institute of Standards and Technology (2016) Submission requirements and evaluation criteria for the post-quantum cryptography standardization process. Available at https://csrc.nist.go

48

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

v/CSRC/media/Projects/Post-Quantum-Cryptography/documents/call-for-proposals-final-dec-201 6.pdf. [27] Alagic G, Apon D, Cooper D, Dang Q, Dang T, Kelsey J, Lichtinger J, Liu YK, Miller C, Moody D, Peralta R, Perlner R, Robinson A, Smith-Tone D (2022) Status report on the third round of the NIST post-quantum cryptography standardization process (National Institute of Standards and Technology, Gaithersburg, MD), NIST Interagency or Internal Report (IR) 8413. https://doi.org/10.6028/NIST.IR.8413-upd1. [28] Avanzi R, Bos J, Ducas L, Kiltz E, Lepoint T, Lyubashevsky V, Schanck JM, Schwabe P, Seiler G, Stehlé D (2020) CRYSTALS-Kyber algorithm specifications and supporting documentation, 3rd Round submission to the NIST’s post-quantum cryptography standardization process. Available at https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standar dization/round-3-submissions. [29] Housley R (2009) Cryptographic Message Syntax (CMS), Internet Engineering Task Force (IETF) request for comments (RFC) 5652, https://doi.org/10.17487/RFC5652. [30] Schnorr C (1990) Efficient identification and signatures for smart cards. Advances in Cryptology — CRYPTO’ 89 Proceedings, ed Brassard G (Springer New York, New York, NY), pp 239–252. https: //doi.org/10.1007/0-387-34805-0_22. [31] Josefsson S, Liusvaara I (2017) Edwards-Curve Digital Signature Algorithm (EdDSA), RFC 8032. https: //doi.org/10.17487/RFC8032. [32] Lyubashevsky V (2021) Round 3 Official Comment: CRYSTALS-DILITHIUM. Available at https://groups .google.com/a/list.nist.gov/g/pqc-forum/c/BjfjRMIdnhM/m/W7kkVOFDBAAJ. [33] Hamburg M (2024) Dilithium hint unpacking. Available at https://groups.google.com/a/list.nist.gov/ g/pqc-forum/c/TQo-qFbBO1A/m/YcYKjMblAAAJ. [34] Mattsson (on behalf of Sönke Jendral) JP (2024) Dilithium hint unpacking. Available at https://grou ps.google.com/a/list.nist.gov/g/pqc-forum/c/TQo-qFbBO1A/m/sLjseYlSAwAJ. [35] Lee S (2024) Updates for FIPS 203. Available at https://groups.google.com/a/list.nist.gov/g/pqc-for um/c/Rb0nFvfFTEQ/m/lw-k7tVdBQAJ.

49

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

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

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

▷ the inverse of 𝑞 modulo 232

With this algorithm, the modular product of 𝑎 and 𝑏 is 𝑐 = MontgomeryReduce(𝑎 ⋅ 𝑏), where 𝑎, 𝑏, and 𝑐 are in Montgomery form. The return value of the algorithm is not necessarily less than 𝑞 in absolute value, but it is less than 2𝑞 in absolute value. This is not a concern in practice since the objective of Montgomery Multiplication is to efficiently work with modular values that fit in a 32-bit register. If necessary, the result can be normalized to an integer in (−𝑞, 𝑞) using a comparison and an integer addition. Converting an integer modulo 𝑞 to Montgomery form by multiplying by 232 modulo 𝑞 is an expensive operation. When a sequence of modular operations is to be performed, the operands are converted once to Montgomery form. The operations are then performed, and the factor 232 is extracted from the final result.

13

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

50

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

Appendix B — Zetas Array The values 𝜁 BitRev8 (𝑘) mod 𝑞 for 𝑘 = 1, … , 255 used in the NTT Algorithms 41 and 42 may be pre-computed and stored in an array zetas[1..255]. This table of zetas is given below. zetas[0..255] = { 0,

4808194,

3765607,

3761513,

5178923,

5496691,

5234739,

5178987,

7778734,

3542485,

2682288,

2129892,

3764867,

7375178,

557458,

7159240,

5010068,

4317364,

2663378,

6705802,

4855975,

7946292,

676590,

7044481,

5152541,

1714295,

2453983,

1460718,

7737789,

4795319,

2815639,

2283733,

3602218,

3182878,

2740543,

4793971,

5269599,

2101410,

3704823,

1159875,

394148,

928749,

1095468,

4874037,

2071829,

4361428,

3241972,

2156050,

3415069,

1759347,

7562881,

4805951,

3756790,

6444618,

6663429,

4430364,

5483103,

3192354,

556856,

3870317,

2917338,

1853806,

3345963,

1858416,

3073009,

1277625,

5744944,

3852015,

4183372,

5157610,

5258977,

8106357,

2508980,

2028118,

1937570,

4564692,

2811291,

5396636,

7270901,

4158088,

1528066,

482649,

1148858,

5418153,

7814814,

169688,

2462444,

5046034,

4213992,

4892034,

1987814,

5183169,

1736313,

235407,

5130263,

3258457,

5801164,

1787943,

5989328,

6125690,

3482206,

4197502,

7080401,

6018354,

7062739,

2461387,

3035980,

621164,

3901472,

7153756,

2925816,

3374250,

1356448,

5604662,

2683270,

5601629,

4912752,

2312838,

7727142,

7921254,

348812,

8052569,

1011223,

6026202,

4561790,

6458164,

6143691,

1744507,

1753,

6444997,

5720892,

6924527,

2660408,

6600190,

8321269,

2772600,

1182243,

87208,

636927,

4415111,

4423672,

6084020,

5095502,

4663471,

8352605,

822541,

1009365,

5926272,

6400920,

1596822,

4423473,

4620952,

6695264,

4969849,

2678278,

4611469,

4829411,

635956,

8129971,

5925040,

4234153,

6607829,

2192938,

6653329,

2387513,

4768667,

8111961,

5199961,

3747250,

2296099,

1239911,

4541938,

3195676,

2642980,

1254190,

8368000,

2998219,

141835,

8291116,

2513018,

7025525,

613238,

7070156,

6161950,

7921677,

6458423,

4040196,

4908348,

2039144,

6500539,

7561656,

6201452,

6757063,

2105286,

6006015,

6346610,

586241,

7200804,

527981,

5637006,

6903432,

1994046,

2491325,

6987258,

507927,

7192532,

7655613,

6545891,

5346675,

8041997,

2647994,

3009748,

5767564,

4148469,

749577,

4357667,

3980599,

2569011,

6764887,

1723229,

1665318,

2028038,

1163598,

5011144,

3994671,

8368538,

7009900,

3020393,

3363542,

214880,

545376,

7609976,

3105558,

7277073,

508145,

7826699,

860144,

3430436,

140244,

6866265,

6195333,

3123762,

2358373,

6187330,

5365997,

6663603,

2926054,

7987710,

8077412,

3531229,

4405932,

4606686,

1900052,

7598542,

1054478,

7648983 }

51

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

Appendix C — Loop Bounds There are four algorithms in this standard with loops that iterate an indeterminate number of times, though the expected number of iterations is a small constant in each case. Three of the four algorithms involve sampling from the output of an XOF, where the amount of output required from the XOF is proportional to the number of iterations that are performed. Implementations should not bound the number of iterations in these loops or the amount of output that is extracted from the XOFs when executing these functions.14 If an implementation bounds the number of iterations or the number of bytes that may be extracted from the XOF, it shall not use a limit lower than those presented in Table 3. The limits yield a probability of approximately 2−256 (or less) of being reached in a correct implementation of this standard. The probability is calculated under standard assumptions about the output distributions of XOFs and hash functions.

Table 3. While loop and XOF output limits for a 2−256 or less probability of failure Algorithm

Minimum allowable limit (Loop iterations)

Minimum allowable limit (XOF output bytes)

ML-DSA.Sign_internal RejBoundedPoly RejNTTPoly SampleInBall

814 481 298 121

N/A 481 894 221

Implementations may limit the number of iterations of a while loop or the number of bytes drawn from the XOF to not exceed the maximum values in Table 3. If this option is used and the maximum number of iterations or XOF output bytes is exceeded, the algorithm shall destroy all intermediate results. If a return value or exception is produced, it shall be the same for any execution in which the maximum number of iterations or output bytes is exceeded. There is essentially no performance penalty for using a larger than necessary limit, as the limit will only be reached on a faulty execution of the loop. Because of this, limits were chosen that lower-bound the probability of reaching them to 2−256 .

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

RejBoundedPoly Let 𝑋 be the number of coefficients generated in 𝑛 iterations of the while loop of RejBoundedPoly15 . 9 9 15 Then 𝑋 is 𝐵𝑖𝑛𝑜𝑚𝑖𝑎𝑙(2𝑛, 𝜃), where 𝜃 is either 16 or 16 , depending on the parameter 𝜂. For 𝜃 = 16 , the probability that fewer than 256 coefficients are generated in 481 iterations of the main loop in RejBoundedPoly is less than 2−256 . Each iteration consumes one byte of output from H. RejBoundedPoly, RejNTTPoly, and SampleInBall use the incremental APIs described in Section 3.7 in order to extract the amount of output needed from the XOFs, given that the amount needed is not known in advance. 15 Note that 0, 1, or 2 coefficients are generated in each iteration. 14

52

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

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

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

53

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

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

D.1 Differences Between Version 3.1 and the Round 3 Version of CRYSTALSDILITHIUM The lengths of the variables 𝜌′ (private random seed) and 𝜇 (message representative) in the signing algorithm were increased from 384 to 512 bits. The increase in the length of 𝜇 corrects a security flaw that appeared in the third-round submission, where a collision attack against SHAKE256 with a 384-bit output would make it so that parameters targeting NIST security strength category 5 could only meet category 4 [32]. Additionally, the length of the variable 𝑡𝑟 (the hash of the public key) was reduced from 384 to 256 bits. In key generation, the variable 𝜍 was relabeled as 𝜌′ and increased in size from 256 bits to 512 bits.

D.2 Differences Between Version 3.1 of CRYSTALS-DILITHIUM and FIPS 204 Initial Public Draft In order to ensure the properties noted in [14], ML-DSA increases the length of 𝑡𝑟 to 512 bits and increases the length of 𝑐 ̃ to 384 and 512 bits for the parameter sets ML-DSA-65 and ML-DSA-87, respectively. In draft ML-DSA, only the first 256 bits of 𝑐 ̃ are used in the generation of 𝑐. In Version 3.1 of the CRYSTALS-DILITHIUM submission, the default version of the signing algorithm is deterministic with 𝜌′ being generated pseudorandomly from the signer’s private key and the message, and an optional version of the signing algorithm has 𝜌′ sampled instead as a 512-bit random string. In ML-DSA, 𝜌′ is generated by a “hedged” procedure in which 𝜌′ is pseudorandomly derived from the signer’s private key, the message, and a 256-bit string 𝑟𝑛𝑑, which should be generated by an Approved RBG by default. The ML-DSA standard also allows for an optional deterministic version in which 𝑟𝑛𝑑 is a 256-bit constant string. The draft ML-DSA standard also included pseudocode that unintentionally omitted a check for malformed input while unpacking the hint [33]. Failure to perform this check results in a signature scheme that is not strongly existentially unforgeable [34].

D.3 Changes From FIPS 204 Initial Public Draft In the final version of the ML-DSA standard, the omitted malformed input check was restored to the hint unpacking algorithm (Algorithm 21). Additionally, in the final version of ML-DSA, all of the bits of 𝑐 ̃ are used in the generation of 𝑐 (Algorithm 29), and ExpandMask (Algorithm 34) is modified to take output bits from the beginning of the output of H. Based on comments that were submitted on the draft version, more details were provided for the pre-hash version HashML-DSA in Section 5.4. These modifications include domain separation for the cases in which the message is signed directly and cases in which a digest of the message is signed. The changes were made by explicitly defining external functions for both versions of the signing and verification functions

54

FIPS 204

MODULE-LATTICE-BASED DIGITAL SIGNATURE STANDARD

that call an internal function corresponding to the signing or verification functions from the draft FIPS. Domain separation is included in the input to the internal function (see Algorithms 2, 3, 4, 5, 7, and 8). To simplify APIs and for testing purposes, this document also introduced a similar external/internal split for key generation (see Algorithms 1 and 6), but this is a purely editorial change, as the external key generation algorithm is functionally equivalent to the key-generation algorithm from the draft FIPS. Finally, to offer misuse resistance against the possibility that keys for different parameter sets might be expanded from the same seed [35], domain separation was added to line 1 of Algorithm 6.

55

Related documents

• NIST SP 1800-40 ipd: Automation of the NIST Cryptographic Module Validation Program#13964
• NIST SP 800-111: Guide to Storage Encryption Technologies for End User Devices#2859
• NIST FIPS 186-5: Digital Signature Standard (DSS)#2810
• NIST FIPS 205: Stateless Hash-Based Digital Signature Standard#2818
• NIST SP 800-208: Recommendation for Stateful Hash-Based Signature Schemes#2958