階層型IDベース暗号
階層型IDベース暗号方式
- 階層型IDベース暗号
階層型ID ベース暗号 (HIBE)は,IDベース暗号のセンタを階層化した方式である. HIBE はユーザID を木構造の各ノードに対応させた IDベース暗号で, ユーザ ID
に対応する秘密鍵はユーザの親が生成する. 階層 $t$ のユーザ $v$ を $v = v_1 \cdots v_t$ と表記し,その秘密鍵を $SK_v$ と表す (木のルートが $t = 1)$.このとき,HIBE
は次の性質を満たす.
- ユーザ $v\ (v = v_1 \cdots v_t)$ の秘密鍵 $SK_v$ はユーザ $v$ の親 $v_1 \cdots v_{t-1}$ が生成する.
- ユーザ $v\ (v = v_1 \cdots v_t)$ は自分の秘密鍵 $SK_v$ を用いて,子 $vv_{t+1} = v_1 \cdots v_{t+1}$ の鍵 $SK_{vv_{t+1}}$ を生成する.
このため,$v$ へ送付された暗号文は $v$ の祖先は全て開封できる性質をもつ.
HIBE は次の 4 つの確率的アルゴリズム (HIBE-KGen, HIBE-KDer, HIBE-Enc, HIBE-Dec) で構成される.
- $\mathrm{Setup}$:$\mathrm{HIBE-KGen}(S, t)$
入力のセキュリティパラメータ $S$ 及びユーザの階層 $t$ に対して,公開鍵 $PK$,ルートセンタの秘密鍵 $SK_e$ を出力する確率的多項式時間アルゴリズムである.
- $\mathrm{Extraction}$:$\mathrm{HIBE-KDer}(P, v, v_{t+1}, SK_v)$
公開鍵 $PK$, ユーザ ID $v\ (=v_1 \cdots v_l)$,ユーザ $v$ の秘密鍵 $SK_v$, ユーザ $v$ の子の ID $vv_{l+1}$ に対して
$vv_{l+1}$ の秘密鍵 $SK_{vv_{l+1}}$ を出力するアルゴリズムである.
- $\mathrm{Encryption}$:$\mathrm{HIBE-Enc}(PK, v, M)$
公開鍵 $PK$, ユーザ ID $v\ (= v_1 \cdots v_l)$, 平文 $M$ の入力に対し,暗号文 $C$ を出力する多項式時間アルゴリズムである.
- $\mathrm{Decryption}$:$\mathrm{HIBE-Dec}(SK_v, C, v)$
ユーザ $v$ の秘密鍵 $SK_v$ と暗号文 $C$ の入力に対し,平文 $M$ を出力する多項式時間アルゴリズムである.
- アルゴリズム
具体的なアルゴリズム例を示す.
- $\mathrm{Setup}$:
- セキュリティパラメータ $k$ を元に,双線形写像 $e : G_1 \times G_1 \rightarrow G_2$ を持つ素数位数 $q$ の群 $G_1$,$G_2$ を生成する.
- 任意の生成元 $P_0 \in G_1$ を選択する.
- 乱数 $s_0 \in Z_q$ を選択し,$Q_0 = s_0 P_0$ を計算する.
- 以下の2つのハッシュ関数を選択する.
$\mathrm{H_1} : \{0, 1\}^* \rightarrow G_1$
$\mathrm{H_2} : G_2 \rightarrow \{0, 1\}^n$
メッセージ(平文)空間は $M = \{0, 1\}^n$ であり,暗号文の空間は
$C = {G_1}^t \times \{0, 1\}^n$ になる.ここで,$t$ は受信者のレベル(階層)である.
システムパラメータは,$(G_1, G_2, e, P_0, Q_0, \mathrm{H_1}, \mathrm{H_2})$ である.
- $\mathrm{Lower\ level\ Setup}$:
レベル $t$ のエンティティ $E_t$ は $s_t \in Z_q$ をランダムに選択する.
- $\mathrm{Extraction}$:
$E_t$ を ID 情報 $(ID_1,\ldots,ID_t)$ を持つレベル $t$ のエンティティとする. また,$S_0$ を $G_1$ の単位元とする.
- $\mathrm{Encryption}$:
公開鍵 $P_i (i = 1,\ldots, t)$,ユーザ ID $(ID_1,\ldots,ID_t)$, 平文 $M$ の入力に対し,暗号文 $C$ を計算する.
- $P_i = \mathrm{H_1}(ID_1, \ldots, ID_i) \in G_1$ を計算する $(1 \le i \le t)$.
- 乱数 $r \in Z_q$ を選択する.
- 以下の暗号文 C を計算する.
$C =[r P_0, r P_2, \ldots, r P_t, M \oplus \mathrm{H_2}(g^r)],\quad g = e(Q_0, P_1)$
∈ G2
- $\mathrm{Decryption}$:
秘密情報 $S_t$ ,ユーザID $(ID_1, \ldots , ID_t)$ で暗号化された暗号文
$C = [U_0, U_2 , \ldots , U_t, V]$ に対し,平文 $M$ を以下により計算する.
$V \oplus \mathrm{H_2}(e(U_0, S_t) / \prod_{i=2}^t e(Q_{i-1}, U_i)) = M$
階層型IDベース署名方式
階層型IDベース署名は,階層型ID ベース暗号と同様に IDベース署名を階層化した方式である.
階層型IDベース署名のアルゴリズム例を示す.
- アルゴリズム
- $\mathrm{Setup}$
- セキュリティパラメータ $k$ を元に,双線形写像 $e : G_1 \times G_1 \rightarrow G_2$ を持つ素数位数 $q$ の群 $G_1$,$G_2$ を生成する.
- 任意の生成元 $P_0 \in G_1$ を選択する.
- 乱数 $s_0 \in Z_q$ を選択し,$Q_0 = s_0 P_0$ を計算する.
- 以下の2つのハッシュ関数を選択する.
$\mathrm{H_1} : \{0, 1\}^* \rightarrow G_1$
$\mathrm{H_3} : \{0, 1\}^* \rightarrow G_1$
署名空間は $S = {G_1}^{t+1} \times \{0, 1\}^n$ になる.ここで,$t$ は署名者のレベル(階層)である. システムパラメータは,$(G_1, G_2, e, P_0, Q_0,
\mathrm{H_1}, \mathrm{H_3})$ である.
- $\mathrm{Lower\ level\ Setup}$
レベル $t$ のエンティティ $E_t$ は $s_t \in Z_q$ をランダムに選択する.
- $\mathrm{Extraction}$
$E_t$ を ID情報 $(ID_1, \ldots, ID_t)$ を持つレベル $t$ のエンティティとする.
$S_0$ を $G_1$ の単位元とする.
- $\mathrm{Signing}$
ID 情報 $(ID_1, \ldots, ID_t)$ でメッセージ $M$ を以下の手順で署名する.
- $P_M = \mathrm{H_3}(ID_1, \ldots, ID_t, M) \in G_1$ を計算する.
- 署名 $Sig(ID_1, \ldots, ID_t, M) = S_t + s_t P_M$ を計算する.
- 署名 $Sig(ID_1, \ldots, ID_t, M)$ と $Q_i = s_i P_0\ (i = 1, \cdots, t)$ を検証者に送る.
- $\mathrm{Verification}$
署名 $[Sig, Q_1, \ldots , Q_t] \in S$ に対し,署名検査を以下の式を検証することにより行う.
\[ e(P_0, Sig) = e(Q_0, P_1) e(Q_t, P_M) \prod_{i=2}^t e(Q_{i-1},P_i) \]