電子署名
電子署名(でんししょめい)とは、電磁的記録(電子文書)に付与する、電子的な徴証であり、紙文書における印章やサイン(署名)に相当する役割をはたすものである。主に本人確認や、改竄検出符号と組み合わせて偽造・改竄(かいざん)の防止のために用いられる。
電子署名を実現する仕組みとしては、公開鍵暗号方式に基づくデジタル署名が有力である。日本では、「電子署名及び認証業務に関する法律に基づく特定認証業務の認定に係る指針」の第3条で、RSA、DSA、ECDSA の3方式を指定している。いずれも公開鍵暗号方式に基づく方式である。
RSA署名、ElGamal署名、DSA署名、Schnorr署名、Cramer-Shoup署名、楕円ElGamal署名、楕円曲線DSA署名、楕円Schnorr署名など様々な署名方式が知られている。
RSA署名、ElGamal署名はそれぞれ素因数分解問題、素体の乗法群上の離散対数問題を基にした署名方式である。この二つの署名方式は、暗号理論の研究の初期に提案された署名方式であるので特に有名である。しかし、RSA署名は(教科書的なRSA署名は、存在的偽造可能であることが自明なので)CMA-EUF安全ではないし、ElGamal署名は(CMA-EUF安全であろうと予想されているものの)CMA-EUF安全であるかどうか分かっていない。DSA署名はElGamal署名の変形版であって米国NISTの標準暗号になっているが、安全性については同様である。
Schnorr署名は、素体の乗法群上の離散対数問題の困難性とランダムオラクル仮定のもとでCMA-EUF安全であることが示されている署名方式であり、ElGamal署名と同程度の効率をもつ。