電子署名
任意の平文mに対し、 P r ( V p k ( m , s ) = A C C E P T | ( p k , s k ) ← G ( 1 k ) , s ← S s k ( m ) ) {\displaystyle \mathrm {Pr} (V_{\mathbf {pk} }(m,s)=\mathbf {ACCEPT} |(\mathbf {pk} ,\mathbf {sk} )\gets G(1^{k}),s\gets S_{\mathbf {sk} }(m))} はoverwhelming。
ランダムオラクルは、暗号理論の研究でよく使用される概念であって、ハッシュ関数が「十分ランダムに振る舞う」ということを理想化した概念である。ランダムオラクル仮定は、「ランダムオラクルが存在する」という仮定であるが、ランダムオラクルはあくまで現実を理想化したものであり、現実的には存在し得ない。
Cramer-Shoup署名は、ランダムオラクルのような理想化された仮定を用いないで安全性が示せる(もので、かつ効率的な)初めての署名方式であり、強RSA仮定のもとでCMA-EUF安全であることが示されていて、RSA暗号の数倍程度の計算量で署名作成・検証が行なえる。
ElGamal署名、DSA署名、Schnorr署名のような素体の乗法群上の離散対数問題を基にした署名方式は、素体の乗法群の代わりに楕円曲線群を用いて計算量を少なくし、しかも署名長を短くすることができる。楕円曲線群を用いたElGamal署名、Schnorr署名を、それぞれ楕円ElGamal署名、楕円曲線DSA署名、楕円Schnorr署名と呼ぶ。