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

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

c
{( , ( , ))}Sx f x x ≡ {view π ( , )}x x ,
1 1 1 1 2 x 1 ,x 2 1 1 2 x 1 ,x 2
c
{ ( ,Sx f 2 ( , ))}x x 2 x 1 ,x 2 ≡ {view π ( , )}x x 2 x 1 ,x 2
1
2
2
1
2
c
两公式成立的概率多项式时间算法 S 1 和 S 2 存在,则称函数 f 可以通过协议π进行保密计算,其中, ≡ 表示计算上
不可区分.
对于一个两方保密计算协议,若要证明其是安全的,就要构造模拟器 S 1 和 S 2 满足上述两公式.当某个参与方
在协议执行中没有任何输出,记该参与方的输出结果为空串λ.
2 高效的向量点积保密计算协议
定义 2. 假设两个参与者 Alice 和 Bob 分别拥有私密的 n 维向量 X=(x 1 ,…,x n )和 Y=(y 1 ,…,y n ),他们希望合作
保密计算两向量的点积 X⋅Y=x 1 y 1 +…+x n y n .协议结束后,如果输出结果为 X⋅Y,称这样的协议为向量点积协议;如果
协议结束后,其中一方得到 s≠0,另一方得到 sX⋅Y 或 X⋅Y+s,我们称这样的协议为共享向量点积协议.
目前已有的关于向量点积(或共享点积)问题的保密计算研究存在的主要问题是:以公钥加密方案为基础设
计的协议安全性较好但复杂性都很高,而避免应用公钥加密系统的协议大多都有不同程度的信息泄露.下面,我
们首先应用基本的代数知识和一定的设计技巧设计一个高效安全的向量点积(共享)协议.在下文中,如果一个
向量的所有分量均为有理数,称这样的向量为有理数向量.
2.1 共享向量点积协议
我们首先构造一个高效的共享向量点积保密计算协议,并证明其安全性.
协议 1. 共享向量点积保密计算协议.
输入:Alice 输入有理数向量 X=(x 1 ,…,x n ),Bob 输入有理数向量 Y=(y 1 ,…,y n ).
输出:Alice 输出 s,Bob 输出 F(X,Y)=sX⋅Y.
1. Alice 将向量 X=(x 1 ,…,x n )按以下方式进行分解:随机选取有理数 a i 和有理数向量 X i =(x i1 ,…,x in )
(i∈[1,t]={1,…,t},2≤t≤n+1),使得 X=a 1 X 1 +…+a t X t 且 a 1 +…+a t ≠0.Alice 将向量 X 1 ,…,X t 发送给 Bob.
2. (a) Bob 随机选取有理数 b j 和有理数向量 Y j =(y j1 ,…,y jn )(j=1,2),使得 Y=b 1 Y 1 +b 2 Y 2 ;
(b) Bob 选取非零随机有理数 k 1 ,k 2 ,r 1 ,r 2 ,计算
z 11 =k 1 X 1 ⋅Y 1 +r 1 ,…,z 1t =k 1 X t ⋅Y 1 +r 1 ,
z 21 =k 2 X 1 ⋅Y 2 +r 2 ,…,z 2t =k 2 X t ⋅Y 2 +r 2 ,
将(z 11 ,…,z 1t )和(z 21 ,…,z 2t )发送给 Alice.
3. Alice 计算 z 1 =s(a 1 z 11 +…+a t z 1t ),z 2 =s(a 1 z 21 +…+a t z 2t ),其中, s = 1 .并将 z 1 ,z 2 发送给 Bob.
a + ... a t
+
1
(z − ) r (z − r )
4. Bob 计算 z = b 1 1 + b 2 2 .
1 2
k 1 k 2
5. Alice 输出 s,Bob 输出 z.
协议 1 的正确性. 我们只需证明 z=sX⋅Y 成立即可.
根据内积的运算性质,对于任意的有理数向量 X 和 Y,以及关于 X 和 Y 的任意分解方式:
X=a 1 X 1 +…+a t X t ,Y=b 1 Y 1 +b 2 Y 2 ,
均有以下等式成立:
z 1 =s(a 1 z 11 +…+a t z 1t )=sk 1 X⋅Y 1 +r 1 ,z 2 =s(a 1 z 21 +…+a t z 2t )=sk 2 X⋅Y 2 +r 2 ,
则
(z − ) r (z − r )
z = b 1 1 + b 2 2 = b (sX Y⋅ ) b+ (sX Y⋅ ) = sX ⋅ (bY + b Y ) = sX . Y ⋅
1 k 2 k 1 1 2 2 1 1 2 2
1 2
因此,协议 1 是正确的.