安全多方计算中空间位置关系的保密判定

安全多方计算中空间位置关系的保密判定 Privacy-Preserving Determination of Spatial Location-Relation in Secure Multi-Party Computation first-author 李占利，男，教授，主要从事计算机图形学、模式识别研究. E-mail:lizl@xust.edu.cn 李占利，男，教授，主要从事计算机图形学、模式识别研究. E-mail: lizl@xust.edu.cn lizl@xust.edu.cn 西安科技大学 计算机科学与技术学院，陕西 西安 710054 西安科技大学 计算机科学与技术学院，陕西 西安 710054 School of Computer Science and Technology, Xi'an University of Science and Technology, Xi'an 710054, Shaanxi, China School of Computer Science and Technology, Xi'an University of Science and Technology, Xi'an 710054, Shaanxi, China 保密判断空间位置关系属于安全多方计算中的几何问题，在军事、商业等领域有着广泛的应用前景.针对空间中位置关系问题，首先将该问题转化为平行四边形面积问题，接着设计了保密计算两向量张成的平行四边形面积协议，然后基于此协议解决了空间中三点共线和点线面位置关系的保密判定问题，最后，利用模拟范例证明了协议的安全性.分析和比较显示：与已有的方案相比，本文的方案避免了多个基础协议的调用，不但提高了效率，而且适用范围更加广泛.此外，由于我们的方案没有使用任何公钥加密算法，因此达到了信息论安全. Privacy-preserving determination of spatial location-relation is classified as geometry problem in secure multiparty computation, and it is widely applied in business and military service. Aiming at spatial location-relation issue, we first transform this problem into the area problem of parallelogram, and then design a protocol to compute the area of the parallelogram formed by the two vectors. Furthermore, based on this protocol, the protocols of the three points collinear, and the location-relation of point line and plane in space are designed. Lastly, we prove the security of our protocols with simulation paradigm. Compared with the existed schemes, our protocols avoids the invoking of multiple basic protocols, and it not only improves the efficiency but also extends the scope of application. In addition, the proposed scheme does not employ any public key encryption algorithm to make our protocols achieve the information security. 安全多方计算 空间位置关系 计算几何 平行四边形面积 secure multi-party computation location-relation computational geometry parallelogram's area 引言 1 安全多方计算 [ 1 1 ] (secure multi-party computation, SMC)最早由姚期智在百万富翁问题中提出，指的是一组互不信任的参与方在不泄露各自输入的前提下, 合作进行计算.安全多方计算问题主要包括：保护隐私的科学计算、保护隐私的几何计算、保护隐私的统计计算等.它在安全入侵检测 [ 2 2 ] 、安全数据库查询 [ 3 3 ] 、安全数据挖掘 [ 4 4 ] 、安全统计分析 [ 5 5 ] 和安全几何计算 [ 6 6 ~ 8 8 6~8 ] 等方面有着广泛的应用. 保护隐私的几何计算是一种特定的安全多方计算问题, 针对此类问题，文献[ 9 9 ]研究了点与凸包位置关系问题，文献[ 10 10 ]研究了三角形面积计算问题，文献[ 11 11 ]研究了云计算下空间位置关系问题等.由于保护隐私的空间几何计算问题是安全多方几何计算的一个重要组成部分，且现实生活中很多问题都可以归结为这类问题, 因此研究其理论意义对现实问题有着重要的应用价值.本文对空间中三点共线和点线面位置关系问题进行了研究. 相关工作 1 空间中三点共线和点线面位置关系问题均属于安全多方计算中的计算几何问题.文献[ 12 12 ]首次提出保密判定空间中三点是否共线问题的解决方案, 将原问题转化为两条直线斜率是否相等问题, 然后利用Paillier公钥加密解决了该问题.由于此协议要用到公钥加密, 因此仅达到了计算性安全, 安全性级别不高. 对于空间中点、线、面位置关系的保密判定问题, 罗永龙等 [ 13 13 ] 将空间位置关系问题转化为数据对应成比例问题, 解决了空间中线线、线面、面面位置关系的保密判定问题, 该方案调用点积协议、比较相等协议和数据对应成比例协议三种基本协议.其中，数据对应成比例协议的复杂性较高, 从而制约了方案的效率.李顺东等 [ 14 14 ] 利用四面体的体积, 将原问题转化为距离问题, 解决了空间中点面、线面和面面的位置关系判定问题.因为无法在点线和线线之间构造出一个满足转化要求的四面体, 进而无法将四面体的体积转化为距离, 因此无法解决空间中点线、线线的位置关系判定问题, 使研究范围受到限制. 综合以上分析, 可以看出, 对于已存空间位置关系的解决方案, 要么由于转化方法的问题，使得方案需要调用多个基础协议, 造成效率不高或解决问题的范围受限，要么由于公钥加密算法的使用, 造成方案的安全性级别不高. 针对上述问题, 本文提出了新的转化方法, 解决了空间位置关系问题, 具体贡献如下: 1) 解决问题更加广泛 将空间中位置关系问题转化为由两个向量张成的平行四边形面积问题, 使得可以解决的问题更加广泛. 2) 提高了效率 基于新提出的转化方法, 设计了解决空间中三点共线和点线面位置关系的6个协议, 在新设计的协议中, 避免了多种基础协议的调用，提高了效率. 3) 达到了信息论安全 本文的7个协议都没有使用任何公钥加密算法, 安全性级别较高, 达到了信息论安全. 预备知识 1 安全多方计算的安全性定义 2 本文所涉及的参与者均为半诚实模型，而恶意模型下的协议可按照文献[ 15 15 , 16 16 ]中的通用转化方法得到.基于这一结论, 本文仅给出半诚实模型下的协议和相应的安全性模拟范例. 1) 半诚实参与者:安全多方计算的协议运行环境分为半诚实参与者模型和恶意参与者模型 [ 15 15 , 16 16 ] .半诚实参与者指在协议执行过程中正确地遵守协议指令, 但可能会记录协议执行过程中的中间结果, 并企图根据中间结果推导出额外的信息. 2) 半诚实模型下的安全性定义:设 f ( x , y )为概率多项式函数， π 表示计算 f 的两方协议, 假设Alice拥有 x , Bob拥有 y , 在不泄露 x , y 的前提下, 合作计算函数 f ( x , y )=( f 1 ( x , y ), f 2 ( x , y )), 目的是为了让Alice和Bob分别得到 f 1 ( x , y ), f 2 ( x , y ).view 1 ( x , y )和view 2 ( x , y )分别表示Alice和Bob在执行协议 π 的时候得到的视图; output 1 ( x , y )和output 2 ( x , y )分别表示Alice和Bob的输出.在文献[ 17 17 ]中Goldreich给出计算不可区分性的半诚实参与者的安全两方计算的定义, 表述如下: 定义1   协议 π 保密地计算了 m < N , 如果存在概率多项式时间算法 S 1 与 S 2 , 使得(1)式与(2)式同时成立: http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258253&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258253&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258253&type=middle http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258266&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258266&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258266&type=middle 其中, http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258534&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258534&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258534&type=middle 表示计算不可区分. 该定义表明任何一方参与者视图中的信息只能从自身输入和所获得的输出中获得, 即任何一方参与者视图中不包含除此之外的信息, 保证了在协议执行过程中, 任何一方得不到其他方的私有信息.因此, 要证明一个两方计算协议是安全的, 需要构造使得(1)和(2)式成立的模拟器 S 1 与 S 2 . 基本的保密内积协议 2 定义2 (内积协议)  假设有两个参与者, Alice秘密输入向量 X =( x 1 , …, x n ), Bob秘密输入向量 Y =( y 1 , …, y n ), 他们希望在不泄露彼此信息下进行合作计算 X · Y . 文中使用的内积协议为文献[ 18 18 ]设计的一个保密内积协议.由于该内积协议没有使用任何公钥加密算法, 因此达到了信息论安全. Hash函数 2 定义3   若函数 y = H ( x ), 满足以下3点: 1) 定长性:对任意长度的消息 x , 将其压缩成固定长度的消息 y ; 2) 单向性:已知 x , 求 H ( x )较为容易; 而已知 y , 求满足 H ( x )= y 的 x 在计算上不可行; 3) 抗碰撞性:寻找两个不同的消息 x 1 , x 2 , 使得 H ( x 1 )= H ( x 2 )在计算上不可行. 则称 H ( x )为Hash函数. 问题的描述与转化 1 本文研究的问题 2 问题1   保密判断空间中三个点是否共线: Alice有空间中的一个点 P ( x 1 , y 1 , z 1 ), Bob有空间中另外一个点 R ( x 2 , y 2 , z 2 ), 他们共同拥有空间中的一个点 Q ( x 3 , y 3 , z 3 ), 在不泄露双方隐私的前提下, Alice和Bob想要知道空间中这三个点是否共线. 问题2   保密判断空间中点与直线的位置关系: Alice有空间中的一个点 P ( x 1 , y 1 , z 1 ), Bob有空间中的一条直线 l : http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258538&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258538&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258538&type=middle .在不泄露双方隐私的前提下, Alice和Bob想要知道空间中点和直线的位置关系. 问题3   保密判断空间中点与平面的位置关系: Alice有空间中的一个点 P ( x 1 , y 1 , z 1 ), Bob有空间中的一个平面 π : Ax + By + Cz + D =0.在不泄露双方隐私的前提下, Alice和Bob想要知道空间中点和平面的位置关系. 问题4   保密判断空间中直线与直线的位置关系:Alice有空间中的一条直线 l 1 : http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258542&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258542&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258542&type=middle http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258547&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258547&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258547&type=middle , Bob有空间中的另外一条直线 l 2 : http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258555&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258555&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258555&type=middle http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258562&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258562&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258562&type=middle .在不泄露双方隐私的前提下, Alice和Bob想要知道空间中两条直线的位置关系. 问题5   保密判断空间中直线与平面的位置关系:Alice有空间中的一条直线 l 1 : http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258568&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258568&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258568&type=middle http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258576&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258576&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258576&type=middle , Bob有空间中一平面 π : Ax + By + Cz + D =0.在不泄露双方隐私的前提下, Alice和Bob想要知道空间中直线和平面的位置关系. 问题6   保密判断空间中平面与平面的位置关系:Alice有空间中的一个平面 π 1 : A 1 x + B 1 y + C 1 z + D 1 =0, Bob有空间中的另外一个平面 π 2 : A 2 x + B 2 y + C 2 z + D 2 =0.在不泄露双方隐私的前提下, Alice和Bob想要知道空间中两个平面的位置关系. 问题的转化 2 空间中三个点是否共线问题可以转化为由这三个点组成的两个向量所张成的平行四边形面积问题; 而空间点与线, 点与面位置关系可以转化为由直线或平面上一点与空间中一点组成的向量和直线方向向量或平面法向量所张成的平行四边形面积问题; 空间中线与线的位置关系可以转化为两个方向向量张成的平行四边形面积问题；空间中线与面的位置关系可以转化为方向向量和法向量张成的平行四边形面积问题；空间中面与面的位置关系可以转化为两个法向量张成的平行四边形面积问题. 例如, 要解决本文的问题2:保密判断空间中点 P 与直线 l 的位置关系, 可以在直线 l 上任取两点 Q , R , 与空间点 P 分别形成向量 QP , QR , 将向量 QP 和向量 QR 张成的平行四边形面积记为 W , W 可分为以下两种情况，如 图 1 图 1 和 图 2 图 2 所示. 1) 如果两者张成的平行四边形的面积 W =0, 则点在直线上; 2) 如果两者张成的平行四边形的面积 W ≠0, 则点在直线外. 因此, 要判断空间中点与直线的位置关系, 只需保密判断两者张成的平行四边形面积是否为0即可. 保密计算两向量张成的平行四边形面积 2 已知Alice持有向量 a =( a 1 , b 1 , c 1 )和Bob持有向量 b =( a 1 , b 2 , c 2 ), 那么两者所张成的平行四边形的面积 W 可通过下面的行列式求出. http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258296&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258296&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258296&type=middle http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258303&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258303&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258303&type=middle 令 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258315&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258315&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258315&type=middle 则 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258580&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258580&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258580&type=middle 将上式中( a 2 , b 2 , c 2 )记成向量 α , ( A 1 , A 2 , A 3 )记成向量 β , 则 W =〈 α , β 〉.Alice已知 α 向量, β 向量可由Bob算出, 那么保密计算平行四边形面积, 可由Alice和Bob借助定义2(内积协议)完成.下面给出具体计算平行四边形面积的协议. 保密计算两向量张成的平行四边形面积协议 3 假设以下协议中所有的参与者都是在半诚实模型下, 网络之间传输都是公开信道. 协议1   保密计算两向量张成的平行四边形面积是否为0. 输入: Alice保密输入向量 a =( a 1 , b 1 , c 1 ), Bob保密输入向量 b =( a 2 , b 2 , c 2 ); 输出: Alice和Bob都知道向量 a 和向量 b 张成的平行四边形面积是否为0. 1) Alice计算 A 1 , A 2 , A 3 , 得向量 a =( A 1 , A 2 , A 3 ), Bob计算向量 b =( a 2 , - b 2 , c 2 ); 2) Alice和Bob执行定义2内积协议, 即: ① Alice和Bob共同商定一个 n × n /2的矩阵 C . ② Alice进行以下操作: (ⅰ) Alice随机产生一个维数为 n /2的向量 R , R =( R 1 , R 2 , …, R n /2 ). (ⅱ) Alice计算 A ′= C × R 和 A ″= A + A ′. (ⅲ) Alice发送 A ″给Bob. ③ Bob进行以下操作: (ⅰ) Bob计算 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258589&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258589&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258589&type=middle 和一个 n /2×1的矩阵 b ′, 其中 b ′= C T × b . (ⅱ) Bob发送 W ′和 b ′给Alice. ④ Alice进行以下操作: (ⅰ) Alice生成一个减法因子 W ″, http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258616&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258616&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258616&type=middle R i . (ⅱ) Alice计算所需内积 W , W = W ′－ W ″. (ⅲ) Alice将内积 W 发送给Bob. 3) 如果保密求内积的结果为零, 则向量 a 和向量 b 张成的平行四边形面积是为0;否则向量 a 和向量 b 张成的平行四边形面积都不为0. 分析   在协议1中, Alice将 A ″发送给Bob; Bob接收到的 A ″中有Alice生成的一个随机向量 R .因此, Bob不能得到Alice的任何信息; Bob将 S ′和 b ′发送给Alice, 由于 b ′= C T × b , 而 C 是一个不可逆矩阵, 因此Alice由 b ′得不到Bob的任何信息; 而且 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258622&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258622&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258622&type=middle , 它并不是两个矩阵相乘而是两个矩阵的对应位置上的数相乘之后相加的结果, 因此Alice由 W ′也得不到Bob的任何信息.整个协议既保护了Alice的隐私又保护了Bob的隐私. 安全性分析 3 定理1   协议1保密地判断两个向量张成的平行四边形面积是否为0. 证   通过构造满足(1)式和(2)式的模拟器 S 1 , S 2 来证明本定理.在该协议中 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258319&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258319&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258319&type=middle 假设 f 1 ( A , b )= f 2 ( A , b )=( W =0), 构造模拟器 S 1 , S 1 将( A , f 1 ( A , b ))作为输入, 进行以下步骤: 第一步: S 1 接受输入( A , f 1 ( A , b ))=( A , W =0)后, 随机选取一个向量 b ′使得 f 1 ( A , b )= f 1 ( A , b ′), 然后用( A , b ′)进行模拟.根据协议1, 输入的向量 A =( A 1 , A 2 , A 3 ), S 1 随机选取向量 b ′=( a 2 ′, b 2 ′, c 2 ′), 使得 A · b = A · b ′. 第二步:利用文献[ 18 18 ]中保密的内积协议计算 A · b ′的值. 第三步:如果得到的结果为零, 则两个向量张成的平行四边形面积为0, 将结果记为 C ′. 在本协议中: http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258329&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258329&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258329&type=middle 因为 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258336&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258336&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258336&type=middle 所以 C = f 1 ( A , b ′)=( W =0), 因此可以得到 C = C ′. 又因为output 2 ( A , b )= f 2 ( A , b )=( W =0), 所以有: http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258341&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258341&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258341&type=middle 同理, 用类似的方法可以构造模拟器 S 2 , 使得: http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258351&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258351&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258351&type=middle 证毕. 其他协议 1 本节将协议1作为基础协议, 进一步判断空间中三点共线, 点与线, 点与面, 线与线, 线与面, 面与面的位置关系.假设以下协议中所有的参与者都是在半诚实模型下, 网络之间传输都是公开信道. 协议2   保密判断空间中三个点是否共线. 输入: Alice保密输入空间中的一个点 P ( x 1 , y 1 , z 1 ), Bob保密输入空间中另外一个点 R ( x 2 , y 2 , z 2 ), 他们共同拥有空间中的一个点 Q ( x 3 , y 3 , z 3 ). 输出: Alice和Bob都知道空间中 P , Q , R 这三个点是否共线. 1) Alice保密计算 QP =( x 1 － x 3 , y 1 － y 3 , z 1 － z 3 ), Bob保密计算 QR =( x 2 － x 3 , y 2 － y 3 , z 2 － z 3 ). 2) 调用协议1, Alice和Bob共同计算: http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258356&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258356&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258356&type=middle 3) 如果最终结果 W 为零, 即由向量 QP 和 QR 张成的平行四边形面积为零, 则空间中这三点共线; 否则其他情况空间中这三点都不共线. 分析   在协议2中, 调用了协议1, 与协议1惟一不同的是在第一步Alice和Bob均自己计算了 QP =( x 1 - x 3 , y 1 - y 3 , z 1 - z 3 )和 QR =( x 2 - x 3 , y 2 - y 3 , z 2 - z 3 ), 而并没有进行交互, 因此双方不会知道对方的任何信息, 故该协议隐私性与协议1相同. 协议3   保密判断空间点与空间直线的位置关系. 输入: Alice保密输入空间中的一个点 P ( x 1 , y 1 , z 1 ), Bob保密输入空间中的一条直线 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258363&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258363&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258363&type=middle 输出: Alice和Bob都知道空间中点 P 在直线 l 上或点 P 在直线 l 外. 1) Bob在直线上任取两点 Q ( x 0 , y 0 , z 0 )和 R ( x 2 , y 2 , z 2 ), 并计算 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258371&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258371&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258371&type=middle 2) 调用协议1, Alice和Bob共同计算 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258379&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258379&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258379&type=middle 3) Bob计算 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258385&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258385&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258385&type=middle 如果最终的结果为零, 即由向量 QP 和 QR 张成的平行四边形面积为零, 则点 P 在直线 l 上; 否则其他情况点 P 在直线 l 外. 分析   在协议3中, Alice和Bob调用了协议1, 隐私性和安全性与协议1相同.该方案保护了各方的隐私, 所以协议安全. 协议4   保密判断空间点与空间平面的位置关系. 输入: Alice保密输入空间中的一个点 P ( x 1 , y 1 , z 1 ), Bob保密输入空间中的一个秘密平面 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258402&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258402&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258402&type=middle 输出: Alice和Bob都知道空间中点 P 在平面 π 内或点 P 在平面 π 外. 1) Bob任取空间平面上一点 Q ( x 0 , y 0 , z 0 )和法向量上一点 R ( x 2 , y 2 , z 2 ). 2) 调用定义2内积协议, Alice和Bob共同计算: http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258411&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258411&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258411&type=middle 如果计算结果为零, 即点 P 和点 Q 之间距离为零, 即点 P 和点 Q 重合, 则点 P 在面 π 内，终止协议; 如果计算结果不为零, 则转入下一步. 3) Bob计算| QR | 2 =( x 2 － x 0 ) 2 +( y 2 － y 0 ) 2 +( z 2 － z 0 ) 2 和 W ′=| QP |·| QR |. 4) 调用协议1, Alice和Bob共同计算 W ″=| QP × QR |. 5) Bob计算 W = W ″－ W ′, 如果最终的结果为零, 即由向量 QP 和 QR 张成的平行四边形面积不为零且形状为矩形, 则点 P 在平面 π 内; 否则点 P 在平面 π 外.如 图 3 图 3 ~ 5 5 所示. 分析   在协议4中, 首先调用定义2内积协议, 保护了双方的隐私, 接着调用协议1, 也保护了双方的隐私, 最后, Bob计算 W = W ″－ W ′, 其中 W ″是调用协议1后得到的结果, 因此Bob不能从中得到Alice的任何信息.同样的, Alice也得不到Bob的任何信息.所以, 该方案保护了各方的隐私, 协议安全. 协议5   保密判断空间中直线与直线的位置关系. 输入: Alice保密输入空间中的一条直线 l 1 : http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258627&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258627&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258627&type=middle , Bob保密输入空间中的另外一条直线 l 2 : http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258634&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258634&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258634&type=middle . 输出: Alice和Bob都知道空间中两条直线的位置关系. 1) Alice拥有直线 l 1 上一点 P ( x 1 , y 1 , z 1 )和直线的方向向量 l 1 =( X 1 , Y 1 , Z 1 ); Bob拥有直线 l 2 上一点 Q ( x 2 , y 2 , z 2 )和直线的方向向量 l 2 =( X 2 , Y 2 , Z 2 ). 2) 调用定义2内积协议, Alice和Bob共同计算: http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258435&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258435&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258435&type=middle 如果得到的结果不为零, 即可由向量 l 1 , l 2 和 QP 张成平行六面体, 则直线 l 1 与 l 2 异面; 如果结果为零，即不能由向量 l 1 , l 2 和 QP 张成平行六面体, 则直线 l 1 与 l 2 共面, 进而转入下一个步骤. 3) 再次调用定义2内积协议, Alice和Bob共同计算| l 1 × l 2 |, 如果得到的结果不为零, 即两个方向向量张成的平行四边形面积不为零, 则直线 l 1 与 l 2 相交; 如果结果为零, 即两个方向向量张成的平行四边形面积为零, 则直线 l 1 与 l 2 平行或重合, 进而转入下一步骤. 4) Alice在直线 l 1 任选一点 R ( x 3 , y 3 , z 3 ), 计算 PR =( x 3 － x 1 , y 3 － y 1 , z 3 － z 1 ), 调用定义2内积协议, Alice和Bob共同计算| PQ × PR |, 如果得到的结果不为零, 即由 PQ 和 PR 张成的平行四边形面积不为零, 则直线 l 1 与 l 2 平行; 如果得到的结果为零, 即由 PQ 和 PR 张成的平行四边形面积为零, 则直线 l 1 与 l 2 重合.如 图 6 图 6 ~ 9 9 所示. 注1:在直线 l 1 与 l 2 异面的判定中, 可将空间向量 QP 和 l 1 , l 2 平移到共同起点，然后Alice和Bob共同计算 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258639&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258639&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258639&type=middle . 分析   在协议5中, 首先调用了两次内积协议，因此, 此时隐私安全性与协议1相同; 接着, Alice在直线 l 1 任选一点 R ( x 3 , y 3 , z 3 ), 计算 PR =( x 3 － x 1 , y 3 － y 1 , z 3 － z 1 ), 再次调用内积协议, 因此隐私安全性与协议1相同, 保护了Alice和Bob的隐私. 协议6   保密判断空间中直线与平面的位置关系 输入: Alice秘密输入空间中的一条直线 l : http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258663&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258663&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258663&type=middle , Bob秘密输入空间中一平面 π : Ax + By + Cz + D =0. 输出: Alice和Bob想要知道空间中直线和平面的位置关系. 1) Alice拥有直线 l 的方向向量 l =( X , Y , Z ); Bob拥有平面 π 的法向量 v =( A , B , C ). 2) 调用定义2内积协议，Alice和Bob共同计算| l × v |，如果结果为零，即方向向量 l 与法向量 v 张成的平四边形面积为零，即方向向量 l 与法向量 v 平行，则直线 l 与平面 π 垂直；如果得到的结果不为零，即方向向量 l 与法向量 v 张成的平四边形面积不为零，则空间直线 l 与平面 π 相交、平行或重合. 3) Alice任取空间直线上一点 P ( x 1 , y 1 , z 1 )，Bob任取空间平面上一点 Q ( x 0 , y 0 , z 0 )和法向量上一点 R ( x 2 , y 2 , z 2 ).调用定义2内积协议，Alice和Bob共同计算： http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258470&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258470&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258470&type=middle 4) Bob计算| QR | 2 =( x 2 － x 0 ) 2 +( y 2 － y 0 ) 2 +( z 2 － z 0 ) 2 和 W ′=| QP |·| QR |. 5) 调用协议1，Alice和Bob共同计算 W ″=| QP × QR |. 6) Bob计算 W = W ″－ W ′，如果最终的结果为零, 即由向量 QP 和 QR 张成的平行四边形面积不为零且形状为矩形, 则直线与平面平行或重合; 如果最终的结果不为零, 即由向量 QP 和 QR 张成的平行四边形面积不为零且形状为平行四边形不为矩形, 则直线 l 与平面 π 相交. 7) Alice有直线上一点 P ( x 0 , y 0 , z 0 ), 得到向量 a =( x 0 , y 0 , z 0 , 1), Bob拥有向量 b =( A , B , C , D ), 调用定义2的内积协议, 计算 a · b , 如果得到的结果为零, 则直线 l 与平面 π 重合; 否则, 其他情况直线 l 与平面 π 平行. 分析   在协议6中, 因为只调用了内积协议, 因此, 隐私性与协议1相同. 协议7   保密判断空间中平面与平面的位置关系 输入: Alice秘密输入空间中一平面 π 1 : A 1 x + B 1 y + C 1 z + D 1 =0; Bob秘密输入空间中另一平面 π 2 : A 2 x + B 2 y + C 2 z + D 2 =0. 输出: Alice和Bob都知道空间中两个平面的位置关系. 1) Alice拥有平面 π 1 的法向量 v 1 =( A 1 , B 1 , C 1 ), Bob拥有平面 π 2 的法向量 v 2 =( A 2 , B 2 , C 2 ). 2) 调用定义2内积协议, Alice和Bob共同计算| v 1 × v 2 |, 如果得到的结果不为零, 即法向量 v 1 和 v 2 张成的平行四边形面积不为零, 则平面 π 1 与 π 2 相交; 如果结果为零，即法向量 v 1 和 v 2 张成的平行四边形面积为零, 则平面 π 1 与 π 2 平行或者重合, 进而转入下一步骤. 3) Alice计算 H ( D 1 )= H 1 , Bob计算 H ( D 2 )= H 2 . 4) Alice和Bob比较 H 1 和 H 2 是否相等, 如果 H 1 = H 2 , 即 D 1 = D 2 , 则平面 π 1 与 π 2 重合; 否则其他情况平面 π 1 与 π 2 平行. 分析   在协议7中, 首先调用了内积协议, 在隐私安全性上与协议1相同.不同的是在步骤3中引入了Hash函数, 因为Hash函数是一个单向限门函数, 具有抗碰撞性的特点, 就算是知道 H ( D 1 )= H ( D 2 ), 也得不到 D 1 和 D 2 的任何信息.由于, Alice和Bob的隐私性都得到了保护, 因此, 该方案是安全的. 安全性分析 1 本节将根据2.1节的安全性模拟范例给出本文协议2~协议7的安全性证明.由于协议1和协议2的证明过程相似, 而协议1已经在3.3.3节中已经证明, 协议3到协议7的证明过程相似, 因此本节只给出协议3的安全性证明, 为了节省篇幅, 其他协议只给出安全性结论. 定理2   协议2保密地判断了空间中三点是否共线问题. 定理3   协议3保密地判断了空间中点与直线的位置关系. 证   通过构造满足(1)式和(2)式的模拟器 S 1 , S 2 来证明本定理.在该协议中 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258481&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258481&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258481&type=middle 假设 f 1 ( P , l )= f 2 ( P , l )= P ∈ l , 构造模拟器 S 1 , S 1 将( P , f 1 ( P , l ))作为输入, 进行以下步骤: 第1步    S 1 接受输入( P , f 1 ( P , l ))=( P , P ∈ l )后, 随机选取一条直线 l ′使得 f 1 ( P , l )= f 1 ( P , l ′), 然后用( P , l ′)进行模拟.根据协议3, 给定的点 P ( x 1 , y 1 , z 1 ), S 1 随机选取直线 l ′上两点 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258670&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258670&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258670&type=middle ( x 0 ′, y 0 ′, z 0 ′)和 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258678&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258678&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258678&type=middle ( x 2 ′, y 2 ′, z 2 ′), 并计算 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258487&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258487&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258487&type=middle 第2步   调用协议1, Alice和Bob共同计算 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258494&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258494&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258494&type=middle 第3步    S 1 计算 W ′= W 2 ′－ W 1 ′. 第4步   判断最终的结果 C ′. 在本协议中, http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258503&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258503&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258503&type=middle http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258512&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258512&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258512&type=middle 因为 P , http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258687&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258687&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258687&type=middle , http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258693&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258693&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258693&type=middle 均为随机选取的, 且 W 1 ′, W 2 ′, W ″是由 P , http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258699&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258699&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258699&type=middle , http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258704&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258704&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258704&type=middle 计算所得, 所以 W 1 , W 1 ′, W 2 , W 2 ″, W , W ′在计算上不可区分.由因为 C = f 1 ( P , l )= P ∈ l , 而 C ′= f 1 ( P , l ′)= P ∈ l ′, f 1 ( P , l )= f 1 ( P , l ′), 所以 C = C ′. 又因为output 2 ( P , l )= f 2 ( P , l )= P ∈ l , 所以 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258518&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258518&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258518&type=middle 同理, 用类似的方法可以构造模拟器 S 2 , 使得: http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258527&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258527&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258527&type=middle 证毕 定理4   协议4保密地判断了空间中点与平面的位置关系. 定理5   协议5保密地判断了空间中直线与直线的位置关系. 定理6   协议6保密地判断了空间中直线与平面的位置关系. 定理7   协议7保密地判断了空间中平面与平面的位置关系. 定理2的证明过程类似定理1，定理4到定理7的证明过程类似定理3, 为了节省篇幅, 这里不再一一赘述了. 效率分析与比较 1 本节将给出本文协议与文献[ 12 12 ~ 14 14 12~14 ]中协议在效率和性能上的比较和分析.对于三点共线问题, 我们将协议2与文献[ 12 12 ]进行比较; 对于空间中点线面位置关系问题, 由于问题转化的原因, 文献[ 14 14 ]并没有解决空间中点、线、面的所有位置关系问题, 因此, 为了便于比较, 本文仅与文献[ 13 13 ]、文献[ 14 14 ]中的保密判断点面、线面和面面位置关系的协议进行比较. 计算复杂度:上述文献的方案中有的使用了公钥加密算法, 有的未使用公钥加密算法, 而在整个执行过程中, 模幂、模乘和数乘的计算开销较大，因此为了便于比较, 将模幂、模乘和数乘总个数和加解密总次数作为衡量计算复杂度的指标, 其他忽略不计.记模幂为 M e 2 , 模乘为 M N 2 , 数乘为 M . 通信复杂度:通常情况下, 衡量通信复杂度的指标是协议交换信息的比特数或通信轮数, 在多方保密计算中通常用轮数(round). 性能:以能解决问题的多少和安全性级别作为衡量性能的指标. 本文与现有文献[ 12 12 ~ 14 14 12~14 ]在三点共线、点面、线面和面面保密判定的效率比较如 表 1 表 1 , 性能比较如 表 2 表 2 . 2 问题 2 方案 2 计算复杂度 通信复杂度 操作运算总次数 加解密总次数 通信轮数(round) 2 三点共线 文献[ 12 12 ] 18 M e 2 +11 M N 2 16 11 6 本文协议2 7 M N 2 0 3 3 点面问题 文献[ 13 13 ] 40 M e 2 +20 M N 2 +8 M 16 3 文献[ 14 14 ] 16 M N 2 0 5 本文协议4 13 M N 2 +4 M 0 5 3 线面问题 文献[ 13 13 ] 12 M e 2 +6 M N 2 +6 M 28 4 文献[ 14 14 ] 24 M N 2 0 3 本文协议6 15 M N 2 +4 M 0 6 3 面面问题 文献[ 13 13 ] 36 M e 2 +18 M N 2 +18 M 48 4 文献[ 14 14 ] 24 M N 2 0 3 本文协议7 6 M N 2 0 3   在性能比较中, “√”代表可以判定位置, 关系; “×”代表不能判定位置关系. 2 方案 2 安全性 6 解决的问题 三点共线 点线 点面 线线 线面 面面 文献[ 12 12 ] 计算性安全 √ × × × × × 文献[ 13 13 ] 计算性安全 × √ √ √ √ √ 文献[ 14 14 ] 信息论安全 × × √ × √ √ 本文方案 信息论安全 √ √ √ √ √ √ 从 表 1 表 1 可以看出, 虽然本文协议6比文献[ 13 13 , 14 14 ]的通信复杂度高, 但是从计算复杂度来看, 本文协议2、协议4、协议6和和协议7均优于文献[ 12 12 ~ 14 14 12~14 ]中的方案.因此, 本文方案与现存方案相比效率较优. 从 表 2 表 2 可以看出, 文献[ 14 14 ]与本文方案均达到了信息论安全, 但是文献[ 14 14 ]仅能解决空间中点面、线面和面面3种位置关系问题, 而我们的方案可以一次性解决空间中三点共线和点线面位置关系问题.除此之外, 文献[ 12 12 , 13 13 ]仅达到计算性安全, 而本文方案达到了信息论安全.因此, 本文方案与已存方案相比, 能解决的问题更加广泛而且到达了信息论安全. 总结和开放性问题 1 保密判断空间中三点共线和点线面位置关系问题均属于安全多方计算中的空间几何问题, 还有许多问题都可以归于此类问题, 因此研究它们具有重要的意义.在已有的方案中由于转化方法的问题使得之前的方案不仅效率较低、适用范围有限, 而且多利用公钥加密, 安全性级别不高.本文首先将空间中位置关系问题转化为由两向量所张成的平行四边形面积问题, 接着设计了保密计算两向量张成的平行四边形面积协议, 然后基于此协议解决了空间中三点共线和点线面位置关系的保密判定问题.在本文的协议中, 没有使用任何公钥加密算法, 达到了信息论安全；而且由于转化方法的巧妙, 使得本文的方案效率相对较优，适用范围更广. 本文仅研究了三维的两个向量张成的平行四边形面积问题，并将它应用于空间位置的保密判断，而对于大于三维的向量如何保密判断其张成的平行四边形面积问题及其应用并没有研究，这个问题将是我们进一步的工作. 参考文献 YAO A C. Protocols for secure computations[C]// Proceedings of 23 rd IEEE Symposium on Foundations of Computer Science . Washington, D C: IEEE, 1982: 160-164. DOI: 10.1109/SFCS.1982.38 http://dx.doi.org/10.1109/SFCS.1982.38 . BISKUP J, FLEGEL U. On pseudonymization of audit data for intrusion detection[C]// International Workshop on Designing Privacy Enhancing Technologies: Design Issues in Anonymity and Unobservability , New York: Springer-Verlag, 2000: 161-180. SAMANTHULA B K, ELMHDWI Y, HOWSER G, et al. A secure data sharing and query processing framework via federation of cloud computing[J]. Information Systems , 2015, 48 (C) : 196-212.DOI:10.1016/j.is.2013.08004. 杨静, 赵家石, 张建沛, 等.一种面向高维数据挖掘的隐私保护方法[J].电子学报, 2013, 41 (11):2187-2192. DOI:10.3969/j.issn.0372-2112.2013.11.012. YANG J, ZHAO J S, ZHANG J P, et al .A Privacy preservation method for high dimensional data mining[J]. Chinese Journal of Electronic , 2013, 41 (11):2187-2192.DOI:10.3969/j.issn.0372-2112.2013.11.012(Ch). KAMM L. Privacy-preserving statistical analysis using secure multi-party computation [D]. Vlikooli : University of TARTU, 2015: 50-54. http://hdl.handle.net/10062/45343 LI C, LIN B G. Privacy-preserving point-inclusion two-party computation protocol[C]//2013 IEEE Fifth International Conference on Computational and Information Sciences ( ICCIS ). Washington, D C: IEEE Computer Society, 2013: 257-260. DOI: 10.1109/ICCIS.2013.75 http://dx.doi.org/10.1109/ICCIS.2013.75 . 王挺, 罗文俊.安全多方计算在空间几何问题中的应用[J].计算机系统应用, 2015, 24 (1):156-160. DOI:10.3969/j.issn.1003-3254.2025.01.029. WANG T, LUO W J.Applications of secure multi-party computation in space geometry problems[J]. Com puter Systems & Applications , 2015, 24 (1): 156-160. DOI:10. 3969/j.issn.1003-3254. 2025.01.029(Ch). QIN J, DUAN H W, ZHAO H W, et al. A new lagrange solution to the privacy-preserving general geometric intersection problem[J]. Journal of Network and Computer Applications , 2014, 46 (1):94-99.DOI:10.1016/j.jnca.2014.08.004. 张静, 罗守山, 杨义先, 等.保护私有信息的点包含协议研究[J].通信学报, 2016, 37 (4):87-95.DOI:10.11959/j.issn.1000-436x.201675. ZHANG J, LUO S S, YANG Y X, et al .Research on the privacy-preserving point-in-polygon protocol[J]. Journal on Communications , 2016, 37 (4):87-95.DOI:10.11959/j.issn.1000-436x.201675(Ch). LIU L, CHEN X, LOU W, et al. A secure three-party computational protocol for triangle area.[J]. International Journal of Information Security, 2016, 15 (1): 1-13. DOI:10.1007/978-3-319-08344-5_6. 陈振华, 李顺东, 黄琼, 等.云外包计算中空间位置关系的保密判定[J].计算机学报, 2017, 40 (2):351-363. DOI:10.11897/SP.J.1016.2017.00351. CHEN Z H, LI S D, HUANG Q, et al .Privacy-preserving determination of spatial location-relation in cloud computing[J]. Chinese Journal of Computers , 2017, 40 (2): 351-363.DOI:10. 11897/SP.J.1016.2017.00351(Ch). 左建祥, 杨晓莉, 李顺东, 等.三点共线的保密判断问题及其应用[J].密码学, 2016, 3 (3):238-248.DOI:10.13868/j.cnki.jcr.000124. ZUO J X, YANG X L, LI S D, et al .Privately determining protocol on three points are collinear and its applications[J]. Journal of Cryptologic Research , 2016, 3 (3):238-248. DOI:10.13868/j.cnki.jcr.000124(Ch). 罗永龙, 黄刘生, 荆巍巍, 等.空间几何对象相对位置判定中的私有信息保护[J].计算机研究与发展, 2006, 43 (3):410-416. LUO Y L, HUANG L S, JING W W, et al . Privacy protection in the relative position determination for two spatial geometric objects[J]. Journal of Computer Research and Development , 2006, 43 (3): 410-416(Ch). LI S D, WU C Y, WANG D S, et al. Secure multiparty-computation of solid geometric problem and their applications[J]. Information Sciences , 2014, 282 : 401-413. GOLDREICH O. Foundations of Cryptography: Basic Applications [M]. London: Cambridge University Press, 2004: 599-729. GOLDREICH O, MICALI S, WIGDERSON A. How to play ANY mental game[C]// Proceedings of the 19 th Annual ACM Conference on Theory of Computing . New York: ACM, 1987: 218-229. DOI: 10.1145/23395.28420 http://dx.doi.org/10.1145/23395.28420 . GOLDREICH O. Secure multi-party Computation(draft)[DB/OL]. [2017-06-03] . http://www.eisdow.weizmann.ac.il/voded/pp.html http://www.eisdow.weizmann.ac.il/voded/pp.html . 1998. CLIFTON C, KANTARCIOGLU M, VAIDYA J, et al. Tools for privacy preserving distributed data mining[J]. ACM Sigkdd Explorations Newsletter , 2002, 4 (2): 28-34. 10.14188/j.1671-8836.2018.02.009 TP309 whdxxblxb-64-2-155 国家自然科学基金资助项目(U1261114) 2017-08-06 2018-04-24 2020-11-30 版权所有© 2018 《武汉大学学报(理学版)》编辑部 Copyright © 2018 Journal of Wuhan University(Natural Science Edition). All rights reserved. 2018 武汉大学学报(理学版) 2 64