ML-DSA（Dilithium）とFIPS 204

ML-DSAとは何か：格子署名の標準

ML-DSA（Module-Lattice-based Digital Signature Algorithm）は、NISTが2024年8月に FIPS 204 として標準化したポスト量子デジタル署名です。母体は CRYSTALS-Dilithium で、標準化に際して ML-DSA へ改名されました。RSA-PSS や ECDSA／EdDSA が依拠する素因数分解・離散対数は Shor のアルゴリズムで量子的に解けてしまうため、それらを置き換える量子耐性署名として設計されています。

横にスクロール

ML-DSA の安全性は、格子暗号で扱う2つの格子問題の困難さに帰着します。鍵の秘匿は Module-LWE（MLWE、誤り付き学習の加群版）、署名の偽造困難性は Module-SIS（MSIS、短整数解問題の加群版）が支えます。MSIS は「与えられた行列 A に対し A·x = 0 を満たす十分に短い非ゼロベクトル x を求める」問題で、短い解を作れなければ有効な署名を捏造できない、という形で偽造耐性に結びつきます。

演算はすべて多項式環 Zq[x]/(x^256+1) の上で行い、n = 256、モジュラス q = 8380417（= 2^23 − 2^13 + 1、23ビットの素数）です。この q は q ≡ 1 (mod 512) を満たすため、多項式の積を数論変換（NTT）で O(n log n) に高速化できます。ハッシュ・擬似乱数展開には SHA-3 系の SHAKE-256／SHAKE-128 を用います。

鍵生成とNTT

鍵生成はシードから決定的に行います。32バイトのシード ξ を SHAKE で展開し、行列 A（Zq[x]/(x^256+1) を成分とする k × l 行列）、秘密ベクトル s1（長さ l）・s2（長さ k）を生成します。s1, s2 の各係数は [-η, η] の小さな範囲に収まる「短い」多項式です（η はパラメータ、2 または 4）。公開鍵の中核は

t = A · s1 + s2   (mod q)

で、これは MLWE インスタンスそのものです。A は乱数、s1, s2 は短い誤差／秘密なので、(A, t) から s1, s2 を復元することが MLWE の困難さに守られます。

サイズ削減のため、t は上位ビット t1 と下位ビット t0 に分割され、公開鍵には t1 のみを載せます（t0 は署名検証時に別経路で補います）。行列 A は公開鍵にシード ρ として畳み込み、検証側が同じ SHAKE 展開で再生成します。これにより公開鍵は行列本体を持たずに済み、サイズを大幅に圧縮できます。

署名：Fiat-Shamir with aborts

署名生成が ML-DSA の心臓部です。手順の骨格は次のとおりです。

1. マスク y を生成（各係数は [-γ1+1, γ1] の一様乱数）
2. w = A · y (mod q) を計算し、上位ビット w1 を取り出す
3. チャレンジ c = H(message || w1 || tr)  ← 係数±1がτ個だけの疎な多項式
4. z = y + c · s1  を計算
5. r0 = LowBits(w - c·s2) を計算
6. 【拒否判定】 ‖z‖∞ ≥ γ1-β  または  ‖r0‖∞ ≥ γ2-β なら
      → y を捨てて手順1へ戻る（abort）
7. ヒント h を作り、署名 σ = (c~, z, h) を出力

ここで最重要なのが手順6の拒否サンプリング（rejection sampling）、すなわち "with aborts" の由来です。z = y + c·s1 をそのまま出すと、z の分布が秘密 s1 に依存して歪み、多数の署名を集めると s1 が統計的に漏れます。そこで z や r0 があらかじめ決めた安全範囲を1つでも外れたら署名を破棄し、新しい y で最初からやり直す。範囲内に収まった z だけを出力すれば、z の分布は s1 から独立した一様分布となり、秘密の情報が滲み出ません。

チャレンジ c は係数が +1/-1 を τ 個だけ持ち残りが 0 の疎な多項式で、c·s1 を小さく保ちます。ヒント h は、公開鍵から捨てた t0 の影響を検証側が復元できるようにする1ビット/係数の補助情報です。

検証手順

検証は署名生成より単純で、abort もマスクも不要です。検証者は σ = (c~, z, h) と公開鍵 (ρ, t1) を受け取り、次を確認します。

1. ρ から A を再生成（SHAKE 展開）
2. c~ からチャレンジ多項式 c を復元
3. w1' = UseHint( h,  A·z - c·t1·2^d )  を計算
4. c'  = H(message || w1' || tr) を再計算
5. 受理条件:  c' == c~   かつ   ‖z‖∞ < γ1-β

核心は手順3の等式です。正規の署名なら A·z − c·t1·2^d = A·y − c·s2 + (誤差) となり、上位ビットは署名時の w1 と一致します。h はこの上位ビットを t0 を持たない検証側でも正しく復元させるためのヒントです。復元した w1' から算出したチャレンジが送られてきた c~ と一致し、かつ z が範囲内（‖z‖∞ < γ1-β）に収まっていれば受理します。範囲チェックは、偽造者が MSIS を解かずに大きな z でごまかすのを防ぎます。

パラメータと鍵・署名サイズ

FIPS 204 は3つのパラメータセットを定義し、NIST セキュリティカテゴリに対応させています。カテゴリは「その水準の攻撃に必要な計算資源が、指定の対称鍵探索と同等以上」を意味します。

k は行列 A の行数、l は列数で、これを増やすほど MLWE／MSIS が難しくなる代わりにサイズと計算量が増えます。ECDSA（P-256）の署名が約64バイト、公開鍵が33バイトであるのと比べると、ML-DSA は署名で数十倍、公開鍵で数十倍の大きさです。この肥大化が、証明書チェーンや署名スキームを使う既存プロトコルへの移行で最大の実務課題になります。

なお FIPS 204 は、メッセージを直接署名する pure 版に加え、事前ハッシュした HashML-DSA（大きなメッセージやストリーミング向け）も規定します。決定的署名（シードから乱数を導出）と、追加乱数を混ぜる hedged 版の両方に対応し、乱数源が壊れても即座に破綻しない設計になっています。

まとめ

ML-DSA（FIPS 204、旧 Dilithium）は、Module-LWE と Module-SIS の困難さに立脚する格子署名です。多項式環 Zq[x]/(x^256+1)（q = 8380417）上で NTT を使い、公開鍵は MLWE インスタンス t = A·s1 + s2 を圧縮して持ちます。署名は Fiat-Shamir with abortsで z = y + c·s1 を作り、拒否サンプリングでマスクの偏りによる秘密鍵漏洩を封じるのが核心です。検証は abort 不要で高速に上位ビットの一致を確かめます。

セキュリティカテゴリ2/3/5に応じた ML-DSA-44/65/87 は公開鍵1.3〜2.6 KB・署名2.4〜4.6 KB と古典署名より桁違いに大きい反面、検証が速く量子耐性を持ちます。詳しくはポスト量子暗号の原理と、既存資産をどう置き換えるかの量子耐性移行戦略を併せて押さえてください。