<<

. 8
( 10)



>>


X.1.1. Chapter Plan. In the next two sections we introduce the work of
Sakai et al. [284], Joux [183] and Boneh and Franklin [38]. Then in Section
X.4, we consider various types of signature schemes derived from pairings.
Section X.5 is concerned with further developments of the IBE scheme of [38]
in the areas of hierarchical identity-based cryptography, intrusion-resilient
cryptography and related topics. Section X.6 considers how the key agree-
ment protocols of [284, 183] have been extended. In the penultimate section,
Section X.7, we look more closely at identity-based cryptography and exam-
ine the impact that pairings have had on infrastructures supporting the use of
public-key cryptography. We also look at a variety of trials and implementa-
tions of pairing-based cryptography. We draw to a close with a look towards
the future in Section X.8.

X.1.2. Pairings as Black Boxes. In this chapter we will largely treat pair-
ings as “black boxes,” by which we mean that we will not be particularly
interested in how the pairings can be selected, computed and so on. Rather
we will treat them as abstract mappings on groups. Naturally, Chapter IX is
the place to look for the details on these issues. The reason to do this is so
that we can concentrate on the general cryptographic principles behind the
schemes and systems we study, without being distracted by the implementa-
tion details. It does occasionally help to look more closely at the pairings,
however. For one thing, the availability of easily computable pairings over
suitably “compact” groups and curves is key to the utility of some of the
pairing-based proposals that we study. And of course the real-world security
of any proposal will depend critically on the actual curves and pairings se-
lected to implement that proposal. It would be inappropriate in a chapter
on applications in cryptography to completely ignore these issues of e¬ciency
and security. So we will “open the box” whenever necessary.
Let us do so now, in order to re-iterate some notation from the previous
chapter and to establish some of the basics for this chapter. We recall the
basic properties of a pairing e : G1 — G2 ’ G3 from Section IX.1. In brief, e
is a bilinear and non-degenerate map and will be derived from a Tate or Weil
pairing on an elliptic curve E(Fq ). In cryptographic applications of pairings,
it is usually more convenient to work with a single subgroup G1 of E(Fq )
having prime order r and generator P as input to the pairing, instead of two
groups G1 and G2 . For this reason, many of the schemes and systems we
study were originally proposed in the context of a “self-pairing” as described
in Section IX.7. To ensure that the cryptographic schemes are not completely
trivial, it is then important that e(P, P ) = 1. The distortion maps of Verheul
[335] are particularly helpful in ensuring that these conditions can be met
for supersingular curves.
As in Section IX.7.3, we assume that E(Fq ) is a supersingular elliptic curve
with r|#E(Fq ) for some prime r. We write k > 1 for the embedding degree
for E and r and assume that E(Fqk ) has no points of order r2 . As usual,
X.1. INTRODUCTION 217

(q k ’1)/r
∈ Fqk for Q ∈ E(Fq )[r] and R ∈ E(Fqk ).
we write e(Q, R) = Q, R r
We then let • denote a non-rational endomorphism of E (a distortion map).
Suitable maps • are de¬ned in Table IX.1. We put G1 = P , where P is
any non-zero point in E(Fq )[r] and G3 = F—k /(F—k )r . We then write e for the
ˆ
q q
map from G1 — G1 to G3 de¬ned by:
e(Q, R) = e(Q, •(R)).
ˆ
The function e is called a modi¬ed pairing. As a consequence of its derivation
ˆ
from the pairing e and distortion map •, it has the following properties:
Bilinearity: For all Q, Q , R, R ∈ G1 , we have
e(Q + Q , R) = e(Q, R) · e(Q , R)
ˆ ˆ ˆ
and
e(Q, R + R ) = e(Q, R) · e(Q, R ).
ˆ ˆ ˆ
Symmetry: For all Q, R ∈ G1 , we have
e(Q, R) = e(R, Q).
ˆ ˆ
Non-degeneracy: We have
e(P, P ) = 1.
ˆ
Hence we have: e(Q, P ) = 1 for all Q ∈ G1 , Q = O and e(P, R) = 1
ˆ ˆ
for all R ∈ G1 , R = O.
Although our notation inherited from the previous chapter suggests that
the map e must be derived from the Tate pairing, this need not be the case.
ˆ
The Weil pairing can also be used. However, as Chapter IX spells out, the
Tate pairing is usually a better choice from an implementation perspective.
Relying on distortion maps in this way limits us to using supersingular
curves. There may be good implementation or security reasons for working
with curves other than these, again as Chapter IX makes clear. (In partic-
ular, special purpose algorithms [2, 3, 86, 185] can be applied to solve the
discrete logarithm problem in Fqk when E is one of the supersingular curves
over a ¬eld of characteristic 2 or 3 in Table IX.1. This may mean that larger
parameters than at ¬rst appears must be chosen to obtain the required secu-
rity levels.) Most of the cryptographic schemes that were originally de¬ned
in the self-pairing setting can be adapted to operate with ordinary curves and
unmodi¬ed pairings, at the cost of some minor inconvenience (and sometimes
a loss of bandwidth e¬ciency). We will encounter situations where ordinary
curves are in fact to be preferred. Moreover, we will present some schemes us-
ing the language of self-pairings that were originally de¬ned using unmodi¬ed
pairings. We will note in the text where this is the case.
We can summarize the above digression into some of the technicalities
of pairings as follows. By carefully selecting an elliptic curve E(Fq ), we can
obtain a symmetric, bilinear map e : G1 — G1 ’ G3 with the property
ˆ
that e(P, P ) = 1. Here, P of prime order r on E(Fq ) generates G1 and
ˆ
218 X. CRYPTOGRAPHY FROM PAIRINGS

G3 is a subgroup of Fqk for some small k. When parameters G1 , G3 , e are
ˆ
appropriately selected, we also have the following properties:
E¬ciency: The computation of e can be made relatively e¬cient (equiv-
ˆ
alent perhaps to a few point multiplications on E(Fq )). Elements of G1
and G3 have relatively compact descriptions as bit-strings, and arith-
metic in these groups can be e¬ciently implemented.
Security: The bilinear Di¬e“Hellman problem and the decision bilinear
Di¬e“Hellman problem are both computationally hard.2


X.2. Key Distribution Schemes
In this section we review the work of Sakai et al. [284] and Joux [183]
on key distribution schemes built from pairings. These papers paved the way
for Boneh and Franklin™s identity-based encryption scheme, the subject of
Section X.3. Note that both papers considered only unmodi¬ed pairings. We
have translated their schemes into the self-pairing setting in our presentation.

X.2.1. Identity-Based Non-Interactive Key Distribution. Key distri-
bution is one of the most basic problems in cryptography. For example,
frequently refreshed, random keys are needed for symmetric encryption al-
gorithms and MACs to create con¬dential and integrity-protected channels.
Consider the situation of two parties A and B who want to compute a shared
key KAB but cannot a¬ord to engage in a Di¬e“Hellman protocol (perhaps
one of them is initially o¬„ine or they cannot a¬ord the communications over-
head of an interactive protocol).
Sakai et al. [284] proposed a pairing-based solution to this problem of
constructing a non-interactive key distribution scheme (NIKDS). An impor-
tant and interesting feature of their solution is its identity-based nature. The
notion of identity-based cryptography dates back to work of Shamir [296].
Shamir™s vision was to do away with public keys and the clumsy certi¬cates
for those public keys, and instead build cryptographic schemes and proto-
cols in which entities™ public keys could be derived from their identities (or
other identifying information) alone. In place of a Certi¬cation Authority
(CA), Shamir envisaged a Trusted Authority (TA) who would be responsible
for the issuance of private keys and the maintenance of system parameters.
Whilst Shamir was able to construct an identity-based signature scheme in
[296], and identity-based NIKDS followed from a variety of authors (see [240,
p. 587]), the problem of constructing a truly practical and provably secure
identity-based encryption scheme remained an open problem until the advent
of pairing-based cryptography. As we shall see in Section X.3, the work of
2
Note that these problems are de¬ned in Section IX.11.3 for unmodi¬ed pairings. We
will de¬ne the BDH problem for modi¬ed pairings below, after which the de¬nition of the
DBDH problem should be obvious.
X.2. KEY DISTRIBUTION SCHEMES 219

Sakai et al. [284] can be regarded as being pivotal in Boneh and Franklin™s
solution of this problem.
Sakai et al. make use of a TA who chooses and makes public the system
parameters of the form G1 , G3 , e (with properties as in Section X.1.2) along
ˆ
with a cryptographic hash function

H1 : {0, 1}— ’ G1

mapping binary strings of arbitrary length onto elements of G1 . We brie¬‚y
indicate in Section X.3.1 below how such a hash function can be constructed.
The TA also selects but keeps secret a master secret s ∈ Z— . The TA interacts
r
with A and B, providing each of them with a private key over a con¬dential
and authenticated channel. These private keys depend on s and the individ-
uals™ identities: the TA computes as A™s secret the value SA = [s]QA , where
QA = H1 (IDA ) ∈ G1 is a publicly computable function of A™s identity. Like-
wise, the TA gives B the value SB = [s]QB , where QB = H1 (IDB ). Because
of its role in distributing private keys, the TA is also known as a Private Key
Generator (PKG) in these kinds of applications.
Now, with this keying infrastructure in place, consider the equalities:

e(SA , QB ) = e([s]QA , QB ) = e(QA , QB )s = e(QA , [s]QB ) = e(QA , SB ),
ˆ ˆ ˆ ˆ ˆ

where we have made use of the bilinearity of e. On the one hand, A has the
ˆ
secret SA and can compute QB = H1 (IDB ) using the public hash function H1 .
On the other hand, B can compute QA and has the secret SB . Thus both
parties can compute the value KAB = e(QA , QB )s and, provided they know
ˆ
each others™ identifying information, can do so without any interaction at all.
A key suitable for use in cryptographic applications can be derived from KAB
by the appropriate use of a key derivation function.
A closely related version of this procedure was rediscovered somewhat
later by Dupont and Enge [108]. Their scheme works in the unmodi¬ed
setting and requires that each entity receive two private key components (one
in each group G1 and G2 ). The security proof in [108] is easily adapted to
the self-pairing setting. The adapted proof models the hash function H1 as a
random oracle and allows the adversary the power to obtain the private keys
of arbitrary entities (except, of course, the keys of entities A and B).
The proof shows that the above procedure generates a key e(QA , QB )
ˆ
which cannot be computed by an adversary, provided that the (modi¬ed)
bilinear Di¬e“Hellman problem (BDH problem) is hard. This problem can
be stated informally as follows (c.f. the de¬nition in Section IX.11.3):
Bilinear Di¬e“Hellman Problem (BDH Problem): given P , P1 =
[a]P , P2 = [b]P and P3 = [c]P in G1 with a, b and c selected uniformly at
random from Z— , compute
r

