ABSTRACT
Bilinear pairing, a mathematical tool that maps two elements in an elliptic-curve group to an element in the related finite field, was originally brought to the cryptographic community to attack elliptic-curve systems [162,163]. These attacks originate from the fact that pairings can be used to transform the discrete logarithm problem on a certain class of elliptic curves or hyperelliptic curves to the discrete logarithm problem on a smaller finite field. Furthermore, a subex-ponential index calculus attack can be mounted to solve the latter problem. Since the seminar work in [9,144,164], bilinear pairing has found various applications in the field of cryptography. More precisely, this powerful tool can be used to construct identity (ID)-based and certificateless cryptographic schemes. Many ID-based and certificate-less cryptographic schemes have been proposed using bilinear pairings. Examples include Boneh-Franklin’s identity-based encryption (IBE) scheme [9], the Cha-Cheon identity-based signature (IBS) scheme [40], Smart’s ID-based authentication key agreement protocol [165], certificateless encryption (CLE) schemes [17,60,69], and certificateless signature (CLS) schemes [17,19,107,138]. However, due to the large element size of the super singular elliptic-curve group that the bilinear pairing is always defined over, the operation time for pairings is significantly longer than that of RSA private key operations [166,167]. In addition, the state-of-the-art implementation result for a pairing operation is at least two (at most 10) times slower than that of a scalar multiplication operation in the elliptic curve depending on the selection of security parameters [168]. Thus, bilinear pairing is regarded as one of the most expensive cryptographic operations and it is desirable to devise pairing-free certificateless cryptographic primitives.
