Boneh–Franklin scheme

Protocol description

Setup

The public key generator (PKG) chooses:

1. the public groups ${\displaystyle G_1}$ (with generator ${\displaystyle P}$) and ${\displaystyle G_2}$ as stated above, with the size of ${\displaystyle q}$ depending on security parameter ${\displaystyle k}$,
2. the corresponding pairing ${\displaystyle e}$,
3. a random private master-key ${\displaystyle K_m=s\in {\mathbb{Z}}_q^{\ast }}$,
4. a public key ${\displaystyle K_{pub}=sP}$,
5. a public hash function ${\displaystyle H_1:{\left\{0,1\right\}}^{\ast }\to G_1^{\ast }}$,
6. a public hash function ${\displaystyle H_2:G_2\to {\left\{0,1\right\}}^n}$ for some fixed ${\displaystyle n}$ and
7. the message space and the cipher space ${\displaystyle \mathcal{M}={\left\{0,1\right\}}^n,\mathcal{C}=G_1^{\ast }\times {\left\{0,1\right\}}^n}$

Extraction

To create the public key for ${\displaystyle ID\in {\left\{0,1\right\}}^{\ast }}$, the PKG computes

1. ${\displaystyle Q_{ID}=H_1\left(ID\right)}$ and
2. the private key ${\displaystyle d_{ID}=s{Q}_{ID}}$ which is given to the user.

Encryption

Given ${\displaystyle m\in \mathcal{M}}$, the ciphertext ${\displaystyle c}$ is obtained as follows:

1. ${\displaystyle Q_{ID}=H_1\left(ID\right)\in G_1^{\ast }}$,
2. choose random ${\displaystyle r\in {\mathbb{Z}}_q^{\ast }}$,
3. compute ${\displaystyle g_{ID}=e\left(Q_{ID},K_{pub}\right)\in G_2}$ and
4. set ${\displaystyle c=\left(rP,m\oplus H_2\left(g_{ID}^r\right)\right)}$.

Note that ${\displaystyle K_{pub}}$ is the PKG's public key and thus independent of the recipient's ID.

Decryption

Given ${\displaystyle c=\left(u,v\right)\in \mathcal{C}}$, the plaintext can be retrieved using the private key:

${\displaystyle m=v\oplus H_2\left(e\left(d_{ID},u\right)\right)}$

Correctness

The primary step in both encryption and decryption is to employ the pairing and ${\displaystyle H_2}$ to generate a mask (like a symmetric key) that is xor'ed with the plaintext. So in order to verify correctness of the protocol, one has to verify that an honest sender and recipient end up with the same values here.

The encrypting entity uses ${\displaystyle H_2\left(g_{ID}^r\right)}$, while for decryption, ${\displaystyle H_2\left(e\left(d_{ID},u\right)\right)}$ is applied. Due to the properties of pairings, it follows that:

${\displaystyle \begin{array}{cc}{H}_2\left(e\left(d_{ID},u\right)\right)& =H_2\left(e\left(s{Q}_{ID},rP\right)\right)\\ & =H_2\left(e{\left(Q_{ID},P\right)}^{rs}\right)\\ & =H_2\left(e{\left(Q_{ID},sP\right)}^r\right)\\ & =H_2\left(e{\left(Q_{ID},K_{pub}\right)}^r\right)\\ & =H_2\left(g_{ID}^r\right)\end{array}}$

Security

The security of the scheme depends on the hardness of the bilinear Diffie-Hellman problem (BDH) for the groups used. It has been proved that in a random-oracle model, the protocol is semantically secure under the BDH assumption.

Improvements

BasicIdent is not chosen ciphertext secure. However, there is a universal transformation method due to Fujisaki and Okamoto that allows for conversion to a scheme having this property called FullIdent.