e(P, P )abc .
ˆ
220 X. CRYPTOGRAPHY FROM PAIRINGS

One implication of the security proof is that the scheme is collusion re-
sistant: no coalition of entities excluding A and B can join together and
compromise the key KAB . Notice, however, that the TA can generate A and
B™s common key for itself “ the scheme enjoys (or su¬ers from, depending on
one™s point of view and the application in mind) key escrow. For this reason,
A and B must trust the TA not to eavesdrop on communications encrypted
by this key and not to disclose the key to other parties. In particular, they
must trust the TA to adequately check claimants™ identities before issuing
them with private keys.
For the purpose of comparison, consider the following alternative tradi-
tional (i.e., certi¬cate-based) means of realizing a NIKDS. A CA publishes
system parameters E(Fq ), P , where P on E is of prime order r. A chooses a
private value a, calculates the public value qA = [a]P and obtains a certi¬cate
on IDA and qA from a Certi¬cation Authority (CA). Entity B does the same
with his value b. Now A can compute a common key as follows: A fetches B™s
certi¬cate and veri¬es that it is valid by checking the CA™s signature. Now
A can combine his secret a with B™s value [b]P to obtain [ab]P . This value
constitutes the common key. Here, A and B have simply engaged in a non-
interactive version of the ECDH protocol. The complexity with this approach
comes from the need for A to obtain B™s certi¬cate, verify its correctness and
check its revocation status, and vice versa. These checks require the use of a
public-key infrastructure (PKI). In contrast, with the identity-based scheme
of [284], all A needs is B™s identity string IDB and the public parameters of
the TA.3 This could be B™s e-mail or IP address, or any other string which
identi¬es B uniquely within the context of the system. The trust in pub-
lic values does not come from certi¬cates but is rather produced implicitly
through A™s trust in the TA™s private key issuance procedures.
At this point, the reader would be justi¬ed in asking: why do A and
B simply not use the key KAB as the basis for deriving an encryption key?
Moreover, if they do, why does the combination of Sakai et al.™s identity-
based NIKDS with this encryption not constitute an identity-based encryp-
tion scheme? There are two parts to the answer to this latter question. First
of all, the key they agree on is static, whereas a dynamic message key would
be preferable. Secondly, and more importantly, both A and B must have
registered ahead of time and have received their private keys before they can
communicate in this way. A true public-key encryption scheme would not
require the encrypting party to register and obtain such a key.

X.2.2. Three-Party Key Distribution. Around the same time that Sakai
et al. proposed their two-party NIKDS, Joux [183] put forward a three-party

3
The revocation issue for the identity-based approach also requires careful consid-
eration. We shall return to this topic in Section X.7, where we take a closer look at
identity-based systems.
X.3. IDENTITY-BASED ENCRYPTION 221

key agreement protocol with the novel feature that only one (broadcast) mes-
sage per participant is required to achieve key agreement. Thus only one
round of communication is needed to establish a shared key. This contrasts
sharply with the two rounds that are needed if a naive extension of the (Ellip-
tic Curve) Di¬e“Hellman protocol is used. We sketch Joux™s protocol. First
of all, it is assumed that the three parties have agreed in advance on system
parameters G1 , G3 , e, P . Then entity A selects a ∈ Z— uniformly at random
ˆ r
and broadcasts an ephemeral value [a]P to entities B and C. Entity B (re-
spectively C) selects b (resp. c) in the same way and broadcasts [b]P (resp.
[c]P ) to the other entities. Now by bilinearity we have:

e([b]P, [c]P )a = e([a]P, [c]P )b = e([a]P, [b]P )c
ˆ ˆ ˆ

so that each party, using its private value and the two public values, can
calculate the common value

KABC = e(P, P )abc ∈ G3 .
ˆ

This value can be used as keying material to derive session keys. On the other
hand, an adversary who only sees the broadcast messages [a]P , [b]P , [c]P is
left with an instance of the BDH problem to solve in order to calculate KABC .
This last statement can be formalized to construct a security proof relating
the security of this protocol against passive adversaries to the hardness of the
(modi¬ed) BDH problem. The protocol is vulnerable to an extension of the
classic man-in-the-middle attack conducted by an active adversary. We will
return to this issue in Section X.6 below.
Note the importance of the fact that e(P, P ) = 1 here. Without this
ˆ
condition, KABC could trivially equal 1 ∈ G3 . Joux™s protocol was originally
stated in the context of an unmodi¬ed pairing and required each participant
to broadcast a pair of independent points of the form [a]P, [a]Q in order to
avoid degeneracy in the pairing computation. Using modi¬ed pairings limits
the range of curves for which the protocol can be realized but decreases its
bandwidth requirements. This point was ¬rst observed by Verheul [335].


X.3. Identity-Based Encryption
As we have discussed above, the construction of a workable and provably
secure identity-based encryption (IBE) scheme was, until recently, an open
problem dating back to Shamir™s 1984 paper [296]. Two solutions appeared
in rapid succession in early 2001 “ the pairing-based approach of Boneh and
Franklin [38] (appearing in an extended version as [39]) and Cocks™ scheme
based on the Quadratic Residuosity problem [83]. It has since become ap-
parent that Cocks™ scheme was discovered some years earlier but remained
unpublished until 2001, when the circulation of Boneh and Franklin™s scheme
222 X. CRYPTOGRAPHY FROM PAIRINGS

prompted its disclosure.4 We do not discuss Cocks™ scheme any further here
but recommend that the interested reader consult [83] for the details.
X.3.1. The Basic Scheme of Boneh and Franklin. We ¬rst discuss the
scheme BasicIdent of [39]. This basic IBE scheme is useful as a teaching
tool, but is not suited for practical use (because its security guarantees are too
weak for most applications). We will study the full scheme FullIdent of [39]
in Section X.3.3. The IBE scheme BasicIdent makes use of essentially the
same keying infrastructure as was introduced above in describing the NIKDS
of Sakai et al. The TA (or PKG) publishes system parameters G1 , G3 , e . Inˆ
addition, the PKG publishes a generator P for G1 , together with the point
Q0 = [s]P , where, as before, s ∈ Z— is a master secret. Note that Q0 is
r
denoted by Ppub in [39]. Descriptions of cryptographic hash functions
H1 : {0, 1}— ’ G1 , H2 : G3 ’ {0, 1}n
are also made public. Here, n will be the bit-length of plaintext messages. So
the complete set of system parameters is
G1 , G3 , e, P, Q0 , n, H1 , H2 .
ˆ
As in the scheme of [284], each entity A must be given a copy of its private
key SA = [s]QA = [s]H1 (IDA ) over a secure channel.
With this set of parameters and keys in place, BasicIdent encryption
proceeds as follows. To encrypt an n-bit plaintext M for entity A with identity
IDA , entity B computes QA = H1 (IDA ), selects t ∈ Z— uniformly at random
r
and computes the ciphertext as:
C = [t]P, M • H2 (ˆ(QA , Q0 )t ) ∈ G1 — {0, 1}n .
e
To decrypt a received ciphertext C = U, V in the scheme BasicIdent,
entity A computes
M = V • H2 (ˆ(SA , U ))
e
using its private key SA = [s]QA .
To see that encryption and decryption are inverse operations, note that
(by bilinearity)
e(QA , Q0 )t = e(QA , P )st = e([s]QA , [t]P ) = e(SA , U ).
ˆ ˆ ˆ ˆ
On the one hand, the encryption mask H2 (ˆ(QA , Q0 )t ) that is computed by
e
entity B is the same as that computed by A, namely, H2 (ˆ([s]QA , U )). On
e
the other hand, the computation of the encryption mask by an eavesdropper
(informally) requires the computation of e(QA , Q0 )t from the values P , QA ,
ˆ
Q0 and U = [t]P . This task is clearly related to solving the (modi¬ed) BDH
problem.
4
Very recently, it has come to our attention that Sakai, Ohgishi and Kasahara proposed
an IBE scheme using pairings in May 2000. Their paper was published in Japanese in the
proceedings of the 2001 Symposium on Cryptography and Information Security, January
2001; an English version is available from the authors.
X.3. IDENTITY-BASED ENCRYPTION 223

Notice that encryption and decryption each require one pairing compu-
tation, but that the cost of this can be spread over many encryptions if the
encrypting party repeatedly sends messages to the same entity. A small num-
ber of other operations is also needed by each entity (dominated by hashing
and exponentiation in G1 and G3 ). Ciphertexts are relatively compact: they
are equal in size to the plaintext plus the number of bits needed to represent
an element of G1 .
The de¬nition of the hash function H1 mapping arbitrary strings onto
elements of G1 requires care; a detailed exposition is beyond the scope of this
survey. The reader is referred to [39, Sections 4.3 and 5.2] for the details of
one approach that works for a particular class of curves and to [42, Section
3.3] for a less elegant method which works for general curves.
X.3.2. Relationship to Earlier Work. It is instructive to examine how
this basic identity-based encryption scheme relates to earlier work. There are
(at least) two di¬erent ways to do so.
Writing QA = [a]P for some a ∈ Z— , we see that the value e(QA , Q0 )t
ˆ
r
ast
appearing in BasicIdent is equal to e(P, P ) . Thus it is formally equal
ˆ
to the shared value that would be agreed in an instance of Joux™s protocol
in which the ephemeral values “broadcast” by the entities were QA = [a]P ,
Q0 = [s]P and U = [t]P . In the encryption scheme, only U is actually
transmitted; the other values are static in the scheme and made available
to B through the system parameters and hashing of A™s identity. One can
think of Q0 = [s]P as being the ephemeral value from a “dummy” entity
here. Entity A gets the value U from B and is given the ability to compute
e(P, P )ast when the PKG gives it the value [s]QA = [sa]P . Thus Boneh and
ˆ
Franklin™s IBE scheme can be regarded as a rather strange instance of Joux™s
protocol.
Perhaps a more pro¬table way to understand the scheme is to compare it
to ElGamal encryption. In a variant of textbook ElGamal, an entity A has a
private key xA ∈ Z— and a public key yA = g xA . To encrypt a message for A,
r
entity B selects t ∈ Z— uniformly at random and computes the ciphertext as:
r

