基于Kyber的小数加法同态密码体制的研究

来源：计算机技术与发展杂志2024年第11期北京时间：

作者：吕经浪;李子臣

摘要：在云端数据存储中普遍存在隐私泄露问题,确保用户云端数据安全性已成为密码学领域的热点。 结合同态加密技术,可以有效实现这一目标。 目前大多数同态加密算法都是基于格上 LWE 和 RLWE 问题构建,出于两者效率和安全方面的考虑,研究者进一步提出了 MLWE 问题,其成为了 Kyber 公钥密码体制的重要理论基础,部分学者对该算法明文域进行了扩展,但未考虑其同态加密性质。 该文首先对扩展明文域后的 Kyber 公钥密码算法做了充分研究,为了使其获得同态特性,采用了一种新型编码方法,使其能够在整数域上正确进行加法同态运算;其次,在整数加法同态的基础上,进行了有限小数到整数的编码,将明文域扩展到有限小数域,使其能够在有限小数域上正确进行加法同态运算;最后,在算法实现部分,该同态加密方案支持无限次加法同态操作,可进行加法同态运算的小数位数为 lg(21792-1)位。另外,还进一步结合SIMD 编码,将方案可加密解密的小数位数扩展到 230位。 通过安全性分析,在 MLWE 问题的安全性假设下,可证明该方案是 IND-CPA 安全的。

关键词：加法同态;有限小数域;SIMD编码;Kyber公钥密码体制;模容错学习问题