Abstract
A new form of elliptic curve was recently discovered by Edwards and their application to cryptography was developed by Bernstein and Lange. The form was later extended to the twisted Edwards form. For cryptographic applications, Bernstein and Lange pointed out several advantages of the Edwards form in comparison to the more well known Weierstraß form. We consider the problem of pairing computation over Edwards form curves. Using a birational equivalence between twisted Edwards and Weierstraß forms, we obtain a closed form expression for the Miller function computation.
Simplification of this computation is considered for a class of supersingular curves. As part of this simplification, we obtain a distortion map similar to that obtained for Weierstraß form curves by Barreto et al and Galbraith et al. Finally, we present explicit formulae for combined doubling and Miller iteration and combined addition and Miller iteration using both inverted Edwards and projective Edwards coordinates. For the class of supersingular curves considered here, our pairing algorithm can be implemented without using any inversion.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Joux, A.: A one round protocol for tripartite Diffie-Hellman. J. Cryptology 17(4), 263–276 (2004)
Boneh, D., Franklin, M.K.: Identity-based encryption from the Weil pairing. SIAM J. Comput. 32(3), 586–615 (2003)
Freeman, D., Scott, M., Teske, E.: A taxonomy of pairing-friendly elliptic curves. Cryptology ePrint Archive, Report 2006/372 (2006), http://eprint.iacr.org/
Frey, G., Rück, H.G.: A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves. Mathematics of Computation 62, 865–874 (1994)
Miller, V.S.: The Weil pairing and its efficient calculation. J. Cryptology 17(4), 235–261 (2004)
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–369. Springer, Heidelberg (2002)
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)
Edwards, H.M.: A normal form for elliptic curves. Bulletin of the American Mathematical Society 44, 393–422 (2007)
Bernstein, D.J., Lange, T.: Faster addition and doubling on elliptic curves. In: Kurosawa, K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 29–50. Springer, Heidelberg (2007)
Bernstein, D.J., Lange, T.: Inverted Edwards coordinates. In: Boztas, S., Lu, H.F. (eds.) AAECC 2007. LNCS, vol. 4851, pp. 20–27. Springer, Heidelberg (2007)
Chatterjee, S., Sarkar, P., Barua, R.: Efficient computation of Tate pairing in projective coordinate over general characteristic fields. In: Park, C.-s., Chee, S. (eds.) ICISC 2004. LNCS, vol. 3506, pp. 168–181. Springer, Heidelberg (2005)
Bernstein, D.J., Birkner, P., Lange, T., Peters, C.: Twisted Edwards curves. Cryptology ePrint Archive, Report 2008/013 (2008) http://eprint.iacr.org/ (Accepted in AFRICACRYPT 2008)
Euler, L.: Observationes de comparatione arcuum curvarum irrectificabilium. Novi Comm. Acad. Sci. Petropolitanae 6(1761), 58–84
Gauss, C.F.: Werke 3, 404
Koblitz, N., Menezes, A.: Pairing-based cryptography at high security levels. In: Smart, N. (ed.) Cryptography and Coding 2005. LNCS, vol. 3796, pp. 13–36. Springer, Heidelberg (2005)
Verheul, E.R.: Evidence that XTR is more secure than supersingular elliptic curve cryptosystems. Journal of Cryptology 17, 277–296 (2004)
Wolfram, S.: The Mathematica Book, 5th edn. Wolfram Media (2003), http://www.wolfram.com
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Das, M.P.L., Sarkar, P. (2008). Pairing Computation on Twisted Edwards Form Elliptic Curves. In: Galbraith, S.D., Paterson, K.G. (eds) Pairing-Based Cryptography – Pairing 2008. Pairing 2008. Lecture Notes in Computer Science, vol 5209. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-85538-5_14
Download citation
DOI: https://doi.org/10.1007/978-3-540-85538-5_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-85503-3
Online ISBN: 978-3-540-85538-5
eBook Packages: Computer ScienceComputer Science (R0)