C = g t , M • H2 (yA t )
while to decrypt C = U, V , entity A computes
M = V • H2 (U xA ).
Thus one can regard the basic IBE scheme of Boneh and Franklin as being
an adaptation of ElGamal encryption in which e(QA , Q0 ), computed from
ˆ
system parameters and A™s identity, replaces the public key yA .
We have already noted the similarities in keying infrastructures used by
Boneh and Franklin™s IBE scheme and in the NIKDS of Sakai et al. [284].
The above discussion shows a relationship between Boneh and Franklin™s IBE
scheme and Joux™s protocol [183]. However, it would be wrong to leave the
impression that Boneh and Franklin™s scheme is just a simple development
224 X. CRYPTOGRAPHY FROM PAIRINGS

of ideas in these earlier papers. Prior to Boneh and Franklin™s work, Joux™s
protocol was merely an interesting curiosity and the work of [284] almost
unknown to the wider community. It was Boneh and Franklin™s work that
quickly led to a wider realization that pairings could be a very useful con-
structive cryptographic tool and the spate of research that followed.
X.3.3. Security of Identity-Based Encryption. Boneh and Franklin pro-
vide in [39] a variant of BasicIdent named FullIdent which o¬ers stronger
security guarantees. In particular, the security of FullIdent can be related
to the hardness of the BDH problem in a model that naturally extends the
widely-accepted IND-CCA2 model for public-key encryption (see De¬nition
III.4) to the identity-based setting. We present the scheme FullIdent below,
outline the security model introduced in [39] and then discuss the security of
FullIdent in this model.
In general, an IBE scheme can be de¬ned by four algorithms, with func-
tions as suggested by their names: Setup, (Private Key) Extract, Encrypt
and Decrypt. For the scheme FullIdent, these operate as follows:
Setup: This algorithm takes as input a security parameter and outputs the
system parameters:
params = G1 , G3 , e, n, P, Q0 , H1 , H2 , H3 , H4 .
ˆ
Here G1 , G3 and e are the usual objects5 , n is the bit-length of plaintexts,
ˆ
P generates G1 and Q0 = [s]P , where s is the scheme™s master secret.
Hash functions H1 and H2 are as above, while H3 : {0, 1}2n ’ Z— and r
H4 : {0, 1} ’ {0, 1} are additional hash functions. In principle, all of
n n

these parameters may depend on .
Extract: This algorithm takes as input an identity string ID and returns the
corresponding private key [s]H1 (ID).
Encrypt: To encrypt the plaintext M ∈ {0, 1}n for entity A with identity
IDA , perform the following steps:
1. Compute QA = H1 (IDA ) ∈ G1 .
2. Choose a random σ ∈ {0, 1}n .
3. Set t = H3 (σ, M ).
4. Compute and output the ciphertext:
C = [t]P, σ • H2 (ˆ(QA , Q0 )t ), M • H4 (σ) ∈ G1 — {0, 1}2n .
e

Decrypt: Suppose C = U, V, W ∈ G1 — {0, 1}2n is a ciphertext encrypted
for A. To decrypt C using the private key [s]QA :
1. Compute σ := V • H2 (ˆ([s]QA , U )).
e
2. Compute M := W • H4 (σ ).
5
Boneh and Franklin make use of a subsidiary instance generating algorithm IG to
produce the parameters G1 , G3 , e (possibly probabilistically) from input , the security
ˆ
parameter.
X.3. IDENTITY-BASED ENCRYPTION 225

3. Set t = H3 (σ , M ) and test if U = [t ]P . If not, reject the ciphertext.
4. Otherwise, output M as the decryption of C.




The reader should compare FullIdent with the basic scheme above.
When C is a valid encryption of M , it is quite easy to see that decrypt-
ing C will result in an output M = M . The value H2 (e(QA , Q0 )t ) is still
used as an encryption mask, but now it encrypts a string σ rather than the
plaintext itself. The string σ is subsequently used to form an encryption key
H4 (σ) to mask the plaintext. The encryption process also now derives t by
hashing rather than by random choice; this provides the decryption algorithm
with a checking facility to reject ciphertexts that are not of the correct form.
In fact, the scheme FullIdent is obtained from the basic scheme of the
previous section by applying the Fujisaki“Okamoto hybridization technique
[128]. It is this technique that ensures FullIdent meets the strong security
de¬nition in the model developed by Boneh and Franklin in [39]. In that
model, an adversary A plays against a challenger C in the following game:
IND-ID-CCA Security Game: The game runs in ¬ve steps:
Setup: C runs algorithm Setup on input some value , gives A the system
parameters params and keeps the master secret s to itself.
Phase 1: A issues a series of queries, each of which is either an Extract
query on an identity, in which case C responds with the appropriate private
key, or a Decrypt query on an identity/ciphertext combination, in which case
C responds with an appropriate plaintext (or possibly a fail message).
Challenge: Once A decides to end Phase 1, it selects two plaintexts M0 , M1
and an identity IDch on which it wishes to be challenged. We insist that IDch
not be the subject of an earlier Extract query. Challenger C then chooses b
at random from {0, 1} and runs algorithm Encrypt on Mb and IDch to obtain
the challenge ciphertext C — ; C then gives C — to A.
Phase 2: A issues another series of queries as in Phase 1, with the restriction
that no Extract query be on IDch and that no Decrypt query be on the
combination IDch , C — . C responds to these as before.
Guess: Finally, A outputs a guess b and wins the game if b = b.
Adversary A™s advantage is de¬ned to be Adv(A) := 2| Pr [b = b] ’ 1 |, 2
where the probability is measured over any random bits used by C (for exam-
ple, in the Setup algorithm) and A (for example, in choosing ciphertexts and
identities to attack). An IBE scheme is said to be semantically secure against
an adaptive chosen ciphertext attack (IND-ID-CCA secure) if no polynomi-
ally bounded adversary A has a non-negligible advantage in the above game.
Here, non-negligiblity is de¬ned in terms of the security parameter used
226 X. CRYPTOGRAPHY FROM PAIRINGS

in the Setup algorithm.6 This model and de¬nition of security extends the
by-now-standard IND-CCA2 notion of security for public-key encryption: it
allows the adversary to access private keys of arbitrary entities (except the
challenge identity, of course) as well as giving the adversary access to a de-
cryption oracle. It also allows the adversary to choose the public key on which
it is to be challenged and automatically captures attacks involving colluding
entities.
It is proved in [39] that the scheme FullIdent is IND-ID-CCA secure in
the Random Oracle model, provided that there is no polynomially bounded
algorithm having a non-negligible advantage in solving the BDH problem.
Here, parameters G1 , G2 , e for the BDH problem are assumed to be gener-
ˆ
ated with the same distribution as by the Setup algorithm of FullIdent.
The proof of security for FullIdent proceeds in several stages. First it is
shown, via a fairly standard simulation argument, that an adversary who can
break FullIdent (in the sense of winning the IND-ID-CCA security game)
can be used to produce an adversary that breaks a related standard public-key
encryption scheme in an IND-CCA2 game. Then results of [128] are invoked
to relate the IND-CCA2 security of the public-key scheme to the security
of a simpler public-key encryption scheme BasicPub, but in a much weaker
attack model (one without decryption queries). Finally, it can be shown
directly that an adversary breaking BasicPub can be used to construct an
algorithm to solve instances of the BDH problem. For details of these steps,
see [39, Lemma 4.3, Lemma 4.6 and Theorem 4.5].7 The security analysis in
[39] depends in a crucial way on the replacement of hash functions H1 , H2 , H3
and H4 by random oracles. At the time of writing, it is still an open problem
to produce an IBE scheme that is provably secure in Boneh and Franklin™s
security model, but without modelling any hash functions as random oracles.
The composition of a sequence of security reductions also yields a fairly loose
relationship between the security of FullIdent and the hardness of the BDH
problem. Tightening this relationship seems to be a di¬cult challenge.
This concludes our description of the identity-based encryption scheme
of Boneh and Franklin [39]. The paper [39] contains much else of interest
besides, and we recommend it be read in detail by every reader who has more
than a passing interest in the subject.

X.3.4. Further Encryption Schemes. In [335], Verheul showed how pair-
ings can be used to build a scheme supporting both non-repudiable signatures
and escrowable public-key encryption using only a single public key.
6
A function f of is said to be negligible if, for any polynomial p( ), there exists 0
such that, for all > 0 , f ( ) < 1/p( ). Naturally, a function is said to be non-negligible if
it is not negligible.
7
But note that the proof of Lemma 4.6 in [39] requires a small repair: when coini = 1,
the values bi should be set to equal 1, so that the ciphertexts Ci do not always fail the
consistency check in the decryption algorithm of BasicPubhy .
X.3. IDENTITY-BASED ENCRYPTION 227

The main idea of Verheul™s scheme is as follows. As usual, we have system
parameters G1 , G3 , e with G1 of prime order r generated by point P . An
ˆ
entity A chooses as its private signing key xA ∈ Z— ; the corresponding public
r
key used for both encryption and signatures is yA = e(P, P )xA ∈ G3 . A CA
ˆ
then issues A with a certi¬cate on the value yA (the scheme is not identity-
based). Any discrete logarithm based digital signature algorithm employing
the values g = e(P, P ), xA and yA = g xA can be used. To encrypt a message
ˆ
M ∈ {0, 1} for A, the sender generates a random t ∈ Z— and computes the
n
r
ciphertext:
C = [t]P, M • H2 ((yA )t ) .
Here, as before, H2 : G3 ’ {0, 1}n is a cryptographic hash function. To
decrypt C = U, V , entity A computes
M = V • H2 (ˆ(P, U )xA ).
e
Notice the similarity of this encryption scheme to that in Section X.3.2. The
escrow service is supported as follows. Ahead of time, A sends to the escrow
agent the value YA = [xA ]P . The escrow agent can then calculate the value
e(P, U )xA for itself using its knowledge of YA and bilinearity:
ˆ
e(YA , U ) = e([xA ]P, U ) = e(P, U )xA .
ˆ ˆ ˆ
Note that A does not give up its private signing key xA to the escrow agent.
Thus A™s signatures remain non-repudiable. Verheul™s scheme currently lacks
a formal security proof. Such a proof would show that the same public key
can safely be used for both signature and encryption.
Verheul™s scheme may be described as providing a non-global escrow: en-
tity A must choose to send the value YA to the escrow agent in order that the
agent may recover plaintexts. Boneh and Franklin in [39, Section 7] gave yet
another variant of pairing-based ElGamal encryption that provides escrow
yet does not require interaction between escrow agent and users. For this
reason, they described their scheme as providing global escrow. Their scheme
works as follows. The system parameters, chosen by the escrow agent, are
G1 , G3 , e, P, Q0 , n, H2 . These are all de¬ned as for the basic IBE scheme in
ˆ
Section X.3.1. In particular, Q0 = [s]P , where s is a master secret. An entity
A™s key-pair is of the form xA , YA = [xA ]P . Thus A™s public key is identical
to the escrowed key in Verheul™s scheme, and A™s private key is the same in
the two schemes. Now to encrypt M ∈ {0, 1}n for A, the sender generates a
random t ∈ Z— and computes the ciphertext:
r

C = [t]P, M • H2 (ˆ(YA , Q0 )t ) .
e
To decrypt C = U, V , entity A computes
M = V • H2 (ˆ([xA ]Q0 , U ))
e
while the escrow agent computes
M = V • H2 (ˆ([s]YA , U )).
e
228 X. CRYPTOGRAPHY FROM PAIRINGS

It is straightforward to see that (by bilinearity) both decryption algorithms
produce the plaintext M . It is claimed in [39] that the security of this scheme
rests on the hardness of the BDH problem. To see informally why this is so,
note that to decrypt an adversary must compute the value e(P, P )stxA given
ˆ
the values Q0 = [s]P , U = [t]P and YA = [xA ]P .
Lynn [228] has shown how to combine ideas from the IBE scheme of [39]
and the NIKDS of [284] to produce an authenticated identity-based encryp-
tion scheme. In this scheme, a recipient A can check which entity sent any
particular ciphertext. Simplifying slightly, this ability is provided by using
the NIKDS key e(QA , QB )s in place of the value e(QA , Q0 )r in the Boneh“
ˆ ˆ
Franklin IBE scheme. This approach cannot yield a non-repudiation service,
since A itself could have prepared any authenticated ciphertext purported to
be from B.
We will report on the hierarchical identity-based encryption scheme of
Gentry and Silverberg [147] and related work in Section X.5.

X.4. Signature Schemes
In this section we outline how pairings have been used to build signature
schemes of various kinds. Our coverage includes identity-based signature and
signcryption schemes, standard (i.e., not identity-based) signature schemes
and a variety of special-purpose signature schemes.

X.4.1. Identity-Based Signature Schemes. Not long after the appear-
ance of Boneh and Franklin™s IBE scheme, a rash of identity-based signature
(IBS) schemes appeared [62, 163, 164, 272]. Sakai et al.™s paper [284] also
contains an IBS; another IBS scheme appears in [350]. Since IBS schemes
have been known since Shamir™s original work on identity-based cryptography
in [296], the main reason to be interested in these new schemes is that they
can make use of the same keying infrastructure as the IBE scheme of [39].
Being identity-based, and hence having built in escrow of private keys, none
of the schemes can o¬er a true non-repudiation service. The schemes o¬er a
variety of trade-o¬s in terms of their computational requirements on signer
and veri¬er, and signature sizes. The scheme of [62] enjoys a security proof
in a model that extends the standard adaptive chosen message attack model
for (normal) signature schemes of [150] to the identity-based setting. The
proof is in the random oracle model and relates the scheme™s security to the
hardness of the computational Di¬e“Hellman problem (CDH problem) in G1
using the Forking Lemma methodology [276]. The ¬rst IBS scheme of [163]
also has a security proof; the second scheme in [163] was broken in [75].
To give a ¬‚avour of how these various IBS schemes operate, we present a
version of the scheme of Cha and Cheon [62] here. An IBS scheme is de¬ned
by four algorithms: Setup, Extract, Sign and Verify. For the scheme of
[62], these operate as follows:
X.4. SIGNATURE SCHEMES 229

Setup: This algorithm takes as input a security parameter and outputs the
system parameters:
params = G1 , G3 , e, P, Q0 , H1 , H2 .
ˆ
Here G1 , G3 , e, P and Q0 = [s]P are as usual; s is the scheme™s master
ˆ
secret. The hash function H1 : {0, 1}— ’ G1 is as in Boneh and Franklin™s
IBE scheme, while H2 : {0, 1}— — G1 ’ Zr is a second hash function.
Extract: This algorithm takes as input an identity ID and returns the cor-
responding private key SID = [s]H1 (ID). Notice that this key is identical to
the private key in the IBE scheme of Boneh and Franklin [39].8
Sign: To sign a message M ∈ {0, 1}— , entity A with identity IDA and private
key SA = [s]H1 (IDA ) chooses a random t ∈ Zr and outputs a signature
σ = U, V where U = [t]H1 (IDA ), h = H2 (M, U ) and V = [t + h]SA .
Verify: To verify a signature σ = U, V on a message M for identity IDA ,
an entity simply checks whether the equation
e(Q0 , U + hQA ) = e(P, V )
ˆ ˆ
holds.
It is a simple exercise to show that the above IBS scheme is sound (sig-
natures created using Sign will verify correctly using Verify).
The IBS scheme of [62] was originally presented in the context of any gap
Di¬e“Hellman group. Informally speaking, these are groups in which the
CDH problem is hard but the DDH problem is easy, a notion ¬rst formalized
in [263] and further explored in [186]. The signature generation algorithm
uses the private key DA to create Di¬e“Hellman tuples while the signature
veri¬cation algorithm amounts to deciding whether P, Q0 , U + hQA , V is a
valid Di¬e“Hellman tuple. Since all the realizations of such gap groups cur-
rently known use pairings on elliptic curves, we have preferred a presentation
using pairings.
X.4.2. Short Signatures. In [42, 43], Boneh, Lynn and Shacham used
pairings to construct a (normal) signature scheme in which the signatures are
rather short: for example, one version of their scheme has signatures that are
approximately 170 bits in length whilst o¬ering security comparable to that
of 320-bit DSA signatures.
A simpli¬ed version of this BLS scheme can be described using modi¬ed
pairings though (for reasons which will be discussed below) this does not lead
to the preferred instantiation. This is essentially the approach taken in [42].
We will begin with this approach for ease of presentation.
8
It is generally good cryptographic practice to use di¬erent keys for di¬erent functions.
If this is required here, then a separate master secret could be used for the IBS scheme,
or the identity string ID could be replaced by the string ID||“Sig”, where “||” denotes a
concatenation of strings.
230 X. CRYPTOGRAPHY FROM PAIRINGS

As usual, we work with system parameters G1 , G3 , e and assume P of
ˆ
prime order r generates G1 . We also need a hash function H : {0, 1}— ’ G1 .
A user™s private key is a value x selected at random from Zr , and the matching
public key is [x]P ∈ G1 . The signature on a message M ∈ {0, 1}— is simply
σ = [x]H(M ) ∈ G1 . To verify a purported signature σ on message M , the
veri¬er checks that the 4-tuple:
P, [x]P, H(M ), σ
is a Di¬e“Hellman tuple. This can be done by checking that the equation:
e(σ, P ) = e(H(M ), [x]P )
ˆ ˆ
holds.
As with the IBS scheme of [62], this signature scheme exploits the fact
that the signer can create Di¬e“Hellman tuples in G1 using knowledge of
the private key x while the veri¬er can check signatures using the fact that
the DDH problem is easy in G1 , thanks to the presence of the pairing e. ˆ
The scheme is very closely related to the undeniable signature scheme of
Chaum and van Antwerpen [66, 67]. That scheme has an identical signing
procedure (except for a change of notation), but the con¬rmation (or denial
of a signature) is via a zero-knowledge protocol in which the signer proves (or
disproves) that the tuple is a Di¬e“Hellman tuple. One can view the scheme
of [42] as being the result of replacing the con¬rmation and denial protocols
by a pairing computation. This makes the signatures veri¬able without the
aid of the signer, thus converting the undeniable signature scheme into a
standard one. Of course, the BLS construction works more generally in the
setting of gap Di¬e“Hellman groups; the observation that signature schemes
could be constructed from gap problems was made in [263, Section 4.1],
though without a speci¬c (standard) scheme being presented. The scheme of
[42] can also be viewed in another way. As is noted in [39], Naor has pointed
out that any IBE scheme can be used to construct a signature scheme as
follows: the private signing key is the master key for the IBE scheme, the
public veri¬cation key is the set of public parameters of the IBE scheme,
and the signature on a message M is simply the private key for “identity”
M in the IBE scheme. To verify a signature, the veri¬er can encrypt a
random string and check that the signature (viewed as a decryption key)
properly decrypts the result. In the special case of the IBE scheme of Boneh
and Franklin, the signature for message M would be the IBE private key
[s]H1 (M ). This is simply a BLS signature on M . The BLS scheme replaces
the trial encryption/decryption with a more e¬cient procedure, but it is
otherwise the signature scheme that can be derived from the Boneh“Franklin
IBE scheme using Naor™s construction.
It is not di¬cult to show that the BLS signature scheme is secure (in the
usual chosen message attack model of [150] and regarding H as a random
oracle) provided the CDH problem is hard in G1 .
X.4. SIGNATURE SCHEMES 231

