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

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

协议 1 的安全性. 为了对协议 1 进行安全性分析,在协议执行中需要分析每个参与者的私密向量的安全性,
并详细分析在协议执行后可能推断出的潜在信息.
首先考虑 Alice 向量的安全性.Alice 秘密将 X 分解为 X=a 1 X 1 +…+a t X t ,Bob 在整个协议的执行过程中得到
Alice 发送给他的 X 1 ,…,X t 以及 z 1 ,z 2 .Bob 根据分解式 X=a 1 X 1 +…+a t X t ,可得到对应的方程组:
+
x = ⎧ 1 ax + 1 11 ... ax 1
tt
⎪
⎨ ... (1)
⎪
+
⎩ x = n ax + 11n ... a x
t tn
当 t<n 时,由公式(1)中的 t+1 个方程联立可能消去 a 1 ,…,a t 而得到 X 向量中 t+1 个分量之间的一个线性关
系式.而当 t=n(或 t=n+1)时,方程组(1)的 n 个方程含有 2n(或 2n+1)个未知数 x 1 ,…,x n 和 a 1 ,…,a t ,由线性方程组的
求解过程可知,需要 n+1(或 n+2)个方程联立才可能消去私密数据 a 1 ,…,a t 而得到 X 向量中 n+1(或 n+2)个分量之
间的一个线性关系式.因此,当 t=n(或 t=n+1)时,根据方程组(1),Bob 得不到 Alice 向量 X 的任何信息.
Bob 根据 z 1 =sk 1 X⋅Y 1 +r 1 ,z 2 =sk 2 X⋅Y 2 +r 2 ,有:
⎧ z − r 1
+
1
⎪ k = sX Y ⋅ 1 = ( s x y + 1 11 ... x y 1n )
n
⎨
⎪ 1 (2)
⎪ z − r 2 = sXY ⋅ = ( s x y + ... x y )
+
2
⎪ k 2 2 1 21 n 2n
⎩
由于公式(2)中两个方程含有 n+1 个未知数,Bob 通过联立两个方程,可得到:
+
xy + ... x y
111 n 1n = l (3)
+
xy + ... x y 2n
121
n
即 x 1 (y 11 −ly 21 )+…+x n (y 1n −ly 2n )=0.
进一步,当方程组(1)和方程组(2)联立时,Bob 可得到关于 a 1 ,…,a t 的一个线性关系式:
a 1 [x 11 (y 11 −ly 21 )+…+x 1n (y 1n −ly 2n )]+…+a t [x t1 (y 11 −ly 21 )+…+x tn (y 1n −ly 2n )]=0 (4)
将公式(4)与方程组(1)联立,得到一个以 x 1 ,…,x n 和 a 1 ,…,a t 为未知数的 n+1 个方程.因此,当 t<n 时,Bob 由公式(4)
式与方程组(1)联立的 n+1 个方程,最多得到 X 向量中 t 个分量之间的线性关系式;当 t=n(或 t=n+1)时,Bob 仅能
得到关于向量 X 的一个线性关系式(3).
综上所述,Alice 向量 X 是安全的,且向量 X 的安全性与 t 值成正比关系.
下面考虑 Bob 向量的安全性.在协议执行中,Alice 仅获得 Bob 发送的信息(z 11 ,…,z 1t )和(z 21 ,…,z 2t ),即有:
⎧ z = k 1 (x y + ... x y+ 1n 1n ) r+ 1
11
11 11
⎪ ⎨ ... (5)
⎪ z = (x y + + +
⎩ 1t k 1 t 1 11 ... x y 1n ) r 1
tn
⎧ z = k 2 (x y + ... x y+ 1n 2n ) r+ 2
21
11 21
⎪ ⎨ ... (6)
⎪ z = (x y + + +
⎩ 2t k 2 t 1 21 ... x y 2n ) r 2
tn
−1
当 t=n 时,Alice 设定矩阵 A=(X 1 ,…,X n )存在可逆矩阵 A ,通过计算:
(z ,...,z )A = − 1 k Y⋅ + r (1,...,1)A − 1 ,
11 1n 1 1 1
(z ,...,z )A = − 1 k Y⋅ + r (1,...,1)A − 1
21 2n 2 2 2
得到:
Y = b 1 (k Y ⋅ ) + b 2 (k Y ⋅ ) = b 1 [(z ,...,z )A − − 1 r (1,...,1)A − 1 ] + b 2 [(z ,...,z )A − − 1 r (1,...,1)A − 1 ] (7)
k 1 1 1 k 2 2 1 k 1 11 1n 1 k 2 21 2n 2
bb
其中, ,,rr 1 , 2 均为 Bob 的私有数据.公式(7)中包含 n 个方程和 n+4 个未知数,所以 Alice 根据公式(7)无法确
1 2
kk 2
1
定 Bob 向量 Y.但当 n>4 时,Alice 可得到向量 Y 中 4 个分量间的线性关系式.