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 \[ \langle g^{r, u_1}r, E_K(m) \rangle \]

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
+

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
+

Verify: given a tuple \(\langle U, V \rangle\) compute \(z = e(V, g)e(u,(g^x)^{U})\) and check that