デジタル署名
デジタル署名は一般的には3つのアルゴリズムから成る。
鍵生成アルゴリズムG - 署名者の"鍵ペア"(PK, SK)を生成する。PKは公開する検証鍵、そしてSKは秘密にする署名鍵である。
署名生成アルゴリズムS - メッセージmと署名鍵SKを入力とし、署名σを生成する。
署名検証アルゴリズムV - メッセージm、検証鍵PK、署名σを入力とし、承認または拒否を出力する。
主に2つの特性が必要とされる。第一に、正当な署名鍵で生成された署名は、対応する検証鍵によって常に承認されること。つまり、署名鍵SKと検証鍵PKが対応する鍵ペアである場合、任意のメッセージmについて、V (m, PK, S (m, SK))は承認が出力される必要がある。第二に、いかなる攻撃者であっても(PKを知っているだけでは)有効な署名を生成する事は困難であることである。