Boneh-Franklin IBE

This page is intended to provide a quick and dirty tutorial on the Boneh-Franklin IBE scheme. It assumes you know a few basic facts, including some idea of how the Elgamal scheme works, and what cyclic groups are. If you don’t know those things, this tutorial might help.

For starters, imagine that we have a cyclic group {\mathbb G} of prime order q, with a generator g. We’ll also imagine that we have a hash function H: \{0,1\}^* \rightarrow {\mathbb G} with the particular property that it can map arbitrary strings to elements of the group {\mathbb G}, such that you will not know the discrete logarithm of the resulting element base g.* These are most of the ingredients we need.

Quick recap of Elgamal

If you’re familiar with Elgamal encryption, you’ll remember that public keys have the form pk = g^s, where the secret key is a random integer s \in \{1,\dots,q-1\}. Encrypting a message m \in {\mathbb G} is done by choosing a random integer r and computing:

C_1 = g^r, C_2 = pk^r \cdot m

The two values C_1, C_2 together represent a ciphertext. To decrypt this ciphertext using the secret key s, one simply computes the formula:

m' = C_2 / C_1^s

(In practice we can’t actually use division, we multiply by the inverse of C_1^s, but this notation is a little easier to read.)

An IBE attempt that doesn’t work

If you’re trying to convert Elgamal into an IBE scheme, you might observe that our hash function H seems like it could be useful here. Recall that H maps to arbitrary elements of {\mathbb G}. So if I compute the value:

h = H("Identity")

I’ll end up with a group element h \in {\mathbb G}, which (because {\mathbb G} is generated by g) can be represented as h = g^x for some unknown value x.

It’s noteworthy that this hash output (h) has the same basic structure as our normal Elgamal public key pk. So the temptation here might be to use h as a public key for the Elgamal cryptosystem. And indeed, this would work fine — if all you needed to do was encrypt. Sadly, it would fail badly if you also wanted to decrypt. This is because we’d need to figure out the secret key x that corresponds to h = g^{x}, and one of two things is true: either (1) the hash function H makes that easy to do, in which case anyone can do it and the scheme is busted. Or (2) the hash function H makes that value hard to find, in which case nobody can decrypt. So decryption does not seem to work in this setting.

So using standard cyclic groups, this idea is kind of a bust.

Another idea would be to conjure up some magical function D: {\mathbb G} \times \mathbb{G} \rightarrow {\mathbb G} that could, given two group elements H(id) = g^x and a master public key pk = g^s, somehow compute the combined value g^{xs}. If we had such a function, we could encrypt under both the hash value h and the public key pk as follows:

C_1 = g^r, C_2 = D(h^r, pk) \cdot m~~~~(= g^{rxs} \cdot m)

To decrypt this ciphertext, you could use knowledge of s and the magical function D as follows:

m' = C_2 / D(C_1, h)^s

This seems awesome, but it falls apart for two reasons. First, we don’t have a magical function D. Moreover, if we did have such a function, there would be any easy attack that breaks the whole scheme. (I’ll leave finding it as an exercise for the reader.) In fact, having a function like D is equivalent to solving the Diffie-Hellman problem, which Elgamal fundamentally relies on for security. So that’s no good.

Adding a pairing

In most common cyclic groups we don’t have a function D that breaks Diffie-Hellman, which is fortunate for the security of schemes like Elgamal. But we do have something close. Specifically, certain elliptic curve subgroups admit an efficiently computable bilinear map. This map e: {\mathbb G} \times {\mathbb G} \rightarrow {\mathbb G}_T looks a lot like our function D, but not exactly. Note that it takes in two elements of {\mathbb G} and outputs an element of a different group {\mathbb G}_T. The critical feature is that there is no way to map back to the original group {\mathbb G} from the target group {\mathbb G}_T.

More importantly, this function preserves the a property called bilinearity, which is that for all a,b the following holds:

e(g^a, g^b) = e(g, g)^{ab}

Notice that the pairing does not break the (computational) Diffie-Hellman problem, because the pairing outputs an element of a different group that is not {\mathbb G} (but does have the same order). (The pairing does allow you to break the decisional variant of the DH problem, but we’ll ignore that problem for the moment.)

These bilinear maps were actually discovered decades before elliptic curve cryptography was a thing people cared about. However, an efficient algorithm for computing them was only discovered in the 1980s by an NSA scientist named Victor Miller. Miller’s algorithm was actually considered a very bad thing for elliptic curve cryptography because it enabled attacks. Thus most NSA- and NIST-standardized curves don’t feature efficiently-computable bilinear maps. But these maps can be very useful if you’re careful.

Let’s go back to our earlier attempt at building an IBE scheme from above. Except this time, we’ll replace the function D with a bilinear pairing, and we’ll also encode the plaintext m into the target group {\mathbb G}_T:

C_1 = g^r, C_2 = e(h^r, pk) \cdot m ~~~~~~~~(= e(g,g)^{rxs} \cdot m)

With knowledge of the secret key s, decryption can be computed as:

m' = C_2 / e(C_1, h^s)

So that’s good. But here’s an even better feature. If you know the secret key s corresponding to the (master) public key pk, you can also derive a secondary form of decryption key that only works for one specific identity. You compute that key as follows:

sk_{ID} = h^s

If I hand someone this key, they can decrypt the ciphertext above using the same decryption equation from above. Indeed, all I’ve done is change the notation below:

m' = C_2 / e(C_1, sk_{ID})

And this is basically the Boneh-Franklin scheme. We set mpk = g^s, msk = s and use the encryption and decryption algorithms above. Unlike our bad attempt higher up, this scheme actually works. Moreover, it can be shown to be secure under reasonable cryptographic assumptions in the random oracle model.

What I’ve illustrated here is the basic “chosen plaintext” version of the scheme. This one is not secure under chosen ciphertext attacks. The Boneh-Franklin paper also incorporates a second version that uses hash functions to solve that problem (and make the scheme a bit more efficient). You can see the paper for details.

Bonus explainer: short signatures from IBE

One of the coolest things about IBE is that once you have one, you also get a digital signature scheme for free. The basic observation here is that you can “turn an IBE scheme around”, and use the master public key as the public key for a signature scheme. To sign a message, you just derive an IBE decryption key for a specific “identity” that corresponds to the message you want to sign.

The generic signature verification algorithm is simple: use the master public key to encrypt a message under the signed message, and try to decrypt it with the given “signature” (decryption key). If decryption works, you have a valid signature!

The neat thing about this is that the “signature” scheme implied by Boneh-Franklin is really efficient: signatures are only one elliptic curve group element, which can be as short as 256 bits. These tiny signatures are called Boneh-Lynn-Shacham signatures, and can be directly proven secure under the Computational Diffie-Hellman problem.

Notes:

* A common way to build this hash function is to hash to a field element a that is in the field used for the underlying elliptic curve, and then to solve the elliptic curve equation to find a full EC point (a,b) that satisfies the curve equation and is in the correct subgroup. Sometimes a does not satisfy these checks, in which case you need to repeat the hash function, e.g., compute H(a) and try again.