SpringerLink
Log in

Implementing Pairings at the 192-Bit Security Level

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

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

Included in the following conference series:

Abstract

We implement asymmetric pairings derived from Kachisa-Schaefer-Scott (KSS), Barreto-Naehrig (BN), and Barreto-Lynn-Scott (BLS) elliptic curves at the 192-bit security level. Somewhat surprisingly, we find pairings derived from BLS curves with embedding degree 12 to be the fastest for our serial as well as our parallel implementations. Our serial implementations provide a factor-3 speedup over the previous state-of-the-art, demonstrating that pairing computation at the 192-bit security level is not as expensive as previously thought. We also present a general framework for deriving a Weil-type pairing that is well-suited for computing a single pairing on a multi-processor machine.

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
EUR 32.99 /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
EUR 29.95
Price includes VAT (Thailand)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
EUR 42.79
Price includes VAT (Thailand)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
EUR 49.99
Price excludes VAT (Thailand)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** 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. Aranha, D.F., Gouvêa, C.P.L.: RELIC is an Efficient LIbrary for Cryptography, http://code.google.com/p/relic-toolkit/

  2. Aranha, D.F., Karabina, K., Longa, P., Gebotys, C.H., López, J.: Faster Explicit Formulas for Computing Pairings over Ordinary Curves. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 48–68. Springer, Heidelberg (2011)

    Chapter  Google Scholar 

  3. Aranha, D.F., Knapp, E., Menezes, A., Rodríguez-Henríquez, F.: Parallelizing the Weil and Tate Pairings. In: Chen, L. (ed.) Cryptography and Coding 2011. LNCS, vol. 7089, pp. 275–295. Springer, Heidelberg (2011)

    Chapter  Google Scholar 

  4. Aranha, D.F., López, J., Hankerson, D.: High-Speed Parallel Software Implementation of the η T Pairing. In: Pieprzyk, J. (ed.) CT-RSA 2010. LNCS, vol. 5985, pp. 89–105. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

  5. 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–368. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  6. Barreto, P.S.L.M., Lynn, B., Scott, M.: Constructing Elliptic Curves with Prescribed Embedding Degrees. In: Cimato, S., Galdi, C., Persiano, G. (eds.) SCN 2002. LNCS, vol. 2576, pp. 257–267. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

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

  8. Brezing, F., Weng, A.: Elliptic curves suitable for pairing based cryptography. Designs, Codes and Cryptography 37, 133–141 (2006)

    Article  MathSciNet  Google Scholar 

  9. Costello, C., Lauter, K., Naehrig, M.: Attractive Subfamilies of BLS Curves for Implementing High-Security Pairings. In: Bernstein, D.J., Chatterjee, S. (eds.) INDOCRYPT 2011. LNCS, vol. 7107, pp. 320–342. Springer, Heidelberg (2011)

    Chapter  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  11. Fuentes-Castañeda, L., Knapp, E., Rodríguez-Henríquez, F.: Faster Hashing to \({\mathbb G}_2\). In: Miri, A., Vaudenay, S. (eds.) SAC 2011. LNCS, vol. 7118, pp. 412–430. Springer, Heidelberg (2012)

    Chapter  Google Scholar 

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

    Chapter  Google Scholar 

  13. Galbraith, S., Paterson, K., Smart, N.: Pairings for cryptographers. Discrete Applied Mathematics 156, 3113–3121 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  14. 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 

  15. Hess, F.: Pairing Lattices. In: Galbraith, S.D., Paterson, K.G. (eds.) Pairing 2008. LNCS, vol. 5209, pp. 18–38. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  16. Hess, F., Smart, N., Vercauteren, F.: The eta pairing revisited. IEEE Transactions on Information Theory 52, 4595–4602 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  17. 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 

  18. Karabina, K.: Squaring in cyclotomic subgroups. Mathematics of Computation (to appear)

    Google Scholar 

  19. Koblitz, N., Menezes, A.: Pairing-Based Cryptography at High Security Levels. In: Smart, N.P. (ed.) Cryptography and Coding 2005. LNCS, vol. 3796, pp. 13–36. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  20. Lauter, K., Montgomery, P.L., Naehrig, M.: An Analysis of Affine Coordinates for Pairing Computation. In: Joye, M., Miyaji, A., Otsuka, A. (eds.) Pairing 2010. LNCS, vol. 6487, pp. 1–20. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

  21. Lenstra, A., Lenstra, H., Lovasz, L.: Factoring polynomials with rational coefficients. Mathematische Annalen 261, 515–534 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  22. Miller, V.: The Weil pairing, and its efficient calculation. Journal of Cryptology 17, 235–261 (2004)

    Article  MATH  Google Scholar 

  23. NSA Suite B Cryptography, www.nsa.gov/ia/programs/suiteb_cryptography/

  24. Pereira, G., Simplício Jr., M., Naehrig, M., Barreto, P.: A family of implementation-friendly BN elliptic curves. Journal of Systems and Software 84, 1319–1326 (2011)

    Article  Google Scholar 

  25. Pollard, J.: Monte Carlo methods for index computation mod p. Mathematics of Computation 32, 918–924 (1978)

    MathSciNet  MATH  Google Scholar 

  26. Schirokauer, O.: Discrete logarithms and local units. Philosophical Transactions of the Royal Society London A 345, 409–423 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  27. Scott, M.: Computing the Tate Pairing. In: Menezes, A. (ed.) CT-RSA 2005. LNCS, vol. 3376, pp. 293–304. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  28. Scott, M.: On the Efficient Implementation of Pairing-Based Protocols. In: Chen, L. (ed.) Cryptography and Coding 2011. LNCS, vol. 7089, pp. 296–308. Springer, Heidelberg (2011)

    Chapter  Google Scholar 

  29. Scott, M., Benger, N., Charlemagne, M., Dominguez Perez, L.J., Kachisa, E.J.: On the Final Exponentiation for Calculating Pairings on Ordinary Elliptic Curves. In: Shacham, H., Waters, B. (eds.) Pairing 2009. LNCS, vol. 5671, pp. 78–88. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  30. Vercauteren, F.: Optimal pairings. IEEE Transactions on Information Theory 56, 455–461 (2010)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Brasília, Brazil

    Diego F. Aranha

  2. Computer Science Department, CINVESTAV-IPN, Mexico

    Laura Fuentes-Castañeda & Francisco Rodríguez-Henríquez

  3. Department of Combinatorics & Optimization, University of Waterloo, Canada

    Edward Knapp & Alfred Menezes

Authors
  1. Diego F. Aranha
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Laura Fuentes-Castañeda
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Edward Knapp
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Alfred Menezes
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Francisco Rodríguez-Henríquez
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Départment d’Informatique, École Normale Supérieure and CNRS, 45 rue d’Ulm, 75005, Paris, France

    Michel Abdalla

  2. Department of Mathematics and Computer Science, Technische Universiteit Eindhoven, P.O. Box 513, 5600 MB, Eindhoven, The Netherlands

    Tanja Lange

Rights and permissions

Reprints and permissions

Copyright information

© 2013 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Aranha, D.F., Fuentes-Castañeda, L., Knapp, E., Menezes, A., Rodríguez-Henríquez, F. (2013). Implementing Pairings at the 192-Bit Security Level. In: Abdalla, M., Lange, T. (eds) Pairing-Based Cryptography – Pairing 2012. Pairing 2012. Lecture Notes in Computer Science, vol 7708. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-36334-4_11

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-36334-4_11

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-36333-7

  • Online ISBN: 978-3-642-36334-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation