公開鍵暗号
直観的定義
暗号文を知っていることは、平文を知る上で何の役にもたたない。すなわち、暗号文を知っている状況で攻撃者が知ることができる平文についての部分情報は、暗号文を知らなくても攻撃者が知ることができる情報だけである。
厳密な定義
k {\displaystyle k} をセキュリティ・パラメータとし、 Π = ( G , E , D ) {\displaystyle \Pi =(G,E,D)} を公開鍵暗号方式とする。 A , B {\displaystyle A,B} を多項式時間機械とする。
さらに、 O 1 , O 2 {\displaystyle O_{1},O_{2}} をオラクルとする。
次の2つのゲームを考える。ただしゲーム中で、 M , f {\displaystyle M,f} は多項式時間機械(の動作を記したプログラム)、 S t {\displaystyle St} はビット列で、 A {\displaystyle A} の状態と呼ばれる。
E x p Π − S S − R e a l ( O 1 , O 2 ) ( A , k ) {\displaystyle {\mathsf {Exp}}_{\Pi -{\mathsf {SS-Real}}}^{(O_{1},O_{2})}(A,k)} ( p k , s k ) ← G ( 1 k ) {\displaystyle {\mathsf {(pk,sk)}}\gets G(1^{k})} ( M , S t ) ← A O 1 ( p k ) {\displaystyle (M,{\mathsf {St}})\gets A^{O_{1}}({\mathsf {pk}})} m ← M {\displaystyle m\gets M} C ← E p k ( m ) {\displaystyle C\gets E_{\mathsf {pk}}(m)} ( y , f ) ← A O 2 ( C , S t ) {\displaystyle (y,f)\gets A^{O_{2}}(C,{\mathsf {St}})} If y = f ( m ) {\displaystyle y=f(m)} , return 1. Otherwise return 0.
E x p Π − S S − I d e a l ( O 1 , O 2 ) ( B , k ) {\displaystyle {\mathsf {Exp}}_{\Pi -{\mathsf {SS-Ideal}}}^{(O_{1},O_{2})}(B,k)} ( p k , s k ) ← G ( 1 k ) {\displaystyle {\mathsf {(pk,sk)}}\gets G(1^{k})} ( M , S t ) ← B O 1 ( p k ) {\displaystyle (M,{\mathsf {St}})\gets B^{O_{1}}({\mathsf {pk}})} m ← M {\displaystyle m\gets M} ( y , f ) ← B O 2 ( S t ) {\displaystyle (y,f)\gets B^{O_{2}}({\mathsf {St}})} If y = f ( m ) {\displaystyle y=f(m)} , return 1.