【耐量子計算機暗号・PQC】ML-DSA（CRYSTALS-DILITHIUM）標準について

ML-DSAは2024/8/13にFIPS 204としてNIST標準化されたPQCデジタル署名アルゴリズムである。FIPS文書はよくまとめられており、読んだだけでなんとなく実装できる感じになっているが「なんでそうなっているのか」みたいな深いところまでは書いてない。一部の証明などは標準化前の文書CRYSTALS-DILITHIUMを参照したほうがいい。

ML-DSAは構成としては（モジュール）格子版のシュノア署名である。シュノア署名は3-wayのシグマプロトコルをFiat-Shamir変換で非対話にしたものであるとみなせるため、シュノア署名の説明およびML-DSAの説明でもこの3-way（コミット・チャレンジ・レスポンス）の用語が使われる。

というわけでML-DSAを格子版のシュノア署名として理解すればある程度簡潔なのだが、効率化するために様々な圧縮テクニックやそれを保証するためのルーチン（Fiat-Shamir with Abort）が使われているためにごちゃついたアルゴリズムになっている。

下の説明では多項式やベクトル、係数の表記を区別してないが許して

シュノア署名

パブリックパラメータ

• 位数$q$の群$G$上の生成元$g$
• ハッシュ関数$H: \{0,1\}^* \rightarrow Z_q$

鍵生成

• 乱数$s \in Z_q$を秘密鍵とする。
• $p=g^{s}$を公開鍵とする。

署名生成

• 秘密の乱数$r \in Z_q$を生成
• $e=H(m;g^r)$をチャレンジとする。（$g^r$はコミットに対応する）
• $y=r-se$をレスポンスとする。
• $\sigma=(y,e)$が署名

検証

• $e'=H(m;g^yp^e)$とし、$e=e'$なら検証成功。
• Correctness: 署名が正当な時$g^yp^e=g^{r-se}g^{se}=g^r$なので検証に成功する。
• Soundness: よくわからんけどランダムオラクルで示せる

ML-DSA(simplified)

シュノア署名との対応をわかりやすくするため、簡潔にしたバージョンをまず導入する。

鍵生成

• $A \in R_q^{k \times \ell}$および非常に短い多項式$s_1 \in R_q^\ell, s_2 \in R_q^k$を一様ランダムに生成
• $(A, t=As_1+s_2)$を公開鍵、$(s_1,s_2)$を秘密鍵とする

署名生成

• $y \in R_q^\ell$を一様ランダムに生成
• $w=Ay$をコミットとする。
• メッセージ$m$に対して$c=H(m;w)$をチャレンジとする。
• $z=y+cs_1$をレスポンスとする。
• $\sigma=(z,c)$が署名

検証

