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

刘旭红:高效安全向量计算及其推广 3643

若记 Z j =(z j1 ,…,z jm )(j=1,2,3),则公式(17)等价于以下方程组:
z = ⎧ r X ⋅ A + s
⎪ 1i i 1 i
z = ⎨ 2i r X ⋅ i 2 A + i , s i = 1,...,m (18)
⎪ z = r X ⋅ A +
⎩ 3i i 3 i s
对 Alice 来说,方程组(18)有 3m 个方程,却具有 4m+1 个独立的未知数 u i ,v i ,w i ,r i (i=1,…,m)以及 s;且由于所有未知
数均可取任意有理数,因此即使 Alice 有无限的计算能力,也不可能通过求解方程组(18)而获得 Bob 的矩阵 A.
但对于每一个 i∈[1,m],Alice 由方程组(18)可以得到以下的关系式:
z − z (X − X ) A⋅
k = 1i 2i = 1 2 i ,
i
z − z 3i (X − 1 X ⋅ 3 ) A i
1i
从而得到向量 A i 所有分量的一个线性关系式.
根据上面的分析可知,在协议执行过程中,Bob 仅可能以 1/m 的概率猜对 x 0 ,y 0 的一个关系式;而对于每一个
i∈[1,m],Alice 仅能获得 A i 所有分量 u i ,v i ,w i 间的一个关系式.进一步根据公式(15)可知,Bob 的多边形各顶点坐标
是完全安全的.因此,协议 6 是安全的.
协议 6 的效率分析. 为了分析协议 6 的实际效率,需要详细分析在协议执行过程中的计算复杂性和通信复
杂性.由于本文协议 6 仅应用了基本算术运算,所以分析计算复杂性时仅考虑基本算术运算次数,以通信轮数和
通信数据量(传输的数据个数)衡量协议的通信复杂性;同时,利用 Java 编程语言对本协议进行实验测试.
计算复杂性. 在协议 6 中,Bob 计算矩阵 A 执行了 3m 次乘法运算,接收到 Alice 的分解向量后执行了 10m
次乘法运算和 9m 次加法运算.Alice 执行了 3m+9 次乘法运算和 6 次加法运算.因此,协议 6 共需要执行 25m+15
次基本算术运算.
通信复杂性. 在协议 6 中,共需要 2 轮通信,在协议过程中的通信数据量为 4m+10.
实验测试. 实验设定保密数据的范围为[−100,100].下面分别对本文协议 6 在不同维向量下进行多次实验,
实验结果随机抽取 50 组数据求取平均值.结果见表 4.
Table 4 Analysis of experimental results of Protocol 6
表 4 协议 6 实验结果分析
协议 计算复杂性(B) 通信数据量 50 组实验数据平均值(ms)
本文协议 6 25m+15 (B) 4m+10 112.492 5
在表 4 中,计算复杂性一栏,B 表示基本算术运算次数.由表 4 可知,协议 6 的计算复杂性和通信复杂性较低.

7 结 论

向量问题的保密计算是安全多方计算的一项基本内容,实际生活中遇到的许多问题均可转化为向量问题
得到解决,其中,保密数据挖掘、保密统计分析、保密计算几何等问题与向量问题密不可分.特别地,目前关于有
理数域上向量问题的保密计算研究还不成熟,且现有的研究结果较少.
本文利用代数学基本知识设计了简单高效的向量点积保密计算协议、向量相等保密判定协议及向量优势
保密判定协议.严格的理论分析和实验结果表明,本文协议是安全高效的.应用这些协议作为基本模块,不仅可
以解决更多的安全多方计算问题,而且计算效率更高.本文的协议是在半诚实模型下设计的,未来将进一步研究
恶意模型下的安全多方向量计算问题.

References:
[1] Yao AC. Protocols for secure computations. In: Proc. of the 23th Annual Symp. on Foundations of Computer Science. IEEE, 1982.
160−164. [doi: 10.1109/SFCS.1982.38]
[2] Ben-Or M, Goldwasser S, Wigderson A. Completeness theorems for non-cryptographic fault-tolerant distributed computation. In:
Proc. of the 20th Annual ACM Symp. on Theory of Computing. New York: ACM, 1988. 1−10. [doi: 10.1145/62212.62213]
[3] Cramer R. Introduction to Secure Computation. Berlin: Springer-Verlag, 1999. 16−62. [doi: 10.1007/3-540-48969-X_2]