Identity-based cryptography

IDENTITY-BASED CRYPTOGRAPHY

ISSN 1871-6431

Cryptology and Information Security Series

The Cryptology & Information Security Series (CISS) presents the latest research results in the

theory and practice, analysis and design, implementation, application and experience of

cryptology and information security techniques. It covers all aspects of cryptology and

information security for an audience of information security researchers with specialized

technical backgrounds.

Coordinating Series Editors: Raphael C.-W. Phan and Jianying Zhou

Series editors

Feng Bao, Institute for Infocomm Research, Singapore

Kefei Chen, Shanghai Jiaotong University, China

Robert Deng, SMU, Singapore

Yevgeniy Dodis, New York University, USA

Dieter Gollmann, TU Hamburg-Harburg, Germany

Markus Jakobsson, Indiana University, USA

Marc Joye, Thomson R&D, France

Javier Lopez, University of Malaga, Spain

Nasir Memon, Polytech University, USA

Chris Mitchell, RHUL, United Kingdom

David Naccache, École Normale Supérieure, France

Gregory Neven, IBM Research, Switzerland

Phong Nguyen, CNRS / École Normale Supérieure, France

Andrew Odlyzko, University of Minnesota, USA

Adam Young, MITRE Corporation, USA

Moti Yung, Columbia University, USA

Volume 2

Recently published in this series

Vol. 1. J. Lopez and J. Zhou (Eds.), Wireless Sensor Network Security

Identity-Based Cryptography

Edited by

Marc Joye

Thomson R&D, France

and

Gregory Neven

IBM Zürich Research Laboratory, Switzerland

Amsterdam • Berlin • Oxford • Tokyo • Washington, DC

© 2009 The authors and IOS Press.

All rights reserved. No part of this book may be reproduced, stored in a retrieval system,

or transmitted, in any form or by any means, without prior written permission from the publisher.

ISBN 978-1-58603-947-9

Library of Congress Control Number: 2008940895

Publisher

IOS Press

Nieuwe Hemweg 6B

1013 BG Amsterdam

The Netherlands

fax: +31 20 687 0019

e-mail: [email protected]

Distributor in the UK and Ireland Distributor in the USA and Canada

Gazelle Books Services Ltd. IOS Press, Inc.

White Cross Mills 4502 Rachael Manor Drive

Hightown Fairfax, VA 22032

Lancaster LA1 4XS USA

United Kingdom fax: +1 703 323 3668

fax: +44 1524 63232 e-mail: [email protected]

e-mail: [email protected]

LEGAL NOTICE

The publisher is not responsible for the use which might be made of the following information.

PRINTED IN THE NETHERLANDS

Foreword

In an active field like that of cryptography, a problem that remains open for seventeen

years must be a pretty tough problem. In a practically relevant field like that of cryp￾tography, a solution that inspires hundreds of follow-up papers within a few years’ time

must be a pretty interesting solution.

Posed as an open problem in 1984, but efficiently instantiated only in 2001, identity￾based encryption hasn’t left the forefront of cryptographic research since. Praised by

fans as the economical alternative to public-key infrastructures, booed by critics for its

inherent key escrow — was that 1984 you said?— identity-based cryptography is also

the topic of numerous debates in the cryptographic community.

This book looks beyond the controversy and intends to give an overview of the cur￾rent state-of-the-art in identity-based cryptography. Since research on the topic is still

actively continuing, this is necessarily a snapshot of a field in motion, rather than the

final word about it. Still, we felt the main concepts have by now sufficiently matured to

collect them in a single dedicated volume.

Each of the chapters in this volume is written by international experts on the topic.

Our first word of thanks goes to the authors for their top-quality contributions to the

book. Our special gratitude is due to Jean-Luc Beuchat, Jérémie Detrey, David Galindo,

Kenny Paterson, and Nigel Smart who have looked over various portions of the book

and have given comments and suggestions, and to Michel Abdalla for letting us use his

extensive bibliographic library. We would also like to thank Juliette Joye for the beautiful

illustration on the cover of this book. Finally, we would like to thank the people at IOS

Press for the smooth interaction.

September 2008 Marc Joye

Gregory Neven

Identity-Based Cryptography

M. Joye and G. Neven (Eds.)

IOS Press, 2009

© 2009 The authors and IOS Press. All rights reserved.

v

This page intentionally left blank

Contents

Foreword v

Marc Joye and Gregory Neven

