Compressed Permutation Oracles Revisited

デジタル世界において、セキュリティはしばしば、完璧で予測不可能なマシンの概念に依存しています。暗号学者は、あらゆる入力を受け取り、完全にランダムに見える出力を吐き出すが、一つの重要なルールを持つデバイスを想像します。それは、同じ入力を二度入れた場合、毎回同じ出力が得られるというものです。これはランダム置換として知られています。これは、パスワードの保存方法から通信の完全性を検証するアルゴリズムに至るまで、私たちのデータを安全に保つために使用されるツールの背後にある、目に見えないエンジンです。これらのツールが真に安全であるかをテストするために、科学者たちは、このマシンに質問ができる強力な攻撃者を想定します。古典的な世界では、攻撃者は一度に一つの質問をします。しかし、量子世界では、攻撃者は一度に多くの質問をすることができ、それらを重ね合わせることで、あたかもあらゆる可能な質問を同時にしているかのように実行できます。この重ね合わせ状態でクエリを投げる能力は、攻撃者が直感に反する方法で情報を得るため、セキュリティの証明を極めて困難なものにします。

長年、研究者たちは、量子攻撃者がこれらの質問から何を学ぶかを追跡するための数学的モデルを構築しようと試みてきました。圧縮オラクルと呼ばれる有望な手法の一つは、簡略化されたノートブックのように機能します。このノートブックは、巨大で複雑なマシン全体を追跡するのではなく、攻撃者がこれまでに尋ねた入力と出力の特定のペアのみを記録します。これにより数学的な扱いが可能になり、科学者は特定のセキュリティシステムが安全であることを証明できるようになります。しかし、この手法には重大な問題がありました。そのノートブックは完全に正確ではなかったのです。それは、攻撃者が比較的少ない数の質問を行う場合にのみ正しく機能することが証明されていました。もし攻撃者が多すぎる質問を行った場合、ノートブックの予測は現実から乖離してしまう可能性があり、セキュリティの証明を信頼できないものにしていました。この限界により、多くの現代的な暗号システムに対して、それらが決定的な量子アドバーサリ（敵対者）に対して耐えうるかどうかを確信することができませんでした。

研究チームは、この手法を再検討し、その最も致命的な欠陥を修正しました。彼らは、圧縮されたノートブックがこれまで考えられていたよりもはるかに信頼できるものであることを示しました。彼らの新しい分析は、この手法が、攻撃者が以前よりもはるかに多い数の質問、具体的には全入力数の平方根に達するまでの質問を行った場合でも、正しく機能することを証明しています。これは、以前の限界がその数のごくわずかな割合であったことに比べると、大幅な改善です。研究者たちは、実在する複雑なマシンと簡略化されたノートブックとの間の接続を構築する方法を変更することで、これを達成しました。複雑で間接的な構築の代わりに、彼らはノートブックを、マシンの基礎となる状態の直接的な測定として捉えられることを示しました。この新しい視点は、数学的なプロセスをよりクలーンで直接的なものにするだけでなく、攻撃者が質問できる数に対する人工的な天井を取り除きました。

この改善による影響は、即時的かつ具体的です。研究者たちは、この新しい、より厳密な証明を、現代の暗号学における二つの重要な構造、すなわちスポンジ構成とデイヴィス＝マイヤー圧縮関数に適用しました。これらは、SHA-3標準や、より古いSHA-1およびSHA-2システムを含む、私たちのデジタル世界を保護するハッシュ関数を構築するために使用される設計図です。洗練された手法を用いて、チームはこれらのシステムを打破するために攻撃者がどれだけの量子クエリを必要とするかを正確に計算しました。彼らは、衝突を見つけるためにはシステムのサイズの平方根に比例する操作が必要であり、プリイメージを見つけるためにはさらに多くの操作が必要であるという、これらのシステムの堅牢なセキュリティを明らかにしました。彼らの結果は、SHA-3の主要な4つのバリアントに対して明示的かつ具体的な数値を提示しており、それらが（設計の基礎にある構造的な弱点を突く方法を見つけ出さない限り）強力な量子コンピュータに対しても安全であることを示しています。

