CRYSTALS-Kyber：格子ベースのKEM

CRYSTALS-Kyber（NISTがFIPS 203でML-KEMに改称）は、Module-LWEに基づく鍵カプセル化メカニズム（KEM）です。鍵交換におけるRSAとECDHを置き換え、実用的な性能を維持しながら量子コンピューターに対する耐性を提供します。

KEMは共有秘密をカプセル化します。送信者がランダムな鍵Kを生成し、受信者の公開鍵で暗号化（カプセル化）して、暗号文Cを生成します。受信者は秘密鍵でCをデカプセル化し、Kを復元します。対話的な鍵交換は必要ありません。

Kyberは、環 R_q = Z_q[x]/(x^256+1) 上で、q=3329のModule-LWEを使用します。次元kは、Kyber-512ではk=2、Kyber-768ではk=3、Kyber-1024ではk=4です。安全性レベルはそれぞれ約128ビット、約192ビット、約256ビットです。推奨されるデフォルトはk=3（Kyber-768）です。

シードρから、展開可能な行列A ∈ R_q^{k×k}を生成します。秘密値sとノイズeは、中心二項分布（係数が小さい分布）からサンプリングします。公開鍵は(ρ, t=As+e)、秘密鍵はsです。ノイズeは小さい値ですが、公開鍵からsを復元できないようにします。

公開鍵(ρ, t)の所有者に共有秘密を送信するには、ノイズ分布からr、e1、e2をサンプリングします。u = A^T r + e1、v = t^T r + e2 + round(q/2)*mを計算します。ここでmはランダムな256ビットメッセージです。共有秘密K = KDF(m)とし、暗号文は(u, v)です。

秘密鍵sを使い、m' = decompress(v - s^T u) = decompress(t^T r + e2 + round(q/2)*m - s^T(A^T r + e1))を計算します。ノイズ項はほぼ相殺されるため、m'≈mとなります。K = KDF(m')を計算します。デカプセル化の失敗確率は< 2^{-139}です。

Kyber-768では、公開鍵が1184バイト、秘密鍵が2400バイト、暗号文が1088バイト、共有秘密が32バイトです。ECDH-P256では、公開鍵が65バイト、暗号文が32バイトであることと比較してください。Kyberは約15倍大きくなりますが、量子コンピューターに対して安全です。それでも高速で、最新のCPUではカプセル化とデカプセル化を合わせて1ミリ秒未満です。

R_q = Z_q[x]/(x^256+1) における多項式乗算では、FFTのモジュラー算術版である数論変換（NTT）を使用します。NTTにより、多項式乗算の計算量はO(n^2)からO(n log n)に削減されます。q=3329は、n=256に対してNTTに適した性質を持つように選ばれています。

PQCへの移行中は、ハイブリッド鍵交換としてECDHとKyberを組み合わせます。共有秘密 = KDF(ECDH_output || Kyber_output)です。安全性を確保するには両方を破る必要があります。古典的な攻撃者はどちらも破れず、量子的な攻撃者はECDHを破れますがKyberは破れません。TLS 1.3のドラフト（IETF RFC 8446）はハイブリッドKEMをサポートしています。

単純な実装では、Kyberのデカプセル化はconstant-timeではありません。拒否サンプリングの手順から実行時間が漏えいするためです。リファレンス実装では、constant-timeのNTTと、圧縮された暗号文の比較を使用しています。NIST提出時のリファレンスコード、または監査済みのライブラリ実装を使用してください。

NISTは2024年8月にFIPS 203（ML-KEM）を公開しました。Chromeは2023年にTLS 1.3でKyberのサポートを追加しました。Cloudflare、Google、AWSはハイブリッドECDH+Kyberを導入しています。OpenSSL 3.xはML-KEMのサポートを追加しました。LibSSHとWireGuardの実装は進行中です。

CRYSTALS-Kyberを標準化しているNISTの標準文書は何ですか？

Kyber（ML-KEM）はModule-LWEベースのKEMで、ECDHを置き換えます。鍵サイズは約1 KBで、高速なNTT演算を使用し、量子コンピューターに対する耐性を備えています。移行中はECDHとのハイブリッドとして導入します。FIPS 203として標準化されています。次はCRYSTALS-DilithiumとFalconの署名方式です。