属性ベース暗号 - 暗号理論教室

---

属性ベース暗号（鍵ポリシー型）の機能

• 暗号文は、いくつかの属性の集合γでラベル付けされる。
• 復号鍵は、アクセス構造Aを表現する。
• 暗号文の属性集合γが復号鍵のアクセス構造Aを満たす γ∈A ときのみ、復号できる。- ただし、対象とできるアクセス構造は単調なもの。

属性ベース暗号（鍵ポリシー型）スキーム

ABE = (Setup, Enc, KeyGen, Dec)：

• (PK, MK) ← Setup
• E ← Enc(PK, m, γ)
• D ← KeyGen(PK, A, MK)
• m/⊥ ← Dec(PK, D, E)

完全性 (completness)

∀(PK, MK) ← Setup
∀A : アクセス構造
∀D ← KeyGen(PK, A, MK)
∀γ：属性集合、∀m, ∀E ← Enc(PK, m, γ)
について

• γ∈A ならば Dec(PK, D, E) = m.

属性ベース暗号（鍵ポリシー型）の安全性

ポイントは結託耐性。様々なアクセス構造A_jに対応する秘密鍵D_jをかき集めてきても、γ not∈ ∪_j A_jであるならば、そのようなγを属性集合とする暗号文の復号には、秘密鍵の集まり∪_jD_jはまったく役立たないこと。

ゲーム

• 攻撃者Aを起動し、ターゲットとなる属性集合γを得る。
• (PK, MK) ← Setupを実行し、PKをAに渡す。
• Aが望むだけ以下を複数回繰り返す： 　　　　※　秘密鍵クエリ
  • 攻撃者Aがアクセス構造A_jに対応する秘密鍵を要求したら、
    • γがA_jを満たさないことを確認する。
    • D_j ← KeyGen(PK, A_j, MK)を実行し、D_jをAに渡す。
• 攻撃者Aより２つの平文M₀, M₁ を受け取り、 　　　※　チャレンジクエリ
  • b ← {0,1}、　E ← Enc(PK, M_b, γ)
  • Eを返す。
• Aが望むだけ以下を複数回繰り返す： 　　　　※　秘密鍵クエリ
  • 攻撃者Aがアクセス構造A_jに対応する秘密鍵を要求したら、
    • γがA_jを満たさないことを確認する。
    • D_j ← KeyGen(PK, A_j, MK)を実行し、D_jをAに渡す。
• Aはb'を出力して停止する。

攻撃者Aのアドバンテージ：

