Setup The public key generator (PKG) chooses: • the public groups \textstyle G_1 (with generator \textstyle P) and \textstyle G_2 as stated above, with the size of \textstyle q depending on security parameter \textstyle k, • the corresponding pairing \textstyle e, • a random private master-key \textstyle K_m = s \in \mathbb{Z}_q^*, • a public key \textstyle K_{pub} = sP, • a public hash function \textstyle H_1: \left\{0,1\right\}^* \rightarrow G_1^*, • a public hash function \textstyle H_2: G_2 \rightarrow \left\{0,1\right\}^n for some fixed \textstyle n and • the
message space and the
cipher space \textstyle \mathcal{M} = \left\{0,1\right\}^n, \mathcal{C} = G_1^* \times \left\{0,1\right\}^n
Extraction To create the public key for \textstyle ID \in \left\{0,1\right\}^*, the PKG computes • \textstyle Q_{ID} = H_1\left(ID\right) and • the private key \textstyle d_{ID} = sQ_{ID} which is given to the user.
Encryption Given \textstyle m \in \mathcal{M}, the ciphertext \textstyle c is obtained as follows: • \textstyle Q_{ID} = H_1\left(ID\right) \in G_1^*, • choose random \textstyle r \in \mathbb{Z}_q^*, • compute \textstyle g_{ID} = e\left(Q_{ID}, K_{pub}\right) \in G_2 and • set \textstyle c = \left(rP, m \oplus H_2\left(g_{ID}^r\right)\right). Note that \textstyle K_{pub} is the PKG's public key and thus independent of the recipient's ID.
Decryption Given \textstyle c = \left(u, v\right) \in \mathcal{C}, the plaintext can be retrieved using the private key: \textstyle 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 \textstyle 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 \textstyle H_2\left(g_{ID}^r\right), while for decryption, \textstyle H_2\left( e\left(d_{ID}, u\right) \right) is applied. Due to the properties of pairings, it follows that: \begin{align} H_2\left( e\left(d_{ID}, u\right) \right) &= H_2\left( e\left(sQ_{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{align} ==Security==