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:
  • e(P,P)abc.

  • BDH問題 ≦ CDH問題

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:
    • H : {0,1}* → G1*
  • 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スキーム

文献 [Waters 05]
  • 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
  • skI = (msk・H(u,I)r, g2r)

Enc (pk, ID, M) :
  • (M・e(A1, B2)s, g2s, H(u,I)s).

























最終更新:2012年03月06日 17:57