Fast multiplication of binary polynomials with the forthcoming vectorized VPCLMULQDQ instruction

PI: Nir Drucker, Shay Gueron, Vlad Krasnov


Polynomial multiplication over binary fields F2n is a common primitive, used for example by current cryptosystems such as AES-GCM (with n = 128). It also turns out to be a primitive for other cryptosystems, that are being designed for the Post
Quantum era, with values n 128. Examples from the recent submissions to the NIST Post-Quantum Cryptography project, are BIKE, LEDAKem, and GeMSS, where the performance of the polynomial multiplications, is significant. Therefore, efficient
polynomial multiplication over F2n , with large n, is a significant emerging optimization target.
Anticipating future applications, Intel has recently announced that its future architecture (codename ”Ice Lake”) will introduce a new vectorized way to use the current VPCLMULQDQ instruction. In this paper, we demonstrate how to use this instruction
for accelerating polynomial multiplication. Our analysis shows a prediction for at least 2x speedup for multiplications with polynomials of degree 512 or more.

 ... Read More in the PDF FIle.