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

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

(i) S 2 首先任意选择有理数向量 X ′ = ( ,...,x′ 1 x′ n ) ,并随机选择有理数 a′ 和有理数向量 X ′ i (x′ = 1 i ,..., x′ in )
i
+
(i∈[1,t]={1,…,t},2≤t≤n+1),使得 (F XY = ′ , ) F ( , ),X Y X ′ a X ′ = 1 1 ′ + ... a X ′ + t ′ t 且 a′ + ... a′ ≠ t 0 .
1
(ii) S 2 计算:
z′ 11 k X Y⋅ 1 1 ′ = 1 r 1 ,...,z′ + 1t k X Y⋅ 1 t ′ = 1 + 1 , r
z′ 21 k X Y ⋅ 2 1 ′ = 2 r 2 ,...,z′ + 2t k X Y ⋅ 2 ′ = t 2 + 2 , r
以及
( s az′ +
z′ = ′′ ... az ′ ′ ),
+
1 1 11 t 1t
z′ = 2 ′′ 1 21 ... a z ′ ′ 2t ),
+
( s a z′ +
t
1
其中, s′ = .
a′ ... a′ + +
1 t
(iii) S 2 计算:
(z′ − ) r (z′ − r )
z′ = b 1 1 + b 2 2 .
1 2
k 1 k 2
在协议执行中,
view π ( , )XY = ( ,(Y X 1 ,..., X t ),( , ), ( , )),z z 2 F XY
2
1
而 S 2 在模拟过程中产生的信息序列为
SY 2 ( , ))X Y = ( ,(Y X ′ 1 ,..., X ′ t ),( , ), (z z′ 1 ′ 2 F X ′ , )).Y
( , f
2
c c c c
首先,由于 a i (i∈[1,t])为 Alice 任意选取的随机数,因此 a′≡ a i ,s′≡ ,故有 (X ′ 1 ,..., X ′ t ) (X≡ 1 ,..., X t ), ( , ) ( , )z z′ 1 ′ 2 ≡ z z .
s
2
1
i
又因为 F(X′,Y)=F(X,Y),因此,
c
{ ( ,SY f 2 ( , ))}X Y , i x y i Q∈ ≡ {view π ( , )}X Y , i x y i Q∈ . □
2
2
注解 1. 设定 t=n+1,如果在协议 1 中 Alice 取 s=1,即 a 1 +…+a t =1,这时,协议输出结果为 F(X,Y)=X⋅Y,协议 1
成为一个点积协议.此时,Bob 收到 Alice 发送的数据 z 1 ,z 2 中不再包含未知数 s,Bob 最多可得到两个关系式:
z − r 1 = X Y ⋅ = x y + ... x y ,
1
+
k 1 1 1 11 n 1n
z − r
2 2 = X Y⋅ = x y + ... x y+ ,
k 2 1 21 n 2n
2
且方程组(1)与 a 1 +…+a t =1 联立仍无法得到关于向量 X 的任何信息,所以 Alice 向量 X 仍是安全的.在此过程
中,Alice 收到 Bob 发送的数据(z 11 ,…,z 1t )和(z 21 ,…,z 2t )没有发生改变,因此向量 Y 的安全性没有受到影响.
注解 2. 由于利用向量分解的思想,协议 1 中参与方的向量至少需分解为两个随机向量,由此知:对于维数
n≥3 的向量点积问题,可直接利用本文协议 1 进行解决.对于维数 n=2 的向量点积问题,用本文协议 1,Bob 仍仅
得到关于 Alice 向量 X 的一个线性关系式;Alice 根据(z 11 ,z 12 )(或(z 21 ,z 22 ))无法消去随机数 k 1 ,r 1 (或 k 2 ,r 2 ),所以 Alice
得不到向量 Y 1 ,Y 2 的任何信息,即得不到向量 Y 的任何信息.因此,本文协议 1 适用于 n≥2 的向量点积问题.
如果参与计算的向量维数较小且限制各分量仅能取值 0 或 1 时,本文协议 1 不能安全的解决向量点积问题.
例如,当 n=3 且 x i ,y i ∈{0,1},i=1,2,3 时,向量 X=(x 1 ,x 2 ,x 3 )的可能取值仅有 8 种情形.Bob 得到的公式(3)中含有 3 个
未知数 x 1 ,x 2 ,x 3 ,通过直接代入 0 和 1 进行测试,可知(x 1 ,x 2 ,x 3 )的有些取值满足公式(3),有些不满足,因此就泄露了
向量 X 的部分信息.文献[27]基于可逆矩阵设计的共享点积协议也存在类似的安全性问题,当向量维数 n 较小且
限制各分量取值为整数时,任一方参与者可通过其获得的 n/2 个等式推导获取对方足够多的私有信息.文献[29]
设计的偶数维共享向量点积协议也存在安全性问题,参与者分别泄露其私密向量相邻分量之间的关系式 x 2k−1 +
x 2k 和 y 2k−1 +y 2k 的值.文献[28,30−34]中设计的共享点积协议,当向量维数较小且各分量限制取值为 0 或 1 时,每个
参与者都可在一定程度上推导获取对方向量的某些信息,只是信息泄露的程度有所不同.针对这种向量维数较
小且各分量限制取值为 0 或 1 的情形,可以利用公钥加密方案进行解决,且计算效率较高.因此,本文协议 1 适用
于向量维数 n≥2 且向量的分量取值无限制范围的情形.