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}u_2^{x_2})/e(u_1^r, g^{x_1})e(u_2^r, g^{x_2})$$.

Iterate 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

$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

$U = H(m, z)$

Ben Lynn blynn@cs.stanford.edu 💡