署名方式

通常のディジタル署名方式以外の各種署名方式を紹介します．

ブラインド署名

ブラインド署名とは
ブラインド署名は，署名対象文書の作成者と署名者を分離し，署名者には署名する文書の内容が分からないようにする方式である．封筒に入れ封をした書類に封筒の上から署名をすると，中の書類に被せられたカーボン紙を通して中の書類にも署名が写るイメージである．このとき，署名者には中の書類の内容は分からない．
ブラインド署名は，電子マネーや電子投票などへの適用が考えられている．例えば，選挙で投票内容を見せずに選挙管理委員会から「本人の投票に間違いない」という署名をもらう場合などである．
ブラインド署名の手順
ブラインド署名は，以下の手順で行われる．
1. ブラインド処理
  署名要求者は，署名対象文書 $m$ に対して前処理(ブラインド処理) $\mathrm{F}$ により $\mathrm{F}(m)$ を生成し，署名者に送る．$\mathrm{F}(m)$ は乱数化されており， $\mathrm{F}(m)$ から $m$ を推測することはできない．
2. 署名処理
  署名者は，$\mathrm{F}(m)$ 対して署名処理 $\mathrm{S}$ により署名 $\mathrm{S}(\mathrm{F}(m))$ を生成し，署名要求者に返送する．
3. アンブラインド処理
  署名要求者は，後処理(アンブラインド処理) $\mathrm{G}$ を行い，$\mathrm{G}(\mathrm{S}(\mathrm{F}(m)))$ を計算する．この値は，$\mathrm{F}$ と $\mathrm{G}$ を適切に選ぶ ($\mathrm{G}$ は $\mathrm{F}$ の逆関数の関係)ことにより $m$ に対して直接署名した値 $\mathrm{S}(m)$ に等しくすることができる．すなわち，署名要求者は，文書 $m$ に対する署名 $\mathrm{S}(m)$ を得る．
RSA署名を用いたブラインド署名
RSA署名を用いた上記のブラインド署名の具体例は次のようになる．なお，RSA署名の公開鍵 $e$ が $P_k$ に，秘密鍵 $d$ が $S_k$ に対応する．
1. 署名要求者は，署名対象文書 $m$ に対して乱数 $r$ を生成し，署名者の公開鍵 $P_k$ を用いて $x = \mathrm{H}(m) \cdot r^{P_K}$ を計算し，署名者に送る．ここで，$\mathrm{H}$ はハッシュ関数である．
2. 署名者は，$x$ 対して自身の秘密鍵 $S_k$ を用いて以下の署名処理をを行い，署名要求者に返送する． \[ y = x^{S_k} = (\mathrm{H}(m) \cdot r^{P_K})^{S_k} = \mathrm{H}(m)^{S_k} \cdot r^{P_kS_k} = \mathrm{H}(m)^{S_k} \cdot r\]
3. 署名要求者は，$y$ に対して以下の計算を行い，署名 $\mathrm{H}(m)^{S_k}$ を得る． \[ s = y/r = (\mathrm{H}(m)^{S_k} \cdot r) \cdot r^{-1} = \mathrm{H}(m)^{S_k} \]

フェアブラインド署名

フェアブラインド署名とは
フェアブラインド署名は，ブラインド署名の性質に加えて，事前に定められた第三者機関だけは署名と文書作成者との関係を知ることができるようにする方式である．
フェアブラインド署名の手順
フェアブラインド署名は，以下の2つのステップからなる．
1. ブラインド署名
  署名要求者は，署名者に文書を送り署名結果を受け取る．これにより，署名要求者は文書と署名のペアを得る．署名者は自身が実行したブラインド署名プロトコルと署名者が持つ文書と署名のペアとの対応関係は分からない．