Chapter I. Introduction to Identity-Based Cryptography 1

Antoine Joux

Chapter II. Pairings on Elliptic Curves 13

Frederik Vercauteren

Chapter III. Identity-Based Signatures 31

Eike Kiltz and Gregory Neven

Chapter IV. Identity-Based Encryption and Hierarchical Identity-Based Encryption 45

Sanjit Chatterjee and Palash Sarkar

Chapter V. Flexible IBE and Beyond in the Commutative-Blinding Framework 65

Xavier Boyen

Chapter VI. Generalized IBE in the Exponent-Inversion Framework 83

Xavier Boyen

Chapter VII. Forward-Secure Hierarchical IBE with Applications to Broadcast

Encryption 100

Danfeng (Daphne) Yao, Nelly Fazio, Yevgeniy Dodis and Anna Lysyanskaya

Chapter VIII. Identity-Based Identification and Signature Schemes Using Error

Correcting Codes 119

Pierre-Louis Cayrel, Philippe Gaborit and Marc Girault

Chapter IX. Certificateless Encryption 135

Sherman S.M. Chow

Chapter X. Attribute-Based Encryption 156

Amit Sahai, Brent Waters and Steve Lu

Chapter XI. On Generic Groups and Related Bilinear Problems 169

David Lubicz and Thomas Sirvent

Chapter XII. Software Implementation of Pairings 188

Darrel Hankerson, Alfred Menezes and Michael Scott

Chapter XIII. Hardware Implementation of Pairings 207

Maurice Keller, Robert Ronan, Andrew Byrne, Colin Murphy and

William Marnane

Chapter XIV. Implementation Attacks & Countermeasures 226

Claire Whelan, Dan Page, Frederik Vercauteren, Michael Scott and

William Marnane

vii

Bibliography 245

Author Index 263

viii

Chapter I

Introduction to Identity-Based

Cryptography

Antoine JOUX

DGA and University of Versailles St-Quentin-en-Yvelines, France

Abstract. Identity-based cryptography is a new development of public-key cryp￾tography. It was first proposed by Adi Shamir at CRYPTO ’84. However, it took the

cryptographic community a long while to produce effective identity-based cryp￾tosystems. Indeed, this solution only appeared at the beginning of the twenty-first

century. Nowadays, identity-based cryptography has become a very active field of

research. This introductory chapter presents the basics of identity-based cryptogra￾phy and briefly surveys its early history.

1. Public-Key Cryptography, Certificates and Identity-Based Cryptography

Identity-based cryptography is an extension of the public-key paradigm, which was ini￾tially suggested by Adi Shamir [Sha85] at CRYPTO ’84. In order to better understand

identity-based cryptography, we start by reviewing how traditional public-key systems

are usually put to use in real-life applications. First, to offer reasonable speed, public-key

encryption systems are usually used in conjunction with a secret-key encryption scheme.

More precisely, the public-key scheme is used in order to produce a shared encryption

key for the secret-key scheme, known to the sender and receiver of the communication.

Once this is done, they simply use this common secret key for encrypting the rest of

the communication. This initial phase is usually called a key exchange protocol. It can

be devised in several ways. The simplest approach is simply to let the sender encrypt a

random value R with a public-key encryption scheme such as RSA, using the receiver’s

public key. Since R can be obtained by the receiver after decryption, it is a common

value which can be used to key the secret-key encryption. Note that to avoid simple mul￾tiplicative attacks against RSA, for example the attacks described in [BJN00], R should

preferably be of the length of the RSA modulus. This means that R is usually too long

and must be truncated to obtain the secret key. The other classical approach is to use

Diffie-Hellman key exchange, either in the multiplicative subgroup of a finite field or on

an elliptic curve. There, the common value is no longer chosen by the sender but instead

Identity-Based Cryptography

M. Joye and G. Neven (Eds.)

IOS Press, 2009

© 2009 The author and IOS Press. All rights reserved.

doi:10.3233/978-1-58603-947-9-1

1

implicitly generated by combining a random value together with the public key of the

receiver. Note that once again this common value is usually too long and needs to be

truncated before keying the secret-key encryption.

In both cases, the key exchange protocol requires the receiver’s public key as input.

As a consequence, before sending any message, the sender should take care to go and

obtain this public key. Moreover, he should make sure that the public key he obtains is

indeed the correct one. This introduces two important steps in real life implementation,

fetching the public key and verifying it. At first, it may seem that the second step is

