Fast polynomial inversion for post quantum QC-MDPC cryptography
Fast polynomial inversion for post quantum QC-MDPC cryptography
复制标题
后量子 QC-MDPC 密码学的快速多项式求逆
DOI：
10.1016/j.ic.2021.104799
复制
发表时间：
2021
影响因子：
1
通讯作者：
Kostic, Dusan
中科院分区：
文献类型：
--
作者：
Drucker, Nir;Gueron, Shay;Kostic, Dusan
新的后量子密钥封装机制（KEM）设计在通信带宽和计算开销之间提出了具有挑战性的权衡。作为NIST PQC标准化项目的一部分，这些正在由加密社区和NIST进行评估。在该项目的第2轮中评估的一组有趣的KEM设计基于QC-MDPC代码。因此，BIKE-2使用最小的通信带宽，但其密钥生成需要非常昂贵的多项式求逆运算。在本文中，我们提供了更多的细节和优化的多项式求逆算法的QC-MDPC码，这是最初提出的早期会议版本的这项工作的例子。该算法使得BIKE-2密钥生成的计算成本是可容忍的。它带来了11.4倍于常用的NTL库，83.5倍于OpenSSL。我们还可以通过利用最新的英特尔Vector-PCLMULQD指令实现额外的加速比，比NTL提高14.3倍，比OpenSSL提高103.9倍。我们的算法和代码是BIKE团队选择BIKE-2（的变体）作为其第三轮规范（现在称为BIKE）的唯一方案的原因。这也是NIST选择BIKE-2作为第三轮决赛备选选手的原因之一。
New post-quantum Key Encapsulation Mechanism (KEM) designs pose challenging tradeoffs between communication bandwidth and computational overheads. These are being evaluated by the cryptographic community and by NIST, as part of the NIST PQC standardization project. An interesting set of KEM designs that were evaluated in Round-2 of the project are based on QC-MDPC codes. From this, BIKE-2 uses the smallest communication bandwidth, but its key generation requires a very costly polynomial inversion operation. In this paper, we provide more details and examples on the optimized polynomial inversion algorithm for QC-MDPC codes, which was originally proposed in the earlier conference version of this work. This algorithm makes the computation costs of BIKE-2 key generation tolerable. It brings a speedup of 11.4× over the commonly used NTL library, and 83.5× over OpenSSL. We can also achieve additional speedups by leveraging the latest Intel's Vector-PCLMULQDQinstructions, 14.3× over NTL and 103.9× over OpenSSL. Our algorithm and code was the reason that BIKE team chose (a variant of) BIKE-2 as the only scheme for its Round-3 specification (that is now called BIKE). It was also one of the reasons that NIST chose BIKE-2 as an alternative finalist for Round-3.
使用即将推出的向量化 VPCLMULQDQ 指令进行二进制多项式的快速乘法
DOI：
--
发表时间：
2018
期刊：
IEEE Symposium on Computer Arithmetic
影响因子：
--
作者：
Nir Drucker;S. Gueron;V. Krasnov
通讯作者：
V. Krasnov
具有多种灰度的 QC-MDPC 解码器
DOI：
--
发表时间：
2020
期刊：
IACR Cryptology ePrint Archive
影响因子：
--
作者：
Nir Drucker;S. Gueron;Dusan Kostic
通讯作者：
Dusan Kostic
QC-MDPC位翻转解码器的解码失败率研究
DOI：
--
发表时间：
2019
期刊：
IACR Cryptology ePrint Archive
影响因子：
--
作者：
N. Sendrier;Valentin Vasseur
通讯作者：
Valentin Vasseur