2. リンク関係の復元
  署名者は，第三者機関からブラインド署名プロトコルと文書と署名のペアとの対応関係が分かる情報を得ることができる．
  これには，次の2つのタイプがある．
  - 署名者の持つブラインド署名プロトコル情報を元に，第三者機関がブラインド署名プロトコルと文書と署名のペアとの対応関係を明らかにする情報を提供する．第三者機関は，文書を取り出すことができる．
  - 文書と署名のペアの情報を元に，第三者機関が署名者にブラインド署名プロトコルとその文書の送信者(署名要求者)との対応を明らかにする情報を提供する．

グループ署名・多重署名

グループ署名
グループ署名は，グループのメンバだけが匿名で署名でき，署名の正当性はグループ公開鍵を利用して検証可能な方式である．また，不正がある場合は追跡機関により署名者を特定できる追跡機能を持っている．
グループ署名は，グループの管理者 (GM)，追跡期間 (EM)，グループメンバ $A$ の3つのエンティティからなり，以下の4つの処理からなる．
1. 初期設定
  - グループ管理者 GM，追跡機関 EM はそれぞれの公開鍵と秘密鍵のペア ($P_G, S_G$)，($P_E, S_E$) を生成する．ここで，($P_G, P_E$) がグループ公開鍵に対応する．
  - グループメンバ $A$ は，$P_A = \mathrm{f}(S_A)$ の関係を満たす公開鍵と秘密鍵のペア ($P_A, S_A$) を生成する．$P_A$ と $P_A$ に対するディジタル署名 $\mathrm{Sign_{S_A}}(P_A)$，$P_A$と$S_A$ が正しく作成されていることを証明するゼロ知識証明書 $\mathrm{SPK_c}$ を GM に送る．
  - GM は，送られたデータの正当性を署名検証，ゼロ知識証明書の検証により確認した後，メンバ証明書 $\sigma_A=\mathrm{Sign_{S_G}}(P_A)$ を生成し返信する．また，メンバ証明書とメンバID のペア $(ID_A,P_A,\sigma_A)$ を秘密裏に管理するとともに，$(P_A, \mathrm{Sign_{S_A}}(P_A))$ をメンバリストの追加する．
2. グループ署名生成
  以下の3つの情報を生成し，メッセージ $m$ とともにグループ署名とする．
  - $\mathrm{SPK_{\sigma, \beta}} = \mathrm{SPK\{(\alpha, \beta)\ |\ \mathrm{Verify_{P_G}}(f(\alpha), \beta)=1\}}(m)$
    メッセージ $m$ に対して，秘密鍵 $S_A$ とそれに対応するメンバ証明書 $\sigma_A$ を正しく持っていることを示すゼロ知識証明書
  - $c=E_{P_E}(P_A)$
    公開鍵 $P_A$ を EM の公開鍵で暗号化したもの
  - $\mathrm{SPK_c}$
    $c$ の平文 (公開鍵 $P_A$) に対応する秘密鍵 $S_A$ を持っていることを示すゼロ知識証明書
3. グループ署名検証
  $\mathrm{SPK_{\sigma, \beta}}$，$\mathrm{SPK_c}$ の検証を行う．
4. 追跡
  EM は $c$ を復号してメンバの公開鍵である $P_A$ を求め，$P_A$ を GM に送る．
  GM は，$P_A$ からグループメンバ $A$ を特定する．
多重署名
多重署名は，1つの署名対象データに複数の署名を付与する方式である．単純に署名者が順番に署名を付加していけば通常の署名方式を用いて多重署名は実現できるが，署名サイズが大きくなる欠点がある．
多重署名方式の例としてFiat-Shamir多重署名方式を以下に示す．
1. グループ鍵の生成
  多重署名を行なうグループの秘密鍵 $n$ と公開鍵 $p$，$q\ (n = pq)$ を以下のように生成する．
  素数 $p$，$q$ および以下の関係を満たす任意の $L$ を求める(ランダムに $L$ を選び以下の式を満たす，すなわち $L$ の逆元が存在するように $p$，$q$ を選ぶ)． \[ Ld = 1 \bmod (p-1)(q-1) \]