• Adv_A(s) =^def | Pr[b=b'] - 1/2 |

定義

属性ベース暗号 ABE = (Setup, Enc, KeyGen, Dec) が選択的属性集合攻撃に対し識別不可能であるとは、どのような効率的な攻撃者Aについても上記のゲームにおけるアドバンテージAdv_A(s)が無視可能であることを云う。

属性ベース暗号の構成1

アクセス構造

アクセス構造は木 T で表現：

• 各内部ノードxは閾値ゲート
  • num_x : ノードxの子ノードの数。
  • k_x : ノードxの閾値。（0 ＜ k_x ≦ num_x）

γ∈Tの判定：

• すべての葉ノードを偽に初期化。
• 属性集合γに含まれる各属性について、対応する葉ノードを真にセット。
• 上位ノードに値を再帰的に伝播。
• ルートノードの真偽を出力。

記号:

• parent(x) : xの親ノード
• att(x) : 葉ノードxについてのみ定義。属性を表す。
• index(x) : xの子ノードとしてのインデックス。

部品

• 双線形写像 e : G₁ x G₁ → G₂, 　 #G₁ = #G₂ = 素数p
• ラグランジュ係数 {Δ_i,S(x)}_i∈S
  • S ⊆ Z_p
  • i ∈ S,　 Δ_i,S(x) =^def Π_j∈S,j≠i (x - j) / (i - j).
    • 次数が#S-1以下の任意の多項式q(x)について、Σ_i∈S q(i)Δ_i,S(x) = q(x) となる。

構成

Setup (n) :

• y ← Z_p,　g₁ = g^y, 　g₂ ← G₁
• t₁, ・・・, t_n+1 ← G₁
• N = {1, 2, ・・・, n+1}
• return PK = (g₁,g₂,t₁,・・・,t_n+1), MK = y.
• ※ T(X) =^def g₂^X_n Π_i=1,...,n+1t_i^Δ_i,N(X)　 ( = g₂^Xn g^h(X) with deg h = n+1 )
• ※ T(i) = g₂ⁱⁿ t_i 　　for i ∈ N

Enc (m, γ, PK) :

• s ← Z_p
• return E = (γ, E' = m・e(g₁,g₂)^s, E'' = g^s, {E_i = T(i)^s }_i∈γ ).

KeyGen (T, MK, PK) :

• ※ Tの各ノードxに次数d_xの多項式q_xを配置
• Tの各ノード x ： d_x = k_x - 1
• ルートノード r ： 　　※ 主秘密をルートノードにセット
  • q_r(0) = y,
  • 他の任意のd_r個の点における値をランダムに選択。
• その他のノード x ： 　　※ 親ノードparent(x)の秘密情報を子ノードxに分散
  • q_x(0) = q_parent(x)(index(x)), 　　
  • 他の任意のd_x個の点における値をランダムに選択。
• ※ Then
• 各葉ノード x ：　　※ 各葉ノードの秘密情報q_x(0)を暗号化。これにより、ルートの秘密情報である主秘密を復元できないようにする。
  • r_x ← Z_p, 　D_x = g₂^q_x(0)T(i)^r_x,　　R_x = g^r_x　　
• return D = { (D_x, R_x) }_{x : 葉ノード}.

Dec (E, D) :

• return E' / DecNode(E, D, r).　　※ rはルートノード

DecNode (E=(γ,E',E'',{E_i}), D= {(D_x,R_x)}, x) :

• x : 葉ノード ：
  • i = att(x) ∈^? γ：
    • return e(D_x, E'') / e(R_x, E_i)
  • else return ⊥
• else // x : 内部ノード
  • z ：xの子ノード：
    • F_z = DecNode(E,D,z)
  • S_x ← F_z≠⊥である子ノードzからなる、任意の要素数k_xの集合
• return Π_z∈SxF_z^{Δ_{i=index(z),index(Sx)}(0)}

スキームの観察

暗号文

• E = (γ, E' = m・e(g₁,g₂)^s, E'' = g^s, {E_i = T(i)^s }_i∈γ )

において、mを直接隠しているのは、G₂要素である

• e(g₁, g₂)^s

これは、

• e(E'', g₂)^y

に等しい。

MK = y は秘密鍵Dの構成において、ルートノードにセットされ、それが再帰的に子ノードに秘密分散されて秘密鍵Dの値となった。

分散先である各葉ノードでT(i)^sなどを用いて、

• e(E'', g₂)^q_x(0)

を得る。これらは再帰的にe(E'', g₂)^yを構成する。

定理 (ABE)

判定双線形ディフィー・ヘルマン仮定が成り立つならば、ABEは選択的属性集合攻撃に対し識別不可能である。

構成2

Large Universe Construction [Waters 11]

Setup () :

• Choose a group G of prime order p with generator g
• α, a 　←　Z_p
• Choose a hash function H : {0,1}* → G
• PK = (g, e(g,g)^α, g^a),　MSK = g^α.

Encrypt (PK, (M,ρ), PT) : 　　※ M : l x n

• s, y₂,・・・, y_n 　←　Z_p
• i ∈ [1..l] : λ_i = (s, y₂,・・・, y_n)・M_i
• r₁,・・・, r_l 　←　Z_p
• CT = (C = PT・e(g,g)^αs, C' = g^s, (C_i = g^aλ_i H(ρ(i))^-r_i, D_i = g^r_i)_i=1,...,l).

KeyGen (MSK, S) :

• t 　←　Z_p
• SK = (K = g^αg^at, L = g^t, (K_x = H(x)^t)_x∈S).

Decrypt(CT, SK) :

• I = {i : ρ(i)∈S}
• {ω_i}_i∈I : the set of constants for I
• ※ Σ_i∈I ω_i M_i = (1,0,・・・, 0)
• return C・e(C', K)^-1・Π_i∈I { e(C_i, L)・e(D_i, K_ρ(i)) }^ω_i.

定理 (Large Universe Construction)

判定q-平行BDHE仮定が成り立つならば、Large Universe Constructionは選択的攻撃に対し識別不可能である。

Bethencourt-Sahai-Waters

• PK = (g, h = g^β, f = g^1/β, e(g,g)^α)
• MK = (β, g^α)
• 暗号文
  • (M・e(g,g)^αs, h^s, (g^s_y, H(att(y))^s_y)_y∈Y)
• 属性集合鍵
  • (g^(α+r)/β, (g^rH(j)^r_j, g^r_j)_j∈S)

文献

• [GPSW 06]
• [Waters 11]

上へ

---