DBDH ⇒ Selectively secure IBE (Boneh–Boyen)

Fully-black-box reduction · standard model · BB04b · security loss: none: the reduction answers every key query and embeds its tuple in the challenge

Statement

If decisional BDH holds in a symmetric pairing group, there is an IND-sID-CPA-secure IBE scheme in the standard model, with identities in ${\mathbb{Z}}_p$: the public parameters are $g,g_1=g^{\alpha },g_2,h$, the key for $id$ is $(g_2^{\alpha }(g_1^{id}h{)}^r,g^r)$, and a ciphertext is $(e(g_1,g_2{)}^{s}M,g^s,(g_1^{id}h{)}^s)$ — BB04b.

Sketch

Given the DBDH tuple $(g,g^a,g^b,g^c,T)$ and the committed identity ${id}^{\ast }$, the reduction sets $g_1=g^a$, $g_2=g^b$ and $h=g_1^{-{id}^{\ast }}{g}^d$ for a uniform $d$. For $id\ne {id}^{\ast }$, $g_1^{id}h=g_1^{id-{id}^{\ast }}{g}^d$ and a key can be computed without $g^{ab}$; for ${id}^{\ast }$ it is $g^d$, so the challenge $(T{M}_{\beta },g^c,(g^c{)}^d)$ is a valid encryption exactly when $T=e(g,g{)}^{abc}$ — BB04b.

Notes

• Selective security over an identity space $\mathcal{I}$ gives adaptive security with loss $|\mathcal{I}|$ by guessing (selective ⇒ adaptive IBE) — BB04b; for exponentially many identities Waters’ scheme proves adaptive security directly — Wat05.
• Selectively secure IBE gives IND-CCA2-secure PKE: IND-sID-CPA IBE ⇒ CCA2 PKE — CHK04.