Appears in SIAM J. of Computing, Vol. 32, No. 3, pp. 586-615, 2003. An extended abstract of this
paper appears in the Proceedings of Crypto 2001, volume 2139 of Lecture Notes in Computer Science, pages
213{229, Springer-Verlag, 2001.
Identity-Based Encryption from the Weil Pairing
Dan Boneh
Matthew Frankliny
dabo@cs.stanford.edu
franklin@cs.ucdavis.edu
Abstract
We propose a fully functional identity-based encryption scheme (IBE). The scheme has chosen
ciphertext security in the random oracle model assuming a variant of the computational Die-
Hellman problem. Our system is based on bilinear maps between groups. The Weil pairing on
elliptic curves is an example of such a map. We give precise denitions for secure identity based
encryption schemes and give several applications for such systems.
1
Introduction
In 1984 Shamir [41] asked for a public key encryption scheme in which the public key can be an arbitrary
string. In such a scheme there are four algorithms: (1) setup generates global system parameters and
a master-key, (2) extract uses the master-key to generate the private key corresponding to an arbitrary
public key string ID 2 f0; 1g, (3) encrypt encrypts messages using the public key ID, and (4) decrypt
decrypts messages using the corresponding private key.
Shamir’s original motivation for identity-based encryption was to simplify certicate management
in e-mail systems. When Alice sends mail to Bob at bob@company.com she simply encrypts her message
using the public key string \bob@company.com". There is no need for Alice to obtain Bob’s public key
certicate. When Bob receives the encrypted mail he contacts a third party, which we call the Private
Key Generator (PKG). Bob authenticates himself to the PKG in the same way he would authenticate
himself to a CA and obtains his private key from the PKG. Bob can then read his e-mail. Note that
unlike the existing secure e-mail infrastructure, Alice can send encrypted mail to Bob even if Bob
has not yet setup his public key certicate. Also note that key escrow is inherent in identity-based
e-mail systems: the PKG knows Bob’s private key. We discuss key revocation, as well as several new
applications for IBE schemes in the next section.
Since the problem was posed in 1984 there have been several proposals for IBE schemes [11, 45,
44, 31, 25] (see also [33, p. 561]). However, none of these are fully satisfactory. Some solutions require
that users not collude. Other solutions require the PKG to spend a long time for each private key
generation request. Some solutions require tamper resistant hardware.
It is fair to say that until
the results in [5] constructing a usable IBE system was an open problem. Interestingly, the related
notions of identity-based signature and authentication schemes, also introduced by Shamir [41], do
have satisfactory solutions [15, 14].
In this paper we propose a fully functional identity-based encryption scheme. The performance
of our system is comparable to the performance of ElGamal encryption in F
p. The security of our
system is based on a natural analogue of the computational Die-Hellman assumption. Based on
Supported by DARPA contract F30602-99-1-0530, NSF, and the Packard Foundation.
ySupported by an NSF Career Award and the Packard Foundation.
1
this assumption we show that the new system has chosen ciphertext security in the random oracle
model. Using standard techniques from threshold cryptography [20, 22] the PKG in our scheme can
be distributed so that the master-key is never available in a single location. Unlike common threshold
systems, we show that robustness for our distributed PKG is free.
Our IBE system can be built from any bilinear map e : G1 G1 ! G2 between two groups G1; G2 as
long as a variant of the Computational Die-Hellman problem in G1 is hard. We use the Weil pairing
on elliptic curves as an example of such a map. Until recently the Weil pairing has mostly been used for
attacking elliptic curve systems [32, 17]. Joux [26] recently showed that the Weil pairing can be used
for \good" by using it for a protocol for three party one round Die-Hellman key exchange. Sakai et
al. [40] used the pairing for key exchange and Verheul [46] used it to construct an ElGamal encryption
scheme where each public key has two corresponding private keys. In addition to our identity-based
encryption scheme, we show how to construct an ElGamal encryption scheme with \built-in" key
escrow, i.e., where one global escrow key can decrypt ciphertexts encrypted under any public key.
To argue about the security of our IBE system we dene chosen ciphertext security for identity-
based encryption. Our model gives the adversary more power than the standard model for chosen
ciphertext security [37, 2]. First, we allow the attacker to attack an arbitrary public key ID of her
choice. Second, while mounting a chosen ciphertext attack on ID we allow the attacker to obtain from
the PKG the private key for any public key of her choice, other than the private key for ID. This models
an attacker who obtains a number of private keys corresponding to some identities of her choice and
then tries to attack some other public key ID of her choice. Even with the help of such queries the
attacker should have negligible advantage in defeating the semantic security of the system.
The rest of the paper is organized as follows. Several applications of identity-based encryption are
discussed in Section 1.1. We then give precise denitions and security models in Section 2. We describe
bilinear maps with certain properties in Section 3. Our identity-based encryption scheme is presented
in Section 4 using general bilinear maps. Then a concrete identity based system from the Weil pairing is
given in Section 5. Some extensions and variations (eciency improvements, distribution of the master-
key) are considered in Section 6. Our construction for ElGamal encryption with a global escrow key is
described in Section 7. Section 8 gives conclusions and some open problems. The Appendix contains
a more detailed discussion of the Weil pairing.
1.1 Applications for Identity-Based Encryption
The original motivation for identity-based encryption is to help the deployment of a public key infras-
tructure. In this section, we show several other unrelated applications.
1.1.1 Revocation of Public Keys
Public key certicates contain a preset expiration date. In an IBE system key expiration can be done by
having Alice encrypt e-mail sent to Bob using the public key: \bob@company.com k current-year".
In doing so Bob can use his private key during the current year only. Once a year Bob needs to obtain
a new private key from the PKG. Hence, we get the eect of annual private key expiration. Note
that unlike the existing PKI, Alice does not need to obtain a new certicate from Bob every time Bob
refreshes his private key.
One could potentially make this approach more granular by encrypting e-mail for Bob using
current-date". This forces Bob to obtain a new private key every day.
\bob@company.com
k
2
This might be possible in a corporate PKI where the PKG is maintained by the corporation. With this
approach key revocation is very simple: when Bob leaves the company and his key needs to be revoked,
the corporate PKG is instructed to stop issuing private keys for Bob’s e-mail address. As a result, Bob
can no longer read his email. The interesting property is that Alice does not need to communicate with
any third party certicate directory to obtain Bob’s daily public key. Hence, identity based encryption
is a very ecient mechanism for implementing ephemeral public keys. Also note that this approach
enables Alice to send messages into the future: Bob will only be able to decrypt the e-mail on the date
specied by Alice (see [38, 12] for methods of sending messages into the future using a stronger security
model).
Managing user credentials. A simple extension to the discussion above enables us to manage
user credentials using the IBE system. Suppose Alice encrypts mail to Bob using the public key:
\bob@company.com k current-year k clearance=secret". Then Bob will only be able to read
the email if on the specied date he has secret clearance. Consequently, it is easy to grant and revoke
user credentials using the PKG.
1.1.2 Delegation of Decryption Keys
Another application for IBE systems is delegation of decryption capabilities. We give two example
applications. In both applications the user Bob plays the role of the PKG. Bob runs the setup algorithm
to generate his own IBE system parameters params and his own master-key. Here we view params as
Bob’s public key. Bob obtains a certicate from a CA for his public key params. When Alice wishes to
send mail to Bob she rst obtains Bob’s public key params from Bob’s public key certicate. Note that
Bob is the only one who knows his master-key and hence there is no key-escrow with this setup.
1. Delegation to a laptop. Suppose Alice encrypts mail to Bob using the current date as the IBE
encryption key (she uses Bob’s params as the IBE system parameters). Since Bob has the master-
key he can extract the private key corresponding to this IBE encryption key and then decrypt the
message. Now, suppose Bob goes on a trip for seven days. Normally, Bob would put his private key
on his laptop. If the laptop is stolen the private key is compromised. When using the IBE system
Bob could simply install on his laptop the seven private keys corresponding to the seven days of the
trip. If the laptop is stolen, only the private keys for those seven days are compromised. The master-
key is unharmed. This is analogous to the delegation scenario for signature schemes considered by
Goldreich et al. [23].
2. Delegation of duties. Suppose Alice encrypts mail to Bob using the subject line as the IBE
encryption key. Bob can decrypt mail using his master-key. Now, suppose Bob has several assistants
each responsible for a dierent task (e.g. one is ‘purchasing’, another is ‘human-resources’, etc.). Bob
gives one private key to each of his assistants corresponding to the assistant’s responsibility. Each
assistant can then decrypt messages whose subject line falls within its responsibilities, but it cannot
decrypt messages intended for other assistants. Note that Alice only obtains a single public key from
Bob (params), and she uses that public key to send mail with any subject line of her choice. The
mail can only be read by the assistant responsible for that subject.
More generally, IBE can simplify security systems that manage a large number of public keys. Rather
than storing a big database of public keys the system can either derive these public keys from usernames,
or simply use the integers 1; : : : ; n as distinct public keys.
3
2 Denitions
Identity-Based Encryption. An identity-based encryption scheme E is specied by four random-
ized algorithms: Setup, Extract, Encrypt, Decrypt:
Setup: takes a security parameter k and returns params (system parameters) and master-key. The
system parameters include a description of a nite message space M, and a description of a nite
ciphertext space C. Intuitively, the system parameters will be publicly known, while the master-key
will be known only to the \Private Key Generator" (PKG).
Extract: takes as input params, master-key, and an arbitrary ID 2 f0; 1g, and returns a private key
d. Here ID is an arbitrary string that will be used as a public key, and d is the corresponding private
decryption key. The Extract algorithm extracts a private key from the given public key.
Encrypt: takes as input params, ID, and M 2 M. It returns a ciphertext C 2 C.
Decrypt: takes as input params, C 2 C, and a private key d. It return M 2 M.
These algorithms must satisfy the standard consistency constraint, namely when d is the private key
generated by algorithm Extract when it is given ID as the public key, then
8M 2 M : Decrypt(params; C; d) = M where C = Encrypt(params; ID; M )
Chosen ciphertext security. Chosen ciphertext security (IND-CCA) is the standard acceptable
notion of security for a public key encryption scheme [37, 2, 13]. Hence, it is natural to require that an
identity-based encryption scheme also satisfy this strong notion of security. However, the denition of
chosen ciphertext security must be strengthened a bit. The reason is that when an adversary attacks
a public key ID in an identity-based system, the adversary might already possess the private keys of
users ID1; : : : ; IDn of her choice. The system should remain secure under such an attack. Hence, the
denition of chosen ciphertext security must allow the adversary to obtain the private key associated
with any identity IDi of her choice (other than the public key ID being attacked). We refer to such
queries as private key extraction queries. Another dierence is that the adversary is challenged on a
public key ID of her choice (as opposed to a random public key).
We say that an identity-based encryption scheme E is semantically secure against an adaptive
chosen ciphertext attack (IND-ID-CCA) if no polynomially bounded adversary A has a non-negligible
advantage against the Challenger in the following IND-ID-CCA game:
Setup: The challenger takes a security parameter k and runs the Setup algorithm. It gives
the adversary the resulting system parameters params. It keeps the master-key to itself.
Phase 1: The adversary issues queries q1; : : : ; qm where query qi is one of:
{ Extraction query hIDii. The challenger responds by running algorithm Extract to gen-
It sends di to the
erate the private key di corresponding to the public key hIDii.
adversary.
{ Decryption query hIDi; Cii. The challenger responds by running algorithm Extract to
generate the private key di corresponding to IDi. It then runs algorithm Decrypt to
decrypt the ciphertext Ci using the private key di. It sends the resulting plaintext to
the adversary.
These queries may be asked adaptively, that is, each query qi may depend on the replies
to q1; : : : ; qi1.
4
Challenge: Once the adversary decides that Phase 1 is over it outputs two equal length
plaintexts M0; M1 2 M and an identity ID on which it wishes to be challenged. The only
constraint is that ID did not appear in any private key extraction query in Phase 1.
The challenger picks a random bit b 2 f0; 1g and sets C = Encrypt(params; ID; Mb). It
sends C as the challenge to the adversary.
Phase 2: The adversary issues more queries qm+1; : : : ; qn where query qi is one of:
{ Extraction query hIDii where IDi 6= ID. Challenger responds as in Phase 1.
{ Decryption query hIDi; Cii 6= hID; Ci. Challenger responds as in Phase 1.
These queries may be asked adaptively as in Phase 1.
Guess: Finally, the adversary outputs a guess b0 2 f0; 1g and wins the game if b = b0.
We refer to such an adversary A as an IND-ID-CCA adversary. We dene adversary A’s
advantage in attacking the scheme E as the following function of the security parameter k
(k is given as input to the challenger): AdvE;A(k) = Pr[b = b0] 1
2.
The probability is over the random bits used by the challenger and the adversary.
Using the IND-ID-CCA game we can dene chosen ciphertext security for IBE schemes. As usual, we
say that a function g : R ! R is negligible if for any d > 0 we have jg(k)j < 1=kd for suciently large k.
Denition 2.1. We say that the IBE system E is semantically secure against an adaptive chosen ci-
phertext attack if for any polynomial time IND-ID-CCA adversary A the function AdvE;A(k) is negligible.
As shorthand, we say that E is IND-ID-CCA secure.
Note that the standard denition of chosen ciphertext security (IND-CCA) [37, 2] is the same as
above except that there are no private key extraction queries and the adversary is challenged on a
random public key (rather than a public key of her choice). Private key extraction queries are related
to the denition of chosen ciphertext security in the multiuser settings [7]. After all, our denition
involves multiple public keys belonging to multiple users. In [7] the authors show that that multiuser
IND-CCA is reducible to single user IND-CCA using a standard hybrid argument. This does not hold
in the identity-based settings, IND-ID-CCA, since the adversary gets to choose which public keys to
corrupt during the attack. To emphasize the importance of private key extraction queries we note that
our IBE system can be easily modied (by removing one of the hash functions) into a system which
has chosen ciphertext security when private extraction queries are disallowed. However, the scheme is
completely insecure when extraction queries are allowed.
Semantically secure identity based encryption. The proof of security for our IBE system makes
use of a weaker notion of security known as semantic security (also known as semantic security against
a chosen plaintext attack) [24, 2]. Semantic security is similar to chosen ciphertext security (IND-ID-
CCA) except that the adversary is more limited; it cannot issue decryption queries while attacking the
challenge public key. For a standard public key system (not an identity based system) semantic security
is dened using the following game: (1) the adversary is given a random public key generated by the
challenger, (2) the adversary outputs two equal length messages M0 and M1 and receives the encryption
of Mb from the challenger where b is chosen at random in f0; 1g, (3) the adversary outputs b0 and wins
the game if b = b0. The public key system is said to be semantically secure if no polynomial time
adversary can win the game with a non-negligible advantage. As shorthand we say that a semantically
secure public key system is IND-CPA secure. Semantic security captures our intuition that given a
ciphertext the adversary learns nothing about the corresponding plaintext.
5
To dene semantic security for identity based systems (denoted IND-ID-CPA) we strengthen the
standard denition by allowing the adversary to issue chosen private key extraction queries. Similarly,
the adversary is challenged on a public key ID of her choice. We dene semantic security for identity
based encryption schemes using an IND-ID-CPA game. The game is identical to the IND-ID-CCA game
dened above except that the adversary cannot make any decryption queries. The adversary can only
make private key extraction queries. We say that an identity-based encryption scheme E is semantically
secure (IND-ID-CPA) if no polynomially bounded adversary A has a non-negligible advantage against
the Challenger in the following IND-ID-CPA game:
Setup: The challenger takes a security parameter k and runs the Setup algorithm. It gives
the adversary the resulting system parameters params. It keeps the master-key to itself.
Phase 1: The adversary issues private key extraction queries ID1; : : : ; IDm. The challenger
responds by running algorithm Extract to generate the private key di corresponding to
the public key IDi. It sends di to the adversary. These queries may be asked adaptively.
Challenge: Once the adversary decides that Phase 1 is over it outputs two equal length
plaintexts M0; M1 2 M and a public key ID on which it wishes to be challenged. The
only constraint is that ID did not appear in any private key extraction query in Phase 1.
The challenger picks a random bit b 2 f0; 1g and sets C = Encrypt(params; ID; Mb). It
sends C as the challenge to the adversary.
Phase 2: The adversary issues more extraction queries IDm+1; : : : ; IDn. The only constraint
is that IDi 6= ID. The challenger responds as in Phase 1.
Guess: Finally, the adversary outputs a guess b0 2 f0; 1g and wins the game if b = b0.
We refer to such an adversary A as an IND-ID-CPA adversary. As we did above, the
advantage of an IND-ID-CPA adversary A against the scheme E is the following function of
the security parameter k: AdvE;A(k) = Pr[b = b0] 1
2.
The probability is over the random bits used by the challenger and the adversary.
Denition 2.2. We say that the IBE system E is semantically secure if for any polynomial time IND-
ID-CPA adversary A the function AdvE;A(k) is negligible. As shorthand, we say that E is IND-ID-CPA
secure.
One way identity-based encryption. One can dene an even weaker notion of security called one-
way encryption (OWE) [16]. Roughly speaking, a public key encryption scheme is a one-way encryption
if given the encryption of a random plaintext the adversary cannot produce the plaintext in its entirety.
One way encryption is a weak notion of security since there is nothing preventing the adversary from,
say, learning half the bits of the plaintext. Hence, one-way encryption schemes do not generally provide
secure encryption. In the random oracle model one-way encryption schemes can be used for encrypting
session-keys (the session-key is taken to be the hash of the plaintext). We note that one can extend
the notion of one-way encryption to identity based systems by adding private key extraction queries to
the denition. We do not give the full denition here since in this paper we use semantic security as
the weakest notion of security. See [5] for the full denition of identity based one-way encryption, and
its use as part of an alternative proof strategy for our main result.
Random oracle model. To analyze the security of certain natural cryptographic constructions Bel-
lare and Rogaway introduced an idealized security model called the random oracle model [3]. Roughly
6
speaking, a random oracle is a function H : X ! Y chosen uniformly at random from the set of all
functions fh : X ! Y g (we assume Y is a nite set). An algorithm can query the random oracle at
any point x 2 X and receive the value H(x) in response. Random oracles are used to model crypto-
graphic hash functions such as SHA-1. Note that security in the random oracle model does not imply
security in the real world. Nevertheless, the random oracle model is a useful tool for validating natural
cryptographic constructions. Security proofs in this model prove security against attackers that are
conned to the random oracle world.
Notation. From here on we use Zq to denote the group f0; : : : ; q 1g under addition modulo q. For
a group G of prime order we use G to denote the set G = G n fOg where O is the identity element
in the group G. We use Z+ to denote the set of positive integers.
3 Bilinear maps and the Bilinear Die-Hellman Assumption
Let G1 and G2 be two groups of order q for some large prime q. Our IBE system makes use of a bilinear
map ^e : G1 G1 ! G2 between these two groups. The map must satisfy the following properties:
1. Bilinear: We say that a map ^e : G1 G1 ! G2 is bilinear if ^e(aP; bQ) = ^e(P; Q)ab for all P; Q 2 G1
and all a; b 2 Z.
2. Non-degenerate: The map does not send all pairs in G1 G1 to the identity in G2. Observe that
since G1; G2 are groups of prime order this implies that if P is a generator of G1 then ^e(P; P ) is a
generator of G2.
3. Computable: There is an ecient algorithm to compute ^e(P; Q) for any P; Q 2 G1.
A bilinear map satisfying the three properties above is said to be an admissible bilinear map.
In
Section 5 we give a concrete example of groups G1; G2 and an admissible bilinear map between them.
The group G1 is a subgroup of the additive group of points of an elliptic curve E=Fp. The group G2 is a
subgroup of the multiplicative group of a nite eld F
p2. Therefore, throughout the paper we view G1
as an additive group and G2 as a multiplicative group. As we will see in Section 5.1, the Weil pairing
can be used to construct an admissible bilinear map between these two groups.
The existence of the bilinear map ^e : G1 G1 ! G2 as above has two direct implications to these
groups.
The MOV reduction: Menezes, Okamoto, and Vanstone [32] show that the discrete log problem in
G1 is no harder than the discrete log problem in G2. To see this, let P; Q 2 G1 be an instance
of the discrete log problem in G1 where both P; Q have order q. We wish to nd an 2 Zq such
that Q = P . Let g = ^e(P; P ) and h = ^e(Q; P ). Then, by bilinearity of ^e we know that h = g.
By non-degeneracy of ^e both g; h have order q in G2. Hence, we reduced the discrete log problem
in G1 to a discrete log problem in G2. It follows that for discrete log to be hard in G1 we must
choose our security parameter so that discrete log is hard in G2 (see Section 5).
Decision Die-Hellman is Easy: The Decision Die-Hellman problem (DDH) [4] in G1 is to dis-
tinguish between the distributions hP; aP; bP; abP i and hP; aP; bP; cP i where a; b; c are random
in Z
1. Joux and Nguyen [28] point out that DDH in G1 is easy. To see
this, observe that given P; aP; bP; cP 2 G
q and P is random in G
1 we have
c = ab mod q () ^e(P; cP ) = ^e(aP; bP ):
7
The Computational Die-Hellman problem (CDH) in G1 can still be hard (CDH in G1 is to nd
abP given random hP; aP; bP i). Joux and Nguyen [28] give examples of mappings ^e : G1 G1 !
G2 where CDH in G1 is believed to be hard even though DDH in G1 is easy.
3.1 The Bilinear Die-Hellman Assumption (BDH)
Since the Decision Die-Hellman problem (DDH) in G1 is easy we cannot use DDH to build cryp-
tosystems in the group G1.
Instead, the security of our IBE system is based on a variant of the
Computational Die-Hellman assumption called the Bilinear Die-Hellman Assumption (BDH).
Bilinear Die-Hellman Problem. Let G1; G2 be two groups of prime order q. Let ^e : G1 G1 !
G2 be an admissible bilinear map and let P be a generator of G1. The BDH problem in hG1; G2; ^ei is
as follows: Given hP; aP; bP; cP i for some a; b; c 2 Z
q compute W = ^e(P; P )abc 2 G2. An algorithm A
has advantage in solving BDH in hG1; G2; ^ei if
PrhA(P; aP; bP; cP ) = ^e(P; P )abci
where the probability is over the random choice of a; b; c in Z
random bits of A.
q, the random choice of P 2 G
1, and the
BDH Parameter Generator. We say that a randomized algorithm G is a BDH parameter generator
if (1) G takes a security parameter k 2 Z+, (2) G runs in polynomial time in k, and (3) G outputs a
prime number q, the description of two groups G1; G2 of order q, and the description of an admissible
bilinear map ^e : G1 G1 ! G2. We denote the output of G by G(1k) = hq; G1; G2; ^ei. The security
parameter k is used to determine the size of q; for example, one could take q to be a random k-bit
prime. For i = 1; 2 we assume that the description of the group Gi contains polynomial time (in k)
algorithms for computing the group action in Gi and contains a generator of Gi. The generator of Gi
enables us to generate uniformly random elements in Gi. Similarly, we assume that the description of
^e contains a polynomial time algorithm for computing ^e. We give an example of a BDH parameter
generator in Section 5.1.
BDH Assumption. Let G be a BDH parameter generator. We say that an algorithm A has advan-
tage (k) in solving the BDH problem for G if for suciently large k:
AdvG;A(k) = PrA(q; G1; G2; ^e; P; aP; bP; cP ) = ^e(P; P )abc
hq; G1; G2; ^ei G(1k);
P G
1; a; b; c Z
q (k)
We say that G satises the BDH assumption if for any randomized polynomial time (in k) algorithm
A we have that AdvG;A(k) is a negligible function. When G satises the BDH assumption we say that
BDH is hard in groups generated by G.
In Section 5.1 we give some examples of BDH parameter generators that are believed to satisfy
the BDH assumption. We note that Joux [26] (implicitly) used the BDH assumption to construct a
one-round three party Die-Hellman protocol. The BDH assumption is also needed for constructions
in [46, 40].
8