论文标题
紧凑而有效的KEM在NTRU晶格上
Compact and Efficient KEMs over NTRU Lattices
论文作者
论文摘要
NTRU晶格是构建实用密码系统的有前途的候选人，特别是关键封装机制（KEM），对量子计算攻击具有抵抗力。尽管如此，基于NTRU的KEM方案仍然存在一些固有的障碍，在整体上具有安全性，具有安全性，带宽，错误概率和计算效率\ emph {整体}的障碍，它们比基于基于的\ {r，m \} lwe lwe lwe flasts。在这项工作中，我们通过提出一个新的基于NTRU的KEM计划（称为CTRU和CNTR）来解决这个问题。通过桥接低维晶格代码和仔细的设计和分析的高维基于NTRU-存在的密码学，就我们的最佳知识而言，CTRU和CNTR是首个基于NTRU的KEM计划，具有可扩展的Ciphertext the ciphertext压缩，仅通过一个\ emph {single} ciphertexteft {single} ciphertextext persem-em-exter-exter-exter-exter-exter-exterperform-k k \ k \ ky。综合性能方案。例如，与当前是NIST的唯一标准化的KEM相比，在建议的参数集CNTR-768上，CNTR-768的$ 12 \％$ $ $ $ $ $ $ $ $ $，同时将384位键封装为固定的256位键的Kyber的固定密钥尺寸，安全性增强了$（8,7,7）$（8,7,7）$（8,,7）$（8,,7） （$ 2^{ - 230} $ of CNTR-768 vs. $ 2^{ - 164} $ KYBER-768）。与Kyber-768的最新AVX2实现相比，CNTR-768在Keygen中的速度更快为1.9倍，封装为2.6倍和1.2倍。与NIST第3轮决赛选手NTRU-HRSS相比，我们的CNTR-768的密码较小约15美元，并且安全性分别以$（55,49）$ bits的$（55,49）来加强古典和量子安全性。至于AVX2实现，CNTR-768的速度比NTRU-HRSS在KeyGen中比NTRU-HRSS快，分别为2.3倍，封装和1.6倍。
The NTRU lattice is a promising candidate to construct practical cryptosystems, in particular key encapsulation mechanism (KEM), resistant to quantum computing attacks. Nevertheless, there are still some inherent obstacles to NTRU-based KEM schemes in having integrated performance, taking security, bandwidth, error probability, and computational efficiency \emph{as a whole}, that is as good as and even better than their \{R,M\}LWE-based counterparts. In this work, we solve this problem by presenting a new family of NTRU-based KEM schemes, referred to as CTRU and CNTR. By bridging low-dimensional lattice codes and high-dimensional NTRU-lattice-based cryptography with careful design and analysis, to the best of our knowledge CTRU and CNTR are the first NTRU-based KEM schemes with scalable ciphertext compression via only one \emph{single} ciphertext polynomial, and are the first that could outperform \{R,M\}LWE-based KEM schemes in integrated performance. For instance, compared to Kyber that is currently the only standardized KEM by NIST, on the recommended parameter set CNTR-768 has about $12\%$ smaller ciphertext size while encapsulating 384-bit keys compared to the fixed 256-bit key size of Kyber, security strengthened by $(8,7)$ bits for classical and quantum security respectively, and significantly lower error probability ($2^{-230}$ of CNTR-768 vs. $2^{-164}$ of Kyber-768). In comparison with the state-of-the-art AVX2 implementation of Kyber-768, CNTR-768 is faster by 1.9X in KeyGen, 2.6X in Encaps, and 1.2X in Decaps, respectively. When compared to the NIST Round 3 finalist NTRU-HRSS, our CNTR-768 has about $15\%$ smaller ciphertext size, and the security is strengthened by $(55,49)$ bits for classical and quantum security respectively. As for the AVX2 implementation, CNTR-768 is faster than NTRU-HRSS by 19X in KeyGen, 2.3X in Encaps, and 1.6X in Decaps, respectively.
