証明可能な安全性と還元

証明可能な安全性とは、暗号スキームを破ることが、困難であると信じられている問題を解くことと少なくとも同程度に難しいことを示すものである。これは、想定される困難な問題からスキームへのあらゆる攻撃への明示的な還元を与えることによって行われる。

Definition

セキュリティ還元とは、暗号スキームを破るあらゆる効率的な攻撃者を、困難であると仮定されている問題を解く効率的なアルゴリズムに変換する証明であり、それによって、その問題が容易でない限りスキームが安全であることを示すものである。

Scope

このトピックでは、暗号証明における還元ベースの手法、すなわち、セキュリティ還元の構造、タイトネスと具体的な安全性、ゲームベースおよびシミュレーションベースの証明スタイル、ランダムオラクルモデルと標準モデル、そしてこのアプローチの限界と批判について扱う。セキュリティ保証がどのように述べられ、議論されるかについて述べる。特定の困難性仮定、定義、および攻撃者モデルは、関連トピックで扱われるため、ここでは除外する。

Core questions

• 還元は、スキームへの攻撃を困難な問題の解決策にどのように変換するのか？
• ゲームベースの証明とシミュレーションベースの証明の違いは何か？
• 還元の「タイトネス」は、現実世界のセキュリティパラメータにとって何を意味するのか？
• ランダムオラクルモデルと標準モデルとは何か、そして前者が物議を醸すのはなぜか？
• 証明可能な安全性に関する議論の限界と一般的な落とし穴は何か？

Key concepts

• セキュリティ還元
• ゲームベースの証明
• シミュレーションベースの証明
• タイトな還元とルーズな還元
• 具体的な安全性
• ランダムオラクルモデル
• 標準モデル
• 無視できる優位性
• 困難性仮定

Key theories

還元主義的証明手法

スキームの安全性を証明するために、それを破る攻撃者を仮定し、その攻撃者をサブルーチンとして使用して、基礎となる困難な問題を解くアルゴリズムを構築する。したがって、攻撃が成功すれば、困難性仮定と矛盾することになる。

ランダムオラクルモデル

多くの効率的なスキームは、ハッシュ関数を真にランダムなオラクルとして理想化することで安全性が証明される。このモデルは実用的な構成の証明を可能にするが、実際の関数はランダムオラクルではないため、ヒューリスティックである。

Mechanisms

還元において、証明者は、無視できない優位性をもってスキームを破る仮想的な攻撃者を想定し、困難な問題のインスタンスを攻撃者の視点に埋め込み、攻撃者を実行し、その出力を使用して問題を解くラッパーを構築する。ゲームベースの証明は、実際のスキームから攻撃者が明らかに勝てないスキームへと、区別できないゲームのシーケンスを通じて進行する。還元のタイトネス（優位性と実行時間の損失の程度）は、目標とするセキュリティレベルに必要な鍵のサイズを決定する。

Clinical relevance

証明可能な安全性は、暗号スキームが信頼と標準化を獲得するための基準である。NISTのAES、SHA-3、およびポスト量子プロセスでは、セキュリティ証明が重視され、TLS 1.3のようなプロトコルには還元主義的および機械検証された分析が伴った。還元を理解することで、実務家はセキュリティ主張が何を保証し、何を保証しないかを判断し、還元のタイトネスを考慮したパラメータを選択することができる。

Evidence & guidelines

現代の実践では、可能な限り標準モデルでの証明が好まれ、ランダムオラクル証明は絶対的な保証ではなく、強力なヒューリスティックな証拠として扱われる。ツール支援フレームワーク（EasyCrypt、CryptoVerif）は、機械検証された証明を提供する。具体的な（厳密な）セキュリティ分析は、リソースの関数として攻撃者の優位性を定量化するものであり、実際のパラメータを設定するために、純粋に漸近的な記述よりも好まれる。

History

還元主義的手法は、1980年代初頭の定義革命とともに登場し、1990年代を通じて体系化された。BellareとRogawayは、実用的なスキームの安全性を証明するためにランダムオラクルモデル（1993年）を導入し、後に保証を定量化するために「具体的な安全性」分析を導入した。Canetti、Goldreich、およびHaleviによる1998年の結果は、ランダムオラクルモデルでは安全だが、インスタンス化されると安全でないスキームがあることを示し、理想化されたモデルに関する議論を深めた。

Key figures

• Mihir Bellare
• Phillip Rogaway
• Oded Goldreich
• Shafi Goldwasser
• Silvio Micali

Seminal works

• bellare1993
• katz2020
• goldreich2001

Frequently asked questions

セキュリティ証明は、スキームが絶対に破られないことを意味するのか？

いいえ。証明は、スキームを破ることが、指定されたモデル内で仮定された困難な問題を解くことを意味することを示します。仮定が失敗した場合、モデルが非現実的である場合、または実装が分析されたスキームから逸脱している場合、攻撃は依然として可能です。証明はリスクを軽減しますが、排除するものではありません。

ランダムオラクルモデルが物議を醸すとされるのはなぜか？

それはハッシュ関数を完全にランダムな関数としてモデル化しますが、具体的な関数で真にそうであるものはありません。このモデルでの証明は強力な証拠であり、効率的なスキームを可能にしますが、モデルでは安全だが、オラクルが実際のハッシュに置き換えられると安全でなくなる（不自然な）スキームが存在するため、そのような証明はヒューリスティックです。