Speeding Up Pairing Computations on Genus 2 Hyperelliptic Curves with Efficiently Computable Automorphisms | SpringerLink
Skip to main content
Springer Nature Link
Log in

Speeding Up Pairing Computations on Genus 2 Hyperelliptic Curves with Efficiently Computable Automorphisms

  • Conference paper
Pairing-Based Cryptography – Pairing 2008 (Pairing 2008)

Part of the book series: Lecture Notes in Computer Science ((LNSC,volume 5209))

Included in the following conference series:

Abstract

Pairings on the Jacobians of (hyper-)elliptic curves have received considerable attention not only as a tool to attack curve based cryptosystems but also as a building block for constructing cryptographic schemes with new and novel properties. Motivated by the work of Scott, we investigate how to use efficiently computable automorphisms to speed up pairing computations on two families of non-supersingular genus 2 hyperelliptic curves over prime fields. Our findings lead to new variants of Miller’s algorithm in which the length of the main loop can be up to 4 times shorter than that of the original Miller’s algorithm in the best case. We also implement the calculation of the Tate pairing on both a supersingular and a non-supersingular genus 2 curve with the same embedding degree of k = 4. Combining the new algorithm with known optimization techniques, we show that pairing computations on non-supersingular genus 2 curves over prime fields use up to 55.8% fewer field operations and run about 10% faster than supersingular genus 2 curves for the same security level.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Avanzi, R.M., Cohen, H., Doche, C., Frey, G., Lange, T., Nguyen, K., Vercauteren, F.: Handbook of Elliptic and Hyperelliptic Curve Cryptography. Chapman & Hall/CRC, Boca Raton (2006)

    MATH  Google Scholar 

  2. Barreto, P.L.S.M., Galbraith, S., Ó’hÉigeartaigh, C., Scott, M.: Efficient Pairing Computation on Supersingular Abelian Varieties. Design, Codes and Cryptography 42, 239–271 (2007)

    Article  MATH  Google Scholar 

  3. Barreto, P.L.S.M., Kim, H.Y., Lynn, B., Scott, M.: Efficient Algorithm for Pairing-Based Cryptosystems. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 354–368. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  4. Barreto, P.L.S.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)

    Google Scholar 

  5. Boneh, D., Franklin, M.: Identity-Based Encryption from the Weil Pairing. SIAM Journal of Computing 32(3), 586–615 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  6. Choie, Y., Lee, E.: Implementation of Tate Pairing on Hyperelliptic Curve of Genus 2. In: Lim, J.-I., Lee, D.-H. (eds.) ICISC 2003. LNCS, vol. 2971, pp. 97–111. Springer, Heidelberg (2004)

    Google Scholar 

  7. Choie, Y., Jeong, E., Lee, E.: Supersingular Hyperelliptic Curves of Genus 2 over Finite Fields. Journal of Applied Mathematics and Computation 163(2), 565–576 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  8. Cocks, C., Pinch, R.G.E.: Identity-based Cryptosystems Based on the Weil Pairing (unpublished manuscript, 2001)

    Google Scholar 

  9. Duursma, I., Gaudry, P., Morain, F.: Speeding up the Discrete Log Computation on Curves with Automorphisms. In: Lam, K.-Y., Okamoto, E., Xing, C. (eds.) ASIACRYPT 1999. LNCS, vol. 1716, pp. 103–121. Springer, Heidelberg (1999)

    Google Scholar 

  10. Duursma, I., Lee, H.S.: Tate Pairing Implementation for Hyperelliptic Curves y 2 = x p − x + d. In: Laih, C.-S. (ed.) ASIACRYPT 2003. LNCS, vol. 2894, pp. 111–123. Springer, Heidelberg (2003)

    Google Scholar 

  11. Fan, X., Gong, G., Jao, D.: Efficient Pairing Computation on Genus 2 Curves in Projective Coordinates. Centre for Applied Cryptographic Research (CACR) Technical Reports, CACR 2008-03, http://www.cacr.math.uwaterloo.ca/techreports/2008/cacr2008-03.pdf

  12. Freeman, D.: Constructing Pairing-Friendly Genus 2 Curves over Prime Fields with Ordinary Jacobians. In: Takagi, T., Okamoto, T., Okamoto, E., Okamoto, T. (eds.) Pairing 2007. LNCS, vol. 4575, pp. 152–176. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  13. Frey, G., Lange, T.: Fast Bilinear Maps from The Tate-Lichtenbaum Pairing on Hyperelliptic Curves. In: Hess, F., Pauli, S., Pohst, M. (eds.) ANTS 2006. LNCS, vol. 4076, pp. 466–479. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  14. Frey, G., Rück, H.-G.: A Remark Concerning m-Divisibility and the Discrete Logarithm Problem in the Divisor Class Group of Curves. Mathematics of Computation 62(206), 865–874 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  15. Furukawa, E., Kawazoe, M., Takahashi, T.: Counting Points for Hyperelliptic Curves of Type y 2 = x 5 + ax over Finite Prime Fields. In: Matsui, M., Zuccherato, R.J. (eds.) SAC 2003. LNCS, vol. 3006, pp. 26–41. Springer, Heidelberg (2004)

    Google Scholar 

  16. Galbraith, S.D., McKee, J.F., Valença, P.C.: Ordinary Abelian Varieties Having Small Embedding Degree. Finite Fields and Their Applications 13(4), 800–814 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  17. Gaudry, P.: An Algorithm for Solving the Discrete Log Problem on Hyperelliptic Curves. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 19–34. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  18. Granger, R., Hess, F., Oyono, R., Thériault, N., Vercauteren, F.: Ate Pairing on Hyperelliptic Curves. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 430–447. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  19. Haneda, M., Kawazoe, M., Takahashi, T.: Suitable Curves for Genus-4 HEC over Prime Fields: Point Counting Formulae for Hyperelliptic Curves of Type y 2 = x 2k + 1 + ax. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 539–550. Springer, Heidelberg (2005)

    Google Scholar 

  20. Hankerson, D., Menezes, A., Vanstone, S.: Guide to Elliptic Curve Cryptography. Springer, New York (2004)

    MATH  Google Scholar 

  21. Ó’hÉigeartaigh, C., Scott, M.: Pairing Calculation on Supersingular Genus 2 Curves. In: Biham, E., Youssef, A.M. (eds.) SAC 2006. LNCS, vol. 4356, pp. 302–316. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  22. Hess, F., Smart, N.P., Vercauteren, F.: The Eta Pairing Revisited. IEEE Transactions on Information Theory 52(10), 4595–4602 (2006)

    Article  MathSciNet  Google Scholar 

  23. Hitt, L.: Families of Genus 2 Curves with Small Embedding Degree, Cryptology ePrint Archive, Report 2007/001 (2007), http://eprint.iacr.org/2007/001

  24. 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)

    Chapter  Google Scholar 

  25. Kawazoe, M., Takahashi, T.: Pairing-friendly Hyperelliptic Curves of Type y 2 = x 5 + ax, Cryptology ePrint Archive, Report 2008/026 (2008) http://eprint.iacr.org/2008/026

  26. Kozaki, S., Matsuo, K., Shimbara, Y.: Skew-Frobenius Maps on Hyperelliptic Curves. In: The 2007 Symposium on Cryptography and Information Security - SCIS 2007, IEICE Japan, pp. 1D2–4 (January 2007)

    Google Scholar 

  27. Lee, E., Lee, H.-S., Lee, Y.: Eta Pairing Computation on General Divisors over Hyperelliptic Curves y 2 = x 7 − x ±1. In: Takagi, T., Okamoto, T., Okamoto, E., Okamoto, T. (eds.) Pairing 2007. LNCS, vol. 4575, pp. 349–366. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  28. Menezes, A., Okamoto, T., Vanstone, S.A.: Reducing Elliptic Curve Logarithms to a Finite Field. IEEE Transactions on Information Theory 39(5), 1639–1646 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  29. Miller, V.S.: Short Programs for Functions on Curves (unpublished manuscript, 1986), http://crypto.stanford.edu/miller/miller.pdf

  30. Miller, V.S.: The Weil Pairing and Its Efficient Calculation. Journal of Cryptology 17(4), 235–261 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  31. Park, Y.-H., Jeong, S., Lim, J.: Speeding Up Point Multiplication on Hyperelliptic Curves with Efficiently-Computable Endomorphisms. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 197–208. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  32. Rubin, K., Silverberg, A.: Supersingular Abelian Varieties in Cryptography. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 336–353. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  33. Sakai, R., Ohgishi, K., Kasahara, M.: Cryptosystems Based on Pairings. In: Proceedings of the 2000 Symposium on Cryptography and Information Security - SCIS 2002, Okinawa, Japan, pp. 26–28 (2000)

    Google Scholar 

  34. Scott, M.: Faster Pairings Using an Elliptic Curve with an Efficient Endomorphism. In: Maitra, S., Veni Madhavan, C.E., Venkatesan, R. (eds.) INDOCRYPT 2005. LNCS, vol. 3797, pp. 258–269. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  35. Scott, M., Barreto, P.L.S.M.: Compressed Pairings. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 140–156. Springer, Heidelberg (2004)

    Google Scholar 

  36. Silverman, J.H.: The Arithmetic of Elliptic Curves. Graduate Texts in Mathematics 106. Springer, Heidelberg (1986)

    MATH  Google Scholar 

  37. Solinas, J.: Generalized Mersenne Primes, Centre for Applied Cryptographic Research (CACR) Technical Reports, CORR 99-39, http://www.cacr.math.uwaterloo.ca/techreprots/1999/corr99-39.pdf

  38. Takashima, K.: Scaling Security of Elliptic Curves with Fast Pairing Using Efficient Endomorphism. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Science E90-A(1), 152–159 (2007)

    Article  Google Scholar 

  39. Zhao, C., Zhang, F., Huang, J.: Speeding Up the Bilinear Pairings Computation on Curves with Automorphisms, Cryptology ePrint Archive, Report 2006/474 (2006), http://eprint.iacr.org/2006/474

Download references

Author information

Authors and Affiliations

  1. Department of Electrical and Computer Engineering, University of Waterloo, Waterloo, Ontario, N2L 3G1, Canada

    Xinxin Fan & Guang Gong

  2. Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, N2L 3G1, Canada

    David Jao

Authors
  1. Xinxin Fan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Guang Gong
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. David Jao
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Steven D. Galbraith Kenneth G. Paterson

Rights and permissions

Reprints and permissions

Copyright information

© 2008 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Fan, X., Gong, G., Jao, D. (2008). Speeding Up Pairing Computations on Genus 2 Hyperelliptic Curves with Efficiently Computable Automorphisms. 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_17

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-85538-5_17

  • 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)

Publish with us

Policies and ethics

Search

Navigation