A signature in this scheme consists of a single element of G1 (as does the
public key). Thus short signatures will result whenever G1 can be arranged
to have a compact representation. Using point compression, elements of G1
can be represented using roughly log2 q bits if G1 is a subgroup of E(Fq ).9
So in order to obtain signatures that are as short as possible, it is desirable
to make q as small as possible whilst keeping the ECDHP in G1 (a subgroup
of E(Fq )) hard enough to make the scheme secure. However, one must bear
in mind that, because of the presence of the pairing e, the ECDLP in E(Fq )
ˆ
can be translated via the MOV reduction into the DLP in Fqk , where k is the
embedding degree of E(Fq ). Thus the security of the scheme not only rests
on the di¬culty of solving the ECDHP in E(Fq ), but also on the hardness of
the DLP in Fqk .
At ¬rst sight, it seems that Table IX.1 gives a pair of characteristic 3
supersingular curves E1 , E2 which are ¬t for purpose.10 When is odd,
the curves have embedding degree 6, so the MOV reduction translates the
ECDLP on Ei (F3 ) into the DLP in F36 , a relatively large ¬nite ¬eld. Thus
it should be possible to select a moderate sized and obtain short, secure
signatures. For example, according to [43, Table 2], taking = 121, one can
obtain a signature size of 192 bits for a group G1 of size about 2155 while the
MOV reduction yields a DLP in F3726 , a ¬eld of size roughly 21151 . This set
of parameters would therefore appear to o¬er about 80 bits of security.11
However, as is pointed out in [43], Coppersmith™s discrete logarithm al-
gorithm [86], although speci¬cally designed for ¬elds of characteristic 2, also
applies to ¬elds of small characteristic and is more e¬cient than general pur-
pose discrete logarithm algorithms. The function ¬eld sieve as developed in
[2, 3, 185] is also applicable and has better asymptotic performance than
Coppersmith™s algorithm for ¬elds of characteristic 3. But it is currently
unclear by how much these algorithms reduce the security o¬ered by BLS
signatures for particular curves de¬ned over ¬elds of characteristic 3. For
example, it may well be that the algorithm reduces the security level below
the supposed 80 bits for the parameters in the paragraph above. The con-
clusion of [43] is that in order to obtain security similar to that o¬ered by
DSA, curves Ei (F3 ), where 36 is much greater than 1024 bits in size, are
needed. Similar security considerations apply when using the same curves in
other cryptographic applications. In the current context, this results in much
longer signatures, running counter to the whole rationale for the BLS scheme.
The problem of constructing signatures that are simultaneously short and se-
cure should provide motivation for a detailed study of the performance of the
9
A modi¬ed veri¬cation equation is then needed to handle the fact that two elements
of G1 are represented by each x ∈ Fq .
10
These curves are named E + , E ’ in [42].
11
This choice of parameters was not present in the original version [42] because of the
threat of Weil descent attacks; according to [43], the work of Diem in [104] shows Weil
descent to be ine¬ective for = 121.
232 X. CRYPTOGRAPHY FROM PAIRINGS

function ¬eld sieve in characteristic 3. Some estimates for the size of factor
bases arising in the function ¬eld sieve for ¬elds of small characteristic can
be found in [154].
In [43], Boneh, Lynn and Shacham explain how ordinary (i.e., non-supersingular)
curves and unmodi¬ed pairings can be used to remedy the situation. Assume
now we have a triple of groups G1 , G2 , G3 and a pairing e : G1 — G2 ’ G3 .
For i = 1, 2, let Pi of prime order r generate Gi . A user™s private key is still a
value x ∈ Zr , but now the matching public key is [x]P2 ∈ G2 . The signature
on a message M ∈ {0, 1}— is still σ = [x]H(M ) ∈ G1 . To verify a purported
signature σ on message M , the veri¬er now checks that
P2 , [x]P2 , H(M ), σ
is a valid co-Di¬e“Hellman tuple, that is, a tuple in which the second pair
of elements (in G1 ) are related by the same multiple as the ¬rst pair (in G2 ).
This can be done using the pairing e by checking that the equation:
e(σ, P2 ) = e(H(M ), [x]P2 )
holds. The security of this scheme rests on the hardness of the co-CDH
problem, a variant of the CDH problem appropriate to the situation where
two groups G1 and G2 are in play. The security proof has an interesting twist,
in that the existence of an e¬ciently computable isomorphism ψ : G2 ’ G1
is required to make the proof work.
Boneh, Lynn and Shacham [42] show how groups and pairings suitable for
use with this scheme can be obtained from MNT curves (see Section IX.15.1)
and how ψ can be constructed using the trace map. They report an example
curve E(Fq ) where q is a 168-bit prime and where the embedding degree is 6.
The curve has an order that is divisible by a 166-bit prime r; using appropriate
subgroups of E(Fq ) and E(Fq6 ) for G1 and G2 , one can obtain a scheme with
168-bit signatures where the best currently known algorithm for the co-CDH
problem requires either a generic discrete logarithm algorithm using around
283 computational steps or taking a discrete logarithm in a 1008-bit ¬eld of
large characteristic (where Coppersmith™s algorithm and the function ¬eld
sieve are ine¬ective). Unfortunately, the public key, being a point on E(Fq6 ),
is no longer short, an issue that may limit the wider applicability of this
scheme.
The above discussion gives a clear example where unmodi¬ed pairings
should be used in preference to modi¬ed pairings for reasons of e¬ciency and
security.
X.4.3. Further Signature Schemes. We provide brief references to a se-
lection of the other relevant literature.
Libert and Quisquater developed an identity-based undeniable signature
scheme in [222]. Pairings were used to construct a variety of proxy signa-
turechemes by Zhang et al. in [359]. Identity-based blind signatures and
ring signatures were considered by Zhang and Kim in [354, 355], but the
X.4. SIGNATURE SCHEMES 233

schemes presented lack a full security analysis. Herranz and S´ez [162] used
a
the Forking Lemma methodology to build provably secure identity-based ring
signatures from pairings.
Thanks mainly to their simple algebraic structure, BLS signatures have
been productively exploited by a number of authors. Boldyreva [32] showed
how to adapt the scheme of [42] to produce provably secure threshold signa-
tures, multisignatures and blind signatures. The blinding capability of BLS
signatures was also noted by Verheul in [337]. In the same paper, Verheul
also considered the use of pairings to construct self-blindable credential cer-
ti¬cates. Steinfeld et al. [318] extended the BLS signature scheme to obtain
a new primitive, universal designated-veri¬er signatures. Boneh et al. [40]
also used BLS signatures as a basis to produce an aggregate signature scheme
(in which multiple signatures can be combined to form a single, short, veri¬-
able signature), a veri¬ably encrypted signature scheme (with applications to
fair exchange and optimistic contract signing), and a ring signature scheme.
In turn, Boldyreva et al. [33] used the aggregate signature scheme of [40] to
construct e¬cient proxy signature schemes. See also [166] for an attack on
and repair of the veri¬ably encrypted signature scheme of [40] and [89] for a
result relating the complexity assumption that was used to establish security
for the aggregate signature scheme in [40] to the CDH problem.
Recently, Libert and Quisquater [223] modi¬ed the BLS signature scheme
to produce a particularly e¬cient signcryption scheme, that is, a scheme in
which the signature and encryption are combined into a single “monolithic”
operation. An alternative scheme of Malone-Lee [231] has a security proof
in a multi-user model and o¬ers ciphertexts that are even shorter than in the
scheme of [223]. Malone-Lee™s scheme is not based on BLS signatures but
does use pairings as a tool in the security proofs.
Zhang et al. [358] modi¬ed the BLS signature scheme to obtain a more
e¬cient signature scheme that does not require the use of a special hash
function (i.e., one that outputs elements of G1 ). The scheme is provably
secure in the random oracle model, but its security is based on the hardness of
the non-standard k-weak CDH problem that was introduced in [250]. Zhang
et al. [357] adapted the scheme of [358] to obtain a veri¬ably encrypted
signature scheme, also based on pairings, but more e¬cient than the scheme
of [40].
Boneh, Mironov and Shoup [44] used pairings to construct a tree-based
signature scheme whose security can be proved in the standard model (i.e.,
without the use of random oracles), based on the hardness of the CDH prob-
lem. A much more e¬cient scheme, also secure in the standard model, was
presented in [35]. Here, the security relies on the hardness of another non-
standard problem, the Strong Di¬e“Hellman problem. This problem is re-
lated to the k-weak CDH problem of [250].
234 X. CRYPTOGRAPHY FROM PAIRINGS

X.4.4. Identity-Based Signcryption. A number of authors have consid-
ered combining signature and encryption functions in a single identity-based
scheme. The ¬rst attempt appears to be that of Malone-Lee [230], who
provided an identity-based signcryption scheme. Unfortunately, the compu-
tational costs of the signcryption and matching un-signcryption operations in
[230] are not much less than the sum of the costs of the encryption/decryption
and signature/veri¬cation algorithms of [39] and [62] (say). On the other
hand, the scheme™s ciphertexts are a little shorter than they would be in the
case of a simple “sign then encrypt” scheme. In contrast to the scheme of
Lynn [228], Malone-Lee™s scheme o¬ers non-repudiation: an entity A can
present a message and ciphertext to a judge who can then verify that they
originated from another entity B. However, as is pointed out in [221], this
property means that Malone-Lee™s scheme cannot be semantically secure.12
An identity-based signcryption scheme which does not su¬er from this weak-
ness was presented by Libert and Quisquater in [221]. The scheme uses
pairings, is roughly as e¬cient as the scheme of [230] and has security that
depends on the hardness of the decision bilinear Di¬e“Hellman problem (de-
¬ned in Section IX.11.3 for unmodi¬ed pairings). This scheme also allows
non-repudiation, but the origin of ciphertexts can be veri¬ed by third parties
without knowledge of the underlying plaintext. This last feature may be a
positive or negative one depending on the intended application.
A two-layer approach to combining identity-based signature and encryp-
tion was taken by Boyen in [48]. The resulting mechanism, called an IBSE
scheme, has comparable e¬ciency but stronger security guarantees than the
earlier work of [221, 230]. As well as providing the usual properties of con-
¬dentiality and non-repudiation, the pairing-based scheme of Boyen in [48]
o¬ers ciphertext unlinkability (allowing the sender to disavow creating a ci-
phertext), ciphertext authentication (allowing the recipient to be convinced
that the ciphertext and signed message it contains were prepared by the
same entity) and ciphertext anonymity (making the identi¬cation of legiti-
mate sender and recipient impossible for any entity not in possession of the
recipient™s decryption key, in contrast to the scheme of [221]). These prop-
erties are not available from single-layer signcryption schemes and a major
contribution of [48] is to identify and formalize these properties. The secu-
rity of Boyen™s IBSE scheme depends on the hardness of the BDH problem.
An examination of the scheme shows that it builds on the NIKDS of Sakai
et al. [284], with the key e(QA , QB )s once again being at the heart of the
ˆ
matter. Chen and Malone-Lee [72] have recently proposed an identity-based
signcryption scheme that is secure in the model of [48] but more e¬cient than
Boyen™s IBSE scheme.

