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

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

对于 i∈[1,m],记 u i =s i a i ,v i =s i b i ,w i =s i c i ,并记 X=(x 0 ,y 0 ,1),A i =(u i ,v i ,w i )以及
⎛ u u ... u ⎞
⎜ ⎜ 1 2 m ⎟ ⎟
A = ( ,..., A m ) = ⎜ ⎜ v 1 v 2 ... v m ⎟ ⎟ (15)
A
1
⎜ ⎟
⎜ w w ... w ⎟
⎝ 1 2 m ⎠
则条件(14)可表示为 Y=XA=(X⋅A 1 ,…,X⋅A n )>0.如此,可以通过计算 Y=XA,根据其每个分量是否大于 0 来判断点 P 0
是否在多边形 S 内部.
为方便后面的叙述,定义二元谓词 P(P 0 ,S)如下:如果点 P 0 在多边形 S 内部,定义 P(P 0 ,S)=1;否则,P(P 0 ,S)=0.
根据上面的计算原理,容易设计出点与多边形位置关系的保密判定协议,具体如下.
协议 6. 点与凸多边形的位置关系判定协议.
输入:Alice 输入点 P 0 (x 0 ,y 0 ),Bob 输入凸多边形 S:P 1 P 2 …P m ,顶点坐标为 P i :(x i ,y i )(i∈[1,m]).
输出:Bob 输出 P(P 0 ,S).
1. Bob 按照公式(15)计算矩阵 A.
2. Alice 将向量 X=(x 0 ,y 0 ,1)按以下方式进行分解:随机选取有理数 t 1 ,t 2 ,t 3 和有理数向量 X i =(x i1 ,x i2 ,x i3 )(i=1,
2,3),使得 X=t 1 X 1 +t 2 X 2 +t 3 X 3 ,其中,t=t 1 +t 2 +t 3 >0;并将(X 1 ,X 2 ,X 3 )发送给 Bob.
3. Bob 随机选取有理数 r i >0,i∈[1,m]和有理数 s,计算 A = (rA ,...,r A ) 和 Z = XA sE+ ,Z = X A sE+ ,
11 m m 1 1 2 2
Z = XA sE+ ,其中,E=(1,…,1);并将(Z 1 ,Z 2 ,Z 3 )发送给 Alice.
3 3
1
4. Alice 计算 Z = (tZ + t Z + t Z ) ,选取向量 Z 中的最小分量 z min 发送给 Bob.
t 11 2 2 3 3
5. Bob 比较 z min 与 s.如果 z min >s,Bob 输出 P(P 0 ,S)=1;否则,输出 P(P 0 ,S)=0.
协议 6 的正确性. 我们首先证明 Z = 1 XA sE+ 成立.
t
根据矩阵运算性质,对于向量 X=(x 0 ,y 0 ,1),及 X 的任意分解方式 X=t 1 X 1 +t 2 X 2 +t 3 X 3 ,均有以下等式成立:
1 1 1
Z = (t Z + 11 t Z + 2 2 t Z 3 ) = ( ( t X AsE+ 1 ) t X A sE+ 2 ( 2 + ) t X AsE+ 3 ( 3 + )) = XAsE+ ;
3
1
t t t
进一步,根据有理数 r i >0,i∈[1,m]和 t>0 可知:
Y = XA = (X A⋅ 1 ,..., X A⋅ m ) > 0 ⇔ XA = (r XA 1 ,...,r XA m ) > 0 ⇔ z min > . s
1
m
因此,协议 6 是正确的.
协议 6 的安全性. 协议 6 是结合协议 1 和协议 3 的设计思想进行设计的,类似于协议 1 和协议 3 的安全性
证明思想进行证明.
首先考虑 Alice 向量的安全性.Alice 秘密选择有理数 t 1 ,t 2 ,t 3 和有理数向量 X 1 ,X 2 ,X 3 ,将向量 X=(x 0 ,y 0 ,1)进行
分解.Bob 在协议执行中得到 Alice 发送的 X 1 ,X 2 ,X 3 ,Bob 由关系式 X=t 1 X 1 +t 2 X 2 +t 3 X 3 ,即
x = ⎧ tx + t x + t x
⎪ 0 1 11 2 21 3 31
y = ⎨ 0 t x + 1 12 t x + 2 22 t x (16)
3 32
⎪
=
⎩ 1 tx + 113 t x + 2 23 t x
3 33
推算 X 的相关信息.方程组(16)中有 3 个方程,但含有 5 个未知数 x 0 ,y 0 ,t 1 ,t 2 ,t 3 .由于 t 1 ,t 2 ,t 3 均由 Alice 随机选择,Bob
即使有无限的计算能力,也得不到向量 X 的任何信息.在第 4 步中,Bob 还收到 Alice 发送的向量 Z 中最小分量
z min .如果 Bob 猜测对于某一个 i ∈ 0 [1, ],m z min = z ,这时,Bob 可联立求解方程组(16)以及 z min = (r 0 i / )t X A⋅ 0 i + s ,得
0 i
到关于 x 0 ,y 0 的一个关系式.由于 Bob 无法获知对于哪个分量有 z min =z i ,Bob 能猜对 x 0 ,y 0 关系式的概率仅有 1/m.
下面再考虑 Bob 向量的安全性.在协议执行中,Alice 仅获得 Bob 发送的信息:
⎧ Z = XA sE = + (r X ⋅ A + s ,...,r X ⋅ A + ) s
⎪ 1 1 1 1 1 m 1 m
Z = ⎨ 2 XA sE = + (r X ⋅ 1 2 A + 1 s ,...,r X ⋅ m 2 A + m ) s (17)
2
⎪
⎩ Z = 3 XA sE+ 3 = (r X ⋅ 1 3 A + 1 s ,...,r X ⋅ m 3 A + m ) s