電子署名の安全性(Security)の要件をより厳密に定義する。「検証を通過するのは正当な署名者が作った署名文に限る」というのが、いかなる条件下でいかなる目標を達する事を指すのかによって電子署名方式の安全性の定義は数種類に存在するが、単に「安全」といった場合選択文書攻撃に対する存在的偽造不能性(Existencial Unforgeability against Chosen Message Attack, EU-CMAと略す）を指す事が普通なので、ここではこの定義を紹介する。

準備
Σ = ( G , S , V ) {\displaystyle \Sigma =(G,S,V)} を電子署名方式とし、kをセキュリティ・パラメータとする。Aを電子署名方式 Σ {\displaystyle \Sigma } に対する攻撃者とする。攻撃者Aを用いて、次のような実験(experiment ゲーム(game)とも言う)を行なう。
まず1kを入力として鍵生成アルゴリズムを走らせ、公開鍵・秘密鍵ペア(pk,sk)を作る。そしてpkとkを攻撃者Aに渡す。
攻撃者Aは実験の最中、署名オラクルO(sk,・)に任意の回数アクセスする事ができる。署名オラクルとは、攻撃者Aから平文mを送信されると、秘密鍵skを使ってmに対する署名文s=Ssk(m)を作成し、sをAに送信するオラクルの事である。
攻撃者Aの目標は、平文mと署名文sとの組(m,s)で検証を通り、しかも署名オラクルOにmを送信していないものを出力する事。そのような(m,s)を作成できればAの勝ち、そうでなければAの負けである。
以上の実験をより形式的に書くと、以下の通り。

Experiment ( p k , s k ) ← G ( 1 k ) {\displaystyle (\mathbf {pk} ,\mathbf {sk} )\gets G(1^{k})} ( m , s ) ← A O ( s k , ⋅ ) ( 1 k , p k ) {\displaystyle (m,s)\gets A^{O(\mathrm {sk} ,\cdot )}(1^{k},\mathbf {pk} )} If( A {\displaystyle A{}} が O ( s k , ⋅ ) {\displaystyle O(\mathbf {sk} ,\cdot )} に m {\displaystyle m{}} を聞いた事がある) Return LOSEIf( V p k ( m , s ) = R e j e c t {\displaystyle V_{\mathbf {pk} }(m,s)=\mathbf {Reject} } ) Return LOSEReturn WIN

実験でAが勝つ確率を S u c c Σ k ( A ) {\displaystyle \mathbf {Succ} _{\Sigma }^{k}(A)} と書く事にする。(注：この記号は比較的良く使われるものの、必ずしも皆の合意がとれた記号ではないので、使用するときには一言説明が必要である)。
ただしここで確率はG,S,V,Aの内部乱数をランダムに選んだときのもの。