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

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

当 t<n(或 t=n+1)时:
bb
• 首先,矩阵 A=(X 1 ,…,X t )不存在可逆矩阵,则关系式(7)不存在,消去 Bob 的私有随机数 ,,rr 2 1 , 2 也无从
1
kk 2
1
谈起,所以 Alice 无法得到 Bob 向量 Y 的信息.
• 其次,方程组(5)(或方程组(6))中有 t 个方程,但包含有 n+2 个未知数 y 11 ,…,y 1n 以及 k 1 ,t 1 (或 y 21 ,…,y 2n 以
及 k 2 ,t 2 ),由于 n+2>t,且所有未知数为有理数,因此即使 Alice 有无限的计算能力,也不可能通过求解方程
组(5)(或方程组(6))直接得到向量 Y 1 (或 Y 2 ),从而无法得到向量 Y.
但是,Alice 根据方程组(5)可以得到以下关系式:
⎧ z − 13 z 11 (x − 31 x 11 )y + 11 ... (x − + 3n x 1n )y 1n
⎪ z − z = (x − x )y + ... (x − + x )y
⎪ ⎪ 12 11 21 11 11 2n 1n 1n
⎨ ... (8)
⎪ z − z (x − x )y + ... (x − + x )y
⎪ 1t 11 = 1 t 11 11 tn 1n 1n
⎪ ⎩ z − 12 z 11 (x − 21 x 11 )y + 11 ... (x − + 2n x 1n )y 1n
方程组(8)是以 y 11 ,…,y 1n 为未知数,含有 t−2 个方程的线性方程组.由于 t−2<n,Alice 最多可求得关于向量 Y 1 的任
意 n−t+3 个分量的线性关系式(同理,Alice 最多可求得关于向量 Y 2 的任意 n−t+3 个分量的线性关系式).进一步,
由 Y=b 1 Y 1 +b 2 Y 2 可知,Alice 需要将向量 Y 1 和 Y 2 联立才能求解向量 Y,但 Alice 仅知道关于向量 Y 1 和 Y 2 各自分量
独立的线性关系式,且不知道随机数 b 1 ,b 2 的值,所以无法联立求解,故无法得到向量 Y 的任何信息.
综上所述,当 t<n(或 t=n+1)时,Alice 得不到 Bob 向量 Y 的信息,向量 Y 是安全的.
根据上面的分析,当 t<n 时,Bob 向量 Y 是安全的,Bob 最多得到向量 X 中 t 个分量之间的关系式;当 t=n 时,
Alice 最多得到向量 Y 中 4 个分量之间的关系式,Bob 仅能得到关于向量 X 的一个关系式(3);当 t=n+1 时,Bob 向
量 Y 是安全的,Bob 仅能得到关于向量 X 的一个关系式(3).因此,t=n+1 时,协议 1 的安全性最好,且与理想模型下
协议相比仅有微小差别:Bob 能得到 Alice 向量 X 的一个线性关系式.
关于协议 1 的安全性有下面的定理 1.
定理 1. 共享向量点积保密计算协议 1 是安全的.
证明:下面应用模拟范例严格证明定理 1,即需要构造模拟器 S 1 (或 S 2 ),使两公式成立.
首先构造 S 1 .接收到输入(X,s)后,S 1 按以下方式运行:
(i) S 1 首先任意选择有理数向量 Y′ ( ,...,y′ = y′ ) ,并随机选取有理数 b′ 和有理数向量 Y′ (y′ = ,..., y′ ) (j=1,
1 n j j 1 j jn
2),使得 Y′ bY ′ = ′ b Y ′ + ′ .
11 2 2
′′
(ii) S 1 任意选取非零随机有理数 ,, ,kk r r ′ ′ ,计算:
1
2
2
1
z′ 11 k X Y′ ⋅ ′= 1 1 1 r′+ 1 ,...,z′ 1t k X Y′ ⋅ 1 ′= t 1 1 , r′+
z′ k X Y′ ⋅ ′= r′ + ,...,z′ k X Y′ ⋅ ′= r′ +
21 2 1 2 2 2t 2 t 2 2
在协议执行中,
view 1 π ( , )X Y = ( , (X z 11 ,..., z 1t ),(z 21 ,...,z 2t ), )s ,
而 S 1 在模拟过程中产生的信息序列为
SX 1 = ( , (X z′ 11 ,...,z′ 1t ),(z′ 21 ,...,z′ 2t ), )s .
( , ( , ))f X Y
1
由于有理数 b j ,k 1 ,k 2 ,r 1 ,r 2 和有理数向量 Y j =(y j1 ,…,y jn )(j=1,2)是 Bob 随机选取的,对 Alice 来说,有:
c c
b ≡ j b′ j ,Y ≡ j Y j , ′
c c c c
k ≡ ′ , k k ≡ k′ ,r r r ′ ≡ , ≡ , r′
1 1 2 2 1 1 2 2
c c
因此, (z 11 ,..., z ≡ 1t ) (z′ 11 ,...,z′ 1t ), (z 21 ,...,z 2t ) (z′ ≡ 21 ,...,z′ 2t ) .故
c
{ ( , ( , ))}SX f X Y ≡ {view π ( , )}X Y .
1 1 , i x y i Q∈ 1 , i x y i Q∈
接收到输入(Y,f 2 (X,Y)=F(X,Y))后,S 2 按以下方式运行: