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})/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 \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 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 \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 that

\[U = H(m, z)\]