Abstract
The Weil and Tate pairings have been used recently to build new schemes in cryptography. It is known that the Weil pairing takes longer than twice the running time of the Tate pairing. Hence it is necessary to develop more efficient implementations of the Tate pairing for the practical application of pairing based cryptosystems. In 2002, Barreto et al. and Galbraith et al. provided new algorithms for the fast computation of the Tate pairing in characteristic three. In this paper, we give a closed formula for the Tate pairing on the hyperelliptic curve y 2 = x p – x + d in characteristic p. This result improves the implementations in [BKLS02], [GHS02] for the special case p=3.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
The Pairing-Based Crypto Lounge, http://planeta.terra.com.br/informatica/paulobarreto/pblounge.html
Barreto, P.S.L.M., Kim, H.Y., Lynn, B., Scott, M.: Efficient Algorithms for Pairing-Based Cryptosystems. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 354–368. Springer, Heidelberg (2002)
Blake, I., Seroussi, G., Smart, N.P.: Elliptic curves in cryptography. London Mathematical Society. LNS, vol. 265. Cambridge University Press, Cambridge (1999) (reprinted 2000)
Boneh, D., Franklin, M.: Identity-based encryption from the Weil pairing. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 213–229. Springer, Heidelberg (2001)
Boneh, D., Silverberg, A.: Applications of multilinear forms to cryptography. Contemporary Mathematics, vol. 324, pp. 71–90. American Mathematical Society (2003)
Cha, J.C., Cheon, J.H.: An Identity-Based Signature from Gap DiffieHellman Groups. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 18–30. Springer, Heidelberg (2002)
Diffie, W., Hellman, M.: New direction in cryptography. IEEE Trans. Information Theory IT-22(6), 644–654 (1976)
Duursma, I.: Class numbers for hyperelliptic curves. In: Pellikaan, Perret, Vladuts (eds.) Arithmetic, Geometry and Coding Theory, pp. 45–52. deGruyter, Berlin (1996)
Duursma, I., Sakurai, K.: Efficient algorithms for the Jacobian variety of hyperelliptic curves y2 = xp? x + 1 over a finite field of odd characteristic p. In: Coding theory, cryptography and related areas (Guanajuato, 1998), pp. 73–89. Springer, Berlin (2000)
Frey, G., Rück, H.-G.: A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves. Math. Comp. 62(206), 865–874 (1994)
Galbraith, S.D.: Supersingular curves in cryptography. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 495–513. Springer, Heidelberg (2001)
Galbraith, S.D., Harrison, K., Soldera, D.: Implementing the Tate pairing. In: Fieker, C., Kohel, D.R. (eds.) ANTS 2002. LNCS, vol. 2369, pp. 324–337. Springer, Heidelberg (2002)
Hess, F.: Exponent group signature schemes and efficient identity based signature schems based on pairing. In: Proceedings of the Workshop Selected Areas in Cryptology, SAC (August 2002)
Hess, F.: A Note on the Tate Pairing of Curves over Finite Fields (2002), Available on: http://www.math.tu-berlin.de/~hess
Izu, T., Takagi, T.: Efficient computations of the tate pairingfor the large MOV degrees. In: Lee, P.J., Lim, C.H. (eds.) ICISC 2002. LNCS, vol. 2587, pp. 283–297. Springer, Heidelberg (2003)
Joux, A.: A one round protocol for tripartite Diffie-Hellman. In: Bosma, W. (ed.) ANTS 2000. LNCS, vol. 1838, pp. 385–394. Springer, Heidelberg (2000)
Koblitz, N.: An elliptic curve implementation of the finite field digital signature algorithm. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 327–337. Springer, Heidelberg (1998)
Miller, V.: Short Programs for Functions on Curves (1986) (unpublished manuscript)
Menezes, A., Okamoto, T., Vanstone, S.: Reducing elliptic curve logarithms to logarithms in a finite field. IEEE Trans. on Inform. Theory 39, 1639–1646 (1993)
Paterson, K.G.: ID-based signature from pairings on elliptic curves. Electronics Letters 38(18), 1025–1026 (2002)
Sakai, R., Ohgishi, K., Kasahara, M.: Cryptosystems based on pairing. In: Symposium on cryptography and Information Security, Okinawa, Japan, pp. 26–28 (2000)
Smart, N.P.: An identity based authentication key agreement protocol based on pairing. Electronics Letters 38, 630–632 (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Duursma, I., Lee, HS. (2003). Tate Pairing Implementation for Hyperelliptic Curves y 2 = x p – x + d . In: Laih, CS. (eds) Advances in Cryptology - ASIACRYPT 2003. ASIACRYPT 2003. Lecture Notes in Computer Science, vol 2894. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-40061-5_7
Download citation
DOI: https://doi.org/10.1007/978-3-540-40061-5_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20592-0
Online ISBN: 978-3-540-40061-5
eBook Packages: Springer Book Archive