DBDH ⇒ IBE (Waters, standard model)

Fully-black-box reduction · standard model · Wat05 · security loss: a factor O(n q) in advantage for n-bit identities and q key queries, from the chance that the partition answers every key query and embeds the challenge; the artificial abort adds running time polynomial in nq/ε

Statement

If decisional BDH holds in a symmetric pairing group, there is an IND-ID-CPA-secure IBE scheme in the standard model: for $n$-bit identities the public parameters are $g,g_1=g^{\alpha },g_2,u^{\prime }$ and $u_1,\dots ,u_n$, the key for $v$ is $(g_2^{\alpha }(u^{\prime }{\prod }_{i:v_i=1}{u}_i{)}^r,g^r)$, and a ciphertext is $(e(g_1,g_2{)}^{t}M,g^t,(u^{\prime }{\prod }_{i:v_i=1}{u}_i{)}^t)$ — Wat05.

Sketch

The reduction chooses $u^{\prime }$ and the $u_i$ so that $u^{\prime }{\prod }_{i:v_i=1}{u}_i=g_2^{F(v)}{g}^{J(v)}$ for functions $F,J$ it knows. It can answer key queries on identities with $F(v)\ne 0\mathrm{mod}p$ and can embed its challenge only where $F(v^{\ast })=0$; choosing $F$ at random from a small range makes this split occur with probability about $1/(nq)$ — Wat05.

Notes

• Efficiency: the public parameters have $n+4$ group elements, keys two and ciphertexts two plus one target-group element; decryption costs two pairings — Wat05.
• With selective security, where the challenge identity is fixed before setup, a scheme with constant-size parameters follows from the same assumption: DBDH ⇒ selectively secure IBE — BB04b.
• In the random-oracle model, computational BDH suffices: BDH ⇒ IBE — BF01.