Fast multiplication of binary polynomials with the forthcoming vectorized VPCLMULQDQ instruction
Fast multiplication of binary polynomials with the forthcoming vectorized VPCLMULQDQ instruction
复制标题
使用即将推出的向量化 VPCLMULQDQ 指令进行二进制多项式的快速乘法
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
V. Krasnov
中科院分区：
文献类型：
--
作者：
Nir Drucker;S. Gueron;V. Krasnov
二进制域$mathbb{F}_{2^{n}}$上的多项式乘法是一种常见的原语，例如由当前的密码系统如AES-GCM（其中$n=128）$使用。它也被证明是为后量子时代设计的其他密码系统的原始值，其值为$ngg 128$。最近提交给NIST后量子密码学项目的例子是BIKE，LEDAKem和GeMSS，其中多项式乘法的性能非常重要。因此，在$mathbb{F}_{2^{n}}$上的高效多项式乘法（具有大的$n$）是一个重要的新兴优化目标。预计未来的应用，英特尔最近宣布，其未来的架构（代号“冰湖”）将引入一种新的矢量化方式来使用当前的VPCLMULQDQ指令。在本文中，我们演示了如何使用此指令来加速多项式乘法。我们的分析显示，对于次数为512或更高的多项式的乘法，预测至少有2倍的加速。
Polynomial multiplication over binary fields $mathbb{F}_{2^{n}}$ 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 $ngg 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 $mathbb{F}_{2^{n}}$, 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.