Programming ECC - Quick-Reference: Identity-Based Cryptosystems

See Jerome Solinas' slides for a brief summary of various identity-based cryptosystems.

Let $G_{1} \times G_{2} \to G_{T}$ be a bilinear map, where each group has prime order $r$ .

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})$ .

Encrypt: suppose Alice wishes to send a message $m$ to Bob. Alice picks random $r \in ℤ_{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 $⟨ g^{r}, E_{K} (m) ⟩$ to Bob.
Decrypt: Bob can compute K from $e (g^{r}, u^{x})$ .

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 ℤ_{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 ℤ_{r}$ and derive a key K from $e (g^{r}, u_{0}^{x})$ . Then send $⟨ g^{r}, u_{1}^{r}, E_{K} (m) ⟩$
Decrypt: Bob can compute K from $e (g^{r}, u_{0}^{x_{0}} u_{1}^{x_{1}}) / e (u_{1}^{r}, g_{1}^{x})$ .
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 ℤ_{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 ℤ_{r}$ and derive a key K from $e (g^{r}, u_{0}^{x})$ . Then send $⟨ g^{r}, u_{1}^{r}, u_{2}^{r}, E_{K} (m) ⟩$
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 continue this process and build an arbitrarily deep hierarchical identity-based encryption system.

Sign: given a message $m$ , private key $u^{x}$ (and ID that hashes to $u$ ), pick random $r \in ℤ_{r}$ and compute $h = H (m, u^{r})$ where $H : {0,1}^{*} \times G_{1} \to ℤ_{r}$ is some hash function. Output $⟨ u^{r}, u^{x (r + h)} ⟩$
Verify: given a tuple $⟨ U, V ⟩$ compute $h = H (m, U)$ and check that $e (u^{x (r + h)}, g) = e (u^{r} u^{h}, g^{x})$

Sign: given a message $m$ , private key $u^{x}$ (and ID that hashes to $u$ ), pick random $r \in ℤ_{r}$ and compute $z = e (u, g^{r})$ Compute $h = H (m, z)$ where $H : {0,1}^{*} \to ℤ_{r}$ is some hash function and output $⟨ h, u^{x h} u^{r} ⟩$
Verify: given a tuple $⟨ U, V ⟩$ compute $z = e (V, g) e (u, (g^{x})^{- U})$ and check that $U = H (m, z)$