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
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
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
where \(H : \{0,1\}^* \times G_1 \rightarrow \mathbb{Z}_r\) is some hash function. Output
Verify: given a tuple \(\langle U, V \rangle\) compute \(h = H(m, U)\) and check
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
Compute \(h = H(m,z)\) where \(H:\{0,1\}^* \rightarrow \mathbb{Z}_r\) is some hash function and output
Verify: given a tuple \(\langle U, V \rangle\) compute \(z = e(V, g)e(u,(g^x)^{-U})\) and check