Polynomial multiplication over binary finite fields: new upper bounds

When implementing a cryptographic algorithm, efficient operations have high relevance both in hardware and in software. Since a number of operations can be performed via polynomial multiplication, the arithmetic of polynomials over finite fields plays a key role in real-life implementations—e.g., accelerating cryptographic and cryptanalytic software (pre- and post-quantum) (Chou in Accelerating pre-and post-quantum cryptography. Ph.D. thesis, Technische Universiteit Eindhoven, 2016). One of the most interesting papers that addressed the problem has been published in 2009. In Bernstein (in: Halevi (ed) Advances in Cryptology—CRYPTO 2009: 29th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 16–20, 2009. Proceedings, pp 317–336. Springer Berlin Heidelberg, Berlin, Heidelberg, 2009), Bernstein suggests to split polynomials into parts and presents a new recursive multiplication technique which is faster than those commonly used. In order to further reduce the number of bit operations (Bernstein in High-speed cryptography in characteristic 2: minimum number of bit operations for multiplication, 2009. http://​binary.​cr.​yp.​to/​m.​html) required to multiply n-bit polynomials, researchers adopt different approaches. In CMT: Circuit minimization work. http://​www.​cs.​yale.​edu/​homes/​peralta/​CircuitStuff/​CMT.​html a greedy heuristic has been applied to linear straight-line sequences listed in Bernstein (High-speed cryptography in characteristic 2: minimum number of bit operations for multiplication, 2009. http://​binary.​cr.​yp.​to/​m.​html). In 2013, D’angella et al. (Applied computing conference, 2013. ACC’13. WEAS. pp. 31–37. WEAS, 2013) skip some redundant operations of the multiplication algorithms described in Bernstein (in: Halevi (ed) Advances in Cryptology—CRYPTO 2009: 29th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 16–20, 2009. Proceedings, pp 317–336. Springer Berlin Heidelberg, Berlin, Heidelberg, 2009). In 2015, Cenk et al. (J Cryptogr Eng 5(4):289–303, 2015) suggest new multiplication algorithms. In this paper, (a) we present a “k-1”-level recursion algorithm that can be used to reduce the effective number of bit operations required to multiply n-bit polynomials, and (b) we use algebraic extensions of \(\mathbb {F}_2\) combined with Lagrange interpolation to improve the asymptotic complexity.