ML-DSA
FIPS 204 モジュール格子ベースのデジタル署名標準 Module-Lattice-Based Digital Signature Standard
IBMなどが開発
EdDSAと同じようにPureなのとHashなのがある
概要
デジタル署名は、データへの不正な変更を検出し、署名者の身元を認証するために使用されます。さらに、署名されたデータの受信者は、デジタル署名を証拠として、署名が実際に署名者によって生成されたことを第三者に示すことができます。これは、署名者が後日署名を容易に否認できないため、否認防止と呼ばれます。この標準は、デジタル署名の生成と検証に使用できる一連のアルゴリズムであるML-DSAを規定しています。ML-DSAは、大規模な量子コンピュータを所有する敵対者に対しても安全であると考えられています。
キーワード
FIPS 204 モジュール格子ベースデジタル署名標準
連邦情報処理標準規格 204
発行日: 2024年8月13日
発効日: 2024年8月13日
モジュールラティスベースデジタル署名標準の発表
連邦情報処理標準（FIPS）出版物は、米国国立標準技術研究所（NIST）が15 U.S.C. 278g-3に基づき策定し、商務長官が40 U.S.C. 11331に基づき発行する。
1. 標準名称：モジュール格子上のデジタル署名標準 Module-Lattice-Based Digital Signature Standard（FIPS 204）。
2. 標準カテゴリ：コンピュータセキュリティ。サブカテゴリ：暗号化。
3. 説明：本標準は、手書き署名ではなくデジタル署名を必要とするアプリケーション向けの格子ベースデジタル署名アルゴリズムであるML-DSAを規定する。追加のデジタル署名方式は、他のNIST特別出版物およびFIPS出版物（例：FIPS 186-5 1）で規定および承認されている。デジタル署名は、コンピュータ内でビット列として表現され、署名者の身元とデータの整合性を検証するための一連の規則とパラメータを用いて計算される。 デジタル署名は、保存データと伝送データの両方に対して生成できます。
署名生成では、秘密鍵を用いてデジタル署名を生成します。署名検証では、秘密鍵に対応する公開鍵を使用しますが、秘密鍵と同一ではありません。各署名者は、秘密鍵と対応する公開鍵からなる鍵ペアを保有します。公開鍵は公開できますが、秘密鍵は秘密に保持する必要があります。署名者の公開鍵を用いることで、誰でも署名を検証できます。秘密鍵を保有するユーザーのみが、対応する公開鍵で検証可能な署名を生成できます。
デジタル署名は、署名されたデータと共に、意図された検証者に提供されます。検証者は、署名者の公開鍵を用いて署名を検証します。同様の手順を用いて、保存データと伝送データの両方に対して署名を生成および検証することができます。
本規格は、ML-DSAの使用が承認されている複数のパラメータセットを規定しています。追加のパラメータセットは、将来のNIST特別刊行物において規定および承認される可能性があります。
4. 承認機関：商務長官
5. 保守機関 商務省、国立標準技術研究所、情報技術研究所（ITL）。
6. 適用範囲。本規格は、米国法典第10編第2315条または米国法典第44編第3502条(2)の適用を受けない、機微な非機密情報の保護に関して、すべての連邦政府省庁および機関に適用される。連邦政府省庁および機関が運用する、または契約に基づいて運用される公開鍵署名システムの設計および実装には、本規格、FIPS 205、FIPS 186-5、またはNIST特別刊行物800-208のいずれかを使用するものとする。
将来、FIPSまたはNIST特別刊行物において、追加のデジタル署名方式が規定され、承認される可能性がある。
本規格は、民間組織および商業組織が採用および使用することができる。
7. アプリケーション。デジタル署名アルゴリズムは、署名されたデータの完全性と署名者の身元を認証することを可能にします。署名されたメッセージの受信者は、デジタル署名を証拠として、署名が実際に署名者によって生成されたことを第三者に示すことができます。これは、署名者が後日署名を容易に否認できないため、否認防止と呼ばれます。デジタル署名アルゴリズムは、電子メール、電子送金、電子データ交換、ソフトウェア配布、データストレージ、およびデータの完全性保証とデータ発信元の認証を必要とするその他のアプリケーションでの使用を目的としています。
8. 実装。デジタル署名アルゴリズムは、ソフトウェア、ファームウェア、ハードウェア、またはそれらの任意の組み合わせで実装できます。NISTは、本規格のアルゴリズムへの実装の適合性をテストするための検証プログラムを開発します。本規格で規定されているすべての計算手順について、適合する実装では、指定された一連の手順を数学的に同等な任意の一連の手順に置き換えることができます。言い換えれば、すべての入力に対して正しい出力を生成する異なる手順が許容されます。
機関は、デジタル署名鍵ペアを他の目的に使用しないよう勧告されます。
9. その他の承認済みセキュリティ機能。本規格に準拠するデジタル署名の実装では、連邦政府の機密情報の保護のために承認された暗号アルゴリズムを使用する必要があります。承認済みの暗号アルゴリズムと技術には、次のいずれかが含まれます。
a. 連邦情報処理標準（FIPS）出版物で指定されているもの
b. FIPSまたはNIST勧告で採用されているもの
c. SP 800-140Cの承認済みセキュリティ機能リストで指定されているもの
10. 輸出管理。特定の暗号デバイスおよびそれらに関する技術データは、連邦輸出管理の対象となります。本規格を実装した暗号モジュールおよびそれらに関する技術データの輸出は、これらの連邦規制に準拠し、米国商務省産業安全保障局の許可を得る必要があります。輸出規制に関する情報は、https://www.bis.doc.gov でご覧いただけます。 11. 特許。本規格のアルゴリズムは、米国または外国の特許によって保護されている場合があります。
12. 実装スケジュール。本規格は、最終発行後直ちに発効します。
13. 仕様。連邦情報処理標準（FIPS）204、モジュール格子ベースデジタル署名標準（添付）。
14. 資格。デジタル署名システムのセキュリティは、署名者の秘密鍵の機密性を維持することに依存します。したがって、署名者は秘密鍵の漏洩を防ぐ必要があります。本規格は、デジタル署名生成に関する一般的なセキュリティ要件を規定することを意図していますが、本規格への適合は特定の実装のセキュリティを保証するものではありません。デジタル署名機能を実装するモジュールが安全な方法で設計および構築されていることを保証するのは、実装者の責任です。
同様に、本規格に準拠した実装を含む製品の使用は、その製品が使用されるシステム全体のセキュリティを保証するものではありません。各機関または部署の責任当局は、全体的な実装が許容可能なレベルのセキュリティを提供することを保証する必要があります。
この種の規格は、科学技術の進歩と革新に適応できる柔軟性を備えていなければならないため、本規格は5年ごとに見直しを行い、その適切性を評価します。
15. 免除手続き。連邦情報セキュリティマネジメント法（FISMA）は、商務長官によって義務付けられた連邦情報処理標準（FIPS）の免除を認めていません。
17. この出版物の引用方法。NISTは、NIST技術シリーズ出版物識別子構文に基づき、このFIPSの出版物識別子としてNIST FIPS 204を割り当てています。NISTは、以下の引用方法を推奨しています。 18. お問い合わせとご意見。本FIPSに関するお問い合わせやご意見は、fips-204-comments@nist.govまでお送りください。
連邦情報処理標準規格204
モジュール格子ベースデジタル署名標準の仕様
もくじ(略)
1. はじめに
1.1 目的と適用範囲
本規格は、バイナリデータ（一般に「メッセージ」と呼ばれる）の保護に使用可能なデジタル署名生成方法と、それらのデジタル署名の検証および妥当性確認方法を含むデジタル署名スキームを定義する。NIST Special Publication (SP) 800-175B 2「連邦政府における暗号標準の使用に関するガイドライン：暗号メカニズム」には、デジタル署名に関する一般的な説明が含まれている。 本規格は、鍵生成、署名生成、および署名検証に必要な数学的手順を規定している。デジタル署名の有効性を確保するには、同一性や秘密鍵の所有の保証といった追加の保証が必要である。SP 800-89「デジタル署名アプリケーションにおける保証の取得に関する推奨事項」 3 では、必要な保証とその取得方法を規定している。 この標準で承認されているデジタル署名方式は、モジュール格子ベースデジタル署名アルゴリズム（ML-DSA）であり、モジュール学習エラー問題 4 に基づいています。ML-DSA は、大規模なフォールトトレラント量子コンピュータを所有する敵対者に対しても安全であると考えられています。特に、ML-DSA は強力な偽造不可能性を持つと考えられており、これは、この方式を使用して、データへの不正な変更を検出し、署名者（秘密鍵を所有する者）の身元を認証できることを意味します。さらに、この方式で生成された署名は、署名が実際に主張する署名者によって生成されたことを第三者に示す証拠として使用できます。後者の特性は、署名者が後で署名を簡単に否認できないため、否認不可性として知られています。 この標準では、ML-DSA 鍵生成、署名生成、および署名検証（セクション 5）のアルゴリズムと、それらで使用されるサポートアルゴリズム（セクション 7）を示します。 ML-DSAは、それぞれ異なるセキュリティ強度に対応する3つのパラメータセットで標準化されています。第4節では、これらのアルゴリズムで使用されるグローバルパラメータについて説明し、この標準で承認されているML-DSAのパラメータセットを列挙します。ML-DSAは、NIST FIPSおよび特別出版物（例：FIPS 186-5、デジタル署名標準（DSS）1）で規定されている他のデジタル署名方式の代わりに使用できます。 1.2 背景
過去数年間、量子コンピュータの構築は着実に進展してきました。大規模な量子コンピュータが実現した場合、一般的に使用されている多くの公開鍵暗号システムのセキュリティが危険にさらされることになります。これには、整数因数分解と離散対数（有限体上および楕円曲線上の両方）に基づく鍵確立スキームやデジタル署名が含まれます。その結果、NISTは2016年に、標準化に向けた耐量子暗号（PQC）標準化プロセスを開始しました。このプロセスでは、標準化対象となる耐量子公開鍵暗号アルゴリズムが選定されました。合計82の候補アルゴリズムがNISTに提出され、3回にわたる評価と分析を経て、NISTは標準化に向けて最初の4つのアルゴリズムを選定しました。 ML-DSAは、選定された方式の一つであるCRYSTALS-DILITHIUM 5, 6から派生したものであり、暗号学的に重要な量子コンピュータの登場後も含め、予見可能な将来にわたって米国政府の機密情報を保護することを目的としています。ML-DSAとCRYSTALS-DILITHIUMの違いについては、付録Dを参照してください。 2. 用語、頭字語、記号の用語集
2.1 用語と定義
承認済み approved
FIPS承認済みおよび/またはNIST推奨済み。1) FIPSまたはNIST勧告で規定されている、2) FIPSまたはNIST勧告で採用されている、または3) NIST承認済みセキュリティ機能のリストで規定されているアルゴリズムまたは手法。
所有の保証 assurance of possession
ある主体が秘密鍵および関連する鍵素材を所有しているという確信。
非対称暗号 asymmetric cryptography
2つの異なる鍵を用いてデータを交換します。1つはデータの暗号化またはデジタル署名に、もう1つはデータの復号化またはデジタル署名の検証に使用されます。公開鍵暗号とも呼ばれます。
ビット列 bit string
0と1の順序付けられたシーケンス。
バイト byte
{0, 1, 2, …, 255} の集合に含まれる整数。
バイト列 byte string
順序付けられたバイトのシーケンス。
証明書 certificate
公開鍵と、それに対応する秘密鍵、そしてその鍵ペアの使用を許可された所有者を一意に識別するデータセット。証明書には所有者の公開鍵と、場合によってはその他の情報が含まれており、認証局（信頼できる機関）によってデジタル署名されており、これにより公開鍵と所有者が結び付けられます。
認証局 (CA) certification authority (CA)
公開鍵基盤（PKI）において、証明書の発行とPKIポリシーの厳格な遵守を担当する機関。
主張署名者 claimed signatory
検証者の観点から見ると、主張署名者とは、デジタル署名を生成したとされる主体です。
破棄 destroy
鍵または秘密データに適用されるアクション。鍵または秘密データが破棄されると、その値に関する情報は回復できなくなります。
デジタル署名 digital signature
データの暗号変換の結果であり、適切に実装されると、発信元の真正性とデータの完全性を検証し、署名者の否認防止を強化するメカニズムを提供します。
エンティティ(実在物) entity
個人、組織、デバイス、またはプロセス。パーティと同義で使用されます。
同等のプロセス equivalent process
2つのプロセスは、各プロセスに同じ値（入力パラメータ、プロセス中に利用可能な値、またはその両方）を入力したときに同じ出力が生成された場合、同等であるとみなされます。
拡張可能出力関数 (XOF) eXtendable-Output Function (XOF)
ビット文字列に対する関数で、出力を任意の長さに拡張できます。承認されたXOF（例えば、FIPS 202 7 で規定されているもの）は、指定された出力長が単純な攻撃を阻止できるほど十分に長い限り、以下の特性を満たすように設計されています。 1. (一方向性) 任意の入力が、事前に指定された任意の新しい出力にマッピングされることは、計算的に不可能です。
2. (衝突耐性) 任意の2つの異なる入力が、同じ出力にマッピングされることは、計算的に不可能です。
新しい乱数 fresh random value
ランダムビットジェネレータの未使用の出力。
ハッシュ関数 hash function
出力の長さが固定されたビット列に対する関数。承認されたハッシュ関数（FIPS 180 8 や FIPS 202 7 で規定されているものなど）は、以下の特性を満たすように設計されています。 1. (一方向性) 任意の入力が、事前に指定された任意の新しい出力にマッピングされることは、計算量的に不可能です。
2. (衝突耐性) 任意の2つの異なる入力が、同じ出力にマッピングされることは、計算量的に不可能です。
ハッシュ値 hash value
メッセージダイジェストを参照。
鍵 key
暗号アルゴリズムの動作を決定するパラメータ。この規格に適用可能な暗号アルゴリズムの例としては、以下のものが挙げられます。
1. データからのデジタル署名の計算
2. デジタル署名の検証
鍵ペア key pair
公開鍵とそれに対応する秘密鍵。
リトルエンディアン little-endian
バイト列のバイトが重要度の昇順に並んでいる性質。特に、左端（最初）のバイトが最も重要度が低く、右端（最後）のバイトが最も重要度が高い。「リトルエンディアン」という用語は、ビット列にも同様に適用される場合がある（例えば、8ビット文字列 11010001 は、バイト $ 2^0 + 2^1 + 2^3 + 2^7 = 139 に対応する）。
メッセージ message
署名されたデータ。署名の検証および検証プロセスでは、署名済みデータとも呼ばれます。
メッセージダイジェスト message digest
メッセージにハッシュ関数を適用した結果。ハッシュ値とも呼ばれます。
否認防止 non-repudiation
データの完全性と出所を保証するために用いられるサービス。これにより、データの完全性と出所は、第三者によって検証され、秘密鍵を保有する特定のエンティティ（例, 署名者）から発信されたものであることが確認されます。
所有者 owner
鍵ペアの所有者とは、鍵ペアの秘密鍵を使用する権限を持つエンティティです。
当事者 party
個人、組織、デバイス、またはプロセス。エンティティと同義で使用されます。
公開鍵基盤（PKI） public-key infrastructure (PKI)
公開鍵証明書の発行、維持、および失効のために確立されたフレームワーク。
秘密鍵 private key
非対称（公開鍵）暗号アルゴリズムで使用される暗号鍵。秘密鍵は所有者に一意に関連付けられており、公開されません。秘密鍵は、対応する公開鍵を使用して検証可能なデジタル署名を計算するために使用されます。
疑似乱数 pseudorandom
プロセスまたはプロセスによって生成されるデータは、結果が決定論的でありながら、プロセスの内部動作が観察できない限り、実質的にランダムである場合、疑似乱数と呼ばれます。暗号学において、「実質的にランダム」とは、「意図されたセキュリティ強度の限度内で、計算的にランダムと区別できない」ことを意味します。
公開鍵 public key
非対称（公開鍵）暗号アルゴリズムで使用され、秘密鍵と関連付けられる暗号鍵。公開鍵は所有者に関連付けられ、公開される場合がある。デジタル署名の場合、公開鍵は対応する秘密鍵を用いて生成されたデジタル署名を検証するために使用される。
セキュリティカテゴリ security category
NIST（9、5.6節を参照）によって規定された、耐量子暗号アルゴリズムのセキュリティ強度に関連付けられた数値。 セキュリティ強度 security strength
暗号アルゴリズムまたはシステムを解読するために必要な作業量（すなわち、演算回数）に関連付けられた数値。
シード seed
疑似乱数処理への入力として使用されるビット列。
shall
この規格の要件を示すために使用されます。
should
この規格の要件ではなく、強い推奨を示すために使用されます。この推奨事項を無視すると、望ましくない結果につながる可能性があります。
署名者 signatory
秘密鍵を用いてデータにデジタル署名を生成する主体。
署名生成 signature generation
デジタル署名アルゴリズムと秘密鍵を用いてデータにデジタル署名を生成するプロセス。
署名有効性検証 signature validation
デジタル署名の数学的検証と、適切な保証（例：公開鍵の有効性、秘密鍵の所有など）の取得。
(有効であること/妥当であることを認める/確認する/認証すること)
署名検証 signature verification
デジタル署名アルゴリズムと公開鍵を用いてデータにデジタル署名を検証するプロセス。
(正しいこと/事実であることを確かめる/実証する/検証すること)
署名済みデータ signed data
デジタル署名の計算対象となるデータまたはメッセージ。「メッセージ」も参照。
信頼できる第三者（TTP） trusted third party (TTP)
鍵ペアの所有者と検証者以外の、所有者、検証者、またはその両方から信頼されている主体。「信頼できる当事者」と略されることもあります。
検証者 verifier
署名者の公開鍵を用いてデジタル署名の真正性を検証する主体。
2.2 略語
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省庁間または内部報告書 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 セキュアハッシュアルゴリズム KECCAK Secure Hash Algorithm KECCAK
SP 特別出版物 Special Publication
SUF-CMA 選択メッセージ攻撃に対する強存在偽造不可能性 Strongly existentially UnForgeable under Chosen Message Attack
XOF 拡張可能出力関数 eXtendable-Output Function
2.3 数学記号
この規格では以下の記号および数式が使用されています。
$ q 素数$ q = 2 − 213 + 1 = 8380417 .
$ \mathbb{B} 1 バイトで表される整数の集合 {0, 1, … , 255}。
$ \mathbb{N} 自然数の集合{1, 2, 3, …}。
$ \mathbb{Z} 整数の環。
$ \mathbb{Z}_m 𝑚を法とする整数の環で、その要素の集合は{0, 1, …, 𝑚 − 1}です。
$ \mathbb{Z}^n_m ℤ-加群構造を備えた $ \mathbb{Z}_m上の $ n-組の集合。
$ R $ X^{256} + 1 を法とするZ上の一変数多項式の環。$ Z[X]/(X^{256} + 1) とも表記される。
$ R_m $ X^{256} + 1 を法とする$ \mathbb{Z}_m 上の一変数多項式の環。$ \mathbb{Z}_m[X]/(X^{256} + 1) とも表記される。
$ B_r $ R_q 内の多項式$ \textstyle p = \sum_{i=0}^{255}p_iX^i のうち、$ p_i の係数のうちちょうど$ \tau が集合$ \{−1, 1\} から得られ、その他の係数はすべてゼロとなるような多項式全体の集合。(セクション 7.3 を参照)
$ \Pi 2 つ以上の環の直積を表すために使用されます。この場合、加算と乗算は成分ごとに実行されます。
$ T_q 環 $ \textstyle \prod_{j=0}^{255}\mathbb{Z}_q
$ A \times B 2つの集合 $ A 、$ B の直積。
$ [a,b] 2つの整数$ a \le b に対して、$ [a, b] は整数の集合$ \{a,a+1,…,b\}を表します。
bitlen $ a 正の整数$ a のビット長。$ a のビット長は、$ a を2進数で表現した際に現れる桁数であり、表現の最上位桁は1と仮定します（例：bitlen 32 = 6、bitlen 31 = 5）。$ ^1
$ ^1この仕様では、bitlen 𝑎 は 𝑎 の少数の有限の値でのみ呼び出されるため、これらの値に対して bitlen 𝑎 を事前に計算し、結果をその場で計算するのではなくハードコードすると便利な場合があります。
$ BitRev_8(r) 8ビット整数$ r のビット反転。$ r = r_0 + 2r_1 + 4r_2 + … + 128r_7 $ r_i \in \{0,1\}の場合、$ BitRev_8(r) = r_7 + 2r_6 + 4r_5 + … + 128r_0 となります。
0x 16 進表現で記述された整数の接頭辞。
$ \log_2x $ x の2を底とする対数。例えば、$ \log_2(16) = 4。
$ \bmod $ a が正の整数で、$ m \in \mathbb{Z} または$ m \in \mathbb{Z}_a の場合、$ m \mod a は、$ 0 \le m' < a' の範囲で、$ m と$ m' が$ aを法として合同となる唯一の元$ m' \in \mathbb{Z}を表します。
$ \bmod^\pm $ 𝛼 が正の整数で、$ m \in \mathbb{Z} または $ m \in \mathbb{Z}_a の場合、$ 𝑚 \bmod^\pm a は、範囲 $ -\lceil a/2\rceil<m'\le\lfloor a/2 \rfloor 内の唯一の元 $ m' \in \mathbb{Z} を表し、$ m と$ m' は$ a を法として合同です。
$ \lfloor x \rfloor 実数$ x 以下の最大の整数。これは$ x の床値(floor of x)と呼ばれます。例えば、$ \lfloor2.1\rfloor=2、$ \lfloor4\rfloor=4です。
$ \lceil x\rceil 実数$ x 以上の最小の整数。これは$ x の天井値と呼ばれます。例えば、$ \lceil5\rceil =5、$ \lceil5.3\rceil=6です。
$ \|・\|_\infin 無限大ノルム(norm)。$ w \in \mathbb{Z} の元に対して、$ \|w\|_\infin=|w| 、$ w の絶対値。$ w \in \mathbb{Z}_q の元に対して、$ \|w\|_\infin=|w \bmod^\pm q| 。$ R または$ R_q の元$ w に対して、$ \|w\|_\infin=max_{0\le i<256}\| w_i \|_\infin 。または$ R から$ R_q のエントリを持つlength-𝑚ベクトル$ \bold{w} の場合、$ \|\bold{w}\|_\infin=max_{0\le i<m}\|w[i]\|_\infin です。
$ a!階乗量 1 ⋅ 2 ⋅ 3 ⋅ … ⋅ 𝑎。値 0! は 1 と定義されます。
$ (^a_b)$ a \ge bの場合、量$ a!/(b!(a-b)!)。
$ s ← x 擬似コードでは、この表記は変数$ sに式$ xの値が割り当てられることを意味します。
$ s ← \mathbb{B}^l 擬似コードでは、この表記は変数$ sに$ l個のランダムバイト配列の値が割り当てられることを意味します。これらのバイトは、承認されたRBGによるランダム性を用いて生成する必要があります。セクション3.6.1を参照してください。
$ x\in S ←y 型キャスト。変数$ xには、おそらく異なる集合$ T内の式$ yの値から構成される集合$ S内の値が代入されます。集合$ Tと$ Tから$ Sへの写像は明示的には指定されていませんが、この文が現れる文脈から明らかです。
$ [[a<b]] ブール述語。二重角括弧$ [[a<b]] 内の比較演算子は、式がブール値として評価されることを示します。ブール値は、1 が真、0 が偽を表す $ \mathbb{Z}_2 の要素として解釈することもできます。
$ \langle\langle f(x)\rangle\rangle 計算結果$ f(x) を一時変数に格納し、再計算することなく何度も利用できるようにします。これは、一時変数$ y ← f(x)を定義することと同等です。変数名を$ \langle\langle f(x) \rangle\rangleとすることで、擬似コードが簡潔になります。
$ a||b 2 つのビットまたはバイト文字列$ aと$ bの連結。
$ a \circ b 環$ T_qにおける$ aと$ bの乗算。
$ a・b または $ ab 環 $ \mathbb{Z}、$ \mathbb{Z}_m、$ R、または$ R_mのいずれかにおける乗算。
$ a+b $ aと$ bの加算。
$ a/b 整数の割り算。この表記法を用いる場合、$ aと$ bは常に整数です。$ b:が$ aを割り切れないと仮定できない場合は、$ \lfloor a/b \rfloorまたは$ \lceil a/b \rceilのいずれかを用います。
$ \perp アルゴリズムの失敗または出力の欠如を示す空白の記号。
2.4 表記
2.4.1 環 Rings
環 $ \mathbb{Z}, \mathbb{Z}_q, \mathbb{Z}_2, R, R_q の元は、イタリック体の小文字（例：$ \mathit{𝑤} ）で表されます。環 $ T_q の元は、$ \mathbb{Z}_q の元の長さ256の配列であり、イタリック体の文字にハット記号（例：$ \mathit{\hat{w}} ）を付けて表されます。$ T_q の元の加算と乗算は、要素ごとに実行されます。したがって、$ T_q の2つの要素$ \hat{u} と$ \hat{v} の積の$ i 番目の要素は、$ \hat{u}[i]・\hat{v}[i] \in \mathbb{Z}_q です。$ T_q における乗算演算は記号$ \circ で表されます（2.3節参照）。
積(product)$ a・b または和(sum)$ a+b と表記され、$ a または$ b のいずれかが$ m を法とする合同類である場合（つまり、$ a または$ b のいずれかが$ \mathbb{Z}_m または$ R_m の元である場合）、その積または和も$ m を法とする合同類であると理解されます（つまり、$ \mathbb{Z}_m または$ R_m の元である場合）。同様に、$ R または$ \mathbb{Z} の要素は、それぞれ$ R_m または$ \mathbb{Z}_m の要素に「型キャスト」することができ、それぞれ $ R_m または$ \mathbb{Z}_m の要素に作用するように指定された関数の入力として使用することができます。どちらの場合も、要素自体またはその係数は、整数を含む$ m を法とする唯一の合同類をとることによって、$ \mathbb{Z} から $ \mathbb{Z}_m にマッピングされます。
$ R または$ R_m の要素$ wの係数は$ w_iで表され、$ w = w_0 + w_1X + … + w_{255}X^{255}となります。
$ wが$ R (それぞれ$ R_m) に属し、$ tが$ \mathbb{Z}(それぞれ$ \mathbb{Z}_d) に属する場合、$ w(t)は$ X=tで評価された多項式$ w = w_0 + w_1X + … + w_{255}X^{255}を表します。
2.4.2 ベクトルと行列
$ Rまたは$ R_mの要素を持つベクトルは、太字の小文字で表されます（例：$ \bold{v}）。$ Rまたは$ R_mの要素を持つ行列は、太字の大文字で表されます（例：$ \bold{A}）。
$ Sが環で、$ \bold{v}が$ S上の長さ$ Lベクトルである場合、ベクトル$ \bold{v}の要素は
$ v[[0], v[1], … ,v[L-1] と表されます。
$ S 上の$ K \times L 行列$ \bold{A} の要素は$ \bold{A}[i,j] と表されます。ただし、$ 0\le i < K かつ$ 0 \le j < L です。
$ S 上の長さ$ L ベクトル全体の集合は$ S^L で表されます。$ S 上のすべての$ K\times L 行列の集合は$ S^{K\times L}と表されます。長さ$ Lのベクトルは$ L\times1行列として扱うこともできます。
2.5 NTT表現
数論変換（NTT: Number Theoretic Transform）は、環$ R_qと$ T_qの間の特定の同型写像です。
$ 𝜁 = 1753 \in \mathbb{Z}_q とすると、これは1の512乗根です。$ w \in R_qならば、
$ NTT(w) = (w(𝜁_0), w(𝜁_1), … , w(𝜁_{255})) \in T_q
となります。(2.1)
ここで、$ 𝜁_i = w(𝜁^{2BitRev_8(𝑖)+1}) \bmod q である。$ NTT と $ NTT^{−1} の実装については7.5節を参照のこと。
NTT を使用する理由は、環$ T_q上では乗算がかなり高速になるからである。NTT は同型なので、任意の$ a,b \in R_q に対して、
$ NTT(ab) = NTT(a) \circ NTT(b) が成り立つ。(2.2)
$ \bold{A}が$ R_qを要素とする行列である場合、$ NTT(\bold{A}) は NTT を$ \bold{A}に要素ごとに適用して計算される行列を表す。記号$ \circは、$ T_qを要素とする行列の乗算を表すためにも用いられます。したがって、$ NTT(\bold{AB}) = NTT(\bold{A}) \circ NTT(\bold{B}) となります。$ T_q上の線形代数の明示的なアルゴリズムは7.6節で示します。
3. ML-DSA署名方式の概要
ML-DSAは、CRYSTALS-DILITHIUM 6に基づくデジタル署名方式です。ML-DSAは、3つの主要なアルゴリズム、ML-DSA.KeyGen（アルゴリズム1）、ML-DSA.Sign（アルゴリズム2）、ML-DSA.Verify（アルゴリズム3）から構成されます。ML-DSA方式は、Fiat-Shamir With Aborts構造10, 11を採用しており、12, 13で提案された方式と最も類似しています。 本文書では、密接に関連しているもののドメイン分離型の署名方式であるHashML-DSAも定義します。HashML-DSAは、署名前に追加の事前ハッシュステップを含む点でML-DSAと異なります。これは、ML-DSA で使用されるものと同じキー生成アルゴリズムである ML-DSA.KeyGen (アルゴリズム 1)、HashML-DSA.Sign (アルゴリズム 4)、および HashML-DSA.Verify (アルゴリズム 5) の 3 つの主要なアルゴリズムで構成されています。
3.1 セキュリティ特性
ML-DSAは、選択メッセージ攻撃（SUF-CMA）に対して、存在的偽造不可能となるように設計されている。つまり、たとえ攻撃者が正当な当事者に任意のメッセージに署名させたとしても、署名者が既に署名を提供しているメッセージを含め、署名者の公開鍵に基づいて追加の有効な署名を作成することはできないと予想される。
ML-DSAは、偽造不可能性に加えて、14で説明されている追加のセキュリティ特性を満たすように設計されている。 3.2 計算上の仮定
格子ベースデジタル署名方式の安全性は、典型的には、誤り学習（LWE: Learning With Errors）問題と短整数解（SIS: short integer solution）問題に関連している。LWE問題 15 は、$ \bold{s} が満たすランダムな「ノイズの多い」線形方程式の集合$ ^2が与えられた場合に、ベクトル$ \bold{s} \in\mathbb{Z}^𝑛_𝑞 を復元する問題である。SIS問題は、$ \bold{At} = \bold{0} の形式をとる $ ℤ_𝑞 上の線形システムに対して、$ \|\bold{t}\|_\infin が小さいような非ゼロ解$ \bold{t}\in\mathbb{Z}^n_q を求める問題である。パラメータを適切に選択すれば、これらの問題は、ガウス消去法などの既知の手法を用いても解くことができない。 LWEおよびSISにおける加群$ \mathbb{Z}^n_qを$ R_qよりも大きな環（例えば$ R_q）上の加群に置き換えた場合、結果として生じる問題は、モジュール誤り学習（MLWE: Module Learning With Errors）4およびモジュール短整数解（MSIS: Module Short Integer Solution）と呼ばれます。ML-DSAの安全性は、$ R_q上のMLWE問題と、SelfTargetMSIS 16と呼ばれるMSISの非標準版に基づいています。 $ ^2 具体的には、LWE問題は、𝐀𝐬 + 𝐞 = 𝑏 という形式の連立方程式を解くことです。ここで、𝐀と𝑏は与えられており、𝐞は与えられていませんが、小さいことが分かっています。
3.3 ML-DSAの構築
ML-DSA は、いくつかの最適化が施された Schnorr（シュノア) のような署名です。Schnorr 署名方式は、$ g（離散対数が困難であると考えられる群の生成元）と値$ y = g^xを知っている検証者と、$ gと$ xを知っている証明者との間の対話型プロトコルに、Fiat-Shamir ヒューリスティック(発見的問題解決)を適用します。この対話型プロトコルでは、証明者が検証者に$ xの知識を証明し、以下の 3 つのステップで構成されます。
1. コミットメント：証明者は$ gのorder未満のランダムな正の整数$ rを生成し、$ g^rを検証者に送信することで、その値をコミットします。
2. チャレンジ：検証者は$ gのオーダー未満のランダムな正の整数$ cを証明者に送信します。
3. 応答: 証明者は$ s = r - cxを$ gの位数を法として減算したものを返し、検証者は$ g^s ⋅y^c = g^rかどうかを確認します。
このプロトコルは、ステップ2における検証者のランダムな$ c選択を、署名対象メッセージに連結されたコミットメント$ g^rのハッシュから擬似ランダムに$ cを導出する決定論的プロセスに置き換えることで、非対話型となり、署名スキームに変換されます。この署名スキームでは、$ yは公開鍵、$ xは秘密鍵です。
ML-DSAや類似の格子署名方式の基本的な考え方は、類似の対話型プロトコルから署名方式を構築することである。このプロトコルでは、小さな係数（$ \mathbf{S}_1 と$ \mathbf{S}_2 について）を持つ行列$ \mathbf{A} \in \mathbb{Z}_q^{K \times L} 、$ \mathbf{S}_1 \in \mathbb{Z}_q^{L \times n}、および$ \mathbf{S}_2 \in \mathbb{Z}_q^{K \times n}を知っている証明者が、$ \mathbf{A}と$ \mathbf{T} \in \mathbb{Z}_q^{K \times n}=\mathbf{AS}_1+\mathbf{S}_2を知っている検証者にこれらの行列の知識を実証する。このような対話型プロトコルは以下のように進行する。
1. コミットメント: 証明者は小さな係数を持つ$ \mathbf{y} \in \mathbb{Z}_q^Lを生成し、$ \mathbf{w}_{Approx} = \mathbf{Ay} + \mathbf{y}_2を検証者に送信することでその値をコミットします。ここで、$ \mathbf{y}_2 \in \mathbb{Z}_q^Kは小さな係数を持つベクトルです。
2. チャレンジ: 検証者は小さな係数を持つベクトル$ \mathbf{c} \in \mathbb{Z}_q^nを証明者に送信します。
3. レスポンス: 証明者は$ \mathbf{z} = \mathbf{y} + \mathbf{S}_1\mathbf{c}を返し、検証者は$ \mathbf{z}が小さな係数を持ち、$ \mathbf{Az} - \mathbf{Tc} \approx \mathbf{w}_{Approx} であることを確認します。
書かれているとおり、上記のプロトコルにはセキュリティ上の欠陥があります。レスポンス$ \mathbf{z}は秘密値$ \mathbf{S}_1に関連した方向に偏ります。同様に、$ \mathbf{r} = \mathbf{w}_{approx} − \mathbf{Az}+\mathbf{Tc} = \mathbf{y}_2 + \mathbf{S}_2\mathbf{c}は秘密値 $ \mathbf{S}_2に関連した方向に偏ります。ただし、この欠陥は対話型プロトコルを署名スキームに変換する際に修正できます。Schnorr 署名と同様に、署名者はメッセージに連結されたコミットメントのハッシュから疑似乱数プロセスによってチャレンジを導出します。この偏りを修正するために、署名者は$ \mathbf{z} に拒否サンプリングを適用します。$ \mathbf{z} の係数が指定された範囲外になった場合、署名プロセスは中止され、署名者は$ \mathbf{y}の新しい値からやり直します。同様に、$ \mathbf{r}にも同様の拒否サンプリングを適用する必要があります。これらのチェックは、アルゴリズム7の23行目で行われるチェックと同様です。簡略化されたFiat-Shamir With Aborts署名では、公開鍵は$ (\mathbf{A},\mathbf{T})、秘密鍵は$ (\mathbf{S}_1,\mathbf{S}_2)です。
ML-DSA標準では、セキュリティや効率性上の理由から、この基本フレームワークにいくつかの調整と修正が加えられています。
ML-DSAは、鍵と署名のサイズを縮小し、NTTベースの高速な多項式乗算を利用するために、モジュール構造の行列を使用します。上記の基本方式と比較して、ML-DSAは、次元$ n \times nの行列ブロックと次元$ nのベクトルブロックを、環 , 𝐒1 ∈ 𝐿×𝑛 , 𝐒𝟐 ∈ �𝐾×𝑛𝑅𝑞 内の多項式に置き換えます。したがって、$ \mathbf{A}\in\mathbb{Z}_q^{K \times L}、$ \mathbf{T}\in\mathbb{Z}_q^{K \times n}、 𝐲 ∈ ℤ𝐿 𝑞 、 𝐜 ∈ ℤ𝑞 𝑛 の代わりに、 ML-DSA では 𝐀 ∈ 𝑅𝑞 𝑘×ℓ 、 𝐭 ∈ 𝑅𝑞 𝑘 、 𝐬1 ∈ 𝑅𝑞 ℓ 、 𝐬2 ∈ 𝑅𝑞 𝑘 、 𝐲 ∈ となります。 𝑅𝑞 ℓ , 𝑐 ∈ 𝑅𝑞、ただし ℓ = 𝐿/𝑛、𝑘 = 𝐾/𝑛。