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

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

一种基于MLWE的同态内积方案

同态内积在安全多方几何计算、隐私数据挖掘、外包计算、可排序的密文检索等场景有广泛的应用.但现有的同态内积计算方案大多是基于RLWE的全同态加密方案,普遍存在效率不高的问题.在柯程松等人提出的基于MLWE的低膨胀率加密算法基础上,提出了一种同态内积方案.首先给出了密文空间上的张量积运算⊗,该密文空间上的运算对应明文空间上的整数向量内积运算;然后分析了方案的正确性与安全性;最后给出了两种优化的加密参数,对应计算两种不同大小的整数向量同态内积的应用场景.通过C++与大整数计算库NTL实现了该方案.对比其他同态加密方案,该方案能够比较高效地计算整数向量的同态内积.