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. $H_1$ maps arbitrary length binary strings to multiples of $P_0\text{.}$ A little care is needed in defining $H_1\text{,}$ since no one should be able, given a binary string $b\text{,}$ to find $k$ with $H_1(b)=k{P}_0\text{.}$ See Exercise 7.

2. $H_2$ maps $q$th roots of unity to binary strings of length $n\text{,}$ where $n$ is the length of the messages that will be sent. Since $H_2$ 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\text{.}$ He computes $P_1=s{P}_0\text{,}$ which is made public.

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

   $$D_{\text{User}}=s{H}_1(ID)\text{.}$$

   Recall that $H_1(ID)$ is a point on $E\text{,}$ so $D_{\text{ User}}$ is $s$ times this point.

3. Arthur uses a secure channel to send $D_{\text{ User}}$ to the user, who keeps it secret. Arthur does not need to store $D_{\text{ User}}\text{,}$ so he discards it.

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

Public: $E\text{,}p\text{,}{P}_0\text{,}{P}_1\text{,}{H}_1\text{,}{H}_2$

Secret: $s$ (known only to Arthur), $D_{\text{ 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 [email protected]. This is his ID. Alice does the following.

1. She computes g=e˜$g=\tilde{e}$$g=\tilde{e}$($H_1$([email protected]), P1$P_1$$P_1$). This is a $q$th root of unity.

2. She chooses a random $r\cancel{\equiv }0(\text{mod }q)$ and computes

   $$t=m\oplus H_2(g^r)\text{.}$$

3. She sends Bob the ciphertext

   $$c=(r{P}_0\text{,}t)\text{.}$$

   Note that $r{P}_0$ is a point on $E\text{,}$ and $t$ is a binary string of length $n\text{.}$

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

1. He computes $h=\tilde{e}(D_{\text{ Bob}}\text{,}U)\text{,}$ which is a $q$th root of unity.

2. He recovers the message as

   $$m=v\oplus H_2(h)\text{.}$$

Why does this yield the message? If the encryption is performed correctly, Bob receives $U=r{P}_0$ and $v=t=m\oplus H_2(g^r)\text{.}$ Since $D_{\text{ Bob}}=s{H}_1$ ([email protected]),

Therefore,

as desired. Note that the main step is Equation (22.1), which removes the secret $s$ from the $D_{\text{ Bob}}$ in the first argument of $\tilde{e}$ and puts it on the $P_0$ in the second argument. This follows from the bilinearity property of the function $\tilde{e}\text{.}$ 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\text{.}$

It is very important that $s$ be kept secret. If Eve obtains $s\text{,}$ then she can compute the points $D_{\text{ User}}$ for each user and read every email. Since $P_1=s{P}_0\text{,}$ the security of $s$ is compromised if Eve can compute discrete logs on the elliptic curve. Moreover, the ciphertext contains $r{P}_0\text{.}$ If Eve can compute a discrete log and find $r\text{,}$ then she can compute $g^r$ and use this to find $H_2(g^r)$ and also $m\text{.}$ Therefore, for the security of the system, it is vital that $p$ be chosen large enough that discrete logs are computationally infeasible.