Ebook: Identity-Based Cryptography

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 cryptography, 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 current 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 is a new development of public-key cryptography. It was first proposed by Adi Shamir at CRYPTO'84. However, it took the cryptographic community a long while to produce effective identity-based cryptosystems. 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 cryptography and briefly surveys its early history.

This chapter presents an overview of the various pairings on elliptic curves used in pairing based cryptography and explains the necessary mathematical background. Several constructions of pairing friendly elliptic curves are also reviewed.

This chapter gives an overview of the literature on identity-based signature (IBS) schemes, from Shamir's seminal scheme to the current state-of-the-art. Rather than presenting all schemes separately, we present three generic transformations that together cover the majority of known IBS schemes as special cases. The first transformation follows a certification approach based on standard signatures; the second is a transformation in the random oracle model from “convertible” identification schemes; and the third is based on hierarchical identity-based encryption. We also discuss a number of direct schemes that escape being covered by any of the generic transformations. Finally, we show how the principles of the first transformation can be extended to a hierarchical setting and to IBS schemes with special properties.

We take a bird's eye view of different identity-based encryption (IBE) and hierarchical identity-based encryption (HIBE) protocols that are available in the literature and use bilinear pairing as the principal building block. We start with the seminal work on IBE by Boneh-Franklin. The concept of IBE has been generalized to HIBE and we illustrate this with Gentry-Silverberg HIBE. The salient features of the security reductions are also discussed along with the protocols. These initial protocols were proven secure in the adaptive setting using random oracle. A non-adaptive security model called the selective-ID model was developed later and protocols secure in this restricted security model are discussed along with an insider's view on their proof technique. Finally, protocols secure in the adaptive setting without the use of random oracle are introduced and their security discussed. The (H)IBE protocols available in the literature are generally shown to be secure against chosen plaintext attack. Generic as well as endogenous techniques from the existing literature are briefly discussed on how to achieve chosen ciphertext security for these protocols.

The cryptographic community has, of late, shown much inventiveness in the creation of powerful new IBE-like primitives that go beyond the basic IBE notion and extend it in many new directions. Virtually all of these “super-IBE” schemes rely on bilinear pairings for their implementation, which they tend to use in a surprisingly small number of different ways: three of them as of this writing.

What is interesting is that, among the three main frameworks that we know of so far, one has acted as a veritable magnet for the construction of many of these “generalized IBE” primitives, whereas the other two have not been nearly as fruitful in that respect. This refers to the Commutative Blinding framework defined by the Boneh-Boyen [Bscr ][Bscr ]₁ IBE scheme from 2004.

The aim of this chapter is to try to shed some light on this approach's popularity, first by comparing its key properties with those of the competing frameworks, and then by providing a number of examples that illustrate how those properties have been used.

The purpose of this chapter is to provide an abstraction for the class of Exponent-Inversion IBE exemplified by the [Bscr ][Bscr ]₂ and [Sscr ][Kscr ] schemes, and, on the basis of that abstraction, to show that those schemes do support interesting and useful extensions such as HIBE and ABE.

Our results narrow, if not entirely close, the “flexibility gap” between the Exponent-Inversion and Commutative-Blinding IBE concepts.

A forward-secure encryption scheme protects secret keys from exposure by evolving the keys with time. Forward security has several unique requirements in hierarchical identity-based encryption (HIBE) scheme: (1) users join dynamically; (2) encryption is joining-time-oblivious; (3) users evolve secret keys autonomously.

We define and construct a scalable pairing-based forward-secure HIBE (fs-HIBE) scheme satisfying all of the above requirements. We also show how our fs-HIBE scheme can be used to realize a forward-secure public-key broadcast encryption scheme, which protects the secrecy of prior transmissions in the broadcast encryption setting. We further generalize fs-HIBE into a collusion-resistant multiple hierarchical ID-based encryption scheme, which can be used for secure communications with entities having multiple roles in role-based access control. The security of our schemes is based on the bilinear Diffie-Hellman assumption in the random oracle model.

