基于理想格的公钥加密方案快速实现技术研究

作者：王伯宇; 高海英^*

来源：密码学报, 2023, 10(04): 852-861.

DOI：10.13868/j.cnki.jcr.000633

• 格公钥密码
• 容错学习问题
• KYBER类加密方案
• 数论变换
• 结合Karatsuba的带预处理的数论变换

在基于理想格和模格的公钥加密方案中,多项式环上的乘法运算是影响方案实现效率的重要模块,而该模块通常可通过数论变换(number theoretic transform, NTT)来快速实现.本文采用结合Karatsuba算法的带预处理的NTT (preprocess-then-NTT with Karatsuba, KNTT),提升格公钥加密方案的实现效率.在使用KNTT前,通过改进采样和密文打(解)包结果的存储方式来调整多项式环元素的数据结构,使之直接适用KNTT,从而省去KNTT算法中的预处理和组合环节.改进了KNTT中的NTT变换的实现方式,进一步提高格公钥加密方案的实现效率. KYBER是NIST在第三轮评选中决定标准化的格公钥密码算法,本文将上述改进技术应用于KYBER类加密方案,得到了KNTT-based KYBER算法,与KYBER.CPAPKE相比,密钥生成实现效率提高了5%–8%,加密实现效率提高了7%–10%,解密实现效率提高了9%–10%.

• 单位
  信息工程大学