×

Improved three-way split formulas for binary polynomial multiplication. (English) Zbl 1284.65199

Miri, Ali (ed.) et al., Selected areas in cryptography. 18th international workshop, SAC 2011, Toronto, ON, Canada, August 11–12, 2011. Revised selected papers. Berlin: Springer (ISBN 978-3-642-28495-3/pbk). Lecture Notes in Computer Science 7118, 384-398 (2012).
Summary: 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 D. J. Bernstein at CRYPTO 2009 [Lect. Notes Comput. Sci. 5677, 317–336 (2009; Zbl 1248.94052)] 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.
For the entire collection see [Zbl 1234.94005].

MSC:

65Y20 Complexity and performance of numerical algorithms
11Y16 Number-theoretic algorithms; complexity
11T99 Finite fields and commutative rings (number-theoretic aspects)
94A60 Cryptography

Citations:

Zbl 1248.94052
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bernstein, D.J.: Batch Binary Edwards. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 317–336. Springer, Heidelberg (2009) · Zbl 1248.94052 · doi:10.1007/978-3-642-03356-8_19
[2] 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) · doi:10.1109/ARITH.2009.11
[3] ElGamal, T.: A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Transactions on Information Theory 31(4), 469–472 (1985) · Zbl 0571.94014 · doi:10.1109/TIT.1985.1057074
[4] 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) · doi:10.1109/TC.2007.19
[5] Fan, H., Sun, J., Gu, M., Lam, K.-Y.: Overlap-free Karatsuba-Ofman Polynomial Multiplication Algorithm (May 2007)
[6] Karatsuba, A.A.: The Complexity of Computations. In: Proceedings of the Steklov Institute of Mathematics, vol. 211, pp. 169–183 (1995) · Zbl 0872.68068
[7] Koblitz, N.: Elliptic curve cryptosystems. Mathematics of Computation 48, 203–209 (1987) · Zbl 0622.94015 · doi:10.1090/S0025-5718-1987-0866109-5
[8] 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) · Zbl 1113.94315 · doi:10.1007/978-3-540-30556-9_27
[9] Miller, V.: Use of Elliptic Curves in Cryptography. In: Williams, H.C. (ed.) CRYPTO 1985. LNCS, vol. 218, pp. 417–426. Springer, Heidelberg (1986) · doi:10.1007/3-540-39799-X_31
[10] Sunar, B.: A generalized method for constructing subquadratic complexity GF(2 k ) multipliers. IEEE Transactions on Computers 53, 1097–1105 (2004) · Zbl 1231.68045 · doi:10.1109/TC.2004.52
[11] Toom, A.L.: The Complexity of a Scheme of Functional Elements Realizing the Multiplication of Integers. Soviet Mathematics 3, 714–716 (1963) · Zbl 0203.15604
[12] Winograd, S.: Arithmetic Complexity of Computations. Society For Industrial & Applied Mathematics, U.S. (1980) · Zbl 0441.68045 · doi:10.1137/1.9781611970364
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.