Abstract
A cryptographic pairing evaluates as an element of a finite extension field, and the evaluation itself involves a considerable amount of extension field arithmetic. It is recognised that organising the extension field as a “tower” of subfield extensions has many advantages. Here we consider criteria that apply when choosing the best towering construction, and the associated choice of irreducible polynomials for the implementation of pairing-based cryptosystems. We introduce a method for automatically constructing efficient towers for more classes of finite fields than previous methods, some of which allow faster arithmetic.
We also show that for some families of pairing-friendly elliptic curves defined over \(\mathbb{F}_{p}\) there are a large number of instances for which an efficient tower extension \(\mathbb{F}_{p^k}\) is given immediately if the parameter defining the prime characteristic of the field satisfies a few easily checked equivalences.
Research supported by the Claude Shannon Institute, Science Foundation Ireland Grant 06/MI/006.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
IEEE P1363.3: Standard for identity-based cryptographic techniques using pairings. Draft 3: Section 5.3.2, http://grouper.ieee.org/groups/1363/IBC/index.html
Arène, C., Lange, T., Naehrig, M., Ritzenthaler, C.: Faster computation of the Tate pairing. Cryptology ePrint Archive, Report 2009/155 (2009), http://eprint.iacr.org/
Bailey, D., Paar, C.: Optimal extension fields for fast arithmetic in public-key algorithms. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 472–485. Springer, Heidelberg (1998)
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)
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. 263–273. Springer, Heidelberg (2003)
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)
Cohen, H., Frey, G. (eds.): Handbook of elliptic and hyperelliptic curve cryptography. CRC Press, Boca Raton (2005)
Devegili, A.J., Scott, M., Dahab, R.: Implementing cryptographic pairings over Barreto-Naehrig curves. In: Takagi, T., Okamoto, T., Okamoto, E., Okamoto, T. (eds.) Pairing 2007. LNCS, vol. 4575, pp. 197–207. Springer, Heidelberg (2007)
Dominguez Perez, L.J., Scott, M.: Automatic generation of optimised cryptographic pairing functions. In: SPEED-CC Workshop Record– Software Performance Enhancement for Encryption and Decryption and Cryptographic Compilers, vol. 1, pp. 55–71 (2009)
Freeman, D., Scott, M., Teske, E.: A taxonomy of pairing-friendly elliptic curves. Journal of Cryptology 23 (2010)
Galbraith, S., Lin, X., Scott, M.: Endomorphisms for faster elliptic curve cryptography on a large class of curves. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 518–535. Springer, Heidelberg (2010)
Granger, R., Page, D., Stam, M.: On small characteristic algebraic tori in pairing based cryptography. LMS Journal of Computation and Mathematics 9, 64–85 (2006)
Hess, F., Smart, N., Vercauteren, F.: The eta pairing revisited. IEEE Trans. Information Theory 52, 4595–4602 (2006)
Kachisa, E., Schaefer, E., 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)
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)
Lee, E., Lee, H., Park, C.: Efficient and generalized pairing computation on abelian varieties. IEEE Trans. Information Theory 55, 1793–1803 (2009)
Lemmermeyer, F.: Reciprocity Laws: From Euler to Eisenstein. Springer Monographs in Mathematics. Springer, Heidelberg (2000)
Lidl, R., Niederreiter, H.: Finite Fields, 2nd edn. Encyclopedia of Mathematics and its Applications, vol. 20. Cambridge University Press, Cambridge (1997)
Baktır, S., Sunar, B.: Optimal tower fields. IEEE Transactions on Computers 53(10), 1231–1243 (2004)
Scott, M.: A note on twists for pairing friendly curves, ftp://ftp.computing.dcu.ie/pub/resources/crypto/twists.pdf
Scott, M., Barreto, P.: Compressed pairings. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 140–156. Springer, Heidelberg (2004), http://eprint.iacr.org/2004/032/
Shirase, M.: Universally constructing 12-th degree extension field for ate pairing. Cryptology ePrint Archive, Report 2009/623 (2009), http://eprint.iacr.org/
Silverman, J.H.: The Arithmetic of Elliptic Curves. Graduate Texts in Mathematics, vol. 106. Springer, New York (1986)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Benger, N., Scott, M. (2010). Constructing Tower Extensions of Finite Fields for Implementation of Pairing-Based Cryptography. In: Hasan, M.A., Helleseth, T. (eds) Arithmetic of Finite Fields. WAIFI 2010. Lecture Notes in Computer Science, vol 6087. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-13797-6_13
Download citation
DOI: https://doi.org/10.1007/978-3-642-13797-6_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-13796-9
Online ISBN: 978-3-642-13797-6
eBook Packages: Computer ScienceComputer Science (R0)