Provable Security
証明可能安全性は、暗号方式の安全性を広く信じられている計算困難問題に帰着させる。多項式時間の攻撃者が方式を破れるなら、困難問題を解く多項式時間アルゴリズムが構成できるという論理である。
目的
暗号方式にヒューリスティック解析ではなく数学的な安全性保証を与える、現代暗号の設計パラダイムである。
メカニズム
安全性帰着を構成する：攻撃者Aが優位性εで方式を破ると仮定すると、Aをサブルーチンとして使い、関連する優位性で困難問題（DDH、LWEなど）を解くアルゴリズムBを構成できる。困難問題に多項式時間解がないと仮定するため、Aは存在し得ない。
ユースケース
- 暗号スキームの安全性証明
- プロトコル設計への適用
- ポスト量子方式の評価