Optimal Pairing and Design of Pairing Friendly Curves

Public-Key Cryptosystems are perhaps the most celebrated contribution of modern cryptography. It is hard to imagine what the world would be like without their revolutionary approach to key distribution. Public Key Cryptography was publicly introduced by Whitefield Diffie and Martin Hellman in 1976. In journey of Public Key Cryptography the first use of elliptic curves was suggested by Koblitz and Miller in 1985. All public-key cryptosystems in wide use today can trace their roots to the Diffie-Hellman key exchange protocol or the RSA cryptosystem. The first use of pairing was linked with cryptanalysis but later it was used for design of cryptosystems. A pairing is a mapping that takes as input two points on an elliptic curve and outputs an element of a multiplicative Abelian group. Optimal pairing is optimisation of traditional cryptographic pairings: the Weil, Tate and Ate pairings. In this paper we developed the theory of optimal pairings and design schemes for generation of pairing friendly curves. We describe an algorithm to construct optimal Ate pairings on parametrized families of pairing friendly elliptic curves. We present R-Ate_i pairing on pairing friendly curves and also show that on these curves computing R-Ate_i pairing is faster than computing both the standard Ate pairing and Ate_i pairing. We show how Edwards curves may be used to improve Miller's algorithm for pairing computations.