グループ署名方式

グループ署名方式とは，自分をアイデンティティを隠しながら，自分がその組織に含まれていることを証明する電子署名方式です．
本記事ではグループ署名方式の中で，特に有名なBBS方式について紹介したいと思います．

はじめに

匿名掲示板などのサービスでは， ユーザが不正を行った場合に， 追跡して責任を明らかにできる必要がある．しかし安易に追跡をできることは，プライバシの懸念をもたらす．

この問題の解決のために, 以下で定義する正当性， 偽造不可能，匿名・リンク不可能， 追跡可能， 失効可能を同時に満たしたい．

要求1. 正当性※ 正しいユーザはサービスを必ず利用できる．
要件2. 偽造不可能性※ 正しいユーザ以外は,サービスを利用できない.
要求3. 匿名性 誰もユーザを誰も特定できない．
要求4. リンク不可能性 誰もユーザを追跡（トラッキング）できない．
要求5. 追跡可能 ユーザの不正が発覚した場合， そのユーザを特定できる．

グループ証明方式

これらの要求を実現する手段に，グループ署名方式 が挙げられる．

グループ署名方式とは， 署名者が特定のグループに含まれることを証明するディジタル署名方式である．グループ署名方式の署名者は検証者から見て匿名であるが， 署名者の不正があった際は， GM(Group Manager) が署名から署名者を追跡できる．

グループ署名方式を，以下のエンティティ，手続き，セキュリティ要件から定義する．

エンティティ

GM メンバーを管理するエンティティであり， メンバーの追加， 失効， 追跡を行う．
メンバー 署名を行うエンティティ
検証者 メンバーによる署名を検証するエンティティ

手続き

グループ署名方式は以下の手続きから成り立つ．

GM はグループ署名のために，必要なパラメータと公開鍵と秘密鍵を生成する．
生成したパラメータと，公開鍵は公開する．

手続き1. 登録 メンバーが GM に登録を求める． GM はメンバーを登録し，
メンバーに対して署名に必要なクレデンシャルを送信する．
手続き2. 署名メンバーは署名したいメッセージに対する署名を生成し，
メッセージとともに署名を検証者に送信する．
手続き3. 検証 検証者は公開されているパラメータ，GM の公開鍵，署名， メッセージをもとに， 署名の検証を行う．
手続き4. 追跡 GM は署名をもとに， 署名したメンバーを追跡する．

セキュリティ要件

グループ署名は以下のセキュリティ要件を満たす．

要件1. 正当性 メンバーが作成した署名は必ず検証者に受理される．
要件2. 偽造不可能性 メンバー以外が作成した署名は， 必ず検証者に棄却される．
要件3. 匿名性 GM 以外は， 署名からメンバーを特定できない
**要件4. リンク不可能性. **GM 以外は， 複数の署名が同じメンバーによって署名されているかわからない．
要件5. 追跡可能性 GM は署名からメンバーを特定できる．

BBS

BBS（Boneh, Boyen, Shacham） 署名法式とは，署名のサイズが小さいグループ署名方式である．BBSでは， ペアリング を用いることで署名サイズを短くしている.

この記事では,BBSの仕組みについて説明するため，以下についてそれぞれ述べる.

1. 数学的な前提知識
2. BBSで提案されたゼロ知識証明※
3. BBSの手順

※特定の条件を持った値を保持していることを証明する技術

数学的準備

ペアリング

ペアリングは次のように定義される。
（厳密な定義ではないが、本記事を読みすすめるには問題ない。）

暗号学的仮定

BBSで用いられる暗号学的仮定について説明する．BBSでは，q-SDH仮定とDLIH仮定といった暗号学的仮定が用いられており，それぞれ以下のように定義する．

暗号学的仮定

DLDH仮定に基づいた公開鍵暗号方式である，線形暗号について説明する．
（BBSでは，線形暗号で暗号化されたユーザのIDを復号することで，追跡機能を実現する．）

以下では線形暗号の手続きと，健全性の証明について述べる．

ゼロ知識証明

秘密の値を隠しながら，その秘密が複数の条件を満たすことを証明する，ゼロ知識証明について説明する．
またゼロ知識証明を含む電子署名である，知識の証明についても紹介する．

これらは特定の条件に当てはまる秘密の保持を証明する技術とも言える．

知識証明の例として,離散対数の保有を証明した知識の証明を取り上げる．

手続き

BBSの手続きについてそれぞれ述べる．次の章で詳細を述べるが，BBSはDLDH仮定のもとに，SDHのペア$(x, A_i)$の保持を証明する知識の証明である．

準備

GMは以下の手順で事前準備を行う．

1. $\xi_1, \xi_2 \leftarrow \mathbb{Z}_p$ をランダムに選ぶ.
2. $u = g_2 ^ {\xi_2}$， $v = g_2 ^ {\xi_1}$，$h = v ^ {\xi_1} = u ^ {\xi_2}$ を計算する．
3. $\gamma \leftarrow \mathbb{Z}_p$ をランダムに選ぶ.
4. $\omega = g_2 ^ {\gamma}$ を計算する.

グループ全体の公開鍵を $gpk = (h, u, v, \gamma,\omega)$とする.

登録

GMは以下の手順で,メンバ$i$の秘密鍵$usk = (x_i, A_i)$を計算する．

1. $x_i \leftarrow \mathbb{Z}_p$
2. $A_i = g ^ {\frac{1}{\gamma + x_i}}$

メンバの秘密鍵を$usk = (x_i, A_i)$ とし，GMはメンバに$usk$を送信する．

署名

メンバは以下の手順でメッセージ $m \in \mathbb{Z}_p$に対する署名$\sigma$を生成する.

