ML-KEM（FIPS 203）：標準化されたCRYSTALS-Kyber

ML-KEM（Module-Lattice-based Key Encapsulation Mechanism）は、2024年8月にFIPS 203として標準化された、Diffie-HellmanおよびRSA鍵交換に代わる耐量子暗号方式です。公開鍵を使って対称鍵をカプセル化し、双方が対称暗号に利用できる共有シークレットを生成します。ML-KEMはCRYSTALS-Kyberを基にしており、仕様をより明確にするための小さな変更が加えられています。

ML-KEMには3つのパラメータセットがあります。ML-KEM-512は、従来の暗号に対して約128ビット、耐量子暗号に対して100ビットの安全性を目標とし、公開鍵は800バイト、暗号文は768バイトです。ML-KEM-768は192ビットの従来型セキュリティを目標とし、公開鍵は1184バイト、暗号文は1088バイトです。ML-KEM-1024は256ビットの従来型セキュリティを目標とし、公開鍵と暗号文はそれぞれ1568バイトです。NISTは、ほとんどの用途でML-KEM-768を推奨しています。

ML-KEMの鍵生成は次のように行います。SHAKE-128を使い、シードからランダムな行列Aを生成します。次に、小さな秘密ベクトルsと誤差ベクトルeを生成し、t = As + e mod qを計算します。公開鍵は（シード、t）、秘密鍵は公開鍵のハッシュとsです。Aそのものを保存する代わりにシードを使うことで、メモリと帯域幅を大幅に節約できます。

カプセル化では、送信者がランダムなメッセージmを生成し、SHA-3によって対称鍵Kと乱数rの両方を導出します。暗号文は2つの部分で構成されます。u = Ar + e1 mod qおよびv = t^T r + e2 + encode(m) mod qです。共有シークレットKはmのハッシュから導出されます。乱数はmから決定論的に導出されるため、暗号文と鍵が結び付けられます。

デカプセル化では、v - s^T uを計算してデコードすることでmを復元し、mからKを再導出します。Fujisaki-Okamoto変換では、重要な手順として、復元したmを使って再暗号化し、暗号文が一致するかを確認します。一致しない場合は、秘密鍵と暗号文のハッシュから導出した疑似乱数値を返します。これにより、デカプセル化が決定論的かつ検証可能になり、選択暗号文攻撃を防ぎます。

ML-KEMは、量子ランダムオラクルモデル（QROM）において、Module-LWE仮定の下で証明されたIND-CCA2安全性を実現します。耐量子攻撃者はハッシュ関数に重ね合わせ状態でクエリできるため、QROMは重要です。Hofheinz、Hovelmanns、Kiltzによる安全性証明（HHKフレームワーク）では、QROMにおけるModule-LWEからML-KEMの安全性へのタイトな帰着が示されています。

同等の安全性レベルで比較すると、鍵交換においてML-KEMはRSAを大幅に上回る性能を発揮します。最新のCPUでは、ML-KEM-768の鍵生成は約16マイクロ秒、カプセル化は20マイクロ秒、デカプセル化は18マイクロ秒で完了します。一方、RSA-2048の鍵生成には数秒かかります。ML-KEMの公開鍵（1184バイト）はECDH（32～64バイト）より大きいものの、RSA-2048（鍵だけで256バイト、実際にはさらに長くなります）よりははるかに小さいサイズです。

移行期間中は、ハイブリッド鍵交換によってML-KEMと従来型アルゴリズム（通常はX25519またはP-256 ECDH）を組み合わせます。共有シークレットは、両方のKEM出力を連結した値のハッシュです。K = Hash(K_classical || K_pqc)。これにより、安全性がどちらの構成要素よりも低くなることを防ぎます。ハイブリッドTLSはIETFのdraft-ietf-tls-hybrid-designで仕様化されており、BoringSSL、OpenSSL 3.x、Rustlsでサポートされています。

IETFは、TLS 1.3向けのハイブリッド鍵共有としてX25519ML-KEM-768を定義しています（draft-ietf-tls-hybrid-design）。Chromeはバージョン124（2024年4月）で、Firefoxはバージョン132（2024年）でサポートを追加しました。CloudflareはTLS終端インフラにML-KEMを導入しました。この急速な普及により、現在では1日あたり数億件のTLS接続に耐量子鍵交換が含まれています。

LWEの誤差項により、攻撃者が存在しない場合でもデカプセル化に失敗する確率がごくわずかにあります。ML-KEM-512では失敗確率は約2^{-139}、ML-KEM-768では2^{-164}です。これらの確率は実用上まったく問題にならないほど低く（比較すると、ハードウェアエラーのほうがはるかに頻繁に発生します）、安全性には影響しませんが、仕様では考慮する必要があります。

ML-KEMは、多数のオープンソースライブラリに実装されています。Kyberチームによるリファレンス実装はパブリックドメインで公開されています。PQCleanは、整理された移植性の高いC実装を提供しています。liboqs（Open Quantum Safeプロジェクト）は、ライブラリラッパーにML-KEMを統合しています。AWS-LC（BoringSSLのAmazonによるフォーク）には、AWSのTLSエンドポイント向けにML-KEMが含まれています。NISTのFIPS 203標準には、すべての操作について詳細な擬似コードが記載されています。

NISTがほとんどの用途で推奨しているML-KEMのパラメータセットはどれですか。

ML-KEM（FIPS 203）は、Module-LWEを基盤とするNIST標準の耐量子KEMです。3つのパラメータセット（512、768、1024）により、従来型暗号に対して128、192、256ビットの安全性を提供します。鍵生成では、ランダムなシードからコンパクトな公開鍵を生成し、カプセル化では共有シークレットを導出し、デカプセル化ではCCA2安全性のためにFO変換を使用します。ML-KEMはRSAより大幅に高速で、すでにChrome、Firefox、CloudflareのTLSに導入されています。