the difficult one. Getting data is reasonably easy, verifying that it is genuine seems to

be much more difficult. However, there is a simple solution that allows one to verify

public keys: public-key certificates. At the most basic level, a public-key certificate is

simply a message that asserts: “The public key of user Bob is upk B.” To make sure that

the certificate is genuine, it needs to be signed. Assuming that the signature scheme is

cryptographically sound, such a certificate cannot be forged. Of course, for certificates

to be useful, several conditions need to be satisfied. The end user that wants to send

a message to Bob should be able to verify the signature. As a consequence, the first

condition is that he needs to know in advance the public verification key of the signer.

The second condition is that the end user should trust the signer. Indeed, if the signer

is dishonest, he can easily substitute Bob’s key in the certificate by another key of his

choice. Doing this could clearly allow him to decrypt any message that a user intends to

send to Bob. These two conditions are not always easy to satisfy. First, if Alice doesn’t

know the public key that would allow her to verify Bob’s certificate, she needs to obtain

another certificate that brings her this key. Of course, if she doesn’t know the verification

of this second certificate, she needs a third one, . . . until she finally reaches a certificate

she can verify. This sequence of successive certificates is called a certification path. Of

course, a given certification path can only be verified if the user knows a public key that

allows him to enter this path. This implies that the certificate approach can only work

when all users are initially given at least one public key in a secure manner. This is a

relatively minor assumption, since such a key can be pre-installed by a manufacturer and

by a system administrator. From this single public key, all certificates can, in principle, be

functionally verified if we ensure that a certification path exists between all pair of users

that can possibly want to communicate. This can be ensured by creating a certification

tree, where a root certification authority certifies delegate authorities, which certifies sub￾delegates until the final users are reached. Each user should know the public keys of all

the authorities between him and the root. Thus checking the certificate of another user

in the tree can be achieved by starting at an authority shared between the two users. To

check a very distant user one simple starts verifying the certification path from the root

authority.

A much more difficult problem when using such certificates is the management of

trust. What guarantees that you can trust the owner of the verification key you initially

hold? In fact, the answer to this question is extremely context sensitive. On one hand,

within a hierarchical organization, this problem is easily solved. The organization des￾ignates a system administrator who is in charge of setting up a certification authority.

Since the administrator is trusted by the organization, he can be trusted by the users for

professional communications. On the other hand, for individual users, there is no easy

answer. If the initial certificate verification key is provided by a company or a govern￾ment, not all users will trust this initial key. To sidestep this difficulty, some systems

2 A. Joux / Introduction to Identity-Based Cryptography

propose to let users create certificates. In such a system, any user can use a certificate

which has been created by a friend he trusts. However, with these systems, another prob￾lem quickly arises. Why should anyone trust friends of friends of friends, i.e. persons he

never met? This shows that in a direct person-to-person trust model, the quick dilution of

trust quickly voids the value of certificates. This trust issue can be limited by obtaining

the same key though several independent channels until one is satisfied that the public

key is indeed valid, however, this is a expensive process and the resulting trust is hard to

quantify.

Where individuals are involved, another issue prevents the use of public-key encryp￾tion in electronic communication. Sending encrypted messages is usually a cumbersome

process. Each time a user wants to communicate with a new person, he needs to get a

public key or a certificate for this person, to check that the key corresponds to an algo￾rithm his encryption software is compatible with and finally to proceed to the encryption

step. Moreover, if the person has not already set up a public key, the user needs an initial

contact to ask for one. These practical difficulties are real issues which usually forestall

or prevent the use of public-key encryption. Indeed, if no one sends them encrypted mail,

most people do not feel the need for a public key. Moreover, when someone does not

possess a public key, it is much easier to send him unencrypted information.

Identity-based encryption offers a nice solution to a large fraction of these practical

problems. Of course, there is no such thing as a free lunch and the associated cost is that

in identity-based cryptosystems, the trust issues are even more touchy than with regular

public-key systems. The basic foundational remark of identity-based encryption is that

even in the case of unencrypted communications, the user already needs to learn some

basic information before he can communicate with another person. At the very least,

he should obtain his telephone number, his e-mail address or a similar information. As

pointed out by Shamir in his seminal paper [Sha85], it would be extremely nice if this

basic information could replace the need for a encryption key altogether.

From the point of view of functionality, this would be extremely practical. First, one

could send encrypted messages to anyone, without worrying about their public key. With￾out, in fact, even worrying about their having a public key. In the identity-based frame￾work, encryption is always possible. Of course, if the recipient of a message does not

