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

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

个线性关系;在协议 2 的后续执行中,又收到 Alice 发送的 w = s (u− | X | ) .当向量 X≠Y 时,Bob 根据得到的关
2
s − 2
系式 w = s (u− | X | ) 得不到向量 X 的任何信息(其中,s 是 Alice 的私有数据).因此,在协议 2 中,Alice 向量 X
2
s − 2
的安全性与协议 1 一致.
下面再考虑 Bob 向量的安全性.在调用协议 1 的过程中,Alice 得到 Bob 向量 Y 1 (和 Y 2 )的任意 2 个分量的线
2
性关系式,得不到向量 Y 的信息.在协议 2 的后续执行中,Alice又获得 Bob 发送的 u=z−|Y| ,对于 Alice 而言,y 1 ,…,y n
2
作为未知数,由关系式 u=z−|Y| 仅能获得关于 Y 的一个二次关系式.
根据上面的分析,在协议 2 的执行过程中,Bob 最多能得到 Alice 向量 X 的一个线性关系式,Alice 最多得到
关于 Bob 向量 Y 的一个二次关系式.根据有理数的稠密性,即使参与者有无限的计算能力,也无法得到对方的私
有向量.协议 2 的安全性与协议 1 类似,安全性很高.
关于协议 2 的安全性,仅叙述下面的定理 2.定理 2 的证明类似于定理 1,故从略.
定理 2. 向量相等保密判定协议 2 是安全的.

4 向量优势保密判定问题

向量优势保密判定问题. 假设有两个有理数向量 X=(x 1 ,…,x n )和 Y=(y 1 ,…,y n ),如果对于所有 i∈[1,n],关系
x i >y i 成立,则称向量 X 关于 Y 具有向量优势,并记为 X>Y;否则,称向量 X 关于 Y 不具有向量优势.向量 X 和 Y 的
优势保密判定问题,即是要保密判定是否有关系 X>Y 成立.
基本原理. 我们知道:判断向量 X>Y,即判断 Z=X−Y=(x 1 −y 1 ,…,x n −y n ):=(z 1 ,…,z n )中每个分量均大于 0,那么只
需判断向量 Z 中最小分量 min{z 1 ,…,z n }>0 即可.
为方便后面的叙述,定义二元谓词如下:
⎧ 1, 如果 X > Y
PX .
(, )Y = ⎨
⎩ 0, 否则
协议 3. 向量优势保密判定协议.
输入:Alice 输入有理数向量 X=(x 1 ,…,x n ),Bob 输入有理数向量 Y=(y 1 ,…,y n ).
输出:Alice 和 Bob 输出 P(X,Y).
1. Alice 随机选取有理数向量 R=(r 1 ,…,r n ),r i >0,计算 Z 1 =X+R:=(z 11 ,…,z 1n ).将向量 Z 1 发送给 Bob.
2. Bob 计算 Z 2 =Z 1 −Y:=(z 21 ,…,z 2n ),并随机选取有理数向量 K=(k 1 ,…,k n ),k i >0,计算 Z 3 =(k 1 z 21 ,…,k n z 2n ):=
(z 31 ,…,z 3n ).将向量 Z 3 发送给 Alice.
⎛ z z ⎞
3. Alice 计算 Z = 4 31 ,..., 3n ⎟ : (z= ⎜ 41 ,...,z 4n ) ,并随机选取有理数 s,计算 Z 5 =Z 4 +sE:=(z 51 ,…,z 5n ).将 Z 5 发送给
⎝ r 1 r n ⎠
Bob.
4. Bob 计算 Z 6 =Z 5 −K:=(z 61 ,…,z 6n ),并选取向量 Z 6 中的最小分量 z min 发送给 Alice.
5. Alice 比较 z min 和 s:当 z min >s 时,输出 P(X,Y)=1;否则,输出 P(X,Y)=0.
协议 3 的正确性. 由 Z 1 到 Z 5 的计算过程可知:
⎛ kx y ) k (x − y ) ⎞
( −
Z = 6 (z 61 ,...,z 6n ) = 1 1 1 + ⎜ s ,..., n n n + s ; ⎟
⎝ r 1 r n ⎠
进一步,由 z min 的定义可知:
( −
kx y )
i
s
i
z > s ⇔ ∀∈ [1, ],n z > ⇔ ∀∈ [1, ],n i i i > 0 ⇔ ∀∈ [1, ],n x − y > 0 ⇔ X > . Y
i
6i
min
r i i
i
因此,协议 3 是正确的.
协议 3 的安全性. 为了分析协议 3 的安全性,需要考察在协议执行过程中每个参与者的私密向量的安全性,