Page 271 - 《软件学报》2021年第11期

柯程松 等:一种基于 MLWE 的同态内积方案 3597

计算、隐私数据挖掘、外包计算、可排序的密文检索等场景.安全计算两个整数向量的内积,是安全多方计算
的重要技术之一.
全同态加密允许对密文进行任意复杂的运算,而不需要解密密文,自然可以应用于安全计算两个整数向量
[2]
的内积.设计全同态加密方案,一直是密码学界的研究热点.2009 年,Gentry 基于理想格构造了第一个全同态加
[3]
密方案,由于需要使用压缩电路、自举等技术,该方案的效率很低,难以应用于实际.2012 年,Brakerski 等人 提出
[4]
了一种基于 RLWE(ring learning with errors)问题 的层级全同态加密方案 BGV,即分成一层层的电路进行同态
[5]
计算,计算效率有所提高. 2014 年,Halevi 等人根据 BGV 方案构造了第一个全同态计算库 HElib ,该计算库是目
[6]
前公认效率最高能够进行全同态加密的计算库.2016 年,Xu 等人 对 HElib 进行了优化,可完成两个整数的密文
四则运算,使用 SIMD 技术将一个明文向量的所有坐标打包到一个密文中,尽管进行了优化,要计算两个 256 维
8bits 整数向量的同态内积,使用 SIMD 技术仍然需要计算一次乘法和 8 次加法共约 20s 左右的时间.这是由于
基于 RLWE 构造同态加密方案,安全性要取较大的安全参数.文献[7]利用基于理想格的全同态加密来安全计算
内积,并应用于身份认证.但是该方案的计算效率并不高,如对两个 2 048 维的 bit 向量,为了安全计算内积,其预
计计算的时间需要 38s;并且该方案只能计算 0-1 向量,使用场景有局限性.除了使用全同态加密,也有学者通过
[8]
其他方法计算整数向量的同态内积.2010 年,Dijk 等人 提出了基于整数的同态加密算法,虽然效率较高,但安全
[9]
性是基于近似 GCD 问题,已被证明是不安全的 .2014 年,Zhou 等人 [10] 提出了一种计算整数同态内积的方法,
效率较高,但也存在安全性问题 [11] .总之,目前已有的方法都难以安全高效地计算两个整数向量的同态内积.
柯程松等人 [12,13] 于 2018 年对 Bos 等人的 Kyber 密钥封装算法 [14] 进行改进,提出了一种基于 MLWE(module
learning with errors)问题 [15] 的低膨胀率加密算法,加密效率高于基于 RLWE 问题构造的加密算法.这是由于
RLWE 问题只能规约到理想格上的困难问题,加密参数会取得很大,所以加密效率较低.但 MLWE 问题能归约到
模格上的困难问题,模格是一般格与理想格的推广,使能够在保证同等安全性的前提下选取更小的加密参数,所
以柯程松等人提出的加密算法效率很高,并且该方案本身保证了具有能够加密多位的整数.在此基础上,本文构
造一种基于 MLWE 的安全高效的同态内积方案.

1 本文贡献与文章结构

1.1 本文贡献
本文构造了一种基于 MLWE 的安全高效的同态内积方案,贡献如下:
(1) 基于 BGV 方案的思想,给出了基于 MLWE 问题构造的同态内积方案的密文空间上运算⊗,该密文空
间上的运算对应明文空间上的整数向量内积运算.
(2) 分析了本文基于 MLWE 问题构造同态内积算法的正确性与安全性.
(3) 针对计算两种不同大小的整数向量同态内积的应用场景,给出了两种优化的加密参数.
(4) 通过 C++与大整数计算库 NTL 实现了本文方案.对比其他同态加密方案,该方案能够高效地计算整数
向量的同态内积.
1.2 文章结构

本文第 2 节将介绍本文中出现的一些符号以及预备知识.第 3 节首先给出本文的同态内积方案,其中定义
了密文空间上的张量运算⊗;接着描述如何通过多项式乘法计算向量内积.其次给出了通过密文空间上的张量
运算⊗计算同态内积的过程;然后分析了方案的正确性.针对两种不同大小的整数向量同态内积的应用场景,给
出了两种优化的加密参数.最后证明了本文方案的 IND-CPA 安全性.第 4 节分析本文同态内积方案的计算复杂
度,并与其他几个方案做同态内积的效率进行对比.第 5 节总结全文,并对下一步值得关注的研究方向和应用场
景进行简单讨论.