12
The adversary, when presented with a challenge ciphertext C — which encrypts one of
M0 , M1 , can simply attempt to verify both pairs M0 , C — and M1 , C — ; a correct veri¬cation
reveals which plaintext Mb was encrypted.
X.5. HIERARCHICAL IDENTITY-BASED CRYPTOGRAPHY AND RELATED TOPICS 235

X.5. Hierarchical Identity-Based Cryptography and Related
Topics
Identity-based cryptography as we have described it so far in this chapter
involves a single trusted authority, the PKG, who carries out all the work
of registering users and distributing private keys. Public-key infrastructures
(PKIs) supporting “classical” public-key cryptography allow many levels of
trusted authority through the use of certi¬cates and certi¬cate chains. A
hierarchy of CAs topped by a root CA can spread the workload and simplify
the deployment of systems relying on public-key cryptography. The ¬rst
attempt to mimic the traditional PKI hierarchy in the identity-based setting
was due to Horowitz and Lynn [172]. Their scheme is restricted to two levels
of hierarchy and has limited collusion resistance. A more successful attempt
was made soon after by Gentry and Silverberg [147]. Their solution, which
extends the IBE scheme of Boneh and Franklin in a very natural way, has
led other researchers to develop further interesting cryptographic schemes. In
this section we outline the contribution of Gentry and Silverberg in [147] and
then give a brief overview of the subsequent research.

X.5.1. The Basic Scheme of Gentry and Silverberg. The basic hier-
archical identity-based encryption (HIBE13 ) scheme of [147] associates each
entity with a level in the hierarchy, with the root authority being at level 0.
An entity at level t is de¬ned by its tuple of identities ID1 , ID2 , . . . , IDt . This
entity has as superior entities the root authority (or root PKG) together with
the t ’ 1 entities whose identities are ID1 , ID2 , . . . , IDi , 1 ¤ i < t. An entity
at level t will have a secret st ∈ Z— , just like the PKG in the Boneh“Franklin
r
IBE scheme. As we describe below, this secret will be used by an entity at
level t to produce private keys for its children at level t + 1.
The scheme BasicHIBE14 is de¬ned by ¬ve algorithms:
Root Setup, Lower-Level Setup,
(Private Key) Extract, Encrypt and Decrypt.
These operate as follows:
Root Setup: To set up the root authority at level 0, this algorithm takes as
input a security parameter and outputs the system parameters:
params = G1 , G3 , e, n, P0 , Q0 , H1 , H2 .
ˆ
Here G1 , G3 , e, n (the bit-length of plaintexts) and hash functions H1 and
ˆ
H2 are just as in the Boneh“Franklin scheme. We write P0 for an arbitrary
13
This is a perhaps more natural acronym than HIDE as used by Gentry and Silverberg,
albeit one that does not have the same neat connotation of secrecy. It also enables us to
use the acronym HIBS for the matching concept of a hierarchical identity-based signature
scheme. It can be no bad thing to mention at least one Scottish football team in this
chapter.
14
BasicHIDE in [147].
236 X. CRYPTOGRAPHY FROM PAIRINGS

generator of G1 and Q0 = [s0 ]P0 , where s0 ∈ Z— is the root authority™s secret
r
value. Apart from these minor changes of notation, this procedure is identical
to the Setup procedure of the scheme BasicIdent in [39].
Lower-Level Setup: An entity at level t in the hierarchy is initialized simply
by selecting for itself a secret value st ∈ Z— .
r

Extract: Consider a level t entity Et with identity tuple ID1 , ID2 , . . . , IDt .
This entity™s parent (having identity ID1 , ID2 , . . . , IDt’1 ) performs the fol-
lowing steps:

1. Compute Pt = H1 (ID1 , ID2 , . . . , IDt ) ∈ G1 .
2. Set St = St’1 + st Pt ∈ G1 and give the private key St to entity Et over
a secure channel. (When t = 1, we set S0 = 1G1 .)
3. Give Et the values Qi = si P0 , 1 ¤ i < t.

t
Notice that, by induction, we have St = si’1 Pi .
i=1

Encrypt: To encrypt plaintext M ∈ {0, 1} for an entity with identity tuple
n

ID1 , ID2 , . . . , IDt , perform the following steps:

1. Compute Pi = H1 (ID1 , ID2 , . . . , IDi ) ∈ G1 for 1 ¤ i ¤ t.
2. Choose a random t ∈ Z— .
r
3. Compute and output the ciphertext:



C = [t]P0 , [t]P2 , . . . [t]Pt , M • H2 (ˆ(P1 , Q0 )t ) ∈ Gt — {0, 1}n .
e 1




Notice that, in order to encrypt a message for an entity, the sender needs
only know the parameters of the root PKG along with the identity tuple of
the intended recipient, and not any parameters associated with intermediate
entities. Note too that the omission of the value [t]P1 from the ciphertext
is deliberate (if it were included, then an eavesdropper could decrypt C by
calculating the mask H2 (ˆ([t]P1 , Q0 ))).
e
Decrypt: Suppose C = U0 , U2 , . . . , Ut , V ∈ Gt — {0, 1}n is a ciphertext
1
encrypted for an entity ID1 , ID2 , . . . , IDt . To decrypt C using the private
key St , the recipient computes


t
e(Qi’1 , Ui )’1 .
M = V • H2 e(St , U0 ) ·
ˆ ˆ
i=2
X.5. HIERARCHICAL IDENTITY-BASED CRYPTOGRAPHY AND RELATED TOPICS 237

