格子暗号方式における安全性証明と帰着

暗号方式のセキュリティ証明とは、その方式を破ることが基礎となる困難問題を解くことを意味することを示す、形式的な数学的論証です。この証明は絶対的な安全性を保証するものではなく、その方式に対する任意の効率的な攻撃者を、困難問題を解く効率的なアルゴリズムに変換できることを示します。困難問題が計算困難であれば、その方式は安全です。

Regevによる画期的な2005年の証明は、決定的LWEを多項式時間で解くアルゴリズムを使って、n次元格子上の最悪時GapSVP（Gap Shortest Vector Problem）を解けることを示しています。この帰着は量子的です。つまり、量子サンプリング手順を使って、LWEソルバーを格子ソルバーに変換します。これは、量子計算のもとでは、LWEが最悪時の格子問題と同等以上に困難であることを意味します。

Regevの帰着はタイトではありません。帰着に含まれる多項式因子により、証明が保証するセキュリティレベルは、既知の最良の攻撃が示唆するものよりやや弱くなります。実用的なパラメータを選択する際、暗号研究者は理論上の帰着境界ではなく、既知の最良の攻撃による具体的セキュリティ（lattice estimatorを使用）を利用します。これは、帰着が保守的だからです。

LWEベースの暗号方式は、ハイブリッド論法によってIND-CPA（選択平文攻撃に対する識別不能性）が証明されます。この証明は、IND-CPA識別器からLWE識別器を構成できることを示します。最初のハイブリッドでは、実際の暗号文を一様ランダムな文字列に置き換えます。この識別不能性はLWE仮定から導かれます。これにより、基本的な格子暗号について明快なセキュリティ証明が得られます。

IND-CPAセキュリティは、TLSで使用される鍵カプセル化メカニズムには十分ではありません。これらにはIND-CCA2（選択暗号文攻撃）セキュリティが必要です。Fujisaki-Okamoto（FO）変換は、ランダムオラクルモデル（ROM）において、任意のIND-CPA方式をIND-CCA2 KEMに変換します。ML-KEMは、基礎となるModule-LWE暗号化にFO変換の変種を適用し、実環境での展開に必要なCCA2セキュリティを実現します。

ランダムオラクルモデル（ROM）では、ハッシュ関数を完全にランダムな関数としてモデル化します。FO変換の証明を含む多くのセキュリティ証明では、ROMが必要です。実際には、SHA-3のようなハッシュ関数は真のランダムオラクルではないため、ROMでの証明は標準モデルにおける安全性を保証しません。しかし、ROMでの証明は、暗号研究コミュニティでは安全性を示す強力な証拠として広く受け入れられています。

標準モデルでの証明はハッシュ関数について理想化を行わず、ROMでの証明より厳密に強力です。実用的な格子方式の多くがROMでの証明を使用するのは、格子ベースのKEMについて標準モデルでCCA2を証明する方がはるかに複雑で、具体的なパラメータも不利になるためです。NISTはML-KEMについてROMベースの証明を受け入れ、目標とするセキュリティレベルには十分だと判断しました。

ML-KEMのセキュリティ証明は2段階で進みます。まず、基礎となるModule-LWE暗号化が、M-LWE仮定のもとでIND-CPAセキュアであることを示します。次に、Fujisaki-Okamoto変換（具体的にはKyberで使用されるT変換とU変換）によって、これを量子ROM（QROM）におけるIND-CCA2へと強化します。QROMは、ランダムオラクルに重ね合わせ状態でクエリを送る攻撃者を扱います。

Albrecht、Player、Scottによるlattice estimatorは、LWEベースの方式の具体的セキュリティを計算するための標準的なツールです。これは、既知の最良の格子攻撃（篩法または列挙法を用いるBKZ）のコストをモデル化し、指定されたパラメータ（n, q, sigma）に対する推定ビットセキュリティを出力します。新しいアルゴリズムやハードウェアのコストモデルが発表されるたびに、このツールは定期的に更新されています。

Block Korkine-Zolotarev（BKZ）アルゴリズムは、最も実用的な格子簡約アルゴリズムです。ブロックサイズ beta のBKZは、最良の篩法アルゴリズムを使うと、およそ 2^{0.292*beta} ゲート操作の計算量で短いベクトルを見つけます。ML-KEM-768では、古典セキュリティは約180ビット、量子セキュリティは約164ビットと推定され、192ビットの目標を十分に上回っています。

漸近的なセキュリティ証明は、十分に大きなパラメータに対して方式が安全であることを示しますが、実際に「十分に大きい」とはどの程度かを示しません。具体的セキュリティ分析は、選択したパラメータに対する最良の攻撃の実際のコストを推定することで、この差を埋めます。ポスト量子暗号の標準化では具体的セキュリティ分析が大きく重視されており、今後30年間に想定される量子ハードウェアによる攻撃に耐えられるよう、パラメータが選択されています。

ML-KEMで、IND-CPA格子暗号をIND-CCA2セキュリティに強化するために使用される変換はどれですか？

格子方式のセキュリティ証明では、方式の安全性をLWEまたはSVPの困難性に帰着させます。Regevの帰着によって、LWEが最悪時の格子問題と同等以上に困難であることが保証されます。Fujisaki-Okamoto変換は、ROMにおいてIND-CPAをIND-CCA2へと強化します。具体的セキュリティは、BKZの計算量モデルを用いるlattice estimatorで評価されます。帰着のタイトネスに関するギャップがあるため、実用的なパラメータは帰着境界だけでなく、攻撃コストの推定に基づいて選択されます。