電子署名
通常の紙文書に用いる印や署名に相当する、電子文書の作成者の証明が可能な仕組み。
If( V p k ( m , s ) = R e j e c t {\displaystyle V_{\mathbf {pk} }(m,s)=\mathbf {Reject} } ) Return LOSE
Return WIN
実験でAが勝つ確率を S u c c Σ k ( A ) {\displaystyle \mathbf {Succ} _{\Sigma }^{k}(A)} と書く事にする。(注:この記号は比較的良く使われるものの、必ずしも皆の合意がとれた記号ではないので、使用するときには一言説明が必要である)。 ただしここで確率はG,S,V,Aの内部乱数をランダムに選んだときのもの。
定義 Σ = ( G , S , V ) {\displaystyle \Sigma =(G,S,V)} を電子署名方式とする。 任意の平均多項式時間確率アルゴリズムAに対し、 S u c c Σ k ( A ) {\displaystyle \mathbf {Succ} _{\Sigma }^{k}(A)} がkに関しnegligibleなとき、 電子署名方式 Σ {\displaystyle \Sigma } は選択文書攻撃に対し存在的偽造不能であるという。
電子文書が改竄されていないことの保証、つまり改竄された場合にそれが検出できる仕組み。