Programming ECC - Quick-Reference: Identity-Based Cryptosystems

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

Master secret: pick $x \in ℤ_{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 ℤ_{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})$ .

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 ℤ_{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 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 ℤ_{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})

Signatures [SKS]

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)