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

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

并详细分析在协议执行后可能推断出的潜在信息.
首先考虑 Alice 向量的安全性.Bob 得到 Alice 发送的向量 Z 1 和 Z 5 ,由 Z 1 ,Z 5 的定义可知:
Z = (z ,...,z ) = (x + r ,...,x + r ),
1 11 1n 1 1 n n
⎛ kx y ) k (x − y ) ⎞
( −
Z = (z 51 ,...,z 5n ) = ⎜ 1 1 1 ++ 1 ,..., n n n ++ n . ⎟
sk
sk
5
⎝ r 1 r n ⎠
分别根据 Z 1 和 Z 5 无法得到向量 X 的任何信息.结合 Z 1 ,Z 5 可以得到以下等式:
(
( −
kx y ) kx − y j )
j
j
i i i − = (z − k − ) (z − k ) = z − z (10)
z − x z − x 5i i 5 j j 6i 6 j
1i i 1 j j
其中,x i ,x j 是未知量.一个方程两个未知数,Bob 根据上述等式无法解得 x i ,x j ,仅可以得到向量 X 中两个分量 x i ,x j
间的二次关系式.因此,Alice 向量 X 是安全的.
下面考虑 Bob 向量的安全性.在协议执行中,Alice 仅获得 Bob 发送的向量 Z 3 和最小分量 z min .根据协议的
执行过程可知:
Z 3 =(k 1 (z 11 −y 1 ),…,k n (z 1n −y n )),
其中,y i ,k i 均为未知量.因此,Alice 根据 Z 3 无法得到向量 Y 的任何信息.根据最小分量 z min 的定义可知,Alice 无法
获知对于哪个 i∈[1,n],有 z min =z 6i .Alice 只能对每一个 i∈[1,n],求解以下公式中的 y i :
( −
⎧ z = z = kx i y i ) + s
i
⎪ min 6i r i (11)
⎨
⎪ z = (x − y +
⎩ 3i k i i i i ) r
若将所得的解记为 y′ ,显然, y′ = y 当且仅当 z min =z 6i .如果仅有一个 i∈[1,n]满足 z min =z 6i ,此时 Alice 仅有 1/n 的概
i
i
i
率猜对满足 y′ = y 的 i 值.除此之外,在协议的整个执行过程中,Alice 得不到关于向量 Y 的任何信息.因此,
i
i
Bob 向量 Y 是安全的.
根据上面的分析及有理数的稠密性可知,协议 3 的安全性和理想模型相比仅有很小的差别.关于协议 3 的
安全性,仅叙述下面的定理 3.定理 3 的证明类似于定理 1,故从略.
定理 3. 向量优势保密判定协议 3 是安全的.
5 效率分析与比较
本节将本文的主要结果与近期较好的工作进行比较,在进行效率分析时,一般地,基本算术运算与模乘运算
的计算复杂性相比较可忽略不计.文献[25,27,28]均研究了向量点积的保密计算问题,但文献中提出的解决方案
需要借助第三方参与者或服务器;文献[25,26,30−34]也研究了向量点积的保密计算问题,但上述文献中提出的
解决方案均需要借助不同的密码体制进行保密计算,仅适用于整数范围内的向量计算且计算复杂性较高.文献
[29]利用基本算数运算设计了偶数维点积协议,适用于有理数向量的保密计算且计算复杂性较低.因此,本文协
议 1 主要与文献[29]进行详细的分析和比较.而关于向量相等保密计算问题和向量优势保密计算问题,现有的相
关文献较少,其中,文献[35]利用散列函数设计了向量相等保密判定协议,文献[36−38]利用不同的公钥加密算法
设计了向量优势协议,这些协议均只适用于整数集上的向量计算.目前还没有关于有理数向量相等问题和有理
数向量优势问题的研究文献,因此本文协议 2 仅与文献[35]进行效率分析和比较,本文协议 3 主要与计算效率相
对较高的文献[38]进行效率分析与比较.
为了便于分析比较,假设两方参与者的向量都是 n 维的.由于我们所设计的协议仅应用了基本算术运算(普
通有理数的加减乘除运算),而已有文献大多是应用公钥加密系统设计协议,所以分析计算复杂性时同时考虑了
基本算术运算次数和模乘运算次数.并且,我们以通信数据量衡量协议的通信复杂性.
点积协议的分析比较. 本文协议 1 中仅应用了有理数的加法及乘法等基本算术运算.具体地,接收到 Alice
的分解向量后,Bob 执行了 2t(n+1)次乘法以及 2tn 次加法运算,且计算 z 执行了 4 次乘法以及 3 次加法运算.Alice
执行了 2(t+1)次乘法运算和 2(t−1)次加法运算,因此协议 1 共需要 4tn+6t+7 次基本算术运算.文献[29]设计了偶