デジタル署名
選択的偽造(selective forgery)攻撃とは、敵に選択された文書の署名が偽造されるという結果をもたらすものである。
存在的偽造(existential forgery)とは、ただ単に敵に知られていない何らかの有効な文書/署名の対が発見されるだけという結果をもたらすものである。
また彼らは、選択文書攻撃でさえ対抗し存在的偽造でさえ防ぐ事が初めて立証できる、GMR署名方式も提示した。
殆どの初期の署名方式は類似していた。それらは、RSA関数などの落とし戸置換(trapdoor permutation)の使用か、あるいはラビン署名方式の場合は合成数Nを法とする二乗の計算を必要とする。落とし戸置換族は、パラメータで指定される置換の集まりであり、その置換の順方向への計算は容易だが、逆方向への計算は困難である。しかしながら、全てのパラメータについて逆方向の計算を容易にする"落とし戸"が存在する。パラメータを公開鍵、落とし戸を秘密鍵とし、また暗号化は順方向へ復号は逆方向へ置換を計算する事に対応させれば、落とし戸置換は公開鍵暗号システムとしてみなす事ができる。また、落とし戸置換はデジタル署名方式とみなす事もでき、秘密鍵を用いた逆方向の計算を署名と考え、また順方向の計算は署名を検証するためにされると考えればよい。署名は復号に相当し検証は暗号化に相当するという対応により、デジタル署名は公開鍵暗号方式を踏まえて説明される事が多いが、これはデジタル署名を算出する唯一の方法ではない。