52 Things: Number 51: What is the security model for ID-based encryption, and describe one IBE scheme.

This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know To Do Cryptography': a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. This week we introduce Identity-Based Encryption.

In public key cryptography, if Alice wants to send a message to Bob, she needs his public key. Typically this will be some very long bitstring (encoding, for example, the product of two large primes).

Suppose instead that Alice could use Bob's name, or email address, as his public key. Practically speaking, this is very convenient: there are no very long strings for Alice to obtain and remember and she doesn't need to verify that some seemingly random string is in fact Bob's public key (and not, for example, Charlie's public key). But to facilitate this, one needs Identity Based Encryption, or IBE.

In IBE, there is an entity called the Private Key Generator, or PKG. The PKG is able to compute Bob's private key using his ID (e.g. his email address) and a master key. Once Bob has authenticated himself to the PKG, he can ask for his private key and then, once he has it, he can decrypt any messages that have been encrypted under his ID.

There is an issue here, though. With the master key, the PKG can generate private keys for any agent it likes. Therefore the PKG can decrypt any messages intended for any agent. This is called key escrow, and it means that you must either trust the PKG not to read your encrypted messages or else not care that it does. In a company, though, senior management often has the right to read your (work) emails, and so IBE can be an appropriate solution for internal correspondence.

Formally, an IBE scheme consists of four algorithms: setup, extract, encrypt and decrypt.

Setup takes a security parameter and outputs the (secret) master key and the (public) system parameters, such as the message and ciphertext spaces.

Extract takes an ID and a master key and returns a private key corresponding to the ID.

Encrypt takes a message and an ID, and returns a ciphertext.

Decrypt takes a ciphertext and a private key, and returns a message.

Boneh and Franklin gave an IBE scheme in this 2003 paper. They prove, under an assumption similar to assuming that the CDH problem is hard, that their scheme is IND-ID-CCA secure in the Random Oracle Model. This means that (assuming all hash functions are random oracles), any attacker, running in polynomial-time with respect to the security parameter, wins the following security game with probability that is only negligibly (with respect to the security parameter) more than 1/2:

First, the attacker

• can request the private keys corresponding to any ID
• can request decryptions of any ciphertexts under any ID.

Then, the attacker chooses two messages $m_0, m_1$ and an ID $ID^*$ that does not occur in the list of IDs for which he has requested the corresponding private key. The attacker then receives the encryption $c^*$ of $m_b$ under $ID^*$ (where the bit $b$ is chosen uniformly at random). Then the attacker

• can request the private keys corresponding to any ID apart from $ID^*$
• can request decryptions of any ciphertexts under any ID apart from $ \left ( c^*, ID^* \right) $

and outputs a bit $b'$. We say the attacker wins if $b' = b$.

The scheme given by Boneh and Franklin relies on a non-degenerate bilinear map $e: G_1 \times G_1 \to G_2$, where $G_1$ is a group of prime order $q$, which we write additively, and $G_2$ is a group, also of order $q$, which we write multiplicatively. They instantiate this map with the Weil pairing on elliptic curves, but we omit details here. All that matters is bilinearity: $e \left( aP, bQ \right ) = e \left( P, Q \right)^{ab}$ for any $a, b \in \mathbb{Z}_q$.

There's not enough space here to describe the scheme in full, but essentially the master key is some non-zero $s \in \mathbb{Z}_q$ and the private key corresponding to $ID$ is $sH \left(ID \right)$, where $H$ is a hash function sending bitstrings to elements of $G_1$. There are public generators $P$ and $P_{pub} = sP$ of $G_1$.

To encrypt $m$ under $ID$, one selects a random string $\sigma$ and XORs $m$ with a hash of $\sigma$, creating $c_m$. Then $M$ and $\sigma$ are hashed together, giving a non-zero element $r \in \mathbb{Z}_q$. Finally one computes the pairing $e \left( H \left( ID \right), P_{pub} \right) $, raises it to the power $r$, hashes this and XORs with $\sigma$, creating $c_{ID}$. The triple $\left( rP, c_{ID}, c_m \right)$ is the ciphertext.

With the private key $d = sH\left(ID \right)$, one decrypts the triple $\left (U, V, W \right)$ as follows: compute $e \left( d, U \right)$, which, by bilinearity, will equal $e \left( H \left( ID \right), P_{pub} \right)^r $ if the ciphertext was genuine. So one XORs $V$ with the hash of the pairing to obtain $\sigma$. Then XORing $W$ with the hash of $\sigma$ will give $m$. To check that this is the intended message, one verifies that $\sigma$ and $m$ hashed together gives $r$ such that $U = rP$.