CRYSTALS-Kyber.

CRYSTALS-Kyber は、構造化格子上の Module Learning With Errors(MLWE)問題に安全性を帰着できる鍵カプセル化メカニズム(KEM)です。NIST は 2022 年に PQC の主力 KEM として選定し、2024 年 8 月に FIPS 203(ML-KEM)として正式に標準化しました。標準では NIST セキュリティカテゴリ 1・3・5 を狙った ML-KEM-512、ML-KEM-768、ML-KEM-1024 の 3 種類のパラメータセットが定義されており、公開鍵はそれぞれ約 800・1184・1568 バイトで、暗号文も同程度の大きさです。

内部的には、IND-CPA の公開鍵方式を Fujisaki–Okamoto 変換によって IND-CCA2 の KEM へと強化しています。すなわち、デカプセル化は復元したメッセージを再暗号化して不一致があれば拒否するため、改ざんされた暗号文は秘密情報を漏らす代わりに擬似ランダムな「暗黙の拒否(implicit reject)」鍵を返します。今のトラフィックを保存しておき将来の量子計算機で解読する「store-now-decrypt-later」型の攻撃者が存在しうるため、Kyber は ハイブリッド モード(例えば X25519MLKEM768)で展開されます。この場合、攻撃者は古典側とポスト量子側の両方を破らなければなりません。

実装のセキュリティは数学そのものと同じくらい重要です。KyberSlash の開示(2024 年)は、法 q = 3329 による秘密情報依存の整数除算が多くの CPU で可変時間になることを示しました。偽造した暗号文のデカプセル化にかかる時間を計測することで鍵ビットを復元できたのです。KyberSlash1 と KyberSlash2 は、除算を乗算に置き換えることでリファレンスコードにおいて修正され(2023 年 12 月)、その修正は liboqs、PQClean、CIRCL、AWS-LC、Botan へと波及しました。

flowchart LR
  KG[鍵生成] --> PK[公開鍵 pk]
  KG --> SK[秘密鍵 sk]
  PK --> ENC[カプセル化: m を選び K と暗号文 c を導出]
  ENC --> C[暗号文 c]
  ENC --> KS1[共有秘密 K]
  C --> DEC[sk でデカプセル化し FO 再暗号化検証を実施]
  SK --> DEC
  DEC -->|一致| KS2[同一の共有秘密 K]
  DEC -->|不一致| REJ[暗黙の拒否: 擬似ランダム鍵]