2. 個人鍵の生成
  多重署名を行うグループのメンバ $i$ の個人鍵データを生成する．
  次の関係より秘密鍵 $s_i$ と公開鍵 $v_i$ を生成する． \[ v_i = 1 / s_i^L \] 公開鍵 $v_i$ をメンバのID情報等をハッシュ関数により圧縮したものとし，これに対応した秘密鍵を上式から求める．
3. 署名前処理
  多重署名を行う前に，一度だけグループのメンバ全員が乱数の積を生成し，IDを連結する．
  乱数 $r_i$ を生成して以下の式を計算する． \[ \begin{array}{l} X_i = r_i^L \bmod n\\ \tilde{X_i} = X_i \cdot \tilde{X_{i-1}} \end{array} \] 各メンバ(署名者) $i$ は，上記の式を計算し，次の署名者 $i + 1$ に $\tilde{X_i}$ を送る．また，最後の署名者 $m$ が計算した $\tilde{X_m}$ を各ユーザに送る．
4. 署名生成
  以下の式を計算する． \[ \begin{array}{l} e = \mathrm{H}(m \parallel \tilde{X_m})\\ \sigma_i = r_i \cdot s_i^e\\ \tilde{\sigma_i} = \tilde{\sigma_{i-1}} \cdot \sigma_i \end{array} \] 各メンバ(署名者) $i$ は，上記の式を計算し，次の署名者 $i + 1$ に $\tilde{\sigma_i}$ を送る．ここで，$\mathcal{H}$ はハッシュ関数，$m$ は文書である．
5. 署名検証
  以下の式を計算し，署名を検証する． \[ \begin{array}{l} e = \mathrm{H}(m \parallel \tilde{X_m})\\ v = \prod_{i=1}^m v_i\\ v^e \cdot \tilde{\sigma_m}^L \stackrel{?}{=} \tilde{X_m} \end{array} \]

リング署名

リング署名は，グループ署名と違い管理者の存在を仮定せず，匿名性を保証しながらグループの代表による署名が可能な方式である．署名から署名者を特定することは署名者本人でも不可能である．

リング署名といわれる所以は，リング状（円形）にメンバが並んでいるとして，署名者から始まって順番に隣のメンバの公開鍵を使って演算していき，最後に署名者へ戻ったときに署名者の秘密鍵を使って署名演算を終了するような形式になっているからである．

以下に，離散対数問題に基づくリング署名の手順を示す．

鍵生成
グループのメンバ（$n$ 人）は，$q|p-1$ を満たす大きな素数 $p$，$q$ と乗法群 ${Z_p}^*$ での位数が $q$ となる生成元 $g$ を求め公開する．
グループのメンバ $i$ は，$x_i \in Z_q$ を秘密鍵，$y_i = g^{x_i} \bmod p$ を公開鍵として生成する．
署名生成

Step 1
$i$ は以下を計算する． \[ T_i = g^\alpha \bmod p, \quad \alpha \in_U Z_q \] \[ c_{i+1} = \mathrm{H}(m || T_i) \]
Step 2
$j = i+1, \ldots , n, 1, \ldots, i-1$ に対して以下を計算する． \[ T_j = g^{s_j} y_j^{c_j} \bmod p,\quad s_j \in_U Z_q \] \[ c_{j+1} = \mathrm{H}(m || T_j) \]
Step 3
\[ s_i = \alpha - x_i c_i \bmod q \] $(c_1, s_1, s_2 ,\ldots, s_n)$ を $m$ に対する署名とする．

署名検証
$j = 1, \ldots, n$ に対して，以下を計算する． \[ T_j = g^{s_j} y_j^{c_j} \bmod p \] \[ c_{j+1} = \mathrm{H}(m || T_j) \] $c_1 = c_{n+1}$ ならば検証成功，さもなくば検証失敗とする．