1. メンバは$A_x$の暗号文$(T_1, T_2, T_3)$ を 以下の手順で計算する.

   1. $\alpha, \beta \leftarrow \mathbb{Z}_p$
   2. $T_1 = u ^ {\alpha}, T_2 = v ^ {\beta}, T_3 = A_i h ^ {\alpha + \beta}$

2. 以下を計算する　

   1. $\delta_1 = x_i \alpha$
   2. $\delta_2 = x_i \beta$

3. 署名$\sigma$を生成するために，以下を計算する．
   \begin{align} \sigma = SPK\{(x_i, A_i, \alpha, \beta): u^{\alpha} = T_1 \land v^{\beta} &= T_2 \land T_1 ^ {x_i} u^{-\delta_1} = 1 \land T_2 ^ {x_i} v^{-\delta_2} = 1 \\ \land e(T_3, g_2) ^ {x_i} e(h, \omega)^{-\alpha - \beta} &e(h, g_2)^{-\delta_1 -\delta_2} = e(g_1, g_2) / e(T_3, \omega) \}(m) & \end{align}

   1. $r_{\alpha}, r_{\beta},r_x,r_{\delta_1},r_{\delta_2} \leftarrow \mathbb{Z}_p$ をランダムに選ぶ．
   2. $R_1 = u^{r_{\alpha}}, R_2 = v ^ {r_{\beta}}, R_3 = T_1 ^ {r_x} u ^ {-r \delta_1}, R_4 = T_2 ^ {r_x} v ^ {-r \delta_2}$
      $R_5 = e(T_3, g_2) ^ {r_x} e(h, w) ^ {-r_{\alpha} - r_{\beta}}e(h, g_2)^{-r_{\delta_1} - r_{\delta_2}}$ をそれぞれ計算する．
   3. $c = H(m, T_1, T_2, T_3, R_1, R_2, R_3, R_4, R_5)$ を計算する．
   4. $s_{\alpha} = r_{\alpha} + c {\alpha}, s_{\beta} = r_{\beta} + c {\beta}$
      $s_{\delta_1} = r_{\delta_1} + c \delta_1, s_{\delta_2} = r_{\delta_2} + c \delta_2$
      $s_x = r_x + c x$ をそれぞれ計算する．
   5. 署名を$\sigma = (T_1, T_2, T_3, c, s_{\alpha}, s_{\beta}, s_x, {\delta_1}, {\delta_2})$

検証

$m$に対する署名$\sigma = (T_1, T_2, T_3, c, s_{\alpha}, s_{\beta}, s_x, {\delta_1}, {\delta_2})$の知識証明を以下の手順で検証する.

1. 以下を計算する
   • $\tilde R_1 = u ^ {s_{\alpha}}T_1^{-c}$
   • $\tilde R_2 = v ^ {s_{\beta}}T_2^{-c}$
   • $\tilde R_3 = T_1 ^ {s_x} u^{-s_{\delta_1}}$
   • $\tilde R_4 = T_2 ^ {s_x} v^{-s_{\delta_2}}$
   • $\tilde R_5 = e(T_3, g_2)^{s_x}e(h,\omega)^{-s_{\alpha} -s_{\beta}} e(h, g_2)^{-s_{\delta_1} -s_{\delta_2}}\Bigl(\frac{e(T_3,\omega)}{e(g_1, g_2)}\Bigl) ^c$
2. 以下を検証して，成り立てば1,成り立たなければ0を返す．
   $c \stackrel{?}{=} H(m, T_1, T_2, T_3, \tilde R_1, \tilde R_2, \tilde R_3, \tilde R_4, \tilde R_5)$

追跡

GMは以下の$A_x$を持つメンバを探す.
$$A_x = \frac{T_3}{T_1^{\xi_1} T_2 ^ {\xi_2}}$$

証明

BBSがグループ署名方式の要件を満たすことを証明する．

正当性

検証者が必ず正しい証明を受理することを以下に証明する．

偽装不可能性

正しい$A_i$と$x$のペアを持たない敵対者は，有効な署名を作ることができない．

※要追記

匿名性

以下の理由で，GM以外のエンティティは署名者を追跡できない．

• DLDH仮定より，$T_1, T_2, T_3$から，$(A_x, x)$を見つけることはできない．
• 離散対数の保有に関する知識の証明より， $(T_1, T_2, T_3, c, s_{\alpha}, s_{\beta}, s_x, {\delta_1}, {\delta_2})$から，$(A_x, x)$を見つけることはできない．

※要追記

リンク不可能性

以下の理由で，GM以外のエンティティは署名者の署名$\sigma, \sigma'$を紐付けられない．

$\sigma = (T_1, T_2, T_3, c, s_{\alpha}, s_{\beta}, s_x, {\delta_1}, {\delta_2})$
$\sigma' = (T_1', T_2', T_3', c', s_{\alpha}', s_{\beta}', s_x', {\delta_1}', {\delta_2}')$

• DLDH仮定より，$T_1', T_2', T_3'$と$T_1', T_2', T_3'$を紐付けることができない．
• 離散対数の保有に関する知識の証明より， $(T_1, T_2, T_3, c, s_{\alpha}, s_{\beta}, s_x, {\delta_1}, {\delta_2})$と$(T_1', T_2', T_3', c', s_{\alpha}', s_{\beta}', s_x', {\delta_1}', {\delta_2}')$を紐付けることができない．

※要追記

追跡可能性

署名$\sigma$の$T_1, T_2, T_3$ は 秘密鍵$\xi_1, \xi_2$による$A_x$の暗号文である.
よってGMは署名$\sigma$から$A_x$を計算することができる.

まとめ

正当性， 偽造不可能，匿名・リンク不可能， 追跡可能， 失効可能を同時に満たすため,利用されるグループ署名方式について解説した．