Tate and Ate pairings for \(y^2=x^5-\alpha x\) in characteristic five. (English) Zbl 1222.14044

Summary: We consider the Tate and Ate pairings for the genus-2 supersingular hyperelliptic curves \(y^2 =x^5-\alpha x\) (\(\alpha = \pm 2\)) defined over finite fields of characteristic five. More precisely, we construct a distortion map explicitly, and show that the map indeed gives an input for which the value of the Tate pairing is not trivial. We next describe a computation of the Tate pairing by using the proposed distortion map. We also see that this type of curve is equipped with a simple quintuple operation on the Jacobian group, which leads to an improvement for computing the Tate pairing. We further show the Ate pairing, a variant of the Tate pairing for elliptic curves, can be applied to this curve. The Ate pairing yields an algorithm which is about 50% more efficient than the Tate pairing in this case.


14G15 Finite ground fields in algebraic geometry
14G50 Applications to coding theory and cryptography of arithmetic geometry
14Q20 Effectivity, complexity and computational aspects of algebraic geometry
Full Text: DOI


[1] P.S.L.M. Barreto, S. Galbraith, C. Ó hÉigeartaigh and M. Scott, Efficient pairing computation on supersingular Abelian varieties. IACR Cryptology ePrint Archive, 2004/375, 2004, to appear in Designs, Codes and Cryptography.
[2] P.S.L.M. Barreto, H.Y. Kim, B. Lynn and M. Scott, Efficient algorithms for pairing-based cryptosystems. Advances in Cryptology—CRYPTO 2002, Lecture Notes in Computer Science,2442, Springer-Verlag, 2002, 354-368. · Zbl 1026.94520
[3] J.L. Beuchat, M. Shirase, T. Takagi and E. Okamoto, An algorithm for ηT pairing calculation in characteristic three and its hardware implementation. IACR Cryptology ePrint Archive, 2006/327, 2006.
[4] Boneh, D.; Franklin, M., Identity-based encryption from the Weil pairing, SIAM J. Computing, 32, 586-615 (2003) · Zbl 1046.94008 · doi:10.1137/S0097539701398521
[5] D. Boneh, B. Lynn and H. Shacham, Short signatures from the Weil pairing. Advances in Cryptology—ASIACRYPT 2001, Lecture Notes in Computer Science,2248, Springer-Verlag, 2001, 514-532. · Zbl 1064.94554
[6] Cantor, D. G., Computing in the Jacobian of a hyperelliptic curve, Math. Comp., 48, 95-101 (1987) · Zbl 0613.14022 · doi:10.2307/2007876
[7] Y. Choie, E. Jeong and E. Lee, Supersingular hyperelliptic curves of genus 2 over finite fields. IACR Cryptology ePrint Archive, 2002/032, 2006.
[8] Y. Choie and E. Lee, Implementation of Tate pairing on hyperelliptic curves of genus 2. International Conference on Information Security and Cryptology (ICISC 2003), Lecture Notes in Computer Science,2971, Springer-Verlag, 2004, 97-111. · Zbl 1092.94504
[9] Cohen, H., A Course in Computational Algebraic Number Theory, Graduate Texts in Math. (1993), Berlin Heidelberg: Springer-Verlag, Berlin Heidelberg · Zbl 0786.11071
[10] H. Cohen and H.W. Lenstra Jr., Heuristics on class groups of number fields. Number Theory, Lecture Notes in Mathematics,1068, Springer-Verlag, 1984, 33-62. · Zbl 0558.12002
[11] I. Duursma and H.S. Lee, Tate pairing implementation for hyperelliptic curvesy^2 =x^p −x +d. Advances in Cryptology—ASIACRYPT 2003, Lecture Notes in Computer Science,2894, Springer-Verlag, 2003, 111-123. · Zbl 1189.11056
[12] Duursma, I.; Sakurai, K., Efficient algorithms for the Jacobian variety of hyperelliptic curvesy^2 =x^p −x + 1 over a finite field of odd characteristicp, Coding theory, cryptography and related areas, 73-89 (2000), Berlin: Springer, Berlin · Zbl 1009.11047
[13] K. Eisenträger, K. Lauter and P.L. Montgomery, Improved Weil and Tate pairings for elliptic and hyperelliptic curves. Algorithmic Number Theory Symposium—ANTS VI, Lecture Notes in Computer Science,3076, Springer-Verlag, 2004, 169-183. · Zbl 1116.11042
[14] G. Frey and T. Lange, Fast bilinear maps from the Tate-Lichtenbaum pairing on hyperelliptic curves. Algorithmic Number Theory Symposium—ANTS VII, Lecture Notes in Computer Science,4076, Springer-Verlag, 2006, 466-479. · Zbl 1143.94345
[15] 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, 865-874 (1994) · Zbl 0813.14045 · doi:10.2307/2153546
[16] S.D. Galbraith, K.G. Paterson and N.P. Smart, Pairings for cryptographers. IACR Cryptology ePrint Archive, 2006/165, 2006.
[17] S.D. Galbraith and J. Pujolás, Distortion maps for genus two curves. Proceedings of a workshop on Mathematical Problems and Techniques in Cryptology, 2005, 46-58. Available at http://www.isg.rhul.ac.uk/ sdg/jordi-paper.pdf.
[18] S.D. Galbraith, J. Pujolás, C. Ritzenthaler and. B. Smith, Distortion maps for genus two curves. IACR Cryptology ePrint Archive, 2006/375, 2006.
[19] Galbraith, S. D.; Rotger, V., Easy decision Diffie-Hellman groups, LMS J. Comput. Math., 7, 201-218 (2004) · Zbl 1116.14014
[20] R. Granger, F. Hess, R. Oyono, N. Theriault and F. Vercauteren, Ate pairing on hyperelliptic curves. Technical Report CSTR-06-020, 2006. · Zbl 1141.94356
[21] R. Harasawa, Y. Sueyoshi and A. Kudo, Distortion map fory^2 =x^5 − αx in characteristic five. Proceedings of the 2006 Symposium on Cryptography and Information Security (SCIS 2006), 4C2-3, Hiroshima, 2006.
[22] R. Harasawa, Y. Sueyoshi and A. Kudo, Tate pairing fory^2 =x^5 − αx in characteristic five. IACR Cryptology ePrint Archive, 2006/114, 2006. · Zbl 1222.14044
[23] R. Harasawa, Y. Sueyoshi and A. Kudo, Ate pairing fory^2 =x^5 − αx in characteristic five. IACR Cryptology ePrint Archive, 2006/202, 2006. · Zbl 1222.14044
[24] C. Ó hÉigeartaigh and M. Scott, Pairing calculation on supersingular genus 2 curves. IACR Cryptology ePrint Archive, 2006/005, 2006.
[25] Hess, F.; Smart, N. P.; Vercauteren, F., The Eta pairing revisited, IEEE Transactions on Information Theory, 52-10, 4595-4602 (2006) · Zbl 1189.11057 · doi:10.1109/TIT.2006.881709
[26] L. Hitt, On an improved definition of embedding degree. IACR Cryptology ePrint Archive, 2006/415, 2006.
[27] Itoh, T.; Tsujii, S., A fast algorithm for computing multiplicative inversion inGF(2^m) using normal bases, Information and Computation, 78, 171-177 (1988) · Zbl 0672.68015 · doi:10.1016/0890-5401(88)90024-7
[28] A. Joux, A one-round protocol for tripartite Diffie-Hellman. Algorithmic Number Theory Symposium—ANTS IV, Lecture Notes in Computer Science,1838, Springer-Verlag, 2000, 385-394. · Zbl 1029.94026
[29] G. Kang and J.H. Park, Powered Tate pairing computation. IACR Cryptology ePrint Archive, 2005/260, 2005.
[30] Koblitz, N., Hyperelliptic cryptosystems, J. Cryptology, 1, 139-150 (1989) · Zbl 0674.94010 · doi:10.1007/BF02252872
[31] N. Koblitz, CM curves with good cryptographic properties. Advances in Cryptology—CRYPTO ’91, Lecture Notes in Computer Science,576, Springer-Verlag, 1992, 279-287. · Zbl 0780.14018
[32] A.K. Lenstra and E.R. Verheul, The XTR public key system. Advances in Cryptology—CRYPTO 2000, Lecture Notes in Computer Science,1880, Springer-Verlag, 2000, 1-19. · Zbl 0995.94538
[33] V. Miller, Short program for functions on. curves. IBM Thomas J. Watson Research Center, 1986. Available at http://crypto.stanford.edu/miller/miller.ps.
[34] Miller, V., The Weil pairing, and its efficient calculation, J. Cryptology, 17, 235-261 (2004) · Zbl 1078.14043 · doi:10.1007/s00145-004-0315-8
[35] R. Ronan, C. Ó hÉigeartaigh, C. Murphy, T. Kerins and P.S.L.M. Baretto, Hardware implementation of the ηT pairing in characteristic 3. IACR Cryptology ePrint Archive, 2006/371, 2006.
[36] R. Ronan, C. Ó hÉigeartaigh, C. Murphy, M. Scott and W. Marnane, An embedded processor for a pairing-based cryptosystem. Proceedings of the Third International Conference on Information Technology: New Generations (ITNG’06), IEEE Computer Society, 2006.
[37] C. Shu, S. Kwon and K. Gaj, FPGA accelerated Tate pairing based cryptosystem over binary fields. IACR Cryptology ePrint Archive, 2006/179, 2006.
[38] Silverman, J. H., The Arithmetic of Elliptic Curves, Graduate Texts in Math. (1986), New York: Springer-Verlag, New York · Zbl 0585.14026
[39] Stichtenoth, H., Algebraic Function Fields and Codes (1993), Berlin Heidelberg: Springer Universitext, Springer-Verlag, Berlin Heidelberg · Zbl 0816.14011
[40] Stichtenoth, H.; Xing, C., On the structure of the divisor class group of a class of curves over finite fields, Arch. Math., 65, 141-150 (1995) · Zbl 0874.11045 · doi:10.1007/BF01270693
[41] E.R. Verheul, Evidence that XTR is more secure than supersingular elliptic curve crypto-systems. Advances in Cryptology—EUROCRYPT 2001, Lecture Notes in Computer Science,2045, Springer-Verlag, 2001, 195-210. · Zbl 0981.94009
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.