公開鍵暗号
Otherwise return 0.
任意の多項式時間機械 A {\displaystyle A} に対し、ある多項式時間機械 B {\displaystyle B} が存在し、
| Pr ( E x p Π − S S − R e a l ( O 1 , O 2 ) ( A , k ) = 1 ) − Pr ( E x p Π − S S − I d e a l ( O 1 , O 2 ) ( B , k ) ) | {\displaystyle |\Pr({\mathsf {Exp}}_{\Pi -{\mathsf {SS-Real}}}^{(O_{1},O_{2})}(A,k)=1)-\Pr({\mathsf {Exp}}_{\Pi -{\mathsf {SS-Ideal}}}^{(O_{1},O_{2})}(B,k))|}
が k に関して無視できるとき、公開鍵暗号方式 Π = ( G , E , D ) {\displaystyle \Pi =(G,E,D)} は ( O 1 , O 2 ) {\displaystyle (O_{1},O_{2})} -強秘匿 (Semantic Secure) であるという。
直観的な定義
M 0 {\displaystyle M_{0}} 、 M 1 {\displaystyle M_{1}} を攻撃者が指定した2つのメッセージとし、 C {\displaystyle C} を M 0 {\displaystyle M_{0}} もしくは M 1 {\displaystyle M_{1}} を暗号化した暗号文とする。
このとき、攻撃者は C {\displaystyle C} が M 0 {\displaystyle M_{0}} 、 M 1 {\displaystyle M_{1}} のいずれを暗号化したものであるかを(1/2よりも有意な確率で)知る事はできない。
厳密な定義
O 1 {\displaystyle O_{1}} , O 2 {\displaystyle O_{2}} を2つのオラクル、 b {\displaystyle b} をビットとする。
暗号に対する攻撃者 A {\displaystyle A} を用いて次の実験 (Experiment, ゲーム (game) ともいう) をする。