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

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

在 MLWE n,q,χ,k 问题是困难的假设成立的情况下,Adv MLWE [A]可以忽略不计,本文的同态内积方案可证明是
IND-CPA 安全的. □
4 方案效率与计算复杂度

4.1 方案计算复杂度
本节给出了本文方案各个阶段计算复杂度.以下所有的 n,k,dp 均对应第 3 节中给出的加密参数.
本文只分析两个 n 维整数向量做内积时的计算复杂度.如果向量维数小于 n,则在多的位置补 0,计算复杂度
则与 n 维整数向量内积时相同;维数大于 n 时则多次调用本文方案,时间复杂度相应增大.通过第 3.4 节中的方
案正确性分析不难得出:在两种加密参数下,均能保证 n 小于 2 048 时,多次调用本文方案所累计的噪声不影响
解密正确性.更大维数的向量内积则需具体分析,不作为本文的重点.
在生成公私钥对时,由于要调用中心二项分布函数生成满足算法要求分布的噪声,时间复杂度为 O(n),空间
2
复杂度为公钥大小 O(k n).
在进行加密操作时,主要消耗的计算量是多项式乘法,其他计算(如压缩与解压缩操作)的计算复杂度可以
2
2
忽略不计.加密时要进行 k +k 次多项式乘法,根据文献[16],加密时的时间复杂度是 O((k +k)⋅(3nlogn+n)),空间复
杂度为快速傅里叶变换所消耗的空间 O(n).由于本文方案关注的是同态内积,所以不考虑直接解密加密后的明
文的计算复杂度.
2
在进行同态内积操作时,主要消耗的计算量同样是多项式乘法,计算一次同态内积,要进行(k+1) 次多项式
2
乘法.加密时的时间复杂度是 O((k+1) ⋅(3nlogn+n)),空间复杂度为快速傅里叶变换所消耗的空间 O(n).
2
在同态解密阶段,主要分为两步进行:首先,生成计算密钥,要进行 k 次多项式乘法,时间复杂度是
2
O(k ⋅(3nlogn+n)),空间复杂度为快速傅里叶变换所消耗的空间 O(n);然后,解密时,主要求密文以及计算密钥的
2
内积 O((k −1)⋅(3nlogn+n)),空间复杂度为快速傅里叶变换所消耗的空间 O(n).
表 2 给出了本文方案各个阶段的计算复杂度.
Table 2 Scheme computational complexity
表 2 方案计算复杂度
算法阶段 时间复杂度 空间复杂度
2
密钥生成 O(n) O(k n)
2
加密操作 O((k +k)⋅(3nlogn+n)) O(n)
2
同态内积 O((k+1) ⋅(3nlogn+n)) O(n)
2
同态解密 O((2k -1)⋅(3nlogn+n)) O(n)

4.2 方案效率与实现
本文的实验环境采用 CPU 为 Intel Core i5-3470、频率:3.20GHz、内存 8GB 的计算机,操作系统为 CentOS7
64 位,算法使用 C++编程实现,大整数计算调用了 NTL 计算库.
本节给出了两种加密参数下,本文同态内积方案的效率,并与其他几种方案计算同态内积的效率与安全性
进行了对比,见表 3.
Table 3 Scheme efficiency comparison
表 3 方案效率对比
方案 安全性 同态内积效率
[6]
Xu RLWE 256 维 8bits 向量内积大于 20s
[7]
Yasuda 理想格 2048 维 bits 向量内积 38s
[8]
Dijk 近似 GCD 问题 256 维 10bits 向量内积 0.5ms
Zhou [10] LWE 40 维 10bits 向量内积 757.2ms
本文方案(参数 1) MLWE 256 维 7bits 向量内积 10ms
本文方案(参数 2) MLWE 256 维 10bits 向量内积 20ms