Abstract
In this paper we deal with 3-way split formulas for binary field multiplication with five recursive multiplications of smaller sizes. We first recall the formula proposed by Bernstein at CRYPTO 2009 and derive the complexity of a parallel multiplier based on this formula. We then propose a new set of 3-way split formulas with five recursive multiplications based on field extension. We evaluate their complexities and provide a comparison.
Chapter PDF
Similar content being viewed by others
Keywords
- Critical Path
- Polynomial Multiplication
- Elliptic Curve Cryptography
- Inductive Relation
- Arithmetic Complexity
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Bernstein, D.J.: Batch Binary Edwards. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 317–336. Springer, Heidelberg (2009)
Cenk, M., Koç, Ç., Özbudak, F.: Polynomial Multiplication over Finite Fields Using Field Extensions and Interpolation. In: 19th IEEE Symposium on Computer Arithmetic, ARITH 2009, pp. 84–91 (2009)
ElGamal, T.: A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Transactions on Information Theory 31(4), 469–472 (1985)
Fan, H., Hasan, M.A.: A New Approach to Subquadratic Space Complexity Parallel Multipliers for Extended Binary Fields. IEEE Transactions on Computers 56(2), 224–233 (2007)
Fan, H., Sun, J., Gu, M., Lam, K.-Y.: Overlap-free Karatsuba-Ofman Polynomial Multiplication Algorithm (May 2007)
Karatsuba, A.A.: The Complexity of Computations. In: Proceedings of the Steklov Institute of Mathematics, vol. 211, pp. 169–183 (1995)
Koblitz, N.: Elliptic curve cryptosystems. Mathematics of Computation 48, 203–209 (1987)
McGrew, D.A., Viega, J.: The Security and Performance of the Galois/Counter Mode (GCM) of Operation. In: Canteaut, A., Viswanathan, K. (eds.) INDOCRYPT 2004. LNCS, vol. 3348, pp. 343–355. Springer, Heidelberg (2004)
Miller, V.: Use of Elliptic Curves in Cryptography. In: Williams, H.C. (ed.) CRYPTO 1985. LNCS, vol. 218, pp. 417–426. Springer, Heidelberg (1986)
Sunar, B.: A generalized method for constructing subquadratic complexity GF(2k) multipliers. IEEE Transactions on Computers 53, 1097–1105 (2004)
Toom, A.L.: The Complexity of a Scheme of Functional Elements Realizing the Multiplication of Integers. Soviet Mathematics 3, 714–716 (1963)
Winograd, S.: Arithmetic Complexity of Computations. Society For Industrial & Applied Mathematics, U.S. (1980)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cenk, M., Negre, C., Hasan, M.A. (2012). Improved Three-Way Split Formulas for Binary Polynomial Multiplication. In: Miri, A., Vaudenay, S. (eds) Selected Areas in Cryptography. SAC 2011. Lecture Notes in Computer Science, vol 7118. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-28496-0_23
Download citation
DOI: https://doi.org/10.1007/978-3-642-28496-0_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-28495-3
Online ISBN: 978-3-642-28496-0
eBook Packages: Computer ScienceComputer Science (R0)