研究者たちは、数学的モデルのセキュリティを証明することと、実際のハードウェアのセキュリティを証明することを慎重に区別しました。彼らの研究は、もし基礎となるランダム置換が期待通りに振る舞うならば、その上に構築された暗号構成は安全であることを確認しています。彼らは、実世界のSHA-3標準で使用されている特定の置換が完璧であると主張したのではなく、むしろその設計自体が健全であることを主張しました。この区別は極めて重要です。つまり、システムの失敗は、システム全体の根本的な弱さではなく、特定の置換の実装における欠陥に起因する可能性が高いということを意味します。数学的な境界を厳密にすることで、研究者たちは暗号学者が将来のシステムを分析するためのより強力なツールを提供し、次世代のデジタルセキュリティが直面する量子脅威に対して明確かつ正確な理解を持って設計できるようにしました。

彼らの発見の核心は、攻撃者のクエリと既知の回答のデータベースとの関係をどのように扱うかにあります。旧来の手法では、実在のマシンとノートブックとの間の接続はやや緩やかであり、質問が増えるにつれて誤差が蓄積していました。新しいアプローチでは、ノートブックを、マシンの状態を直接的かつコヒーレントに反映するものとして扱います。彼らは、両者の間に橋を架け、正確な数学的関係を維持するようにしました。これにより、ノートブックは、たとえどれだけの質問が行われたとしても、システムの真の状態を見失うことがなくなります。この橋は、情報を（例えば図書館をフロアごとに整理するように）明確なレベルに分離し、その後、それらの間の接続を注意深く正規化するという技術を用いて構築されています。この正規化により、ノートブック内で計算された確率が現実世界の確率と一致することが保証され、以前の手法を制限していた「ドリフト（漂流）」が排除されました。

この研究は単一の証明を改善するにとどまらず、対称暗号における量子セキュリティ分析の基盤全体を強化します。圧縮オラクルを全入力数のわずかな断片から平方根へと押し上げることで、研究者たちは、以前は手の届かなかったシステムの分析への扉を開きました。彼らの結果は、これらの特定の種類の暗号システムを打破する際の量子的な優位性は、設計が十分な容量を備えている限り、恐れられているほど大きくはないことを示唆しています。チームが明示的な定数と具体的な境界を提供できたことは、エンジニアが漠然とした推定に頼るのではなく、システムが提供するセキュリティのレベルを正確に計算できることを意味します。この明晰さは、量子コンピュータが現実のものとなりつつある時代において、私たちのデータが保護され続けるためのデジタルインフラを構築する上で不可欠です。

また、この研究は、多くの暗号スキームの構成要素である理想的なサイファー（理想的な暗号）にもその知見を広げています。このモデルでは、セキュリティは異なる鍵によって制御される置換のファミリーに依存します。研究者たちは、攻撃者が異なる鍵にわたって重ね合わせ状態でシステムにクエリを投げることができる場合でも、改良された手法が同様に有効であることを示しました。これは、多くの鍵が存在することによってシステムのセキュリティが低下しないことを意味するため、重要な成果です。この分析は、鍵の数に関わらず揺るぎなく成立しており、これらの暗号設計の根本的な構造が量子攻撃に対して健全であるという考えを補強しています。

最終的に、この論文は量子セキュリティ分析に使用されるツールの成熟を象徴しています。かつては厳密な証明には脆弱すぎると考えられていた手法を、信頼できる道具へと強化したのです。研究者たちは、圧縮オラクルが単なるヒューリスティックな近似ではなく、量子情報を追跡するための数学的に健全な方法であることを示しました。そうすることで、彼らは暗号コミュニティに対し、より明確な展望を提供し、最も高度な脅威に対しても証明可能な安全性を持つシステムを設計することを可能にしました。この研究は、複雑な量子の現実をより良く反映するために、数学的モデルを洗練させる力の証となっています。