電子署名
公開鍵を公開する場合は、信頼できる第三者機関 (trusted third party, TPP) を介して公開することが望ましい。各公開鍵を、公開鍵の持ち主と対応させる方法は幾つか知られている。代表的な方法は、次の二つである。
信頼できる第三者機関が各人のIDと公開鍵を対応付けた表(公開鍵簿)を作成し、公開する。
信頼できる第三者機関が認証局を運営し、PKI の仕組みを用いて各人の ID と公開鍵とを対応付ける(印鑑証明書に相当する)。
(電子)署名方式((でんし)しょめいほうしき、(digital) signature scheme)は平均多項式時間確率アルゴリズムの三つ組み(G,S,V)である。
Gは鍵生成アルゴリズム(かぎせいせい-、key generation algorithm)と呼ばれ、1を入力されると公開鍵・秘密鍵ペア(pk,sk)を出力する。ただしここでkはセキュリティ・パラメータ。
Sは署名アルゴリズム(しょめい-、signing algorithm)と呼ばれ、'平文mと秘密鍵skの組(m,sk)を入力されると、平文mに対する(電子)署名文((でんし)しょめいぶん, (digital) signature)sを出力する。
Vは検証アルゴリズム(けんしょう-、verification algorithm)と呼ばれ、平文m、署名文s、公開鍵pkの組(m,s,pk)を入力されると文字列ACCEPTもしくはREJECTを出力する。Vpk(m,s)=ACCEPTとなるとき、署名文sは、(公開鍵pk,および平文mに関し)検証を通る(accept,「validである」ともいう)といい、そうでないとき検証を通らない(reject, 「invalidである」ともいう)。