BDH ⇒ IBE (random oracle model)

Fully-black-box reduction · random oracle model · BF01 · security loss: factor $O(q_E{q}_{H_2})$ for BasicIdent with $q_E$ key queries and $q_{H_2}$ queries to $H_2$: IND-ID-CPA advantage $\epsilon$ gives BDH advantage at least $\epsilon /(\mathrm{e}(1+q_E)q_{H_2})$

Statement

If the computational BDH assumption holds and the hash functions are modelled as random oracles, the Boneh–Franklin scheme FullIdent is an IND-ID-CCA-secure IBE and BasicIdent is IND-ID-CPA-secure — BF01.

Sketch

In BasicIdent the master public key is $g^s$, the key of $id$ is $H_1(id{)}^s$, and $m$ encrypts to $(g^r,m\oplus H_2(e(H_1(id),g^s{)}^r))$. The reduction embeds a BDH instance $(g^a,g^b,g^c)$ as $g^s:=g^a$, the challenge’s $g^r:=g^b$ and $H_1({id}^{\ast }):=g^c$ for a guessed target identity, programming $H_1(id):=g^x$ with known $x$ elsewhere so that it can answer key queries. An adversary with non-negligible advantage must query $H_2$ at $e(g,g{)}^{abc}$, which the reduction picks from its list of $H_2$ queries; FullIdent adds the Fujisaki–Okamoto transform for chosen-ciphertext security — BF01.

Notes

• A BasicIdent ciphertext on an $n$-bit message is one element of $\mathbb{G}$ and an $n$-bit string, and FullIdent adds a second $n$-bit string; decryption computes one pairing — BF01.