ML-KEMおよびML-DSA標準の理解

ML-KEMおよびML-DSA標準の理解

1. 格子暗号の台頭

現在、実務的な標準化を主導しているのは格子ベース(Lattice-based)のシステムである。これには、最悪の事例(worst-case)から平均的な事例(average-case)への強力な数学的換算(reductions)が存在し、効率的な実装が可能であるためである [S4]。一方で、コードベース(Code-based)やハッシュベース(Hash-based)方式は保守的な錨(conservative anchors)の役割を果たし、より長いセキュリティ履歴や最小限の仮定のみを要求する特性を持つ [S4]。

2. ML-KEM (Module-Lattice Key Encapsulation Mechanism)

ML-KEMは、以前Kyberとして知られていたアルゴリズムに基づいている。モジュール格子問題(Module Learning With Errors, MLWE)に基づいており、次のような流れを持つ。

• KeyGen: モジュール格子内で公開鍵と秘密鍵を生成。
• Encapsulation: 公開鍵を使用して共有秘密値(Shared Secret)とカプセル化された鍵(Ciphertext)を生成。
• Decapsulation: 秘密鍵を使用してカプセル化された鍵から元の共有秘密値を復旧。

3. ML-DSA (Module-Lattice Digital Signature Algorithm)

ML-DSAはDilithiumに基づいており、「Fiat-Shamir with Aborts」技法を使用する。格子問題の困難さによって偽造耐性を提供し、署名サイズと公開鍵サイズのバランスを取った実用的な標準である。

4. セキュリティの仮定

格子ベースシステムの安全性は、最短ベクトル問題(Shortest Vector Problem, SVP)と密接に関連している。量子コンピュータの「ショアのアルゴリズム(Shor’s Algorithm)」が既存のRSAやECCを効率的に破るのに対し、格子問題は量子アルゴリズムでも多項式時間内には解けないと仮定されている。