Constructing Pairing-Friendly Genus 2 Curves with Split Jacobian | SpringerLink
Skip to main content
Springer Nature Link
Log in

Constructing Pairing-Friendly Genus 2 Curves with Split Jacobian

  • Conference paper
Progress in Cryptology - INDOCRYPT 2012 (INDOCRYPT 2012)

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

Included in the following conference series:

Abstract

Using genus 2 curves with simple but not absolutely simple Jacobians one can obtain pairing-based cryptosystems more efficient than for a generic genus 2 curve. We describe a new framework to construct pairing-friendly abelian surfaces, which are simple but not absolutely simple. The main contribution is the generalization of the notion of complete, complete with variable discriminant, and sparse families of elliptic curves introduced by Freeman, Scott and Teske [13]. We give algorithms to construct families of abelian surfaces of each type, which generalize the Brezing-Weng method. To realize these abelian surfaces as Jacobians we use curves of the form y 2 = x 5 + ax 3 + bx or y 2 = x 6 + ax 3 + b, and apply the method of Freeman and Satoh [12]. As applications we give variable-discriminant families with best ρ-values. We also give some families with record ρ-value.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

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. Barreto, P.S.L.M., Naehrig, M.: Pairing-Friendly Elliptic Curves of Prime Order. In: Preneel, B., Tavares, S. (eds.) SAC 2005. LNCS, vol. 3897, pp. 319–331. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  2. 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); full version: SIAM J. Comput. 32(3), 586–615 (2003)

    Chapter  Google Scholar 

  3. Boneh, D., Lynn, B., Shacham, H.: Short Signatures from the Weil Pairing. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 514–532. Springer, Heidelberg (2001); full version: J. Cryptol. 17, 297–319 (2004)

    Chapter  Google Scholar 

  4. Brezing, F., Weng, A.: Elliptic curves suitable for pairing based cryptography. Des. Codes Cryptogr. 37, 133–141 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  5. Cardona, G., Quer, J.: Field of moduli and field of definition for curves of genus 2, http://arxiv.org/abs/math/0207015

  6. Cardona, G., Quer, J.: Curves of genus 2 with group of automorphisms isomorphic to D 8 or D 12. Trans. Amer. Math. Soc. 359, 2831–2849 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  7. Dryło, R.: A New Method for Constructing Pairing-Friendly Abelian Surfaces. In: Joye, M., Miyaji, A., Otsuka, A. (eds.) Pairing 2010. LNCS, vol. 6487, pp. 298–311. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

  8. Dryło, R.: On Constructing Families of Pairing-Friendly Elliptic Curves with Variable Discriminant. In: Bernstein, D.J., Chatterjee, S. (eds.) INDOCRYPT 2011. LNCS, vol. 7107, pp. 310–319. Springer, Heidelberg (2011)

    Chapter  Google Scholar 

  9. Freeman, D.: Constructing Pairing-Friendly Elliptic Curves with Embedding Degree 10. In: Hess, F., Pauli, S., Pohst, M. (eds.) ANTS 2006. LNCS, vol. 4076, pp. 452–465. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  10. Freeman, D.: Constructing Pairing-Friendly Genus 2 Curves 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 

  11. Freeman, D.: A Generalized Brezing-Weng Algorithm for Constructing Pairing-Friendly Ordinary Abelian Varieties. In: Galbraith, S.D., Paterson, K.G. (eds.) Pairing 2008. LNCS, vol. 5209, pp. 146–163. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  12. Freeman, D., Satoh, T.: Constructing pairing-friendly hyperelliptic curves using Weil restriction. J. Number Theory 131, 959–983 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  13. Freeman, D., Scott, M., Teske, E.: A taxonomy of pairing-friendly elliptic curves. J. Cryptol. 23, 224–280 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  14. Freeman, D., Stevenhagen, P., Streng, M.: Abelian Varieties with Prescribed Embedding Degree. In: van der Poorten, A.J., Stein, A. (eds.) ANTS-VIII 2008. LNCS, vol. 5011, pp. 60–73. Springer, Heidelberg (2008)

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

    Chapter  Google Scholar 

  16. Galbraith, S.D.: Supersingular Curves in Cryptography. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 495–513. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  17. Galbraith, S., McKee, J., Valença, P.: Ordinary abelian varieties having small embedding degree. Finite Fields Appl. 13, 800–814 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  18. Gaudry, P., Schost, É.: On the Invariants of the Quotients of the Jacobian of a Curve of Genus 2. In: Bozta, S., Sphparlinski, I. (eds.) AAECC- 14. LNCS, vol. 2227, pp. 373–386. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  19. Guillevic, A., Vergnaud, D.: Genus 2 Hyperelliptic Curve Families with Explicit Jacobian Order Evaluation and Pairing-Friendly Constructions. To appear in Pairing-Based Cryptography – Pairing 2012. LNCS (2012)

    Google Scholar 

  20. Howe, E., Zhu, H.: On the existence of absolutely simple abelian varieties of a given dimension over an arbitrary field. J. Number Theory 92, 139–163 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  21. Igusa, J.: Arithmetic Variety of Moduli for Genus Two. Ann. Math. 72, 612–649 (1960)

    Article  MathSciNet  MATH  Google Scholar 

  22. Joux, A.: A One Round Protocol for Tripartite Diffie–Hellman. In: Bosma, W. (ed.) ANTS-IV. LNCS, vol. 1838, pp. 385–393. Springer, Heidelberg (2000); full version: J. Cryptol. 17, 263–276 (2004)

    Chapter  Google Scholar 

  23. Kachisa, E.J.: Generating More Kawazoe-Takahashi Genus 2 Pairing-Friendly Hyperelliptic Curves. In: Joye, M., Miyaji, A., Otsuka, A. (eds.) Pairing 2010. LNCS, vol. 6487, pp. 312–326. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

  24. Kachisa, E.J., Schaefer, E.F., Scott, M.: Constructing Brezing-Weng Pairing-Friendly Elliptic Curves Using Elements in the Cyclotomic Field. In: Galbraith, S.D., Paterson, K.G. (eds.) Pairing 2008. LNCS, vol. 5209, pp. 126–135. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  25. Kawazoe, M., Takahashi, T.: Pairing-Friendly Hyperelliptic Curves with Ordinary Jacobians of Type y 2 = x 5 + ax. In: Galbraith, S.D., Paterson, K.G. (eds.) Pairing 2008. LNCS, vol. 5209, pp. 164–177. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  26. Lang, S.: Algebraic Number Theory. Graduate Texts in Mathematics, vol. 110. Springer, Berlin (1994)

    MATH  Google Scholar 

  27. Miyaji, A., Nakabayashi, M., Takano, S.: New explicit conditions of elliptic curve traces for FR-reduction. IEICE Trans. Fundam. E84-A(5), 1234–1243 (2001)

    Google Scholar 

  28. Milne, J.S.: Abelian varieties. In: Cornell, G., Silverman, J. (eds.) Arithmetic Geometry, pp. 103–150. Springer, New York (1986)

    Chapter  Google Scholar 

  29. Murphy, A., Fitzpatrick, N.: Elliptic curves for pairing applications, http://eprint.iacr.org/2005/302

  30. Maisner, D., Nart, E.: Abelian surfaces over finite fields as Jacobians. Experimental Mathematics 11, 321–337 (2002); With an appendix by Everett W. Howe

    Article  MathSciNet  MATH  Google Scholar 

  31. Menezes, A., Okamoto, T., Vanstone, S.: Reducing elliptic curve logarithms to logarithms in a finite field. IEEE Trans. Inf. Theory 39, 1639–1646 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  32. Mestre, J.F.: Construction de courbes de genre 2 à partir de leurs modules. In: Effective Methods in Algebraic Geometry (Castiglioncello, 1990), pp. 313–334. Birkhäuser, Boston (1991)

    Chapter  Google Scholar 

  33. Rubin, K., Silverberg, A.: Using abelian varieties to improve pairing-based cryptography. J. Cryptol. 22, 330–364 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  34. Scott, M., Barreto, P.S.L.M.: Generating more MNT elliptic curves. Des. Codes Cryptogr. 38, 209–217 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  35. Shaska, T., Voelklein, H.: Elliptic subfields and automorphisms of genus 2 function fields. In: Algebra, Arithmetic and Geometry with Applications (West Lafayette, IN, 2000), 703–723. Springer, Heidelberg (2004)

    Google Scholar 

  36. Silverman, J.: The Arithmetic of Elliptic Curves. Springer, Berlin (1986)

    MATH  Google Scholar 

  37. Sakai, R., Ohgishi, K., Kasahara, M.: Cryptosystems based on pairings. In: 2000 Symposium on Cryptography and Information Security – SCIS 2000, Okinawa, Japan (2000)

    Google Scholar 

  38. Sutherland, A.: Computing Hilbert class polynomials with the Chinese remainder theorem. Math. Comp. 80, 501–538 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  39. Tate, J.: Classes d’isogénie des variétés abéliennes sur un corps fini (d’aprés T. Honda.) Séminarie Bourbaki 1968/69, exposé 352. Lect. Notes in Math, vol. 179, pp. 95–110. Springer (1971)

    Google Scholar 

  40. Tate, J.: Endomorphisms of abelian varieties over finite fields. Inventiones Mathematicae 2 (1966)

    Google Scholar 

  41. Waterhouse, W.C.: Abelian varieties over finite fields. Ann. Sci. École Norm. Sup. 2, 521–560 (1969)

    MathSciNet  MATH  Google Scholar 

  42. Waterhouse, W.C., Milne, J.S.: Abelian varieties over finite fields. Proc. Symp. Pure Math. 20, 53–64 (1971)

    MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Mathematics, Polish Academy of Sciences, ul. Śniadeckich 8, 00-950, Warszawa, Poland

    Robert Dryło

  2. Warsaw School of Economics, al. Niepodległości 162, 02-554, Warszawa, Poland

    Robert Dryło

Authors
  1. Robert Dryło
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Mathematics, University of Auckland, Private Bag 92019, 1142, Auckland, New Zealand

    Steven Galbraith

  2. Indian Statistical Institute, Applied Statistics Unit, 203 B.T. Road, 700108, Kolkata, West Bengal, India

    Mridul Nandi

Rights and permissions

Reprints and permissions

Copyright information

© 2012 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Dryło, R. (2012). Constructing Pairing-Friendly Genus 2 Curves with Split Jacobian. In: Galbraith, S., Nandi, M. (eds) Progress in Cryptology - INDOCRYPT 2012. INDOCRYPT 2012. Lecture Notes in Computer Science, vol 7668. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-34931-7_25

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-34931-7_25

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-34930-0

  • Online ISBN: 978-3-642-34931-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation