## Quick-Reference: Identity-Based Cryptosystems

See Jerome Solinas' slides for a brief summary of various identity-based 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: 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

$\langle g^r, u_1^r, u_2^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 identity-based 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

$e(u^{x(r+h)},g) = e(u^r u^h, g^x)$

### 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

$U = H(m, z)$