Security Reduction
安全性帰着は、証明可能安全性の中核技術である。暗号方式への効率的な攻撃を、難問に対する効率的なアルゴリズムに変換することで、背理法により安全性を証明する。
目的
安全性の前提と方式の安全性を結ぶ数学的な橋を架ける、証明可能なセキュリティにおける形式的手法である。
メカニズム
方式への攻撃者 A が与えられたとき、難問ソルバ B を構成する。B は問題のインスタンスを受け取り、それを方式のパラメータに埋め込み、A の攻撃能力を利用して難問の解を抽出する。帰着損失は B と A の効率のギャップを定量化する。
ユースケース
- 暗号プロトコルの安全性証明
- リダクション効率の分析
- プロトコルの安全性評価