Fuzzy IDベース暗号
その中身を見ていく
安全性はDBDH（Decisional Bilinear Diffie-Hellman）仮定
1. 最初のパラメータ設定をするセットアップアルゴリズム．
指定された属性集合のうち何個属性を持っていると復号できるかという下限を $ kとする．
楕円曲線$ Eと位数 $ p の巡回群 $ G とペアリング $ e : E × E → Gを用意する．
$ P,Q ∈ Eと $ y ∈ \mathbb{F}p をとり，$ R := yP とする．
$ y が秘密鍵で $ P, Q,R が公開鍵
属性を「部署名」などの文字列とし，属性の集合から$ E へのハッシュ関数を $ H とする．
2. 属性集合 $ ω_u を持つユーザ$ uに対して秘密鍵 $ K_{ω_u} を生成する鍵生成アルゴリズム．
まず $ k − 1 次の $ Fp 係数多項式で定数項が $ y である $ q_u(x) をランダムに選ぶ($ q_u(0) = y)
$ q_u(x)=y+a_1x+a_2x^2+...+a_{k-1}x^{k-1}
$ ω_u の i 番目の属性 $ a_i に対して $ r_i ∈ F_p をランダムに選び，$ P_i:= r_iP,$ D_i:= q_u(i)Q + r_iH(a_i) とする
$ K_{ω_u}:= {\{ P_i, D_i \} }_{\{ i=1,..., | ω_u| \}}だけをユーザ $ u に渡す
3. 平文$ mを属性集合 ω で暗号化するアルゴリズム $ Enc(m, ω)
属性集合 $ ω を選び，平文 $ m ∈ G を暗号化する．
$ s ∈ Fp をランダムに選び
$ Enc(m, ω) := (ω, t := m · e(R, Q)s, T := sP, Ei:= sH(a_i)_{\{ i=1,...,|ω| \}})
と暗号化する．
これにより$ ω の中のどれか $ k 個の属性を持っている人だけが復号できる
4. ユーザ$ uの属性集合 $ ω_u と暗号化に使われた属性集合 $ ω に対して $ |ω_u ∩ ω| ≥ kならば復号するアルゴリズム．
属性集合 $ ω_u を持つユーザ $ u は $ |ω ∩ ω_u| ≥ k を確認する
成立しなければ復号できない
成立する場合は共通部分の中から $ k 個適当に属性を選びその集合を $ S とする．($ S ⊆ ω ∩ ω_u, |S| = k )
復号は以下のペアリング計算になる
$ z =∏_{a_i∈S} (\frac{e(T, D_i)}{e(P_i, E_i)})^{∆_i,S (0)}$ =∏_{a_i∈S}(\frac{e(sP, q_u(i)Q + r_iH(a_i))}{e(r_iP, sH(a_i))})^{∆_i,S (0)}$ =∏_{a_i∈S}(\frac{e(P,Q)^{sq_u(i)}e(P, H(a_i))^{sr_i}}{e(P, H(a_i))^{sr_i}})^{∆_i,S (0)}$ =∏_{a_i∈S}(e(P, Q)^{sq_u(i)})^{∆_i,S (0)}$ = e(P, Q)^{(∑_{{a_i}∈S}q_u(i)∆i,S (0))s}
Lagrange の補間多項式を使って
$ = e(P, Q)^{q_u(0)s} = e(P, Q)^{ys}
$ t = m · e(yP, Q)^s = m · e(P, Q)^{ys} = mz
なので$ t/z = m
と復号できる
一般化すると$ Dec(Enc(m, ω), ωu) = m
参考文献