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

3638 Journal of Software 软件学报 Vol.32, No.11, November 2021

数维点积共享协议,协议中 Alice 执行了 3n/2 次乘法运算以及 9n/2−1 次加法运算,Bob 执行了 2n 次乘法运算以
及 9n/2−1 次加法运算,因此文献[29]的点积协议共需要 25n/2−2 次基本算术运算.为了具体地将本文协议 1 与文
献[29]进行对比,我们通过以下两种情形 1 和情形 2 分别进行效率分析.
• 情形 1:n<5,t=2 时,协议 1 比文献[29]多执行 21−9n/2 次基本算术运算.n=2 时,协议 1 比文献[29]多执行
12 次基本算术运算;n=3 时,协议 1 比文献[29]多执行 7 次基本算术运算;n=4 时,协议 1 比文献[29]多执
行 3 次基本算术运算.因此,在 n<5 的情形下,两种方案的计算效率相近,均可以高效解决维数较小的向
量保密计算问题,例如信息检索、机器翻译等输入数据量较小的场景.
• 情形 2:n≥5,t=2 时,协议 1 比文献[29]少执行 9n/2−21 次基本算术运算.n=5 时,协议 1 比文献[29]少执行
1 次基本算术运算;n=6 时,协议 1 比文献[29]少执行 6 次基本算术运算;n=7 时,协议 1 比文献[29]少执
行 11 次基本算术运算.进一步,n=10 时,协议 1 比文献[29]少执行 24 次基本算术运算;n=15 时,协议 1
比文献[29]少执行 46 次基本算术运算;n=20 时,协议 1 比文献[29]少执行 69 次基本算术运算.因此,在
n≥5 的情形下,随着向量维数 n 的增加,本文协议 1 的计算效率优势更加明显.故本文协议 1 可以高效
解决向量维数大的安全多方计算问题,例如文本相似度问题、文本挖掘、论文抄袭识别等输入数据量
较大的场景.
本文的点积协议 1 需要的通信数据量为 t(n+2)+2;文献[29]的点积协议需要的通信数据量为 3n.当 t=2 时,
本文协议 1 的通信数据量为 2n+6,且随着向量维数 n 的增加,本文协议 1 的通信效率优势更加明显.
当 t=2 时协议 1 的安全性.根据前面的分析,Bob 最多得到 Alice 向量 X 中任意 t+1=3 个分量之间的一个线
性关系式,Alice 得不到 Bob 向量 Y 的任何信息.而文献[29]中,Alice 和 Bob 分别能够得到对方私密向量相邻分
量之间的关系式 y 2k−1 +y 2k 和 x 2k−1 +x 2k 的值.因此,在选取 t=2 时,本文协议 1 的安全性和效率与文献[29]相比有所
提高,更适用于解决大数据情形下的向量保密计算问题.且本文可以根据具体的向量点积保密计算问题的安全
性要求,灵活选择分解个数 t.本文协议 1 具有更高的灵活性和广泛适用性.
向量相等协议的分析比较. 本文协议 2 研究了两向量相等的判定问题,就我们所知,目前直接研究向量相
等问题的文献较少,文献[35]中的协议 3 可用于比较两向量相等.由于文献[35]的方案仅适用于正整数向量,适用
范围有限,且会出现单边错误,而本文协议 2 是基于共享点积协议 1 设计的,效率更高,适用范围也更广泛.
向量优势协议的分析比较. 我们将本文协议 3 与主要研究向量优势保密判定问题的文献[38]的协议 2 进行
比较.本文协议 3 主要应用基本算术运算,其中,Alice(或 Bob)进行的加减法为 2n 次,乘除法运算为 n 次,整个协
议需要的基本算术运算各为 3n 次.文献[38]应用 Paillier 公钥加密算法设计的协议 2,基本运算是模乘运算,整个
协议共需要 2(mn+1)logN+n 次模乘运算,其中,N 是加密系统中两个大素数的乘积.一般来说,基本算术运算与模
乘运算的计算复杂性相比较可忽略不计.因此,本文协议 3 的计算复杂性相比文献[38]是非常小的.
本文协议 3 需要的通信数据量为 4,文献[38]的协议 2 所需通信数据量为 mn+2.本文协议 3 的通信负载较低.
详细的协议效率比较结果见表 1.在表 1 中,计算功能一栏为所列文献研究的具体内容;计算复杂性一栏,
M(或 B)表示模乘(或基本算术)运算次数;通信复杂性为通信数据量.
Table 1 Efficiency analysis and application range comparison of the protocols
表 1 协议的效率分析与适用范围的比较
协议 计算功能 计算复杂性(M 或 B) 通信数据量 适用范围
文献[29] 点积 25n/2−2 (B) 3n 有理数
文献[38] 优势 2(mn+1)logN+n (M) mn+2 正整数
本文协议 1 点积 8n+19 (B) 2n+6 有理数
本文协议 3 优势 6n (B) 4 有理数

根据 Paillier 公钥加密系统,N 是两个大素数的乘积,一般长度为 1 024 比特.我们注意到,实际生活中有关向
量计算问题,向量维数 n 一般都满足 n<<logN.在此情形下,本文协议 1 的计算复杂性低于已有文献,通信复杂性
也不比已有协议的通信复杂性高;协议 3 的计算复杂性远低于已有文献.而本文协议适用于有理数范围内的向
量计算,适用性更广;并且本文协议 1 和协议 3 在有理数向量情形下安全性更高,泄露的信息对安全性影响极小.