IDベース暗号
IBE = (Setup, Extract, Enc, Dec):
- (params, master_key) ← Setup
- dID ← Extract(params, master_key, ID)
- C ← Enc(params, ID, M)
- M ← Dec(params, C, dID)
完全性 (completness)
∀(params, master_key) ← Setup
∀ID, ∀m
- Dec(params, Enc(params, ID, M), Extract(params, master_key, ID)) = m.
IND-ID-CPA
ゲーム
- params を入力として攻撃者Aを起動する。
- Aが望むだけ以下を複数回繰り返す: ※ 秘密鍵クエリ
- 攻撃者AがIDiの秘密鍵を要求したら、
- di ← Extract(params, master_key, IDi)をAに渡す。
- 攻撃者Aより2つの平文M0, M1とID を受け取り、 ※ チャレンジクエリ
- b ← {0,1}、 E ← Enc(params, ID, Mb)
- Eを返す。
- Aが望むだけ以下を複数回繰り返す: ※ 秘密鍵クエリ
- 攻撃者AがIDiの秘密鍵を要求したら、
- ID≠IDiを確認。
- di ← Extract(params, master_key, IDi)をAに渡す。
- Aはb'を出力して停止する。
攻撃者Aのアドバンテージ:
- AdvA(s) =def | Pr[b=b'] - 1/2 |
注意:
- IDをひとつに固定してしまえば、公開鍵暗号IBEIDとなる。 IBEIDがIND-CPAであること。
- 問題は、各IBEIDが干渉し合わないこと。 →結託耐性。
- 可能なIDの個数に上限がない場合が本質的。
BDH問題
Given:
- (q, G1, G2, e, P, aP, bP, cP),
Find:
Cocksスキーム
Setup (1k) :
- (N, p, q) ← GenBlumMod(1k)
- Choose H : {0,1}* → JN*
- params = N, masterk_key = (p, q).
Extract (ID, master_key, params) :
- a0 = H(ID), a1 = - H(ID)
- return skID = a0 または a1 の平方根.
Enc (params, ID, x) : ※ x = -1 or 1
- t0 ← ZN* s.t. (t0/N) = x
- a0 = H(ID)
- c0 = t0 + a0 / t0
- t1 ← ZN* s.t. (t1/N) = x
- a1 = - H(ID)
- c1 = t1 + a1 / t1
- return c = (c0, c1).
Dec (params, c = (c0, c1), skID = r) :
- a = H(ID)
- r2 =? a : y = c0 + 2 r
- else y = c1 - 2 r
- return x = (y / N).
Boneh-Franklinスキーム
Setup (1k) :
- (q, e, G1, G2) ← Grp(1k), P ← G1
- s ← Zq, Ppub = sP
- Choose:
- params = (P, Ppub), masterk_key = s.
Extract (ID, master_key = s, params) :
- ※ DH組のパラレルワールド
- QID = H(ID)
- return dID = s QID.
Enc (params, ID, M) :
- QID = H(ID)
- ※ G2へワープ
- gID = e(QID, Ppub)
- r ← Zq
- return C = (rP, M gIDr).
Dec (params, C = (U,V), dID) :
- return M = V e(dID, U)-1.
Completeness
- gIDr = e(QID, Ppub)r
- = e(QID, P)s r
- = e(dID, U)
観察
- IDを固定した公開鍵暗号BFIDは、DBDH仮定のもとでIND-CPA。
- 問題は、同じsをベースにしている、IDを変数とするパラレルワールドにおいて、BFID達が干渉をおこさず、独立であること。
- → 結託耐性。
定理
DBDH仮定がなりたつならば、Hについてのランダムオラクルモデルのもとで、Boneh-FranklinスキームはIND-ID-CPA。
Watersスキーム
- H(u, I) = u0 Πi=1..n uiIi
Setup (1k) :
- mpk = (g2, A1, B2, u = (u1,...,un))
- msk = A1b
KeyDer (msk, ID) : // ID ∈ {0,1}n
Enc (pk, ID, M) :
- (M・e(A1, B2)s, g2s, H(u,I)s).
最終更新:2012年03月06日 17:57