ML-DSA（FIPS 204）とSLH-DSA（FIPS 205）

ML-DSA（Module-Lattice-based Digital Signature Algorithm）はFIPS 204として標準化され、CRYSTALS-Dilithiumを基にしています。DilithiumはDucas、Kiltz、Lepoint、Lyubashevsky、Schwabe、Seiler、Stehleによって設計され、2017年にNISTへ提出されました。Module-LWEにFiat-Shamir with abortsフレームワークを適用し、強固な安全性証明を持つ実用的な署名方式を実現しています。

古典的なFiat-Shamir変換は、対話型識別プロトコルを署名に変換します。格子ベース方式にそのまま適用すると、応答ベクトルを通じて秘密鍵の情報が漏えいします。Lyubashevskyによる「with aborts」技法では、リジェクションサンプリングを追加します。署名者は、応答によって情報が漏れる可能性があるかを確認し、その可能性がある場合は中止して再試行します。これにより署名処理にはわずかなオーバーヘッドが加わりますが、安全性のために不可欠です。

署名では、ML-DSAは一様分布からマスキングベクトルyを生成し、コミットメントw = Ayを計算して、（メッセージ、w）をハッシュし、チャレンジ多項式cを得ます。その後、応答z = y + csを計算します。リジェクションサンプリングにより、zからsの情報が漏れるかどうかを確認します。確認に合格した場合、署名は効率的な検証のためのヒントと、（c、z）の組になります。不合格の場合は処理を繰り返します。

ML-DSAには3つのパラメータセットがあります。ML-DSA-44はNIST安全性レベル2（約128ビット）、ML-DSA-65はレベル3（約192ビット）、ML-DSA-87はレベル5（約256ビット）です。数字は方式におけるモジュールランクを示します。公開鍵のサイズはそれぞれ1312、1952、2592バイトです。ML-DSA-65の署名サイズは3293バイトで、128ビットの安全性を持つEd25519の64バイトと比べて大きくなっています。

ECDSAやEdDSAと比較したML-DSAの最大の欠点は、署名サイズです。ML-DSA-65の署名は3293バイトであるのに対し、Ed25519は64バイトです。TLS証明書チェーンやコード署名など、多数の署名を送信するプロトコルでは、帯域幅が増加します。ただし、ML-DSAの署名と検証は非常に高速で、ECDSAと同等かそれ以上の速度であるため、トレードオフは主に通信コストにあります。

SLH-DSA（Stateless Hash-Based Digital Signature Algorithm）はFIPS 205として標準化され、SPHINCS+を基にしています。格子ベース方式とは異なり、SLH-DSAの安全性は基盤となるハッシュ関数（SHA-256またはSHAKE-256）の衝突耐性と第二原像耐性だけに依存します。そのためSLH-DSAは非常に保守的な方式であり、格子仮定が破られた場合でも安全性を維持できます。

SLH-DSAはWOTS+（Winternitz One-Time Signature）を基盤としています。これは、秘密鍵をランダムな文字列の集合とし、それぞれを繰り返しハッシュして公開鍵を生成するハッシュベース方式です。署名では、メッセージのビットに基づいて部分的にハッシュします。WOTS+は、鍵ペアごとに安全に1回しか使用できません。2回使用すると情報が漏えいします。SLH-DSAは、ツリー構造を使ってWOTS+の上に複数回の署名機能を構築しています。

SLH-DSAは、Merkleツリーを組み合わせたハイパーツリーを使用します。各リーフはWOTS+インスタンスの公開鍵です。ルートがSLH-DSAの公開鍵になります。署名は、メッセージに対するWOTS+署名と、リーフからルートまでの認証パスで構成されます。ハイパーツリー構造により、異なるWOTS+リーフを使用して、1つの鍵ペアから多数の署名を生成できます。

SLH-DSAには、ハッシュ関数（SHA-256またはSHAKE-256）、安全性レベル（128s/128f、192s/192f、256s/256f）、最適化（s = 小さい署名、f = 高速な署名処理）を組み合わせた12のパラメータセットがあります。128fバリアントの署名は7856バイトで、署名処理が高速です。128sも7856バイトですが、処理はより低速です。いずれもML-DSAよりはるかに大きい一方で、可能な限り強固な安全性仮定に基づいています。

性能と帯域幅が重要で、格子仮定を信頼できる場合はML-DSAが適しています。ハッシュ関数の安全性だけを信頼する非常に保守的な導入や、格子仮定が将来破られる可能性への備えにはSLH-DSAが適しています。署名頻度は低くても最大限の保証が必要な認証局や政府システムではSLH-DSAが好まれる可能性があります。一方、頻繁に署名するTLSサーバーにはML-DSAが適しています。

FN-DSA（FIPS 206、FALCONを基盤とする方式）は、NTRU格子とガウスサンプリングを使用し、ML-DSAより小さい署名を実現します。128ビットの安全性を持つFALCON-512の署名サイズは897バイトです。ただし、FALCONでは、ガウスサンプラーからのサイドチャネル攻撃を防ぐために、慎重な一定時間実装が必要です。FIPS 206はFIPS 203～205の後に標準化される予定で、リソースに制約のある環境向けに高性能な選択肢を提供します。

SLH-DSAがML-DSAに対して持つ主な安全性上の利点は何ですか。

ML-DSA（FIPS 204）は、Module-LWE上でFiat-Shamir with abortsを使用し、192ビットの安全性で3KBの署名と高速な署名処理を実現します。SLH-DSA（FIPS 205）は、ハッシュベースのMerkleツリー（WOTS+）を使用し、ハッシュ関数の安全性だけに依存しながら、7～50KBの署名を生成します。性能が重視される用途にはML-DSAが、最大限の保守性が求められる用途にはSLH-DSAが適しています。FN-DSA（FALCON、FIPS 206）により、より小さな署名を持つ格子ベースの選択肢が加わる予定です。