22.4 Identity-Based Encryption – Introduction to Cryptography with Coding Theory, 3rd Edition

22.4 Identity-Based Encryption

In most public key systems, when Alice wants to send a message to Bob, she looks up his public key in a directory and then encrypts her message. However, she needs some type of authentication – perhaps the directory has been modified by Eve, and the public key listed for Bob was actually created by Eve. Alice wants to avoid this situation. It was suggested by Shamir in 1984 that it would be nice to have an identity-based system, where Bob’s public identification information (for example, his email address) serves as his public key. Such a system was finally designed in 2001 by Boneh and Franklin.

Of course, some type of authentication of each user is still needed. In the present system, this occurs in the initial setup of the system during the communications between the Trusted Authority and the User. In the following, we give the basic idea of the system. For more details and improvements, see [Boneh-Franklin].

We need two public hash functions:

  1. H1 maps arbitrary length binary strings to multiples of P0. A little care is needed in defining H1,  since no one should be able, given a binary string b,  to find k with H1(b)=kP0. See Exercise 7.

  2. H2 maps qth roots of unity to binary strings of length n,  where n is the length of the messages that will be sent. Since H2 must be specified before the system is set up, this limits the lengths of the messages that can be sent. However, the message could be, for example, a DES key that is used to encrypt a much longer message, so this length requirement is not a severe restriction.

To set up the system we need a Trusted Authority. Let’s call him Arthur. Arthur does the following.

  1. He chooses, once and for all, a secret integer s. He computes P1=sP0,  which is made public.

  2. For each User, Arthur finds the user’s identification ID (written as a binary string) and computes

    DUser=sH1(ID).

    Recall that H1(ID) is a point on E,  so D User is s times this point.

  3. Arthur uses a secure channel to send D User to the user, who keeps it secret. Arthur does not need to store D User,  so he discards it.

The system is now ready to operate, but first let’s review what is known:

Public: E, p, P0, P1, H1, H2

Secret: s (known only to Arthur), D User (one for each User; it is known only by that User)

Alice wants to send an email message m (of binary length n) to Bob, who is one of the Users. She knows Bob’s address, which is bob@computer.com. This is his ID. Alice does the following.

  1. She computes g=e˜(H1(bob@computer.com), P1). This is a qth root of unity.

  2. She chooses a random r0(mod q) and computes

    t=mH2(gr).
  3. She sends Bob the ciphertext

    c=(rP0, t).

    Note that rP0 is a point on E,  and t is a binary string of length n.

If Bob receives a pair (U, v),  where U is a point on E and v is a binary string of length n,  then he does the following.

  1. He computes h=e˜(D Bob, U),  which is a qth root of unity.

  2. He recovers the message as

    m=vH2(h).

Why does this yield the message? If the encryption is performed correctly, Bob receives U=rP0 and v=t=mH2(gr). Since D Bob=sH1 (bob@computer.com),

h=e˜(D Bob, rP0)=e˜(H1, P0)sr=e˜(H1, sP0)r=gr.(22.1)

Therefore,

tH2(h)=tH2(gr)=mH2(gr)H2(gr)=m, 

as desired. Note that the main step is Equation (22.1), which removes the secret s from the D Bob in the first argument of e˜ and puts it on the P0 in the second argument. This follows from the bilinearity property of the function e˜. Almost all of the cryptographic uses of pairings have a similar idea of moving from one masking of the secret to another. The pairing allows this to be done without knowing the value of s.

It is very important that s be kept secret. If Eve obtains s,  then she can compute the points D User for each user and read every email. Since P1=sP0,  the security of s is compromised if Eve can compute discrete logs on the elliptic curve. Moreover, the ciphertext contains rP0. If Eve can compute a discrete log and find r,  then she can compute gr and use this to find H2(gr) and also m. Therefore, for the security of the system, it is vital that p be chosen large enough that discrete logs are computationally infeasible.