ńņš. 8 |

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 |