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

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

3 向量相等保密判定问题

问题描述. Alice 和 Bob 分别具有有理数向量 X=(x 1 ,…,x n )和 Y=(y 1 ,…,y n ),双方想要保密判定两个向量 X 和 Y
是否相等:如果不相等,不应向对方泄露向量 X 或 Y 的任何信息.
计算原理. 首先证明下面的结论.
命题 1. 对于任意两个有理数向量 X=(x 1 ,…,x n )和 Y=(y 1 ,…,y n ),X=Y 的充要条件是以下等式成立:
2
2
|X| +|Y| =2X⋅Y (9)
其中, | X = | 2 x + 1 2 ... x+ 2 n ,| |Y = 2 y + 1 2 ... y+ 2 n .
证明:由于
X = Y ⇔ | X − Y | 0= ⇔ (x + 2 ... x+ 2 ) (y+ 2 + ...+ y 2 ) 2(x y− + ... x y+ ) = 0 ⇔ | X | + 2 | |Y = 2 2X Y⋅ ,
1 n 1 n 1 1 n n
因此,命题 1 得证. □
命题 1 是判定两向量是否相等的基本原理,即,将判定两向量 X,Y 是否相等的问题转化为判定条件(9)是否
成立的问题.下面我们以协议 1 为基础,构造向量相等保密判定协议.Alice 和 Bob 调用协议 1(约定 t=n+1),Alice
2
2
得到随机数 s>2,Bob 得到 z=sX⋅Y.Bob 计算 u=z−|Y| =sX⋅Y−|Y| ,并将 u 发送给 Alice.Alice 计算:
s
2
w = (u− | X | )
s − 2
= s (sX Y ⋅ − | X | − 2 | | )
2
Y
s − 2
s
= ((s − 2)X Y ⋅ + (2X Y ⋅ − | X | − 2 | | ))Y 2
s − 2
= sX Y ⋅ + s (2X Y ⋅ − | X | − 2 | | ),Y 2
s − 2
2
2
并将 w 发送给 Bob.Bob 判断 w 是否等于 z=sX⋅Y:若 w=z,则 2X⋅Y−|X| −|Y| =0,即 X=Y;否则,X≠Y.下面为叙述方便,
定义二元谓词:
⎧ 1, 如果 x = y
Px .
(, )y = ⎨
⎩ 0, 如果 x ≠ y
协议 2. 向量相等保密判定协议.
输入:Alice 和 Bob 分别输入有理数向量 X=(x 1 ,…,x n )和 Y=(y 1 ,…,y n ).
输出:Bob 输出 P(X,Y).
1. 将 X,Y 作为协议 1 的输入向量,Alice 和 Bob 调用协议 1,Alice 得到一个随机数 s>2,Bob 得到 z=sX⋅Y.
2
2. Bob 计算 u=z−|Y| ,并将 u 发送给 Alice.
s
2
3. Alice 计算 w = (u− | X | ) ,并将 w 发送给 Bob.
s − 2
4. Bob 输出 y=P(w,z).
协议 2 的正确性. 根据二元谓词 P(x,y)的定义,需要证明 w=z⇔X=Y.因此,只需证明下式成立即可:
w = s (z− | X | − 2 |Y | ).
2
s − 2
根据向量的运算性质,对于任意有理数向量 X,Y 以及关于 X 和 Y 的任意关系式 z=sX⋅Y,均有以下等式成立:
s s
w = (u− | X | ) = 2 (z− | X | − 2 |Y | ).
2
s − 2 s − 2
因此,协议 2 是正确的.
协议 2 的安全性. 在协议 2 执行中首先调用协议 1,Alice 得到一个保密随机数 s,Bob 得到保密值 z=sX⋅Y.
首先考虑 Alice 向量的安全性.由协议 1 的安全性证明,在调用协议 1 的过程中,Bob 最多可得到向量 X 的一