基于MLWE的低膨胀率加密算法

Low Expansion Rate Encryption Algorithm Based on MLWE

基于模容错学习问题(MLWE)的格密码算法Kyber具有抗量子攻击、加密效率高的优势,但密文膨胀率较大约为1∶25,仅适用于密钥封装等少数场景。为了构建一种能够应用于一般的公钥加密场景的加密算法,提出了一种改进的基于MLWE的低膨胀率公钥加密算法。文中在Kyber加密算法中引入新的加密参数dp,扩大了明文空间,通过严格的理论推导与实验分析了dp对加密算法正确性的影响,并优化了加密参数,降低了密文膨胀率。改进后的算法会扩大有限域(即计算空间),导致直接使用原算法中的有限域上的多项式乘法运算,需调用额外的大整数计算库,从而降低了加密效率。通过使用基于浮点运算的复数域上的快速傅里叶变换进行多项式乘法,避免了在增大后的有限域上进行大整数多项式乘法。最后,对浮点运算产生的误差进行了分析,同时使用C++实现了改进算法,并将其与Kyber的实验数据进行对比。实验表明,所提算法在保证了计算效率的同时使密文膨胀率由1∶25左右降低到了1∶4.25左右。

The lattice encryption algorithm Kyber based on MLWE has the advantage of anti-quantum attack and high encryption efficiency.However,the expansion rate of ciphertext is as high as about 1 ∶ 25 ,which is just suitable for a few scenes such as key encapsulation.In order to give an encryption algorithm that can be applied to common public key encryption scenes,an improved MLWE based low expansion rate public key encryption algorithm was proposed in this paper.A new encryption parameter dp was introduced into this algorithm to expand the plaintext space.By strict theoretical deduction and experiment,the influence of dp on the correctness of the encryption algorithm was analyzed,and the encryption parameter was optimized to reduce the expansion rate of ciphertext.The improved algorithm will work in a large finite field,which leads to low encryption efficiency.To avoid this situation,this paper proposed a polynomial mul- tiplication method based on FFT in complex field by using floating point arithmetic. And the improved algorithm was implemented in C++.Experimental results show that the new method is more efficient and the floating error is controllable.Compared with Kyber,the ciphertext expansion rate is reduced from 1 ∶ 25 to about 1 ∶ 4.25 .