Pairing computation on twisted Edwards form elliptic curves. (English) Zbl 1186.94433

Galbraith, Steven D. (ed.) et al., Pairing-based cryptography – Pairing 2008. Second international conference, Egham, UK, September 1–3, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-85503-3/pbk). Lecture Notes in Computer Science 5209, 192-210 (2008).
Summary: 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.
For the entire collection see [Zbl 1155.94002].


94A60 Cryptography
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
11Y16 Number-theoretic algorithms; complexity


Full Text: DOI


[1] Joux, A., A one round protocol for tripartite Diffie-Hellman, J. Cryptology, 17, 4, 263-276 (2004) · Zbl 1070.94007 · doi:10.1007/s00145-004-0312-y
[2] Boneh, D.; Franklin, M. K., Identity-based encryption from the Weil pairing, SIAM J. Comput., 32, 3, 586-615 (2003) · Zbl 1046.94008 · doi:10.1137/S0097539701398521
[3] Freeman, D., Scott, M., Teske, E.: A taxonomy of pairing-friendly elliptic curves. Cryptology ePrint Archive, Report 2006/372 (2006), http://eprint.iacr.org/ · Zbl 1181.94094
[4] 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) · Zbl 0813.14045 · doi:10.2307/2153546
[5] Miller, V. S., The Weil pairing and its efficient calculation, J. Cryptology, 17, 4, 235-261 (2004) · Zbl 1078.14043 · doi:10.1007/s00145-004-0315-8
[6] Barreto, P. S.L. M.; Kim, H. Y.; Lynn, B.; Scott, M.; Yung, M., Efficient algorithms for pairing-based cryptosystems, Advances in Cryptology - CRYPTO 2002, 354-369 (2002), Heidelberg: Springer, Heidelberg · Zbl 1026.94520 · doi:10.1007/3-540-45708-9_23
[7] Galbraith, S. D.; Harrison, K.; Soldera, D.; Fieker, C.; Kohel, D. R., Implementing the Tate pairing, Algorithmic Number Theory, 324-337 (2002), Heidelberg: Springer, Heidelberg · Zbl 1058.11072 · doi:10.1007/3-540-45455-1_26
[8] Edwards, H. M., A normal form for elliptic curves, Bulletin of the American Mathematical Society, 44, 393-422 (2007) · Zbl 1134.14308 · doi:10.1090/S0273-0979-07-01153-6
[9] Bernstein, D. J.; Lange, T.; Kurosawa, K., Faster addition and doubling on elliptic curves, Advances in Cryptology - ASIACRYPT 2007, 29-50 (2007), Heidelberg: Springer, Heidelberg · Zbl 1153.11342 · doi:10.1007/978-3-540-76900-2_3
[10] Bernstein, D. J.; Lange, T.; Boztas, S.; Lu, H. F., Inverted Edwards coordinates, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, 20-27 (2007), Heidelberg: Springer, Heidelberg · Zbl 1195.14047 · doi:10.1007/978-3-540-77224-8_4
[11] Chatterjee, S.; Sarkar, P.; Barua, R.; Park, C.-s.; Chee, S., Efficient computation of Tate pairing in projective coordinate over general characteristic fields, Information Security and Cryptology - ICISC 2004, 168-181 (2005), Heidelberg: Springer, Heidelberg · Zbl 1133.94310
[12] 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)
[13] Euler, L.: Observationes de comparatione arcuum curvarum irrectificabilium. Novi Comm. Acad. Sci. Petropolitanae 6(1761), 58-84
[14] Gauss, C.F.: Werke 3, 404
[15] Koblitz, N.; Menezes, A.; Smart, N., Pairing-based cryptography at high security levels, Cryptography and Coding, 13-36 (2005), Heidelberg: Springer, Heidelberg · Zbl 1122.94038 · doi:10.1007/11586821_2
[16] Verheul, E. R., Evidence that XTR is more secure than supersingular elliptic curve cryptosystems, Journal of Cryptology, 17, 277-296 (2004) · Zbl 1075.94011 · doi:10.1007/s00145-004-0313-x
[17] Wolfram, S.: The Mathematica Book, 5th edn. Wolfram Media (2003), http://www.wolfram.com
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.