Dependency-Aware ROM/CBD Correctness Bounds for ML-KEM-768 at the Heuristic Failure Scale

デジタル界において、セキュリティはしばしば、一方の方向へは使いやすいが、正しい秘密情報なしには逆方向に進めることが極めて困難な数学的問題に依存しています。ML-KEMは、将来の量子コンピュータに対しても安全性を維持するように設計された、ポスト量子鍵確立メカニズムです。他の格子ベースの暗号システムと同様に、これには「誠実な復号失敗（honest decapsulation failure）」と呼ばれる極めて小さな確率が存在します。たとえ両当事者が正しく振る舞ったとしても、原理的には両者が異なる鍵を導き出してしまう可能性があるのです。これがどれほど稀に起こるかを推定することは、正当性に関する重要な問いです。これまでの分析は、失敗の規模に関するヒューリスティックな推定に大きく依存してきましたが、異なるエラー項間の関連する数学的依存関係を保持したまま、厳密な境界を得ることは実質的にさらに困難なことでした。

オーレリー・デュリエとクリストフ・トマシーニによる新しい研究は、明示的な理想化された乱数関数／中心二項分布、すなわちROM/CBD抽象化の枠組みの中で、ML-KEM-768の厳密な数学的分析を行うことで、この問題に取り組んでいます。この研究はシミュレーションではなく、また正確な失敗率を計算しようとするものでもありません。その代わりに、著者たちは、異なるエラー項間の重要な依存関係を保持しながら、誠実な復号失敗の確率に対する認定された上限を導き出しています。特に、この分析は、エラーを単に独立したものとして扱うのではなく、公開行列および両方の暗号文圧縮項によって引き起こされる依存関係を追跡しています。その結果得られた認定された上限は、2の164.81乗分の1よりも小さい値となります。

この発見は、検討された明示的なモデル内において、ヒューリスティックな失敗規模の推定を、依存関係を考慮した認定された上限に置き換えたという点で重要です。この分析は、関連するエラーが独立していると単に仮定するのではなく、それらの間に生じる数学的な依存関係を保持しています。認定された境界は、以前のヒューリスティックな推定と実質的に同じ規模に達していますが、これはそれらの推定値が正確な失敗確率であることを証明していると解釈されるべきではありません。結果は意図的に限定的なものです。論文で研究された明示的なROM/CBD抽象化の範囲内において、誠実な復号失敗の確率は、極めて小さな値によって厳密に上限が抑えられています。また、本論文は、これが正確な復号失敗率ではないこと、およびFIPS 203の固定されたSHAKE実装に関する情報理論的な言明ではないことも明確にしています。

この作業には、問題に対する異なるアプローチが求められました。簡略化されたヒューリスティックな分析は、いくつかのエラー項を独立したものとして扱えば非常に容易になりますが、実際の代数構造は、厳密な分析が保持しなければならない依存関係を生み出します。そのため、著者たちは、これらの依存関係を破棄するのではなく、計算全体を通じてそれらを追跡する方法を開発しました。研究プロセスでは、候補となるアプローチを探索し、重要なケースを特定し、分析を構造化するために、AIを活用した手法も使用されました。この探索的なAIの使用は、徹底的なコンピュータ検証、正確または認定された算術、および独立して検証可能な計算と組み合わされました。したがって、最終的な数学的主張は、AIの出力そのものではなく、明示的で再現可能な証拠に基づいています。

その結果は、指定された抽象化の範囲内における、厳格かつ透明な認定された正当性の境界です。研究者たちは、計算を独立してチェックできるように、すべてのコード、データ、および裏付けとなる成果物を公開しています。この再現性は、数学的な主張が独立した検証に開かれているべきである暗号技術において、特に重要です。研究は、検討された明示的なROM/CBD抽象化において、誠実な復号失敗の確率が極めて小さなレベルに抑えられていることを示しています。しかし、これはML-KEM-768の安全性全般に対する一般的な証明でも、標準化されたスキームのすべてのセキュリティ特性の証明でも、あるいはあらゆるハードウェアまたはソフトウェアの実装をカバーする言明としても解釈されるべきではありません。

この成果は、明確に定義された抽象化内において、ヒューリスティックな失敗規模の推定から依存関係を考慮した認定された上限へと移行することで、ML-KEM-768の正当性に関する特定の側面への厳密な理解を前進させます。これは、関連するエラー項間の重要な依存関係を保持しながら、ヒューリスティックな規模での境界を確立できることを示しています。164.81という数値は、この上限の認定された指数です。すなわち、指定されたROM/CBD抽象化内において、誠実な復号失敗の確率は2のマイナス164.81乗によって上限が抑えられています。この数値は、ML-KEM-768全体の安全性やセキュリティの一般的な尺度としてではなく、論文で証明された認定された境界の精密な特性として理解されるべきです。

研究者たちはまた、自分たちの研究の限界についても説明することに留意しました。彼らは、自分たちの証明がシステムの特定の抽象化に適用されるものであり、必ずしもソフトウェアのあらゆる可能な実装に適用されるものではないことを指摘しました。彼らは、暗号規格のすべてのバリエーションの問題を解決したと主張したわけでも、システムがあらゆる種類の攻撃に対して免疫を持っていると示唆したわけでもありません。彼らの焦点は、誠実な条件下での復号プロセスの正確性に厳密に絞られていました。何を証明し、何を証明しなかったかを明確にすることで、彼らは自分たちの発見が誤解されないようにしました。この研究は、小さなエラーが巨大な結果をもたらし得る分野において、注意深く詳細な分析がいかに強力であるかを示す証左となっています。それは、十分な厳密さと適切なツールがあれば、最も複雑な数学的システムであっても理解し、検証できることを示しています。

結局のところ、この論文は、精密ではあるが意図的に範囲を限定した結果を提示しています。すなわち、指定されたROM/CBD抽象化内において、誠実な復号失敗の確率は2のマイナス164.81乗によって厳密に上限が抑えられているということです。これは極めて小さな認定された上限ですが、正確な失敗率ではなく、展開された完全なML-KEM-768システムが、あらゆる現実世界の条件下で失敗なしに動作するという包括的な証明でもありません。その貢献は、明確に定義されたモデル内で、ヒューリスティックな失敗規模の推定を、依存関係を考慮した、再現可能で、かつ独立して検証可能な境界に置き換えたことにあります。その強みは、そのモデルを超えた確実性を主張することではなく、何が証明され、何が結果の範囲外であるかを明示的にすることにあります。