Abstract
Efficient computation of the Tate pairing is an important part of pairing-based cryptography. Recently with the introduction of the Duursma-Lee method special attention has been given to the fields of characteristic 3. Especially multiplication in \(\mathbb{F}_{3^{6m}}\), where m is prime, is an important operation in the above method. In this paper we propose a new method to reduce the number of \(\mathbb{F}_{3^{m}}\)-multiplications for multiplication in \(\mathbb{F}_{3^{6m}}\) from 18 in recent implementations to 15. The method is based on the fast Fourier transform and its explicit formulas are given. The execution times of our software implementations for \(\mathbb{F}_{3^{6m}}\) show the efficiency of our results.
Chapter PDF
Similar content being viewed by others
References
Knuth, D.E.: The Art of Computer Programming. In: Seminumerical Algorithms, 3rd edn., vol. 2, Addison-Wesley, Reading MA (1998), First edition (1969)
von zur Gathen, J., Gerhard, J.: Modern Computer Algebra, 2nd edn. Cambridge University Press, Cambridge (2003), First edition (1999)
Department, U.S.: of Commerce / National Institute of Standards and Technology: Digital Signature Standard (DSS), Federal Information Processings Standards Publication 186-2 (January 2000)
Bailey, D.V., 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)
Avanzi, R.M., Mihăilescu, P.: Generic Efficient Arithmetic Algorithms for PAFFs (Processor Adequate Finite Fields) and Related Algebraic Structures (Extended Abstract. In: Matsui, M., Zuccherato, R.J. (eds.) SAC 2003. LNCS, vol. 3006, pp. 320–334. Springer, Heidelberg (2004)
Duursma, I., Lee, H.: Tate-Pairing Implementations for Tripartite Key Agreement. In: Laih, C.-S. (ed.) ASIACRYPT 2003. LNCS, vol. 2894, pp. 111–123. Springer, Heidelberg (2003)
Kerins, T., Marnane, W.P., Popovici, E.M., Barreto, P.S.L.M.: Efficient Hardware for the Tate Pairing Calculation in Characteristic Three. In: Rao, J.R., Sunar, B. (eds.) CHES 2005. LNCS, vol. 3659, pp. 412–426. Springer, Heidelberg (2005)
Karatsuba, A., Ofman, Y.: Multiplication of Multidigit Numbers on Automata. Soviet Physics–Doklady 7(7), 595–596 (1963) Translated from Doklady Akademii Nauk SSSR 145(2), 293–294 (July 1962)
Paar, C.: Efficient VLSI Architectures for Bit-Parallel Computation in Galois Fields. PhD thesis, Institute for Experimental Mathematics, University of Essen, Essen, Germany (June 1994)
Lempel, A., Winograd, S.: A New Approach to Error-Correcting Codes. IEEE Transactions on Information Theory IT-23, 503–508 (1977)
Winograd, S.: Arithmetic Complexity of Computations, vol. 33. SIAM, Philadelphia (1980)
Bürgisser, P., Clausen, M., Shokrollahi, M.A.: Algebraic Complexity Theory. Grundlehren der mathematischen Wissenschaften, vol. 315. Springer, Heidelberg (1997)
Bajard, J.C., Imbert, L., Negre, C.: Arithmetic Operations in Finite Fields of Medium Prime Characteristic Using the Lagrange Representation. IEEE Transactions on Computers 55(9), 1167–1177 (2006)
Blahut, R.E.: Fast Algorithms for Digital Signal Processing. Addison-Wesley, Reading MA (1985)
Cooley, J.W., Tukey, J.W.: An Algorithm for the Machine Computation of the Complex Fourier Series. Mathematics of Computation 19, 297–331 (1965)
Loan, C.V.: Computational Frameworks for the Fast Fourier Transform. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (1992)
von zur Gathen, J., Shokrollahi, J.: Efficient FPGA-based Karatsuba Multipliers for Polynomials over \(\mathbb{F}_{2}\). In: Preneel, B., Tavares, S. (eds.) SAC 2005. LNCS, vol. 3897, pp. 359–369. Springer, Heidelberg (2006)
Montgomery, P.L.: Five, Six, and Seven-Term Karatsuba-Like Formulae. IEEE Transactions on Computers 54(3), 362–369 (2005)
Shoup, V.: NTL: A library for doing number theory, http://www.shoup.net/ntl
Duursma, I., Lee, H.S.: Tate Pairing Implementation for Hyperelliptic Curves \(y\sp 2=x\sp p-x+d\). In: Laih, C.-S. (ed.) ASIACRYPT 2003. LNCS, vol. 2894, pp. 111–123. Springer, Heidelberg (2003)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gorla, E., Puttmann, C., Shokrollahi, J. (2007). Explicit Formulas for Efficient Multiplication in \(\mathbb{F}_{3^{6m}}\) . In: Adams, C., Miri, A., Wiener, M. (eds) Selected Areas in Cryptography. SAC 2007. Lecture Notes in Computer Science, vol 4876. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-77360-3_12
Download citation
DOI: https://doi.org/10.1007/978-3-540-77360-3_12
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-77359-7
Online ISBN: 978-3-540-77360-3
eBook Packages: Computer ScienceComputer Science (R0)