know his private decryption key, he cannot decrypt the messages he receives. However,

this gives him a strong motivation to go and get this key. Clearly, the key ingredient to

identity-based encryption is going to be the computation of these private keys. Of course,

it should not be possible to efficiently compute the private key from the public identity

without any additional trapdoor information. Otherwise, anyone could perform the same

computation and the system would offer no security. However, being identity-based, the

system cannot be based on user specific information other than their public identity. As a

consequence, the computation of the private keys needs to be based on a global trapdoor

information, common to all or at least many users. This implies that the owner of this

trapdoor information is able to compute the private keys of all users. From a functional

point of view, this is a nice feature which allows all users to obtain their private key from

him. For this reason, this owner is usually called the key generation center of the identity￾based cryptosystem. From the security point of view, this is less convenient, since the

complete security of the system hinges on a single centralized point. All users need to

trust the key generation center, its ability to keep the global trapdoor information secret

and its capability to efficiently deliver to any valid user its own private key, after verify￾A. Joux / Introduction to Identity-Based Cryptography 3

ing his identity. As a consequence, the level of trust that is required is even stronger than

the level of trust required for public-key certificates. A certification authority can indeed

generate fake certificates to attack the system, however, this leaves evidence and sooner

or later someone is going to notice the discrepancy. With a key generation center, the

situation is very different. The key generation center can silently keep copies of all keys

he generates, or alternatively recompute these keys at any point in time. With these keys,

he can clearly decrypt any communication that he eavesdrops. The eavesdropping may

leave some evidence, but from the point of view of the key generation center, listening in

the communications is no more difficult than listening in unencrypted communications.

In other words, a key generation center may act as a key escrow agent if it so wishes.

Key escrow has been heavily discussed in the past and is often considered as a bad idea;

see [AAB+97] for a survey of this discussion. However, in identity-based cryptography,

key escrow is not introduced for its own sake but as a necessary consequence of added

functionalities. Thus, in this context, it might become more acceptable.

However, a major weak point of identity-based cryptosystems is their key genera￾tion process. A potential direction for improvement worth considering would be to cre￾ate identity-based systems involving several key generation authorities, where a single

cheating key generation authority cannot compromise the system without help from the

other authorities. Such a scheme could mitigate the trust issue, at the cost of making the

private key generation step heavier, requiring the users to interact with several key gener￾ation authorities. Another approach proposed in [Goy07], is to introduce a cryptographic

mechanism that ensures that a cheating key authority has to construct several different

decryption keys for the same user and can hopefully be detected.

The key escrow discussion also permits to shed some additional light on what might

be acceptable and what certainly is not. In some contexts, it might be useful and legiti￾mate to escrow a decryption key. For example, it might help a company make sure that

no vital trade secret will vanish if a key person disappears in a plane crash. On the other

hand, there are no legitimate reasons for ever escrowing a signature or authentication

key, such a “feature” can only lead to abuse. This basic distinction between encryption

and signature is extremely important and should be kept in mind when devising identity￾based cryptosystems.

2. Formalizing Identity-Based Cryptography

This section makes the notion of identity-based cryptography more precise and gives a

formal definition of this notion.

From the formal definition, it also shows a few elementary facts. In particular, it ex￾plains that realizing identity-based signature schemes or identity-based interactive pro￾tocols is straightforward (for any existing regular signature scheme or protocol).

An identity-based cryptographic protocol is a family of algorithms, usually consist￾ing of four algorithms, that solves a cryptographic problem. Regardless of the specific

problem, there are two algorithms specific to the identity-based paradigm. The first algo￾rithm called Setup, generates the cryptosystem parameters mpk and a master key msk.

This algorithm is run by the key generation center who then publishes the system param￾eters and keeps msk secret. The second algorithm is called KeyGen. Using the system

parameters, a user identity id and the master secret msk, it generates the private key usk

4 A. Joux / Introduction to Identity-Based Cryptography

of the corresponding user. This algorithm is run by the key generation center on behalf

of a user that requests his own private, after checking that the user matches his claimed

identity. The other algorithms in an identity-based system depend on the precise cryp￾tographic primitive that the system realizes. For example, a signature scheme requires a

Sign algorithm for producing a signature and a Vf algorithm for verifying a signature.

Similarly, a key exchange algorithm requires a GenKey algorithm for generating a shared

