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 💡