Bilinear maps have become an important new item in the cryptographer’s toolkit. They first came to prominence when they were used by Menezes, Okamoto and Vanstone to help solve the elliptic curve discrete logarithm problem on elliptic curves of small embedding degree.
In 1984, Shamir developed the first identity based signature scheme, and posed the construction of an identity based encryption scheme as an open problem [118]. Subsequently identity based identification and identity based key agreement schemes were proposed. However, identity based encryption remained an open problem. In 2000, Sakai, Ohgishi and Kasahara used bilinear maps to implement an efficient identity based non-interactive key agreement and identity based digital signature [111]. In 2001, some 17 years after it was suggested, Boneh and Franklin proposed the first efficient identity based encryption scheme, constructed using bilinear maps [31].
In this thesis we review some of the numerous cryptographic protocols that have been constructed using bilinear maps.
We first give a review of public key cryptography. We then review the mathematics behind the two known bilinear maps, the Weil and Tate pairings, including several improvements suggested m [67, 14]. We develop a Java library to implement pairing based cryptography. In Ch 4 we look at some of the cryptographically hard problems that arise from bilinear maps. In Ch 5 we review identity based signature schemes and present the fastest known scheme. In Ch 6 we review some encryption schemes, make some observations that help improve the performance of many identity based cryptosystems, and propose the fastest scheme for public key encryption with keyword search. In Ch 7 we review identity based key agreements and propose the fastest scheme secure in a modified Bellare-Rogaway model [19]. In Ch 8 we review identity based signcryption schemes and present the fastest known scheme.