• ホーム
• 情報セキュリティ
• 暗号技術

IDベース暗号・署名

IDベース暗号方式

IDベース暗号

IDベース暗号方式では，鍵発行センタが各ユーザの ID に対応した秘密鍵を発行し，各ユーザへ秘密裏に配布する．ユーザ $A$ がユーザ $B$ に暗号文を送る場合，ユーザ $B$ の固有の ID（$ID_B$ と以下略記）を公開鍵として暗号化することができ，ユーザ $B$ は鍵センタから配布を受けた $ID_B$ に対応する秘密鍵を用いて復号できる．

ID としてメールアドレスなどの公知のものが使われる．秘密鍵の配布を受けるのは暗号文を受け取ってからでも良い．送信者側から見れば，ID さえ知っておけば相手からあらかじめ公開鍵を入手しなくても暗号化して送付できる，公開鍵が誰のものか証明するために公開鍵証明書を不要とできるなどの利便性がある．

• 概要
  IDベース暗号は次のアルゴリズムから構成される．
  • 準備 ($\mathrm{SetUp}$):
    セキュリティパラメータ $k$ に対して，公開されるシステムパラメータ $params$ とマスタ秘密鍵 $mk$ を生成する．
  • 鍵生成 ($\mathrm{KeyGen}$):
    システムパラメータ $params$ とマスタ秘密鍵 $mk$ を用いてユーザIDに対する秘密鍵 $sk$ を生成する．
  • 暗号化 ($\mathrm{Enc}$):
    システムパラメータ $params$ とユーザIDを用いて平文 $M$ に対する暗号文 $C$ を生成する．
  • 復号 ($\mathrm{Dec}$):
    システムパラメータ $params$ と秘密鍵 $sk$ を用いて，暗号文 $C$ を復号する．
• アルゴリズム
  
  • $\mathrm{SetUp} (k)$：
    セキュリティパラメータ $k$ に対して，ランダムな生成元 $P \in G_1$ を選択する． また，ランダムな $s \in {Z_p}^*$ を選び，$S = s P$ を計算する．
    $params = (P, S, p)$ は，公開のシステムパラメータであり，$s$ はマスタ秘密鍵，$S$ はマスタ公開鍵である．
    以下の2つのハッシュ関数を用意する．

    $\mathrm{H_1}$ : $\{0, 1\}^* \rightarrow G_1$

    $\mathrm{H_2}$ : $G_2 \rightarrow \{0, 1\}^n$

    $G_2$ は，ペアリング演算結果の体 $(G_1 \times G_1 \rightarrow G_2)$ である．
  • $\mathrm{KeyGen} (s, params, ID)$：
    マスタ秘密鍵 $s$ を用いてユーザIDに対する秘密鍵 $sk_{ID}$ を生成する．

    $Q_{ID} = \mathrm{H_1}(ID)$

    $sk_{ID} = s Q_{ID}$

  • $\mathrm{Enc} (ID, params, M)$：
    ユーザIDに対して平文 $M \in \{0, 1\}^n$ の暗号文 $C_{ID}$ を生成する． ここで，任意の乱数 $r \in {Z_p}^*$ を用いる．

    $C_{ID} =$ < $r P, M \oplus \mathrm{H_2}(e(Q_{ID}, S)^r)$ >

  • $\mathrm{Dec} (sk_{ID}, params, C_{ID})$：
    $sk_{ID}$ と暗号文 $C_{ID}=$ < $U, V$ > を用い，以下の式により復号し平文 $M$ を求める．

    $V \oplus \mathrm{H_2}(e(sk_{ID}, U)) = M$

IDベース署名方式

IDベース署名方式では，IDベース暗号システムと同様に鍵発行センタが，各ユーザの ID に対応した署名用の秘密鍵を発行し，各ユーザへ秘密裏に配布する．ユーザ $A$ にユーザ $B$ が署名付き文書を作成して送る場合，ユーザ $B$ に配布された署名用の秘密鍵を利用して行い，署名付き文書を受け取ったユーザ $A$ は，ユーザ $B$ の固有の ID を公開鍵として署名検証ができる．このため相手の ID さえ知っておけば，相手から公開鍵を入手する必要はなく，公開鍵が誰のものか証明するために公開鍵証明書も不要とできるなどの利便性がある．

DHI 署名

DHI Signature(P1363.3/D1)のアルゴリズムを示す．

• $\mathrm{DHI.Setup}$:
  • 双線形写像 $e: G_1 \times G_2 \rightarrow G_3$ をもつ素数位数 $q$ の群 $G_1$，$G_2$，$G_3$ を生成する．
  • 任意の生成元 $Q_2 \in G_2$ を選択する． $Q_1 = φ(Q_2) \in G_1$ を求める．
  • 乱数 $s \in {Z_p}^*$ を選択し，$R = s Q_2$ を計算する．
  • ペアリング値 $V = e(Q_1, Q_2)$ を事前計算する．
  • 公開パラメータを $P = (R, V, Q_1, Q_2, G_1, G_2, G_3, e)$ とする．また，$s$ を秘密情報とする．
  また，以下の2つのハッシュ関数を用意する．

  $\mathrm{H_1} : \{0, 1\}^* \rightarrow Z_p$

  $\mathrm{H_2} : \{0, 1\}^* \rightarrow Z_q$