In this chapter, we propose a survey of identity-based identification and signature schemes using error correcting codes. We describe coding theory, its application to cryptography and the different identification and signature schemes using error correcting codes with their new improvements. We also present the first (and unique up to now) identity-based scheme (provably secure) not based on number theory or generic constructions. The scheme combines two well known code-based schemes: the signature scheme of Courtois, Finiasz and Sendrier and the zero-knowledge identification scheme of Stern (which may also be used for signature). The scheme inherits some of the characteristics of the previous schemes: it has a large public key of order 1MB and requires a certain number of exchange rounds. The scheme can also be used as signature but leads to a very large signature of size 1.5 MB. Eventually, we present schemes obtained from the generic construction.

Certificateless cryptography combines the best of traditional public-key cryptography and the ID-based paradigm. There is no need to get and verify certificates, and the secret keys are not under the key generation center (KGC)'s escrow.

This chapter focuses on giving a complete survey of secure certificateless encryption (CLE) schemes in the literature. In particular, we discuss the techniques behind addressing special security concerns in certificateless paradigm, which include key replacement attack, decryption capabilities for arbitrary public keys (as considered in strongly-secure CLE), partial decryption capabilities (as considered in security-mediated certificateless encryption, or SMCLE) and malicious KGC attack. We also examine some less obvious efficiency issues, in which we compare specific CLE constructions with the normal public key encryption approach.

As more sensitive data is shared and stored by third-party sites on the Internet, there will be a need to encrypt data stored at these sites. One drawback of encrypting data is that it can be selectively shared only at a coarse-grained level (i.e., giving another party your private key). We describe a new concept for fine-grained sharing of encrypted data that we call Attribute-Based Encryption (ABE). In ABE, ciphertexts are labeled with sets of attributes and private keys are associated with access structures that control which ciphertexts a user is able to decrypt. We demonstrate the applicability of ABE to sharing of audit-log information and broadcast encryption. We describe a construction that supports delegation of private keys, which subsumes Hierarchical Identity-Based Encryption (HIBE).

Groups with pairing are now considered as standard building blocks for cryptographic primitives. The security of schemes based on such groups relies on hypotheses related to the discrete logarithm problem. As these hypotheses are not proved, one would like to have some positive security argument for them. It is usual to assess their security in the so called generic group model introduced by Nechaev and Shoup. Over the time, this model has been extended in different directions to cover new features.

The relevance of this model is nevertheless subject to criticisms: in particular, the fact that the answer to any fresh query is a random bit string is not what one expects from a usual group law.

In this chapter, we first present the original model of Nechaev and Shoup as well as some classical extensions, with a focus on ideas rather than formal correctness. Then, we develop rigorously a generic group model with pairing which generalizes all models seen so far in the literature. We provide a general framework in order to prove difficulty assumptions in this setting. In order to improve the realism of this model, we introduce the notion of pseudo-random families of groups.We show how to reduce the security of a problem in such a family to the security of the same problem in the generic group model and to the security of an underlying strong pseudo-random family of permutations.

This chapter describes and compares the software implementation of popular elliptic curve pairings on two architectures, of which the Intel Pentium 4 and Core2 are representatives.

In this chapter the efficient hardware implementation of pairings is considered. For each of the three fields , and suitable curves, pairing algorithms and field arithmetic architectures are presented. An example architecture for computing the η_T pairing in characteristic 2 or 3 is presented and its implementation results on a Xilinx FPGA considered. Finally the implementation results of several pairing architectures from the literature are discussed.

In this chapter the effect of implementation attacks on the security of pairings is examined. This is a particularly pertinent issue given the increasing efficiency of pairing algorithms, which have recently proved viable for implementation on resource constrained devices where such attacks pose a serious threat. Specifically, we discuss power analysis and fault attacks on a range of pairing algorithms. Countermeasures and their impact on performance are also described.