Back to Search Start Over

Polynomial multiplication over binary finite fields: new upper bounds

Authors :
De Piccoli, Alessandro
Visconti, Andrea
Rizzo, Ottavio
Source :
Journal of Cryptographic Engineering; 20240101, Issue: Preprints p1-14, 14p
Publication Year :
2024

Abstract

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.htmla 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 algorithmthat 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$$F2combined with Lagrange interpolation to improve the asymptotic complexity.

Details

Language :
English
ISSN :
21908508 and 21908516
Issue :
Preprints
Database :
Supplemental Index
Journal :
Journal of Cryptographic Engineering
Publication Type :
Periodical
Accession number :
ejs49829814
Full Text :
https://doi.org/10.1007/s13389-019-00210-w