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

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

4. Alice 输出 Z.
协议 5 的正确性. 我们只需要证明 Z=XA 成立即可.
根据矩阵的运算性质,对于任意向量 X=(x 1 ,…,x m )以及关于 X 的任意分解方式 X=a 1 X 1 +…+a t X t ,均有以下的
等式成立:
Z=a 1 z 1 +…+a t z t =a 1 X 1 A+…+a t X t A=(a 1 X 1 +…+a t X t )A=XA.
因此,协议 5 是正确的.
协议 5 的安全性. 协议 5 的设计思想本质上是协议 1 设计思想的推广,向量 X 的安全性与协议 1 类似,矩阵
A 的各列向量的安全性与协议 1 中 Bob 向量 Y 1 (或 Y 2 )的安全性类似.由于矩阵 A 由 n 个列向量联合构成,根据
协议设计可知,A 的各列向量之间没有任何关系,这也保证了矩阵的各元素数据具有较高的安全性.
6.3 点与多边形的位置关系

问题描述. 假设 Alice 有一个私密点 P 0 (x 0 ,y 0 ),Bob 有一个私密凸多边形 S,其顶点按逆时针顺序排列为
P 1 ,…,P m (m≥3),顶点坐标为 P i (x i ,y i )(i∈[1,m]).Alice 和 Bob 想要保密判定点 P 0 (x 0 ,y 0 )是否在多边形 S 的内部.
计算基本原理. 根据点与直线的位置关系可知,两个点 Q 1 ,Q 2 在一条直线 f 的同一侧的充要条件是:
f(Q 1 )f(Q 2 )>0.
那么对于点与多边形的位置关系,我们可以知道点 P 0 位于多边形 S 内部的充要条件是:选取多边形内任意
一点 Q i (包括多边形端点 P j ,j∉{i,i+1}),将点 P 0 和点 Q i 代入多边形 S 的每一条边 P i P i+1 (i∈[1,m])所在的直线 f i ,
都满足 f i (P 0 )f i (Q i )>0.即:当点 P 0 和点 Q i 在多边形的每条边 P i P i+1 的同一侧时,点 P 0 位于多边形内部.如图 1 所示:
当点 P 0 和 Q 1 在直线 f 1 ,f 2 ,…,f 7 的同一侧时,点 P 0 在多边形内部.当然,对于每一条直线 f i ,Bob 可以选择不同的点
Q i 进行计算,在此约定 Bob 对直线 f i 取点 Q i =P i+2 .

Fig.1 Position relationship between point and polygon
图 1 点与多边形的位置关系
Bob 首先写出多边形的边 P i P i+1 (i∈[1,m],P m+1 =P 1 )所在直线方程:
f i (x,y)=a i x+b i y+c i =0.
对于每个 i∈[1,m],为使上面表达式中的函数 f i (x,y)完全确定,如果多边形的边 P i P i+1 不平行于 x 轴,则约定取 a i =1;
否则,取 b i =1.根据计算基本原理可知,点 P 0 位于多边形内部的充要条件是下式成立:
f 1 (x 0 ,y 0 )f 1 (P 3 )>0,f 2 (x 0 ,y 0 )f 2 (P 4 )>0,…,f m (x 0 ,y 0 )f m (P 2 )>0.
Bob 进一步计算 s i =f i (P i+2 ),则上式等价于 s i f i (x 0 ,y 0 )>0,i∈[1,m],或
(sa )x + ⎧ 0 (s b y + 1 1 ) 0 s c > 1 1 0
11
⎪ (sa )x + ⎪ (s b y + ) s c > 0
⎨ 22 0 2 2 0 2 2 (14)
⎪ ...
⎪ (sa )x + (s b y + ) 0 s c > mm 0
⎩
mm
m m
0