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

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

协议 4. 多方向量相等保密判定协议.
输入:m 个参与者 P i (i∈[1,m])分别输入有理数向量 X i .
输出:P(X 1 ,…,X m ).
2
准备:(a) 对于每一个 P i (i∈[2,m]),P i 分别随机选取非零有理数 S i 构造向量 X ′ = (2SX , S− 2 ) ,并随机选取有
i i i i
2
理数 a i1 ,…,a in 和有理数向量 X i1 ,…,X in ,使得 X ′ = aX + ... a X+ ;(b) P 1 构造向量 X ′ = (X ,| X | ) ,并随机选取有
i 1 i 1 i in in 1 1 1
理数 b i1 ,b i2 和有理数向量 U i1 ,U i2 (i∈[2,m]),使得 X ′ = bU + b U .
1 1 i 1 i 2 i 2 i
1. P i (i∈[2,m])和 P 1 分别将向量 X ′ 和 X ′ 作为协议 1 的输入向量,按照准备阶段(a)和阶段(b)合作调用协
i 1
议 1(注解 1 的点积协议),P 1 得到 z 2 ,…,z m ,并计算 Z=z 2 +…+z m ,其中, z = X ′⋅ X ′ .
i i 1
2. 每一个 P i ,i=2,…,m:
2
(a) 从 P i−1 处接收到 w i− 1 = S i 2 | X i | ;
(b) 将 w i 与 w i−1 相加,最后得到 W=w 2 +…+w m ,并发送给 P 1 .
3. P 1 比较 Z 和 W:如果 Z=W,输出 P(Z,W)=1;否则,输出 P(Z,W)=0.
协议 4 的正确性. 需要证明 W=Z⇔X 1 =…=X m .
根据 Z = z + ... z+ X ′= X ′ ⋅ + ... X ′+ X ′ ⋅ = (2S X ⋅ 2 X − S 2 | X | ) ... (2S X+ 2 + 2 ⋅ X − S 2 | X | ) ,那么,W−Z=
2
2 m 2 1 m 1 2 2 1 2 1 m m 1 m 1
2
2
(S 2 X 2 −S 2 X 1 ) +…+(S m X m −S m X 1 ) .因此,W=Z⇔∀i∈[2,m],S i X i −S i X 1 =0⇔∀i∈[2,m],X i −X 1 =0⇔X 1 =…=X m .
因此,协议 4 是正确的.
协议 4 的安全性. 协议 4 是基于向量点积协议 1 设计的,当不考虑合谋攻击时,由协议 1 的安全性分析可知,
参与者 P i (i∈[2,m])向量的安全性完全类似于协议 1 中 Alice 向量的安全性.参与者 P 1 向量的安全性完全类似于
协议 1 中 Bob 向量的安全性.因此,在协议 4 中,各参与者的向量是安全的.
下面我们主要分析协议 4 中的合谋攻击.由于在协议 4 中,参与者 P 1 拥有向量点积 X ′ 1 X ′ ⋅ 2 ,..., X ′ 1 X ′ ⋅ m ,若 P 1

与其他参与者合谋,很容易判断出哪些向量 X i (i∈[2,m])与向量 X 1 相等.因此,我们将仅考虑参与者 P 1 不参与合谋
2
2
的情况.假设参与者 P 3 ,…,P m 合谋,他们最多可得到参与者 P 2 的 SX 值.由于 S 2 是 P 2 的保密数据,因此无法得
2
2
到向量 X 2 的任何信息.
根据协议 4 的设计过程可知,协议仅应用基本的算术运算解决多方向量相等保密判定问题,计算效率较高;
但是协议 4 需要限制参与者 P 1 不参与合谋攻击,具有一定的局限性.据我们所知,现有的抵抗合谋攻击的保密计
算协议均需要借助公钥加密方案,例如:利用 ElGamal 同态加密方案可以构造门限密码体制,进而设计可以抵抗
合谋攻击的多方保密计算协议.现有信息论安全的协议很难有效抵抗合谋攻击,均需要设定一些限制条件.
6.2 向量和矩阵的保密计算问题
假设 Alice 有一个 m 维有理数向量 X=(x 1 ,…,x m ),Bob 有一个 m×n 阶的有理数矩阵 A=(a ij ),Alice 和 Bob 想要
保密计算 X 和 A 的乘积.
记矩阵 A 的第 i 个列向量为 A i (i=1,…,n),则有以下的关系:
Y=XA=(X⋅A 1 ,…,X⋅A n ).
因此,计算 X 和 A 的乘积问题即转化为计算 X 与 A 的列向量的内积问题.利用这一原理,构造向量与矩阵乘
积保密计算协议如下:
协议 5. 向量和矩阵乘积保密计算协议.
输入:Alice 和 Bob 分别输入有理数向量 X=(x 1 ,…,x m )和有理数矩阵 A=(a ij ) m×n .
输出:Alice 输出 Y=XA.
1. Alice 将向量 X=(x 1 ,…,x m )按以下方式进行分解:随机选取有理数 a 1 ,…,a t 和有理数向量 X i =(x i1 ,…,x im )
(i∈[1,t],2≤t<n),使得 X=a 1 X 1 +…+a t X t .Alice 将向量(X 1 ,…,X t )发送给 Bob;
2. Bob 计算 z 1 =X 1 A,…,z t =X t A,将 z 1 ,…,z t 发送给 Alice;
3. Alice 计算 Z=a 1 z 1 +…+a t z t ;