Abstract
We derive a new algorithm for computing the Tate pairing on an elliptic curve over a finite field. The algorithm uses a generalisation of elliptic divisibility sequences known as elliptic nets, which are maps from ℤn to a ring that satisfy a certain recurrence relation. We explain how an elliptic net is associated to an elliptic curve and reflects its group structure. Then we give a formula for the Tate pairing in terms of values of the net. Using the recurrence relation we can calculate these values in linear time. Computing the Tate pairing is the bottleneck to efficient pairing-based cryptography. The new algorithm has time complexity comparable to Miller’s algorithm, and should yield to further optimisation.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Menezes, A.J., Okamoto, T., Vanstone, S.A.: Reducing elliptic curve logarithms to logarithms in a finite field. IEEE Trans. Inform. Theory 39(5), 1639–1646 (1993)
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)
Sakai, R., Ohgishi, K., Kasahara, M.: Cryptosystems based on pairing. In: Symposium on Cryptography and Information Security, Okinawa, Japan (2000)
Joux, A.: A one round protocol for tripartite Diffie-Hellman. In: Bosma, W. (ed.) Algorithmic Number Theory. LNCS, vol. 1838, pp. 385–393. Springer, Heidelberg (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)
Duquesne, S., Lange, T.: Pairing-based cryptography. In: Handbook of elliptic and hyperelliptic curve cryptography. Discrete Math. Appl, pp. 573–590. Chapman & Hall/CRC, Boca Raton, FL (2006)
Paterson, K.G.: Cryptography from pairings. In: Advances in elliptic curve cryptography. London Math. Soc. Lecture Note Ser., vol. 317, pp. 215–251. Cambridge Univ. Press, Cambridge (2005)
Barreto, P.S.L.M.: The pairing-based crypto lounge http://planeta.terra.com.br/informatica/paulbarreto/pblounge.html
Miller, V.: Short programs for functions on curves (1986)
Duquesne, S., Frey, G.: Implementation of pairings. In: Handbook of elliptic and hyperelliptic curve cryptography, Boca Raton. Discrete Math. Appl., pp. 389–404. Chapman & Hall/CRC, Boca Raton, FL (2006)
Galbraith, S.D., Harrison, K., Soldera, D.: Implementing the Tate pairing. In: Fieker, C., Kohel, D.R. (eds.) Algorithmic Number Theory. LNCS, vol. 2369, pp. 324–337. Springer, Heidelberg (2002)
Ward, M.: Memoir on elliptic divisibility sequences. Amer. J. Math. 70, 31–74 (1948)
Everest, G., Poorten, A.v.d., Shparlinski, I., Ward, T.: Elliptic Divisibility Sequences. American Mathematical Society, Providence, pp. 163–175 (2003)
Shipsey, R.: Elliptic Divibility Sequences. PhD thesis, Goldsmiths, University of London (2001)
Stange, K.E.: Elliptic Nets. PhD thesis, Brown University (in preparation)
Silverman, J.H.: The arithmetic of elliptic curves (Corrected reprint of the 1986 original). Graduate Texts in Mathematics, vol. 106. Springer, New York (1992)
Silverman, J.H.: Advanced topics in the arithmetic of elliptic curves. Graduate Texts in Mathematics, vol. 151. Springer, New York (1994)
Swart, C.: Elliptic curves and related sequences. PhD thesis, Royal Holloway and Bedford New College, University of London (2003)
van der Poorten, A.J.: Elliptic curves and continued fractions. J. Integer Seq. Article 05.2.5, (electronic) 8(2), 19 (2005)
Propp, J.: Robbins forum http://www.math.wisc.edu/~propp/about-robbins
Duquesne, S., Frey, G.: Background on pairings. In: Handbook of elliptic and hyperelliptic curve cryptography. Discrete Math. Appl., pp. 115–124. Chapman & Hall/CRC, Boca Raton, FL (2006)
Galbraith, S.: Pairings. In: Advances in elliptic curve cryptography. London Math. Soc. Lecture Note Ser., vol. 317, pp. 183–213. Cambridge Univ. Press, Cambridge (2005)
Frey, G., Lange, T.: Background on curves and Jacobians. In: Handbook of elliptic and hyperelliptic curve cryptography. Discrete Math. Appl., pp. 45–85. Chapman & Hall/CRC, Boca Raton, FL (2006)
Chandrasekharan, K.: Elliptic functions. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 281. Springer, Heidelberg (1985)
Blake, I.F., Seroussi, G., Smart, N.P.: Elliptic curves in cryptography (Reprint of the 1999 original). London Mathematical Society Lecture Note Series, vol. 265. Cambridge University Press, Cambridge (2000)
Hankerson, D., Hernandez, J.L., Menezes, A.: Software implementation of elliptic curve cryptography over binary fields. In: Paar, C., Koç, Ç.K. (eds.) CHES 2000. LNCS, vol. 1965, pp. 1–24. Springer, Heidelberg (2000)
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)
Ciet, M., Joye, M., Lauter, K., Montgomery, P.L.: Trading inversions for multiplications in elliptic curve cryptography. Des. Codes Cryptogr. 39(2), 189–206 (2006)
Koblitz, N., Menezes, A.: Pairing-based cryptography at high security levels. In: Smart, N.P. (ed.) Cryptography and Coding. LNCS, vol. 3796, pp. 13–36. Springer, Heidelberg (2005)
Barreto, P.S.L.M., Lynn, B., Scott, M.: On the selection of pairing-friendly groups. In: Matsui, M., Zuccherato, R.J. (eds.) SAC 2003. LNCS, vol. 3006, pp. 17–25. Springer, Heidelberg (2004)
The PARI Group: Pari/gp development headquarters http://pari.math.u-bordeaux.fr/
Stange, K.E.: Pari/gp scripts for tate pairing via elliptic nets. http://www.math.brown.edu/~stange/tatepairing/
Lynn, B.: Pairing-based cryptography library http://crypto.stanford.edu/pbc/
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Stange, K.E. (2007). The Tate Pairing Via Elliptic Nets. In: Takagi, T., Okamoto, T., Okamoto, E., Okamoto, T. (eds) Pairing-Based Cryptography – Pairing 2007. Pairing 2007. Lecture Notes in Computer Science, vol 4575. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-73489-5_19
Download citation
DOI: https://doi.org/10.1007/978-3-540-73489-5_19
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-73488-8
Online ISBN: 978-3-540-73489-5
eBook Packages: Computer ScienceComputer Science (R0)