• $w'=Az-ct$を計算し、$c'=H(m;w')$が$c$と等しければ検証成功
• Correctness: 真正な署名なら$Az-ct=A(y+cs_1)-c(As_1+s_2)=Ay+cs_2$となるが$s_2$は小さなベクトルなのでうまく取り除くことができ、$w=w'$となる。

このようなSimplified ML-DSAは厳密にはcorrectnessを示せないが、Schnorr署名と対応させるとなんとなく各変数の役割がわかるだろう。実際のML-DSAはcorrectnessを満たすためもしくは署名長・鍵長を短くするために値の下位ビットを捨てる処理が入っており、かつNTT表現が仕様に入っているので複雑になる。

ML-DSA

続いてFIPS 204に基づくML-DSAアルゴリズムを紹介する。

ちなみに鍵・署名サイズは以下である。PQCの中では頑張っている方だが、ECDSAが32バイト〜、RSAでさえ数百バイトであることを考えると確かにでかい。

鍵生成

以下のような32バイト乱数$\xi$を入力として秘密鍵と公開鍵を出力する関数である。処理的にはLWEインスタンスを生成するだけなんだけれど、公開鍵$t$を圧縮して上位ビット$t_1$だけ使うようになっている。

ExpandA

公開シード$\rho$から一様ランダムな多項式行列$A \in R_q^{k\times \ell}$を生成する。ML-KEMの時と同じようにSHAKEから得たビット列から棄却サンプルして$Z_q$の値を作って多項式の係数に入れていくだけ。法$q$が23ビットなので3バイトの一様乱数が係数内に入る確率は1/2くらい。

ExpandS

要素数の異なる二つの秘密多項式ベクトル$s_1 \in R_q^\ell, s_2 \in R_q^k$を一様ランダムにサンプルする関数である。これもExpandAと同じくSHAKEから棄却サンプルするだけだが、多項式係数は$[-\eta,\eta] (\eta \in {2,4})$の小さな範囲からサンプルする。一様乱数なのでML-KEMのCBDよりはシンプル？1バイトから2係数ずつ棄却サンプリングする。

NTT and NTT$^{-1}$

数論変換だが、ML-KEMのところで説明したので省略する。ML-KEMのNTTはいわゆるincomplete NTTと呼ばれるちょっと特殊なやつだったがML-DSAはcomplete NTTなのでより理解しやすいかと思う。

Power2Round

23ビットの$Z_q$を上位１０ビットと下位23ビットに分ける関数である。下位桁の値を$[-4095,4096]$のレンジにするため、単純にビット分解するだけではない。

pkEncode

バイト列$\rho$と、多項式列$t_1$をバイト列pkにエンコードする。$t_1$をバイト列に直すためにSimpleBitPack関数を使う。単に係数を詰められるだけバイト列に詰め込んだだけである。
図にすると複雑っぽいが、実は$z$の係数の並びを次数の大きいほうからにすると、あとはリトルエンディアンでバイト列に変換するだけである。

skEncode

pkEncodeとほぼ同じ。SimpleBitPackではなくBitPack（負の値も許す）関数を使う。BitPackは$[-a,b]$範囲の値をバイト列にする関数。負の値を正にしてからパックするため、$b$から値を引く。例えば$\eta=2$の場合BitPackの範囲は$[-\eta,\eta]=\{-2,-1,0,1,2\}$となる。これを$b$から引いて$\{4,3,2,1,0\}$がパックする値になる。5個値があるので1係数は3ビットにパックされる。pkEncodeと同じく255次の係数から並べた整数にしてリトルエンディアンバイト列にすると楽。
$t_0$のパックは複雑っぽいけど、これも係数の範囲を正に戻してビット数（13ビット）分ずつバイト列に詰め込むだけである。13bit$\times$256係数で$t_0$は416バイトになる。

署名生成

ctxは通常empty-stringだが、アプリケーションによっては使う。署名生成はheadged (randomized) veriantとdeterministic variantが存在し、deterministicの場合は5行目の乱数生成が32バイトの0で固定される。hedged variantはサイドチャネル攻撃を緩和するため、SCAを考慮する環境ではdeterministic variantは使うべきではないとしている。
internal関数内のハッシュを先にやっておくHashML-DSA variantもある。

簡略版と異なるのは、コミット$w$の上位ビット$w_1$のみを使うようになっている点である。また$w_1$の情報だけだと正確な署名検証ができないため、$w$に小さな値を足した時に繰り上がるかどうか？を示すヒントビット$h$が署名に追加される。
さらに$z=y+cs_1$は$s_1$のバイアスがある（単純にいうと定数0中心乱数$y$と$c$の平均が0になるので$z/c$の平均値が$s_1$になる）ので、これを消すために$z$のノルム判定ロジックが追加されている。

skDecode

skEncodeの逆をやる。ただし入力となる$sk$が不正な値である可能性があることに注意。
Encode時のBitPackなどである範囲の値をエンコードしたが、改ざんがあった場合デコード結果はこの範囲を外れる可能性がある。これに対しては、「信頼できるソースからの入力に対してのみ実行されるべきである」とのこと。特に対策が入っているわけではない。

ExpandMask

これも単に一様な多項式ベクトルを生成するだけだが、ExpandAやExpandSと係数のレンジが異なり、$[-\gamma_1,\gamma_1]$からサンプルする。$\gamma_1 \in \{2^{17}, 2^{19}\}$なので$Z_q$全体に一様分布するわけではない。また２ベキに設定されているので棄却サンプルが不要である。

SampleInBall

$\{-1,0,1\}$係数の多項式で、非ゼロ要素が$\tau$個になるようなチャレンジ$c$をサンプリングする。アルゴリズムはFisher-Yatesシャッフルに基づく。Fisher-Yatesはランダム置換を得るためのアルゴリズムであり、SampleInBallではまずすべての係数が0の多項式$c$を作り、次数が高いほうの係数$\tau$個に1または-1を格納する。このときの符号は64ビットの乱数$h$（$h$は$\tau$ビットで足りるはずだが$\tau$の上限値64になっている）から決定する。この$\tau$個の非ゼロ係数をFisher-Yatesでランダム置換するイメージである。
なお$c$のドメイン$B_\tau$の大きさ$|B_\tau|=_{256}C_\tau \cdot 2^\tau$は十分なエントロピーとなるように$\tau$は設定されている（192,225,257）。

HighBits, LowBits, and Decompose

DecomposeはPower2Roundのように値を二つに分割する関数であり、HighBits/LowBitsはその上位/下位桁のみを出力するものである。処理的にはPower2Roundとほとんど同じであるが、$r^+-r_0=q-1$のケースで特殊な分岐を入れているのが大きな違いである。

Power2Roundは$r=r_1 \cdot 2^{13} + r_0$になるように$r$を分解するが、このとき下図のように$r_1=1023$になる範囲が狭くなることが問題になる。ML-DSAは$r_1$部分だけを保持して、下位ビットの誤差は1ビットのヒントで補正するという構造になっている。下図のように$r_1 \ne 0 or 1023$の場合は隣の値との距離が離れているため、小さなノイズ$\le 8192$が加わった場合でも1ビットのヒントで補正できる。しかしながら$r_1 = 0 or 1023$は隣の値との距離が近いため小さなノイズ$\le 8192$の補正に2ビット必要になってしまう。
これを避けるためにやや力技であるが、Decomposeでは$r_1=1023$のケースを排除し、$r_1=0$のケースを拡大することで小さなノイズ$\le 8192$の補正を１ビットでやってのけるのである。

実際のDecomposeは異なるパラメータで動くことに注意（mod $2^{13}$ではない）

MakeHint and UseHint

前述したようにML-DSAはDecomposeにより分解した値の上位ビットのみを使って計算を行う。当然この時下位ビットの情報がなければ正確な計算ができないわけだが、下位ビットによる影響を１ビットのヒントに押し込めることでcorrectnessを達成している。
MakeHintはある値$r$の上位ビットと、それに小さな値$z$を足した時の上位ビットに差があるかどうかを１ビットのヒントとして記録するものである。このとき$z$の範囲が制限できれば、decomposeの図で説明したように上位ビットへの影響を高々$\pm 1$にできる。したがってヒントは実質的に上位ビットへの繰り上がり（キャリー）である。

UseHintは、このヒントを使ってHighBitsを補正する関数である。

Validity check

Fiat-Shamir with AbortのAbort部分のチェックであり、レスポンス$z$が所定のレンジにないときに処理をabortし、署名生成を乱数生成からやり直す。
23行目で$z$と$r_0$の二つをチェックしているが前者はsecurityのために必要であり後者はsecurityおよびcorrectnessのために必要である。

まず$z$のノルムが$\gamma_1-\beta$以上かどうかをチェックしているが、これは$z$によって$s_1$の範囲が絞り込まれないようにしている。ここで$\gamma_1$は$y$の係数の最大値であり$\beta$は$cs_1$の係数の最大値である。極端な話だともし$z$に$\gamma_1+\beta$となる係数があったとすれば$cs_1=\beta$が確定するため$s_1$が特定可能である。

$r_0$のチェックはcorrectnessの意味合いが強いがこれは後述する。
securityの観点に関しては、攻撃者が$w'=Az-ct=Ay-cs_2$を計算できることを前提にしていると思われる。かつもし攻撃者が$w$を計算できたとすると$w-w'=cs_2$であるから秘密情報が漏れそうなのはなんとなくわかる。実際$w$は秘密であるが、その上位ビット$w_1$は検証で明らかになるため$w$の範囲が絞られることになり従って$cs_2$についての不等式が得られる形になる。

FIPS 204では$t_0$は秘密鍵の一部とされたため攻撃者は入手できないが、ML-DSAのsecurity proofでは$t$自体がpublicとして扱われているようである。
CRYPTO2025において大量の署名を集めると$t_0$が復元できることも示されているようである。

署名検証

簡略版では$w'=Az-ct$を計算し、$c'=H(m;w')$が$c$と等しければ（つまり$w'=w$なら）検証成功としていたが、$Az-ct=A(y+cs_1)-c(As_1+s_2)=Ay+cs_2$であるため$w' \ne w$だった。
$cs_2$は小さな多項式ベクトルであるため$w \approx w'$は成り立っており、気持ち的には上位ビットだけで比較すればよいということで$w_1=$Highbits($w$)をチャレンジ生成に使っている。合わせて公開鍵も上位の$t_1$だけ使うことで鍵長を圧縮している。

$w'_{Approx}$

は署名生成時の$w=Ay$の近似である。

$$w'_{Approx}=Az-ct_1\cdot 2^d = A(y+cs_1) -c(t-t_0)= Ay+Acs_1 -c(As_1+s_2 - t_0) = Ay - cs_2 +ct_0$$

なので、$w$から$-cs_2 +ct_0$分の差があるわけだが、$-cs_2 +ct_0$が十分小さいので大体あっているということでApproxになっている。とはいえ署名検証を通過するには近似値ではだめで、署名生成と検証時でチャレンジおよびコミットを一致させる必要がある。そこでML-DSAでは$w$の上位ビット$w_1=HighBits(w)$をチャレンジ生成のためのコミットとして用いている。
検証側では$w_{Approx}'$の上位ビットを使うわけだが、$HighBits(w_{Approx})'$と$HighBits(w)$のずれが高々$\pm1$におさまるように$-cs_2 +ct_0$の範囲を決定している。このずれを補正するのに使うのがヒント$h$であり、

Under construction