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:
maps arbitrary length binary strings to multiples of A little care is needed in defining since no one should be able, given a binary string to find with See Exercise 7.
maps th roots of unity to binary strings of length where is the length of the messages that will be sent. Since 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.
He chooses, once and for all, a secret integer He computes which is made public.
For each User, Arthur finds the user’s identification ID (written as a binary string) and computes
Recall that is a point on so is times this point.
Arthur uses a secure channel to send to the user, who keeps it secret. Arthur does not need to store so he discards it.
The system is now ready to operate, but first let’s review what is known:
Public:
Secret: (known only to Arthur), (one for each User; it is known only by that User)
Alice wants to send an email message (of binary length ) 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.
She computes (([email protected])
, ). This is a th root of unity.
She chooses a random and computes
She sends Bob the ciphertext
Note that is a point on and is a binary string of length
If Bob receives a pair where is a point on and is a binary string of length then he does the following.
He computes which is a th root of unity.
He recovers the message as
Why does this yield the message? If the encryption is performed correctly, Bob receives and Since ([email protected])
,
Therefore,
as desired. Note that the main step is Equation (22.1), which removes the secret from the in the first argument of and puts it on the in the second argument. This follows from the bilinearity property of the function 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
It is very important that be kept secret. If Eve obtains then she can compute the points for each user and read every email. Since the security of is compromised if Eve can compute discrete logs on the elliptic curve. Moreover, the ciphertext contains If Eve can compute a discrete log and find then she can compute and use this to find and also Therefore, for the security of the system, it is vital that be chosen large enough that discrete logs are computationally infeasible.