• $\mathrm{DHI.Extract}$:
  ユーザの識別子 $ID$ から対応する秘密鍵 $K_{ID}$ を生成する．
  • $M = \mathrm{H_1}(ID)\ (\in Z_p)$
  • $K_{ID} = (M + s)^{-1} Q_1$
• $\mathrm{DHI.Sign}$:
  ユーザの秘密鍵 $K_{ID}$ と公開鍵要素 $M$ とからメッセージ $m$ に対する署名を生成する．
  • $u = e(Q_1, Q_2)^r$
  • $h = \mathrm{H_2}(m, u)$
  • $S = (r + h) K_m$　($r$ は乱数)
  • 署名 $(h, S)$ を出力
• $\mathrm{DHI.Verify}$:
  公開パラメータ $P$，公開鍵要素 $M$，署名 $(h, S)$ を入力とし，署名を検証する．
  • 以下を計算する．

    $u = e(S, M Q_2 + R) / e(Q_1, Q_2)^h$

  • $h = \mathrm{H_2}(m, u)$ ならば検証 OK ,さもなくば NG を出力する．

BLS 署名

Boneh, Lynn および Shachamによる署名アルゴリズムを示す．

• $\mathrm{BLS.Setup}$:
  • セキュリティパラメータ $k$ を元に，双線形写像 $e: G_1 \times G_1 \rightarrow G_2$ をもつ素数位数 $q$ の群 $G_1$，$G_2$ を生成する．
  • 任意の生成元 $P \in G_1$ を選択する．
  • 以下のハッシュ関数を選択する．

    $\mathrm{H} : \{0, 1\}^* \rightarrow {G_1}^*$

  システムパラメータ $params$ は，$(G_1, G_2, e, P, \mathrm{H})$ である．
• $\mathrm{BLS.Extract}$:
  システムパラメータ $params$ を元に，乱数 $x \in {Z_q}^*$ を選択し，鍵ペア $(SK, PK) = (x, x P)$ を生成する．
• $\mathrm{BLS.Sign}$:
  秘密鍵 $SK$ とメッセージ $m \in \{0, 1\}^*$ から署名 $σ = x \mathrm{H}(m)$ を出力する．
• $\mathrm{BLS.Verify}$:
  署名 $σ$ とメッセージ $m$ より，以下の関係が成り立つか否かで署名を検証する．

  $e(PK, \mathrm{H}(m))\ ?= e(P, σ)$

IDベース署名 (Cha and Cheon)

• $\mathrm{IBS.Setup}$:
  • セキュリティパラメータ $k$ を元に，双線形写像 $e: G_1 \times G_1 \rightarrow G_2$ をもつ素数位数 $q$ の群 $G_1$，$G_2$ を生成する．
  • 任意の生成元 $P \in G_1$ を選択する．
  • 乱数 $s \in Z_q$ を選択し，$P_{pub} = s P$ を計算する．
  • 以下の2つのハッシュ関数を選択する．

    $\mathrm{H_1} : \{0, 1\}^* \rightarrow G_1$

    $\mathrm{H_3} : \{0, 1\}^* \times G_1 \rightarrow Z_q$

  システムパラメータは，$(G_1, G_2, e, P, P_{pub}, \mathrm{H_1}, \mathrm{H_3})$ であり， $s$ はマスタ秘密鍵である．
• $\mathrm{IBS.Extract}$:
  $ID$ 情報から対応する公開鍵 $Q_{ID}$ と秘密鍵 $D_{ID}$ を計算する．
  • 公開鍵を $Q_{ID} = \mathrm{H_1}(ID)$ として計算する．
  • 秘密鍵を $D_{ID} = s Q_{ID}$ として計算する．
• $\mathrm{IBS.Sign}$:
  秘密鍵 $D_{ID}$ とメッセージ $m$ から署名 $σ = (U, V)$ を生成する．
  • 乱数 $r \in Z_q$ を生成し，$U = r Q_{ID}$ を計算する．
  • $h = \mathrm{H_3}(m, U)$ を計算する．
  • $V = (r + h) D_{ID}$ を計算する．
  • 署名 $σ$ を $σ = (U, V)$ とする．
• $\mathrm{IBS.Verify}$:
  署名 $σ = (U, V)$ とメッセージ $m$ より，以下の関係が成り立つか否かで署名を検証する．

  $e(P_{pub}, U + h Q_{ID})\ ?= e(P, V)$

  ここで，$h = \mathrm{H_3}(m, U)$ である．

／