key and auxiliary data on the sender side and a GetKey algorithm to obtain the shared key

on the recipient side. Finally, an encryption algorithm has an Enc encryption algorithm

and a Dec decryption algorithm. Of course, this can be generalized to a variety of other

cryptographic problems, such as identification, voting, . . .

With this formalization in mind, we see that there are two very different classes

of identity-based cryptosystems. The distinction is based on the natural sequencing of

the cryptographic primitive. The class of systems where the first call to a cryptographic

primitive is made by the owner of the private key is very easy to realize. The other class,

where the first call is made by the other user, is much more difficult. Indeed, when the

owner of the private key starts, he can embed information in the message he creates in

order to convey all the necessary information about his public key. On the contrary, when

the other user starts, he really needs to derive everything from the identity string and the

system parameters, without any help from an auxiliary input.

The typical example of the first case is the folklore generic construction of an

identity-based signature scheme from any regular signature scheme. The regular signa￾ture scheme is a triple of algorithms RegGenerateKeyPair, RegSign and RegVerify. The

first algorithm generates a pair containing a public key and the corresponding private

key. The second algorithm takes as input a private key and a message and produces a

signature. The third algorithm takes as input a public key, a message and a signature and

output either valid or invalid. Using such a signature scheme, we can now generically

construct an identity-based signature scheme:

Setup The key generation center runs RegGenerateKeyPair and produces a public key

and the corresponding private key. The public key is published as part of the system

parameters mpk. The private key becomes the key generation center main key

msk.

Key Generation In order to obtain their identity-based private key users perform the

following steps:

• The user runs RegGenerateKeyPair and produces a public key upk and the cor￾responding private key usk

• The user transmits his identity string id and the public key upk to the key gener￾ation center (normally using a secure channel of communication). For increased

security, the key generation center may require a proof of knowledge of the

private key usk.

• After verifying the user’s identity, the key generation center forms a message:

“The public key upk is the signing key of user id.” and signs it with the pri￾vate key msk using RegSign. The resulting signature is denoted by ucert. This

amounts to creating a key certificate that attributes the key upk to the user with

identity id.

• The certificate ucert is returned to the user.

A. Joux / Introduction to Identity-Based Cryptography 5

Signature With this certificate in hand, the user is now ready to sign messages. The

identity-based signature algorithm Sign is defined as:

• The signing user runs RegSign on the message M to be signed, using usk as

signing key. The resulting signature is denoted by s.

• The user forms the triple

σ = (upk, ucert, s)

and produces it as his identity-based signature.

Verification To verify an identity-based signature, i.e. a triple

σ = (upk , ucert, s)

announced to be a signature of message M by the user with identity id, is done

using algorithm Verify:

• The verifying user runs RegVerify with the public key mpk on the signature

ucert and the message “The public key upk is the signing key of user id.”

• The verifying user runs RegVerify with the public key upk on the signature s

and the message M .

• If at least one verification returned invalid, then output invalid. Otherwise,

return valid.

Of course, this identity-based signature is nothing more than a certificate based sig￾nature scheme, with the certificate being included in every signature, in order to remove

the need to obtain it through another channel. A disadvantage of this approach is that the

resulting signatures are more than twice as long as the regular signatures they are based

on. A noteworthy feature of this generic scheme is that it neatly avoids the trust issue: the

key generation authority never accesses the user’s signing key and thus cannot escrow it.

Thus it can only forge user signatures by producing fake certificates which are hopefully

detected in the long run.

3. The Long Road Towards Identity-Based Encryption

After the invention of the identity-based cryptography paradigm by Shamir [Sha85],

it was clear that identity-based signature schemes were feasible (cf. previous section).

However, identity-based encryption was a much more challenging task. Neither the RSA

nor the Diffie-Hellman cryptosystems can easily be transformed into identity-based en￾cryption systems. With RSA, a tempting idea would be to use a shared encryption mod￾ulus N = pq for all users and to derive the individual encryption exponents from the

users’ identities. The factorization of N would then be a common secret used to pro￾duce decryption exponents. However, it is well-known that given an RSA modulus N,

an encryption exponent e and the corresponding description exponent d, it is easy to re￾cover the factorization of N. A probabilistic method was already described in the paper

of Rivest, Shamir and Adleman [RSA78] which proposed the RSA cryptosystem. More

recently, Coron and May [CM07,May04] described a deterministic algorithm that solves

6 A. Joux / Introduction to Identity-Based Cryptography