CRYSTALS-DilithiumとFalconの署名

RSAとECDSAの署名は、Shorのアルゴリズムによって破られます。そのため、耐量子署名でTLS証明書、コード署名、メール署名（S/MIME、PGP）、ソフトウェア更新の認証を置き換える必要があります。NISTは2つの格子ベース方式、ML-DSAとFN-DSAを標準化しました。

Dilithiumは、Module-LWEとModule-SIS（Short Integer Solution）の困難性に基づいています。QROM（Quantum Random Oracle Model）における安全性証明があります。バリアントはDilithium2（約128ビット）、Dilithium3（約192ビット）、Dilithium5（約256ビット）の3つです。署名処理は単純で、拒否サンプリングを必要としません。

秘密鍵は秘密行列s1、s2です。公開鍵はt = As1 + s2です。署名では、ランダムなyをサンプリングし、w = Ayを計算します。次に、w1 = HighBits(w)として、チャレンジc = H(mu || w1)を計算し、z = y + cs1を計算します。||z||または||r0||が大きすぎる場合は拒否して再試行します。出力は(z, c, hint)です。

(z, c, hint)を検証するには、||z||が小さいことを確認し、w' = Az - ctを計算します。hintを使ってw1を復元し、c == H(mu || w1)を検証します。hintはMakeHint()によって生成される少数ビットです。拒否処理によりzからs1が漏えいしないことが保証されます。これは「aborts-then-uniform」引数と呼ばれる安全性の議論です。

ML-DSA-65（Dilithium3、192ビット安全性）では、公開鍵が1952バイト、秘密鍵が4000バイト、署名が3293バイトです。ECDSA-P256では、公開鍵が64バイト、署名が64バイトです。Dilithiumの署名は約40～50倍大きくなりますが、量子コンピューターに対して安全です。

FalconはNTRU格子に基づき、NTRU格子上でガウスサンプラーを使用します。署名はDilithiumより大幅に小さくなりますが、署名生成には浮動小数点のガウスサンプラーが必要です。そのため、constant-timeでの実装が難しく、安全なコードを書くにはより複雑になります。

Falcon-512（128ビット安全性）では、公開鍵が897バイト、署名が666バイトで、Dilithiumより大幅に小さくなります。トレードオフとして、Falconは安全な実装がより困難です（ガウスサンプリングはタイミング攻撃の影響を受けやすいためです）。帯域幅が限られた環境に適していますが、慎重な実装が必要です。

SPHINCS+はハッシュベースの署名方式で、構造的な代数仮定を置かない保守的な選択肢です。安全性はハッシュ関数の安全性だけに依存します。署名サイズは約8～50 KBと大きく、署名生成も低速です。長期的な信頼性が重要で、性能が二次的な場面で使用されます。

ML-DSA（Dilithium）は汎用的で実装が単純なため、TLS証明書やコード署名に適しています。FN-DSA（Falcon）は、IoTやLPWANなど帯域幅が制約された環境に適しています。SLH-DSA（SPHINCS+）は非常に保守的な選択肢で、長期間使用するルート（CAのオフライン鍵やソフトウェアの信頼の基点）に適しています。

Dilithiumでは、拒否サンプリングによって分岐の実行時間が漏えいする可能性があるため、constant-timeの比較を使用してください。Falconでは、ガウスサンプラーが浮動小数点を使用するため、浮動小数点演算の決定性を確保してください。どちらも多項式演算におけるサイドチャネルを避ける必要があります。NIST提出パッケージのリファレンス実装を使用してください。

NIST FIPS 204はML-DSA（Dilithium）、NIST FIPS 205はSLH-DSA（SPHINCS+）、NIST FIPS 206はFN-DSA（Falcon）を規定しています。すべて2024年8月に公開されました。OpenSSL 3.x、BoringSSL、liboqs（Open Quantum Safeプロジェクト）などのライブラリが3方式すべてを実装しています。

FalconがDilithiumより優れている主な点は何ですか？

ML-DSA（Dilithium）は格子ベースで実装が単純、署名サイズは約3 KBです。FN-DSA（Falcon）はNTRUベースで署名サイズは約700バイトですが、実装が複雑です。SLH-DSA（SPHINCS+）はハッシュベースで保守的ですが、サイズが大きくなります。すべてFIPS 204/205/206で標準化されています。次は、ハイブリッド方式によるPQCへの移行です。