To see that decryption works properly, consider the following chain of
equalities, established using the bilinearity of e:
ˆ
t t t
’1
e([si’1 ]P0 , [t]Pi )’1
e(St , U0 ) · [si’1 ]Pi , [t]P0 ) ·
ˆ e(Qi’1 , Ui )
ˆ = e(
ˆ ˆ
i=2 i=1 i=2
t t
[si’1 ]Pi , [t]P0 ) ·
= e(
ˆ e(’[si’1 ]Pi , [t]P0 )
ˆ
i=1 i=2
t t
[si’1 ]Pi , [t]P0 ) · e(’
= e(
ˆ ˆ [si’1 ]Pi , [t]P0 )
i=1 i=2
= e([s0 ]P1 , [t]P0 )
ˆ
= e(P1 , [s0 ]P0 )t
ˆ
= e(P1 , Q0 )t .
ˆ
A few comments on this scheme are in order. Firstly, note that encryption
only requires one pairing computation, and this needs only to be computed
once to enable communication with any entity registered in the hierarchy. On
the other hand, t pairing computations are required for every decryption. It
would be interesting to ¬nd hierarchical schemes with an alternative balance
between the costs of encryption and decryption. Secondly, notice how the
length of ciphertexts grows with t “ this seems inescapable in a hierarchical
system. Thirdly, note that the scheme has a strong in-built escrow, in that
any ancestor of an entity can decrypt ciphertexts intended for that entity: an
ancestor at level j can use the equation
j
e(Qi’1 , Ui )’1
M = V • H2 e(Sj , U0 ) ·
ˆ ˆ
i=2

to decrypt a message encrypted for a child at level t.
X.5.2. Extensions of the Basic Scheme. In [147], Gentry and Silverberg
also showed how to use the techniques of Fujisaki“Okamoto [128] to produce
a strengthened encryption scheme which is secure against chosen-ciphertext
attackers in the random oracle model, provided that the BDH problem is hard.
The security model adopted in [147] is su¬ciently strong to capture collusions
of entities attempting to compromise the private keys of their ancestors. This
is because it allows the adversary to extract the private keys of entities at
any level in the hierarchy and to adaptively select the identity on which it
wishes to be challenged.
Naor™s idea for turning an IBE scheme into a signature scheme was ex-
ploited in [147] to produce a hierarchical identity-based signature (HIBS)
scheme. The security of this scheme depends on the hardness of the CDH
problem in G1 . Gentry and Silverberg also considered how the NIKDS of
Sakai et al. can be used to reduce the amount of computation needed for
238 X. CRYPTOGRAPHY FROM PAIRINGS

encryption between two parties who are “near” to one another in the hierar-
chy. The resulting scheme also enjoys shorter ciphertexts. A number of other
variants on this theme are also explored in [147].

X.5.3. Related Topics. Canetti, Halevi and Katz [55] built upon the work
of [147] to produce the ¬rst non-trivial forward-secure public-key encryption
(FS-PKE) scheme. In an FS-PKE scheme, a user has a ¬xed public key but
a private key which evolves over time; such a scheme should then have the
property that a compromise of the user™s private key at time t does not a¬ect
the security of messages encrypted during earlier time periods (though clearly
no security can be guaranteed after time t).
The scheme in [55] makes use of a basic primitive called a binary tree
encryption (BTE) scheme. A BTE scheme consists of a single “master” public
key, a binary tree of private keys together with encryption and decryption
algorithms and a routine which computes the private keys of the children
of a node from the private key at that node. The encryption algorithm
takes as input the public key and the label of a node. A selective-node
chosen-ciphertext attack (SN-CCA) against a BTE scheme goes roughly as
follows. The adversary selects a target node to attack in the challenge phase
in advance. The adversary is then given the private keys for a certain set
of nodes. This set consists of all the children of the target together with all
the siblings of the target™s ancestors. This is the maximal set of private keys
which the adversary can be given without enabling the trivial computation of
the private key of the target node. The adversary™s job is then to distinguish
ciphertexts encrypted under the public key and target node, given access to
a decryption oracle.
Canetti, Halevi and Katz show how a BTE scheme secure against SN-
CCA attacks can be constructed from a simpli¬cation of the HIBE scheme of
[147]. They then show how any SN-CCA secure BTE scheme can be used in
a simple construction to obtain an encryption scheme that is forward-secure
in a natural adaptation of the standard IND-CCA2 model for public-key en-
cryption. The trick is to traverse the tree of the BTE in a pre-order traversal,
with the key at the tth node in the traversal determining how the private key
in the forward-secure scheme is updated at time t. The security de¬nition for
a BTE scheme quickly converts into the desired forward security. Combining
their constructions, the authors of [55] obtain an e¬cient, forward-secure en-
cryption scheme whose security rests of the hardness of the BDH problem in
the random oracle model.
A BTE scheme secure in the SN-CCA sense, but without requiring random
oracles, is also constructed in [55]. The construction uses O( )-wise indepen-
dent hash functions, and the security of the resulting BTE scheme depends on
the hardness of the DBDH problem rather than the BDH problem. However
the construction gives a completely impractical scheme because of its reliance
on non-interactive zero-knowledge proofs. As an interesting aside, Canetti,
X.5. HIERARCHICAL IDENTITY-BASED CRYPTOGRAPHY AND RELATED TOPICS 239

Halevi and Katz go on to show how an HIBE scheme can be constructed from
a BTE scheme, though with a weaker security model than is considered in
[147]. A corollary of this result is the construction of an IBE scheme (and an
HIBE scheme) that is secure in the standard model (i.e., without the use of
random oracles) assuming the hardness of the DBDH problem, though only
for an adversary who speci¬es in advance which identity he will attack. Again
the scheme will be impractical if it is to be secure against chosen-ciphertext
attacks.
One issue that the proofs of security in [55] have in common with those of
[39, 147] (and indeed many papers in the area) is that the security reductions
are not particularly tight. For example, a factor of 1/N is introduced in [55,
Proof of Theorem 4], where N is the number of time periods supported by
the FS-PKE scheme. It seems to be a challenging problem to produce results
tightly relating the security of the schemes to the hardness of some underlying
computational problems.
Canetti, Halevi and Katz [56] have shown a surprising connection between
IBE and chosen-ciphertext security for (normal) public-key encryption. They
give a construction for an IND-CCA2 secure scheme of the latter type from
a weakly-secure IBE scheme and a strongly unforgeable one-time signature
scheme. Here, the IBE scheme need only be secure against chosen-plaintext
attacks by selective-ID adversaries, that is, adversaries who specify in advance
which identity they will attack in the challenge phase. The twist needed to
make the construction work is to interpret the public key of the signature
scheme as an identity in the IBE scheme, for which the decrypting party holds
the master secret. Since a weakly-secure IBE scheme can be constructed in
the standard model, the results of [56] yield a new IND-CCA2 secure public-
key encryption scheme whose security does not rely on the random oracle
assumption.
Boneh and Boyen [36] provided new and e¬cient constructions for an
HIBE scheme and an IBE scheme using pairings. Both schemes are secure
in the standard model, against selective-ID, chosen plaintext attackers. The
HIBE scheme is secure given that the DBDH problem is hard. It can be
converted into a selective-ID, chosen-ciphertext secure HIBE scheme using
the method of [56]; the resulting scheme is e¬cient. The security of the new
IBE scheme in [36] depends on the hardness of a new problem, the decision
bilinear Di¬e“Hellman Inversion problem (DBDHI problem), which is related
to a decisional version of the k-weak CDH problem of [250]. This scheme is
also closely related to the signature scheme of [35]. Unfortunately, no e¬cient
conversion to a chosen-ciphertext secure scheme is currently known. However,
by combining this scheme with ideas in [56] and the signature scheme of [35],
one obtains a reasonably e¬cient public-key encryption scheme that is IND-
CCA2 secure in the standard model.
240 X. CRYPTOGRAPHY FROM PAIRINGS

Forward secure encryption is perhaps the most basic form of what might
be called “key updating cryptography.” Here the general approach is to have
an evolving private key which may or may not be updated with the help of
a second entity called a base or helper. Several other papers use pairings to
address problems in this area. Of particular note is the work of Bellare and
Palacio in [23] and of Dodis et al. in [107]. In the former paper, the authors
construct a strongly key-insulated encryption scheme from the IBE scheme of
Boneh and Franklin. Such a scheme allows a user to cooperate with a helper
to refresh his private key; the scheme remains secure even if the user™s private
key is corrupted in up to some threshold number of time periods, and even if
the helper is compromized (so long as the user™s key then is not). Bellare and
Palacio also provide an equivalence result in [23, Theorem 4.1], relating the
existence of a secure IBE scheme to that of a secure strongly key-insulated
encryption scheme. Dodis et al. [107] work with an even stronger security
model, in which the base can also be frequently corrupted, and construct
an intrusion-resilient public-key encryption scheme from the forward-secure
scheme of [55].
Yum and Lee [352] have explored similar concepts in the context of signa-
tures, using the IBS scheme of [62] to obtain e¬cient key updating signature
schemes.

X.6. More Key Agreement Protocols
Alongside encryption and signatures, key agreement is one of the fun-
damental cryptographic primitives. As we have already seen in Section X.2,
pairings were used early on to construct key agreement schemes and protocols.
In this section we examine how this area has developed since the foundational
work of [284, 183].

X.6.1. Two-Party Key Agreement Protocols. The NIKDS of Sakai et
al. [284] allows two parties to non-interactively agree the identity-based
key KAB = e(QA , QB )s after they have registered with the same TA and
ˆ
obtained their respective private keys SA = [s]QA , SB = [s]QB . However, the
key KAB is a static one, while many applications require a fresh key for each
communications session.
Smart [312] was the ¬rst author to consider how pairings could be used
to develop identity-based, authenticated key agreement protocols. His pro-
tocol uses the same keying infrastructure as the IBE scheme of Boneh and
Franklin. In particular, system parameters G1 , G3 , e, P, Q0 = [s]P, H1 are
ˆ
pre-established and entities A, B possess private keys SA = [s]QA , SB =
[s]QB . Here, QA = H1 (IDA ), where IDA is the identity string of A. QB is
de¬ned similarly. In Smart™s protocol, A and B exchange ephemeral values
TA = [a]P and TB = [b]P , where a, b are selected at random from Z— . No-
r
tice that these are identical to the messages exchanged in a straightforward
X.6. MORE KEY AGREEMENT PROTOCOLS 241

Di¬e“Hellman protocol for the group G1 . Entity A then computes:
KA = e([a]QB , Q0 ) · e(SA , TB )
ˆ ˆ
while entity B computes:
KB = e([b]QA , Q0 ) · e(SB , TA ).
ˆ ˆ
It is an easy exercise to show that
KA = KB = e([a]QB + [b]QA , [s]P )
ˆ
so that this common value can be used as the basis of a shared session key. The
bandwidth requirements of the protocol are moderate, being one element of
G1 per participant. A version of the basic protocol o¬ering key con¬rmation is
also considered in [312]: this service ensures that each entity gets a guarantee
that the other entity actually has calculated the shared key. While no attacks
have been found on this protocol to date, no formal security analysis has been
given either.
Smart™s protocol requires two pairing computations per participant. An
alternative protocol was given by Chen and Kudla in [71]. In their protocol, A
and B exchange ephemeral values WA = [a]QA and WB = [b]QB and compute
the keys
KA = e(SA , WB + [a]QB ),
ˆ KB = e(WA + [b]QA , SB ).
ˆ
Now KA = KB = e(QA , QB )s(a+b) can be computed using just one pairing
ˆ
operation. A useful security model that is applicable for this type of pro-
tocol is the extension of the Bellare-Rogaway model [25] to the public key
setting that was developed by Blake-Wilson et al. in [28, 29]. It is proved
in [70] that the above protocol is a secure authenticated key agreement in
this model, provided the BDH problem is hard. The original proof of this
result published in [71] is ¬‚awed, and a strong restriction on adversarial be-
haviour is needed to provide the corrected version in [70]. Chen and Kudla
also consider modi¬cations of their protocol which provide forward secrecy,
anti-escrow features and support for multiple TAs.
Other authors have also tried to adapt Smart™s protocol. Shim™s attempt
[302] was shown to be vulnerable to a man-in-the-middle attack in [322].
Yi™s protocol [351] halves the bandwidth required by Smart™s protocol using
a form of point compression.
An alternative approach to identity-based key agreement was taken by
Boyd et al. in [47]. In this work the non-interactively agreed key KAB =
e(QA , QB )s of Sakai et al. is used as the key to a MAC algorithm to pro-
ˆ
vide authentication of the messages in a Di¬e“Hellman key exchange. The
resulting protocol is provably secure in the model developed in [22, 57] and
has the interesting privacy feature of providing deniable authentication: since
either party could have computed all the messages in a protocol run, both
parties can also deny having taken part in the protocol. The authors of [47]
also considered the use of identity-based encryption as a session key transport
242 X. CRYPTOGRAPHY FROM PAIRINGS

mechanism. Related uses of the key e(QA , QB )s in “secret handshake” key
ˆ
agreement protocols were also explored in [13], where the integration of these
protocols into the SSL/TLS protocol suite was also studied.
X.6.2. Multi-Party Key Agreement Protocols. In this section we dis-
cuss how Joux™s protocol [183] has inspired new protocols for multi-party key
agreement.
Recall that in Joux™s protocol, the key agreed between three parties is
equal to e(P, P )abc when the ephemeral broadcast values are [a]P , [b]P and
ˆ
[c]P . We have noted in Section X.2.2 that this protocol is vulnerable to man-
in-the middle attacks because it is not authenticated. An obvious way to
enhance the security of the protocol is to add signatures to the ephemeral
values. A number of e¬cient, signature-free approaches to securing Joux™s
protocol were described in [8]. It was also shown in [8], perhaps surprisingly,
that an authenticated version of Joux™s protocol has no bene¬t over a sim-
ple extension of the Di¬e“Hellman protocol when three-party, authenticated
protocols with con¬rmation are considered in a non-broadcast environment:
any secure protocol will require at least six messages in this context. Gal-
braith et al. [135] have studied the bit security of the BDH problem; their
results can be applied to Protocols of [8] and [312] to show that it is secure
to use a ¬nite-¬eld trace operation to derive a session key from the raw key
material exchanged in these protocols.
Shim™s attacks [300] on the protocols of [8] show that adding authenti-
cation to three-party protocols is a delicate business. Zhang and Liu [356]
developed identity-based, authenticated versions of Joux™s protocol.15 Nalla
and Reddy [259] also put forward identity-based, three-party key agreement
protocol, but these were all broken in [74, 299]. Meanwhile, Shim™s proposal
for a three-party protocol [301] was broken in [322].16
Protocols for more than three parties, using Joux™s protocol and its deriva-
tives as a building block, have been considered by several authors [281, 14].
Lack of space prevents their detailed consideration here. For attacks on some
other schemes which attempted to mimic the Burmester-Desmedt protocol of
[53], see [353].

X.7. Applications and Infrastructures
It should be apparent that one of the major uses of pairings has been
in developing identity-based cryptographic primitives. So far, we have said
little about what identity-based public-key cryptography (ID-PKC) has to
15
Note that there is no real bene¬t in deriving eight di¬erent keys from a single key
exchange by algebraic manipulations as in [356]: a simple key derivation function based
on hashing su¬ces.
16
Even though the protocol de¬ned in [301] does not actually make mathematical
sense! For it involves an exponentiation of an element e(P, P ) in G3 to a power that is a
ˆ
product of an element in Z— and an element in G3 .
r
X.7. APPLICATIONS AND INFRASTRUCTURES 243

o¬er in comparison to more traditional forms of public-key cryptography. We
rectify this in the ¬rst part of this section. We go on to study how pairings
have been used to develop new architectures supporting the deployment of
public-key cryptography. Then in the third part we outline a variety of recent
work in which pairings have been put into practice, either in trials of identity-
based technology or in on-paper proposals outside the immediate con¬nes of
cryptography.


X.7.1. Further Development of Identity-based Systems. We intro-
duced the concepts of identity-based encryption (IBE) and, more generally,
ID-PKC in Sections X.2.1 and X.3, portraying them as being useful alterna-
tives to traditional PKIs. Here we explore in a little more detail why this is the
case and critically examine some of the problems inherent in identity-based
approaches.


X.7.1.1. Identity-Based Systems Versus Traditional PKIs. Recall that
in an identity-based system, a TA is responsible for issuing private keys to
the correct users. This TA in e¬ect replaces the CA in a traditional PKI, but
the roles of TA and CA are somewhat di¬erent. The CA in a traditional PKI
does not usually know users™ private keys, but rather issues certi¬cates which
assert a binding between identities and public keys. The TA in an identity-
based system is responsible for checking that applicants do have the claimed
identity and then issuing the corresponding private key. Thus identity-based
systems automatically have a key escrow facility. Whether this is a good
thing or not will depend on the particular application at hand. It will cer-
tainly be a useful feature in many “corporate” deployment scenarios, where
the recovery of encrypted ¬les and e-mail may well be important should an
employee leave the organization, say. However, escrow can complicate the is-
sue of non-repudiation of signatures. For example, an important piece of EU
legislation [EU 1999] requires that the signing key be under the sole control
of the signing party in order that a signature be recognized as an “advanced
electronic signature.” Thus traditional signatures supported by a PKI are
likely to be more useful than identity-based signatures in practice.
Note that, in both ID-PKC and traditional PKI, it is important to au-
thenticate applicants before issuing valuable data (private keys in the former,
certi¬cates in the latter). So some additional authentication mechanism is
needed at the time of registration/key issuance. Both systems also require
that any system parameters (e.g., a root certi¬cate or a TA™s public param-
eters) are authentically available to users. However, with ID-PKC, there is
an additional requirement: the private keys must be delivered over con¬den-
tial and authentic channels to the intended recipients. Again this seems to
point towards the enterprise as being a fruitful deployment area for ID-PKC
244 X. CRYPTOGRAPHY FROM PAIRINGS

“ for example, one could use a company™s internal mail system and person-
nel database to distribute keys and control registration for low-to-medium
security applications.
The particular IBE scheme of Boneh and Franklin [39] supports multiple
TAs and split private keys in a very natural way. This goes some way to
addressing escrow concerns. For example, suppose two TAs share parameters
G1 , G3 , e, P but have master secrets s1 , s2 ∈ Z— and public values Q1 =
ˆ r
[s1 ]P , Q2 = [s2 ]P . Then a user A with identity string IDA can form his
private key as the sum [s1 ]QA + [s2 ]QA = [s1 + s2 ]QA of the private keys
obtained from each TA. To encrypt to A, ciphertexts of the form
[t]P, M • H2 (ˆ(QA , Q1 + Q2 )t )
e
can be used. More generally, a k-out-of-n escrow capability can be established
“ see [39] for details. Such a facility is also supported by many other ID-based
schemes developed post-Boneh“Franklin.
The ability to make use of multiple TAs was exploited in [69] to create
cryptographic communities of interest. Here, each TA represents a particular
group (e.g., the group of all people having the same citizenship, profession or
name); a sum of keys from di¬erent groups creates intersections of groups all
of whose members can calculate the same private key.
Another point of comparison for traditional public key and ID-PKC sys-
tems is the issue of revocation. Whenever a certi¬cate in a traditional system
expires (perhaps because the end of its validity period is reached or because
of a private key compromise), this fact must be communicated to the parties
relying on the certi¬cates. There is the same requirement for timely trans-
mission of revocation information in an ID-PKC system too. It has been
suggested by many authors that in ID-PKC, one can simply attach a validity
period to identities, for example “john.smith 2004”, so that public keys au-
tomatically expire. However, such a system is no longer purely identity-based,
and one must still ¬nd a way to deal with keys that become compromized
before the end of their expiry period.
A deeper comparison of revocation and many other issues for ID-PKC and
traditional PKIs is made in [274]. Whether ID-PKC really has something to
o¬er over traditional PKIs and even symmetric systems very much depends
on the application context, on what is to be secured and on what constraints
there are on the solutions that can be adopted. It is certainly not the case
that an identity-based approach will be the correct one in every circumstance.

X.7.1.2. Cryptographic Work¬‚ows. An apparently innocuous feature of
IBE is that when encrypting a message for entity A, the sender can choose
the identity string IDA used in the encryption process. Only if A has the
matching private key [s]QA = [s]H1 (IDA ) will he be able to decrypt the
message. Naturally, in many situations, it is most convenient if the sender
chooses a string IDA for which this is the case. However, it is possible that
X.7. APPLICATIONS AND INFRASTRUCTURES 245

A™s identity IDA and public key QA are actually determined before the private
key [s]QA . This can have interesting consequences. For example, the sender
can encode in A™s identity string a set of conditions (or a policy) that should
be met before the TA, acting as a policy monitor, should issue the private
key.
The idea of encoding conditions in identity strings can be combined with
the use of multiple TAs to create a cryptographic work¬‚ow, that is, a sequence
of private key issuances that must be successfully carried out before an en-
tity can decrypt a ciphertext. In this context, the “I” in ID-PKC is better
interpreted as “identi¬er”, since rarely will identities be used alone.
As an example of this concept in action, consider the scenario where a
customer wants his bank manager to have access to a particular instruction,
but only after a certain time. Suppose the bank acts as a TA for its employees
in a Boneh“Franklin IBE scheme with the usual parameters G1 , G3 , e, P , ˆ
master secret sbank and public parameter Qbank = [sbank ]P . Suppose that
the bank manager has received his private key [sbank ]H1 (IDbm ). Suppose also
that a third party operates an encrypted time service as follows. The third
party, using the same basic public parameters as the bank, acts as a TA with
master secret stime and public parameter Qtime = [stime ]P . At time T , the
third party broadcasts to all subscribers the private key [stime ]H1 (T ). Now,
to encrypt an instruction M for the bank manager to be read only after time
T0 , the customer creates the ciphertext:
C = [t]P, M • H2 (ˆ(Qbank , H1 (IDbm ))t · e(Qtime , H1 (T0 ))t ) .
e ˆ
Here, the customer has encrypted M using both the identity of the bank
manager and the time T0 after which the message is to become decryptable.
Only after time T0 can the bank manager access the value [stime ]H1 (T0 ) and
combine this with his private key [sbank ]H1 (IDbm ) in the bank™s scheme to
compute the value:
H2 (ˆ([t]P, [sbank ]H1 (IDbm )) · e([t]P, [stime ]H1 (T0 ))),
e ˆ
allowing the decryption of the ciphertext C.
In this example, the customer created a special public key for encryption
out of two identi¬ers, the bank manager™s identity and the time identi¬er.
These identi¬ers come from two di¬erent schemes with two di¬erent TAs, but
ones who share some parameters “ perhaps they are using standardized groups
and pairings.17 The customer has used multiple TAs to create a work¬‚ow that
the bank manager must follow in order to access the desired information: ¬rst
the bank manager must obtain his private key in the bank™s scheme; then he
must wait for the time service to reveal the private key at time T0 .
It is easy to imagine other scenarios where the dynamic creation of work-
¬‚ows in this way could be very useful. There is no theoretical limit on the
17
In fact, the reliance on shared parameters can be almost completely eliminated by
slightly modifying the encryption algorithm.
246 X. CRYPTOGRAPHY FROM PAIRINGS

number of private keys that the recipient must fetch or the types of roles or
identi¬ers that can be used. The recipient may be required to perform some
kind of authentication (based on identity, address, role in an organization,
etc.) at each stage. Further research along these lines, allowing the expres-
sion of more complex conditions in identi¬ers, can be found in [69, 314].

X.7.2. New Infrastructures. Some form of hierarchy seems necessary in
order to address the scalability and availability issues inherent in any system
with a single point of distribution for keying material. We have seen how the
work of Gentry and Silverberg [147] allows a hierarchy of TAs in ID-based
systems. Chen et al. [68] have studied the bene¬ts of developing a mixed
architecture, with identity-based TAs administering users at the lowest levels
of the hierarchy being supported by a traditional PKI hierarchy above.
In [146], Gentry introduced the concept of Certi¬cate-Based Encryption
(CBE), with a view to simplifying revocation in traditional PKIs, and used
pairings to construct a concrete CBE scheme. We give a brief review of
Gentry™s scheme using notation as previously established: P generates G1 of

<<

. 8
( 10)



>>