QuickReference: IdentityBased Cryptosystems
See Jerome Solinas' slides for a brief summary of various identitybased cryptosystems.
Let $G_1 \times G_2 \rightarrow G_T$ be a bilinear map, where each group has prime order $r$.

Master secret: pick $x \in \mathbb{Z}_r$

System parameters: choose $g \in G_2$, also output $g^x$.

Extract: hash ID to $u \in G_1$, private key is $u^x$
Key Agreement [SOK]
Suppose $G_1 = G_2$. Let $u, v$ be the hashes of the IDs of Alice and Bob respectively. Then Alice can compute $e(u^x, v)$, while Bob can compute $e(u, v^x)$.
Encryption [BF]

Encrypt: suppose Alice wishes to send a message $m$ to Bob. Alice picks random $r \in \mathbb{Z}_r$, computes $e(u^r, g^x)$ and derives a key $K$ from this (where $u$ is the hash of Bob’s ID). She sends $ \langle g^r, E_K(m) \rangle $ to Bob.

Decrypt: Bob can compute K from $e(g^r, u^x)$.
Encryption, Hierarchical [GS]

Suppose Alice now wishes to start her own IBE system (running under the one she is already part of) and Bob becomes a user of Alice’s system. For this part, rename $u$ as $u_0$ and $x$ as $x_0$.

Extract: Alice picks a secret $x_1 \in \mathbb{Z}_r$. Suppose Bob’s ID hashes to $u_1 \in G_1$. Then she gives the private key $u_0^{x_0}u_1^{x_1}$ along with the public value $g^{x_1}$ to Bob.

Encrypt: Suppose someone wants to encrypt a message $m$ to Bob. First pick a random $r \in \mathbb{Z}_r$ and derive a key K from $e(g^r, u_0^x)$. Then send

Decrypt: Bob can compute K from $e(g^r, u_0^{x_0}u_1^{x_1})/e(u_1^r, g^x_1)$.

Now suppose Bob wants to start his own IBE system underneath Alice’s, and say Carol wants to become a user of Bob’s system.

Extract: Bob picks a secret $x_2 \in \mathbb{Z}_r$. Let Carol’s ID hash to $u_2 \in G_2$. Then Bob gives Carol $u_0^{x_0}u_1^{x_1}u_2^{x_2}$ along with $g^{x_1}, g^{x_2}$.

Encrypt: to encrypt a message $m$ to Carol, pick a random $r \in \mathbb{Z}_r$ and derive a key K from $e(g^r, u_0^x)$. Then send

Decrypt: Carol can compute K from $e(g^r, u_0^{x_0}u_1^{x_1})/e(u_1^r, g^{x_1})e(u_2^r, g^{x_2})$.
We can iterate this process to build an arbitrarily deep hierarchical identitybased encryption system.
Signatures [CC]

Sign: given a message $m$, private key $u^x$ (and ID that hashes to $u$), pick random $r \in \mathbb{Z}_r$ and compute
\[ h = H(m, u^r) \]where $H : \{0,1\}^* \times G_1 \rightarrow \mathbb{Z}_r$ is some hash function. Output
\[ \langle u^r, u^{x(r+h)} \rangle \] 
Verify: given a tuple $\langle U, V \rangle$ compute $h = H(m, U)$ and check that
Signatures [SKS]

Sign: given a message $m$, private key $u^x$ (and ID that hashes to $u$), pick random $r \in \mathbb{Z}_r$ and compute
\[ z = e(u,g^r) \]Compute $h = H(m,z)$ where $H:\{0,1\}^* \rightarrow \mathbb{Z}_r$ is some hash function and output
\[ \langle h, u^{x h}u^r \rangle \] 
Verify: given a tuple $\langle U, V \rangle$ compute $z = e(V, g)e(u,(g^x)^{U})$ and check that