NTRU格上高效紧凑密钥封装方案

An Efficient and Compact Key Encapsulation Mechanism Based on NTRU Lattice

基于NTRU格设计后量子密钥封装方案是格密码领域主流方向之一.为降低密文尺寸,现有方案会引入额外的困难性假设和使用纠错码来辅助压缩密文,但这会导致方案的假设过强和实现更复杂.为克服这些障碍,提出了一个仅基于NTRU单向困难性假设、不使用纠错码也能压缩密文的高效紧凑的密钥封装方案LTRU.给出一套性能均衡的LTRU参数集:具有128 b量子安全强度、与之匹配且可忽略的错误率、较小的公钥尺寸和密文尺寸.LTRU基于NTT友好环构造,给出一种高效的混合基数论变换算法来计算该环上多项式运算还给出了LTRU的C实现和AVX2实现.与NIST第3轮决赛方案NTRU-HRSS相比,LTRU的经典安全强度和量子安全强度分别增强6 b和5 b,LTRU的公钥尺寸降低14.6%,密文尺寸降低26.0%,总带宽降低20.3%;在AVX2实现的密钥生成和解封装算法上分别快了10.9倍和1.7倍.

Constructing post-quantum key encapsulation mechanism based on NTRU lattice is one of the popular research fields in lattice-based cryptography.To reduce the ciphertext size,some current schemes compress the ciphertext with the aid of extra hardness assumptions and error correction codes,which leads to idealistic underlying assumption and complicated implementation.To address the issues,an efficient and compact key encapsulation mechanism,named LTRU,is proposed.LTRU is only based on NTRU one-wayness assumption and enables ciphertext compression without using any error correction codes.The performance-balanced parameter set of LTRU is provided,featuring 128 b quantum security level along with the matching and negligible error probability,and smaller public key size and ciphertext size.LTRU is based on the NTT-friendly polynomial ring.To compute the polynomial operations of LTRU,an efficient mixed-radix NTT is presented.At last,both C implementation and AVX2 implementation of LTRU are provided.When compared with NIST Round 3 finalist NTRU-HRSS,the classical and quantum security of LTRU are strengthened by 6 b and 5 b,respectively.LTRU reduces the public key size,ciphertext size and total bandwidth by 14.6%,26.0%and 20.3%,respectively.LTRU is 10.9 times faster in key generation and 1.7 faster in decapsulation with respect to AVX2 implementation,respectively.