安全多方空间两平行直线间距离计算*

于金霞，赵翠平，张 静,2，汤永利+

1.河南理工大学 计算机科学与技术学院，河南 焦作 454000

2.北京交通大学 计算机与信息技术学院，北京 100044

安全多方空间两平行直线间距离计算*

于金霞1，赵翠平1，张 静1,2，汤永利1+

1.河南理工大学 计算机科学与技术学院，河南 焦作 454000

2.北京交通大学 计算机与信息技术学院，北京 100044

为提高三维空间两平行直线间距离协议的计算效率，基于安全两实数和平方（secure square of two real numbers sum，SSTS）计算协议与Paillier同态加密算法（Paillier homomorphic encryption algorithm，PHEA）分别提出了三维空间两平行直线间的距离计算协议。SSTS协议利用空间任一点到直线的距离推导出三维空间两平行直线间的距离，通过安全两实数和平方计算协议构造辅助数据来隐藏自己的具体数据；PHEA协议通过Paillier同态加密算法将自己直线方程的系数隐藏，能与对方进行交流计算，但不会泄露自己的具体数据；两个协议均能保密地计算出三维空间两平行直线间的距离。分别证明了两个协议的正确性，并利用模拟范例证明了两个协议的安全性。最后，对SSTS协议和PHEA协议与现有协议进行比较分析，结果表明，新协议有较低的计算复杂性和通信复杂性，比现有协议至少降低了50%。

隐私保护的计算几何；空间距离；安全两实数和平方；同态加密；模拟范例

1 引言

随着互联网的快速发展，陌生用户之间的合作计算变得越来越重要，企业和组织机构既要在合作计算交流信息的过程中保密自己的有价值数据，又要通过整合资源获得利益，在此背景下安全多方计算应运而生。安全多方计算最初是图灵奖获得者Yao[1]提出的，经过了Goldreich等人的发展[2]，逐渐成为现代密码学及电子商务等众多应用领域的重要研究课题之一。安全多方计算（secure multi-party computation，SMC）是信息社会隐私数据保护的核心技术，是指两个或多个参与者在不泄露各自输入的隐私数据情况下，能够利用这些隐私数据参加保密计算，共同完成某项计算任务。安全多方计算在大数据安全与隐私保护[3-6]、基因序列[7-9]、数据挖掘[10]、密钥分配、科学计算等方面得到应用广泛。

基于隐私保护的计算几何是安全多方计算领域重要研究内容之一，在商业、军事和保密图像处理等方面拥有广泛的应用前景[11]和潜在的应用价值。目前已经有一些重要的研究成果：在平面几何方面，Du等人[12]利用置换协议和安全两方点积协议不仅提出了平面上两条直线的相交判定问题和凸包的相交问题，而且给出了解决此类问题有用的知识模块，但是函数求值时可能产生信息泄露。文献[13]针对Du的算法进行了修改，但当用户输入的隐私数据需要保护时，对传统算法做简单改进也不能满足要求，对此提出半诚实模型下计算几何中关于线段最核心的算法——叉积协议，此协议不仅可以用于解决保护私有信息的计算几何问题，而且可以用于解决秘密比较等一般的安全多方计算问题，但对方可以恶意输入虚假数据或者随意终止协议运行。文献[14]针对Du的两线段相交计算复杂性高的问题提出一种高效的不经意传输协议，并将高效不经意传输协议扩展到判定两个任意多边形和两个任意几何图形相交问题。文献[15-18]研究了点包含问题，文献[15]中的协议只使用于一些简单多边形域，文献[16]中的协议只使用于圆域，文献[17]研究了点与椭圆之间的关系，文献[18]研究了点是否在一个凸多边形内。由于文献[15-18]都具有局限性，文献[19]基于角旋转法提出了保护隐私的任意多边形点包含两方计算协议，并给出正确性和安全性证明，但此协议计算效率低。文献[20]所提协议不仅可以判定点与任意多边形的包含问题，而且比现有协议更加高效和安全，但是基于半诚实模型的，是不切实际的。文献[15-18]研究的都是点包含问题，但在实际应用中具有局限性。文献[21]研究了点与曲线关系的隐私保护协议，解决了在不泄露任何信息的情况下和在不同情形下如何确定点与曲线位置关系的问题。文献[22]研究了安全两方圆计算协议，并利用这些协议解决了保护私有信息的圆与圆的位置关系和圆与直线的位置关系判定问题。以上研究仅局限于平面对象，对更为复杂的空间问题并未涉及。文献[23]对平面线段相交问题进行了研究和扩展，利用点积协议和比较相等协议设计了保护私有信息的对应成比例判定协议，解决了空间几何对象相对位置判定问题，但此协议是在两方安全环境下提出的，具有较高的计算复杂度；多数保护私有信息的几何对象相对位置协议侧重于定性研究，文献[24]则定量对线、面之间的角度及线线之间的距离问题进行更深入的研究，构建出三维空间线、面夹角协议和线、线距离协议，有效降低了计算复杂度，并且可用于解决更多的其他计算几何问题，但协议是基于半诚实模型的，在恶意模型下对这些问题的协议分析和设计都非常复杂。文献[11]研究了空间几何中四面体的体积、点到平面的距离、直线与平面关系和两平面关系的多方安全问题及其应用，并利用模拟范例证明协议是安全的，但仍有许多计算几何问题需要研究。文献[25]研究了空间两平行直线间的距离问题，但计算复杂度和通信复杂度很高。

本文针对三维空间两平行直线间的距离问题提出了两个新的安全计算协议：SSTS（secure square of two real numbers sum）协议基于安全两实数和平方协议的方法解决了空间两平行直线间距离问题的安全多方计算，PHEA（Paillier homomorphic encryption algorithm）协议基于Paillier的同态加密算法高效解决了空间两平行直线间距离问题的安全多方计算。经过理论分析，SSTS协议在计算复杂度和通信复杂度上比现有解决方案的复杂度至少降低了50%，并证明了其正确性和安全性。在SSTS协议的基础上，进一步提出了更加安全高效的解决方案——PHEA协议。

2 预备知识

2.1 安全两实数和平方计算协议

协议1安全两实数和平方计算[22]。

Alice和Bob各有1个实数n1和n2,Alice和Bob希望在不泄露各自的私有输入信息时，保密地计算(n1+n2)2。经计算，Alice得到r1,Bob 得到r2,使得r1+r2=(n1+n2)2。

步骤2 Alice和Bob利用退化的一维安全两方点积协议计算n1∙n2：Alice得到R1，Bob 得到R2，使得R1+R2=n1∙n2。

2.2 同态加密方案

同态加密方案[26]在云计算和安全多方计算中发挥着不可替代的作用，是公钥加密方案中的一种。同态加密的特质可以采用对密文进行运算代替对明文的某些运算并取得同样的效果，而不影响明文数据的保密性。本文运用的是Paillier加密方案[27]的加法同态Ek(x)·Ek(y)=Ek(x+y),从加法同态性的性质得E(x)m=E(mx)。

2.3 Paillier加密方案

密钥产生：

（1）随机选取两个素数p和q，且满足gcd(pq,(p-1)(q-1))=1。

（2）计算n=pq和λ=lcm(p-1,q-1)。

加密/解密：

对于明文m(m∈Zn)，选择随机数r(r∈Z∗n)。

加密，c=gmrnmodn2。

解密，m=L(cλmodn2)umodn。

2.4 安全性

假设Alice与Bob都是半诚实的参与者，Alice拥有私有数据x，Bob拥有私有数据y，他们希望合作计算函数F∶(x,y)→ ( )f1(x,y),f2(x,y)而不泄露各自拥有的私有数据x和y。即Alice与Bob保证各自提供私有数据真实的前提下，严格按照协议的流程执行，不会中途退出或更改协议执行的步骤，但有可能会保留中间过程产生的结果用于推算对方的隐私数据。设P为计算函数F的协议，当输入为(x,y)时,记为Alice（Bob）在执行协议P的过程中所得到的消息序列，是,其中r1(r2)表示Alice（Bob）独立的硬币抛投结果；表示Alice（Bob）第i次收到的信息。记为Alice（Bob）得到的输出结果。

定义1（半诚实参与者的保密性[28]）对于一个函数F，如果存在概率多项式时间算法S1与S2（也称这样的多项式时间算法为模拟器）使得：

则称P保密地计算函数F（其中表示计算上不可区分）。

3 安全多方计算方案

3.1 空间两平行直线间距离问题的解决方案1

文献[25]虽然解决了空间两条平行直线间的距离问题，但是因为利用不经意传输协议，其计算复杂度和通信复杂度很高。本文根据几何学知识和安全两实数和平方计算协议理论提出了三维空间两平行直线间的距离计算协议。首先，该协议是针对三维空间两平行直线的标准式提出的；然后，根据三维空间点到直线的距离推导出三维空间两条平行直线间的距离；最后，通过安全两实数和平方协议计算出辅助数据，使Alice和Bob只知道他们隐私数据和的平方值，但永远不可能知道对方数据的具体值。此协议在通信安全保密中的优势：文献[25]空间两平行直线间距离的保密计算协议共调用6次不经意传输协议和6次点积协议，本文中SSTS协议只调用3次点积协议。文献[25]计算复杂度是12(m+1)lgk,而SSTS协议的计算复杂度是6mlgk；文献[25]通信复杂度是6(m+1)，而SSTS协议的通信复杂度是3m+1。总之，在计算复杂度和通信复杂度上，SSTS协议比文献[25]至少降低了50%。由于SSTS协议使用了安全两实数和平方计算协议，即点积协议，本协议的安全性主要依赖于点积协议。对于点积协议，在输入阶段，Alice和Bob分别通过随机值来掩盖其隐私向量；协议执行后，Alice和Bob都只能获得点积的计算值而无法得知对方的向量值。

假设空间有一点P1(x1,y1,z1)和一条直线，取直线t2上的一点M0(x2,y2,z2)，设M0P1与直线t2方向向量e=ai+bj+ck所成夹角为θ，则P1到直线e(t2)的距离应为。如图1所示，,则：

最外面“||”表示矢量取模。

对于三维空间两平行直线t1、t2，取t1上点P1(x1,y1,z1)，P1到t2的距离即为三维空间两条平行直线间的距离。

方案的主要思想是基于点到直线的距离保密地推导出三维空间两条平行直线间的距离。假设Alice拥有一条保密直线t1，在t1上选择一个保密的点P1(x1,y1,z1)，Bob拥有一条保密直线t2，他们分别利用安全两实数和平方计算协议计算辅助数据，最后计算出三维空间两条平行直线间的距离d。

协议2保密地计算出空间两平行直线间的距离（此协议记为SSTS协议）。

Fig.1 Distance of pointP1to straight linet2图1 点P1到直线t2的距离

输出：Alice与Bob合作计算t1和t2间的距离d。

步骤1 Alice在t1上选择一个保密的点P1(x1,y1,z1)，并计算(y1c-z1b)，Bob在t2上选择一个保密的点P2(x2,y2,z2)，并计算(z2b-y2c)；Alice与Bob分别利用安全两实数(y1c-z1b),(z2b-y2c)和平方计算协议，保密计算[(y1c-z1b)+(z2b-y2c)]2；经计算，Alice得到，Bob得到，使得。

步骤2 Alice计算(z1a-x1c),Bob计算(x2c-z2a);Alice与Bob分别利用安全两实数(z1a-x1c),(x2c-z2a)和平方计算协议，保密计算；经计算，Alice得到，Bob得到，满足。

步骤3 Alice计算(x1b-y1a)，Bob计算(y2a-x2b);Alice与Bob分别利用安全两实数(x1b-y1a),(y2a-x2b)和平方计算协议，保密计算；经计算，Alice得到，Bob得到，满足。

步骤5 Bob计算F,并将F发送给Alice。

定理1 SSTS协议能正确计算出三维空间两平行直线间的距离。

本文根据SSTS协议的具体验算过程如下。

Alice和Bob合作计算后得到的信息分别为Alice：。

Alice计算：

Bob计算：

Alice收到Bob的信息，计算：

Alice计算得到d，但Alice无法从d这个式子中得到关于Bob的任何信息。整个过程中没有泄露任何信息，并且完成了三维空间两平行直线间的距离计算，正确性得以证明。

定理2 SSTS协议能安全计算出三维空间两平行直线间的距离。

在SSTS协议中，首先假定参与的两方Alice和Bob是半诚实的，在协议执行后，Alice和Bob都只能获得自己辅助数据的值，无法得知对方的具体值。

在输入阶段，Alice的输入为保密直线l1，Bob的输入为保密直线l2。步骤1～步骤3，Alice和Bob先分别选择自己直线上一个保密的点；然后，分别计算出自己数据的值；最后，分别利用安全两实数和平方计算协议得到各自辅助数据的值。但Alice无法从中得到Bob值，Bob也无法从中得到Alice的值。步骤4，Alice对自己得到的辅助数据进行计算。步骤5，Bob也对自己得到的辅助数据进行计算，并将计算结果发送给Alice。步骤6，Alice收到Bob的信息后，计算得到M=E+F,E+F是Alice与Bob辅助数据的总和。总之，SSTS协议每一步都是隐私保护的，下面利用模拟器进行具体证明。

证明 通过构造出使式（1）和（2）成立的模拟器S1和S2来证明其安全性。

（1）首先构造模拟器S1使得式（1）成立。在SSTS协议中,其中t1、t2分别是Alice与Bob的输入。

S1的模拟过程如下：

步骤1S1接受( )t1,f1(t1,t2)作为Alice的输入，根据f1(t1,t2)的值，任意选定直线t2′，满足f1(t1,t2′)=f1(t1,t2)，记。

S1利用安全两实数和平方计算协议分别计算出的值。

步骤2S1根据的值计算出,进而计算出M′=E+F′。根据构造过程知道f1(t1,t2′)=f1(t1,t2)。

步骤3S1根据M′、G的值，计算出。

因为

（2）类似地，还可以构造S2使下式成立：

根据定义1可知此协议是安全的。 □

3.2 空间两平行直线间距离问题的解决方案2

SSTS协议解决了空间两条平行直线标准式的距离问题。现在研究空间两条平行直线交面式距离问题的解决方案，Alice拥有一条保密直线L1，Bob拥有一条保密直线L2,Alice与Bob希望在不泄露自己直线方程系数的情况下，保密计算出空间两平行线间的距离d。该方案的思想是基于Paillier同态加密方案提出了三维空间两平行直线间的距离计算协议。首先，该协议是针对三维空间两平行直线的交面式提出的；然后，利用Paillier同态加密方案将Alice直线方程的系数进行加密后发送给Bob，Bob利用Paillier同态加密方案进行计算后发送给Alice；最后，Alice和Bob合作计算出三维空间两平行直线间的距离。此协议在通信安全保密中的优势：由3.1节可知文献[25]计算复杂度是12(m+1)lgk，大约进行180次模指数运算，SSTS协议的计算复杂度是6mlgk，大约进行90次模指数运算；Pailler一次加密需要2次模指数运算，一次解密需要1次模指数运算，而PHEA协议共进行25次模指数运算。由3.1节可知文献[25]通信复杂度是6(m+1)，SSTS协议的通信复杂度是3m+1；而PHEA协议中通信轮数为3。总之，在计算复杂度和通信复杂度上，PHEA协议效率最优。PHEA协议主要利用了Paillier同态加密算法：（1）同态加密的特质可以用对密文进行运算代替对明文的某些运算并取得同样的效果，而不影响明文数据的保密性。（2）Paillier同态加密算法是基于计算和判断上的n次剩余问题的困难性，并给出了一种能够验证消息完整性的加密算法，在随机预言模型下证明了该加密算法能够抵抗适应性攻击。

协议3保密地计算空间两平行直线间的距离（此协议记为PHEA协议）。

输出：Alice与Bob合作计算L1和L2间的距离d。

步骤1设(G,E,D)是Paillier同态加密方案，k是设定的安全参数，Alice运行G(k)生成同态加密的公钥和私钥，Alice向Bob公布生成的公钥。

步骤2 Alice计算M1=(a1b2+a2b1),M2=(a1c2+a2c1),M3=(a1d2+a2d1),M4=2b1b2,M5=(b1c2+b2c1),M6=(b1d2+b2d1),M7=2c1c2,M8=(c1d2+c2d1),M9=(b1c2-b2c1)2+(c1a2-c2a1)2+(a1b2-a2b1)2，对Mi(i=1,2,…,8)用公钥进行加密，E(L)=E(Mi)，并将E(L)发送给Bob。

步骤3 Bob计算N1=(c3d4-c4d3),N2=(b3d4-b4d3),N3=(b3c4-c3b4),B=1/N23选 取 随 机 数R1、R2、R3、R4、R5、R6、R7、R8、R9,然后分别利用 Paillier同态加密方案计算出：

并将B发送给Alice。

步骤4 Alice收到Bob的消息后用私钥将Wi(i=1,2,…,9)进行解密，并计算出Q1、Q2、Q3。

利用解密得到的Wi(i=1,2,3,4,5,6,7,8,9)计算出Qi(i=1,2,3),其中，Q1=(W1-W2+W3)2,Q2=(W4-W5+W6)2,Q3=(W7-W8+W9)2,则,并将A发送给Bob。

定理3 PHEA协议能正确计算出三维空间两平行直线间的距离。

证明（1）当a1b2-a2b1≠0时，空间两平行直线间的距离公式：

（2）当a2c1-a1c2≠0时，空间两平行直线间的距离公式：

（3）当b1c2-b2c1≠0时，空间两平行直线间的距离公式：

A的代数余子式：

ni是平面πi的法向量。

下面根据PHEA协议以情况（3）为例进行具体验算。

Alice直线的密文信息：

Bob收到Alice的密文信息，计算：

Alice收到Bob的信息后，解密得到：

并计算：

但Alice无法从d这个式子中得到关于Bob的任何信息。整个过程中没有泄露任何信息，并且完成了三维空间两平行直线间的距离计算，正确性得以证明。 □

定理4 PHEA协议能安全计算出三维空间两平行直线间的距离。

为了能够证明PHEA协议在半诚实模型下的保密性，只需要去验证协议各方的输入输出，然后进行模拟分析。因为在PHEA协议中没有可信的第三方，所以只需从Alice和Bob的视角来分析其输入输出，并作出相应的保密性分析即可。

对于Alice，Alice的输入为保密直线l1，Alice收到Bob的消息，用私钥进行解密操作后，Alice得到的是一系列数字，但这些数字中并不包含Bob直线的任何信息值，仅仅是随机数。因此，从Alice的角度来讲满足隐私性的要求。

对于Bob，Bob的输入为保密直线l2，Alice对自己的隐私数据用公钥进行加密后发送给Bob，但Bob并不知道Alice的私钥，所以Bob无法获取Alice直线的任何信息。因此，从Bob的角度来讲满足隐私性的要求。

总之，PHEA协议对于Alice和Bob都是隐私保护的，下面利用模拟器进行具体证明。

证明 通过构造出使式（1）和（2）成立的模拟器S1和S2来证明其安全性。

（1）首先构造模拟器S1使得式（1）成立。

在解决方案2中：

其中，L1、L2分别是Alice与Bob的输入；E(L)是L的密文。

S1的模拟过程如下：

步骤1S1接受(L1,f1(L1,L2))作为Alice的输入，根据f1(L1,L2)的值，任意选定直线L2′，满足

S1分别计算出M1,M2,…,M9,B′的值。

步骤 2S1任意选取 9 个随机数R1′,R2′,…,R9′，使得R3′=R2′-R1′,R6′=R5′-R4′,R9′=R8′-R7′,用同样的方法加密Mi(i=1,2,…,8),并且分别计算出W1′,W2′,…,W9′,Q1′,Q2′,Q3′,A′的值。根据构造过程知道f1(L1,L2′)=f1(L1,L2)。

步骤 3S1根据A′、B′的值，计算出d′=A′∙B′,则为空间两条平行直线间的距离。

（2）类似地，还可以构造S2使下式成立：

4 复杂性分析

计算复杂性：文献[25]空间两平行直线间距离的保密计算协议共调用6次不经意传输协议和6次点积协议。本文SSTS协议共调用3次点积协议，PHEA协议进行了8次加密运算，9次解密运算。假设安全参数为m，一次不经意传输协议至少需要2lgk次模指数运算，一次点积协议至少需要2mlgk次模指数运算，文献[25]共需12(m+1)lgk次模指数运算。一般情况下当m＞5,k＞8时才能达到基本的安全级别，故至少需要180次模指数运算。本文SSTS协议至少需要6mlgk次模指数运算，Pailler一次加密需要2次模指数运算，一次解密需要1次模指数运算，PHEA协议共进行25次模指数运算。

通信复杂性：衡量通信复杂性的指标可以采用协议交换的比特数或通信轮数，在安全多方计算研究中通常用通信轮数来衡量计算复杂性。文献[25]通信轮数为6(m+1)次，本文SSTS协议通信轮数为3m+1次，PHEA协议通信轮数为3。各方案复杂性比较如表1所示。

Table1 Complexity comparison of schemes表1 各方案复杂性比较

因此本文协议计算效率和通信效率更高，适用范围更广。

5 结束语

在半诚实模型下，基于安全两实数和平方计算协议和Paillier同态加密方案分别提出了计算空间两平行直线间的SSTS和PHEA距离协议，有效降低了计算复杂度和通信复杂度，并且对SSTS和PHEA协议的正确性和安全性分别进行了证明。因为SSTS和PHEA协议都是基于半诚实模型的，当然还有不足之处，在恶意模型下对安全多方空间两平行直线距离协议进行研究和分析会比较困难，所以未来将继续对此进行探讨并推广到其他应用领域。

[1]Yao A C C.Protocols for secure computations[C]//Proceedings of the 23rd Annual Symposium on Foundations of Computer Science,Chicago,USA,Nov 3-5,1982.Washington:IEEE Computer Society,1982:160-164.

[2]Goldreich O,Micali S,Wigderson A.How to play ANY mental game[C]//Proceedings of the 19th Annual ACM Symposium on Theory of Computing,New York,May 25-27,1987.New York:ACM,1987:218-229.

[3]Kaushik M,Jain A.Challenges to big data security and privacy[J].International Journal of Computer Science and Information Technologies,2014,5(3):3042-3043.

[4]Bertino E.Big data-security and privacy[C]//proceedings of the 2015 International Congress on Big Data,New York,Jun 27-Jul 2,2015.Washington:IEEE Computer Society,2015:757-761.

[5]Thuraisingham B M.Big data security and privacy[C]//Proceedings of the 5th Conference on Data and Application Security and Privacy,San Antonio,USA,Mar 2-4,2015.New York:ACM,2015:279-280.

[6]Patil H K,Seshadri R.Big data security and privacy issues in healthcare[C]//Proceedings of the 2014 International Congress on Big Data,Anchorage,USA,Jun 27-Jul 2,2014.Washington:IEEE Computer Society,2014:762-765.

[7]Erlich Y,Narayanan A.Routes for breaching and protecting genetic privacy[J].Nature Reviews Genetics,2014,15(6):409-421.

[8]Xie Wei,Kantarcioglu M,Bush W S,et al.SecureMA:protecting participant privacy in genetic association metaanalysis[J].Bioinformatics,2014,30(23):3334-3341.

[9]Sandfuchs B.Privacy nudges:an introduction[M]//Akrivopoulou C M.Protecting the Genetic Self from Biometric Threats:Autonomy,Identity,and Genetic Privacy.Hershey,USA:IGI Global,2015:256-264.

[10]Lindell Y,Pinkas B.Secure multiparty computation for privacy-preserving data mining[J].Journal of Privacy&Confidentiality,2008,25(2):761-766.

[11]Li Shundong,Wu Chunying,Wang Daoshun,et al.Secure multiparty computation of solid geometric problems and their applications[J].Information Sciences,2014,282:401-413.

[12]Du Wenliang,Atallah M J.Privacy-preserving cooperative scientific computations[C]//Proceedings of the 14th Computer Security Foundations Workshop,Cape Breton,Canada,Jun 11-13,2001.Washington:IEEE Computer Society,2001:273-294.

[13]Luo Yonglong,Huang Liusheng,Jing Weiwei,et al.Privacypreserving cross product protocol and its applications[J].Chinese Journal of Computers,2007,30(2):248-254.

[14]Li Shundong,Dai Yiqi,Wang Daoshun,et al.Secure multiparty computations of geometric intersections[J].Journal of Tsinghua University:Science and Technology,2007,47(10):1692-1695.

[15]Atallah M J,Du Wenliang.Secure multi-party computational geometry[C]//LNCS 2125:Proceedings of the 7th International Workshop on Algorithms and Data Structures,Providence,USA,Aug 8-10,2001.Berlin,Heidelberg:Springer,2001:165-179.

[16]Li Shundong,Dai Yiqi.Secure two-party computational geometry[J].Journal of Computer and Technology,2005,20(2):258-263.

[17]Luo Yonglong,Huang Liusheng,Zhong Hong.Secure twoparty point-circle inclusion problem[J].Journal of Computer and Technology,2007,22(1):88-91.

[18]Luo Yonglong,Huang Liusheng.A secure protocol for determining whether a point is insider a convex polygon[J].Chinese Journal of Electronics,2006,15(4):578-582.

[19]Chen Li,Lin Bogang.Privacy-preserving point-inclusion twoparty computation protocol[C]//Proceedings of the 4th International Conference on Computational and Information Sciences,Shiyan,China,Jun 21-23,2013.Washington:IEEE Computer Society,2013:257-260.

[20]Li Shundong,Wang Daoshun,Dai Yiqi.Efficient secure multiparty computational geometry[J].Chinese Journal of Electronics,2010,19(2E):324-328.

[21]Liu Liang,Wu Chunying,Li Shundong.Two privacy-preserving protocols for point-curve Relation[J].Journal of Electronics,2012,29(5):422-430.

[22]Liu Wen,Luo Shoushan,Yang Yixian,et al.A study of secure two-party circle computation problem[J].Journal of Beijing University of Posts and Telecommunications,2009,32(3):32-35.

[23]Luo Yonglong,Huang Liusheng,Jing Weiwei,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.

[24]Zhong Hong,Sun Yanfei,Yan Feifei,et al.Privacy-preserving relative position calculation protocols for spatial geometric objects[J].Journal of Harbin Engineering University,2011,32(4):458-463.

[25]Xin Xin,Hao Lin,Tang Yu.Privacy-preserving computational protocol on minimum distance between two three-dimension parallel straight line[J].Application Research of Computers,2013,30(5):1530-1532.

[26]Frederick R.Core concept:homomorphic encryption[J].Proceedings of the National Academy of Sciences,2015,112(28):8515-8516.

[27]Wu Jiehong,Zhang Po,Shi Xiangbin.Research of MA protection based on addition-multiplication homomorphism and composite function technology[J].Journal of Chinese Computer Systems,2012,33(10):2223-2226.

[28]Reimer B,Fried R,Mehler B,et al.Brief report:examining driving behavior in young adults with high functioning autism spectrum disorders:a pilot study using a driving simulation paradigm[J].Journal of Autism&Developmental Disorders,2013,43(9):2211-2217.

附中文参考文献：

[13]罗永龙,黄刘生,荆巍巍,等.保护私有信息的叉积协议及其应用[J].计算机学报,2007,30(2):248-254.

[14]李顺东,戴一奇,王道顺,等.几何相交问题的多方保密计算[J].清华大学学报:自然科学版,2007,47(10):1692-1695.

[22]刘文,罗守山,杨义先,等.安全两方圆计算协议[J].北京邮电大学学报,2009,32(3):32-35.

[23]罗永龙,黄刘生,荆巍巍,等.空间几何对象相对位置判定中的私有信息保护[J].计算机研究与发展,2006,43(3):410-416.

[24]仲红,孙彦飞,燕飞飞,等.保护私有信息几何对象的相对位置计算[J].哈尔滨工程大学学报,2011,32(4):458-463.

[25]辛欣,郝林,汤瑜.空间两平行直线间距离的保密计算协议[J].计算机应用研究,2013,30(5):1530-1532.

[27]吴杰宏,张坡,石祥滨.基于加乘同态与组合函数技术的MA保护研究[J].小型微型计算机系统,2012,33(10):2223-2226.

2016-08,Accepted 2017-01.

Secure Multi-Party Computation on Spatial Distance Between Two Parallel Straight Lines*

YU Jinxia1,ZHAO Cuiping1,ZHANG Jing1,2,TANG Yongli1+
1.College of Computer Science and Technology,Henan Polytechnic University,Jiaozuo,Henan 454000,China
2.School of Computer and Information Technology,Beijing Jiaotong University,Beijing 100044,China
+Corresponding author:E-mail:yltang@hpu.edu.cn

To improve the computational efficiency of the distance between two three-dimension parallel straight lines,this paper proposes two protocols of a secure square of two real numbers sum protocol(SSTS)and Paillier homomorphic encryption algorithm(PHEA).Firstly,SSTS is to derive the distance between two three-dimension parallel straight lines by the distance from a point to a straight line,and it constructs auxiliary data to hide their own specific data by a secure square of two real numbers sum protocol.Secondly,PHEA uses Paillier homomorphic encryption algorithm to hide linear equation coefficient.Parties can communicate with each other,but will not reveal their specific data.Two protocols are confidential to calculate the distance between two three-dimension parallel straight lines.In addition,this paper proves the validity of two protocols,and proves the security by the simulation example.Finally,this paper analyzes the computation complexity and communication complexity of SSTS and PHEA with the existing protocol.The results show that the new protocols are at least 50%less than that of the existing protocol.

privacy-preserving computational geometry;space distance;secure square of two real numbers sum;homomorphic encryption;simulation paradigm

10.3778/j.issn.1673-9418.1608069

*The National Natural Science Foundation of China under Grant No.61300216(国家自然科学基金);the International Science and Technology Cooperation Program of Science and Technology Office of Henan Province under Grant No.152102410048(河南省科技厅国际科技合作计划);the Research of Basic and Advanced Technology of Henan Province under Grant No.142300410147(河南省基础与前沿技术研究);the Natural Science Research Project of Education Department of Henan Province under Grant Nos.12A520021,16A520013(河南省教育厅自然科学研究项目).

CNKI网络优先出版:2017-01-05,http://www.cnki.net/kcms/detail/11.5602.TP.20170105.0828.002.html

YU Jinxia,ZHAO Cuiping,ZHANG Jing,et al.Secure multi-party computation on spatial distance between two parallel straight lines.Journal of Frontiers of Computer Science and Technology,2017,11(11)：1764-1774.

A

TP309

YU Jinxia was born in 1974.She received the Ph.D.degree in artificial intelligence from Central South University in 2007.Now she is a professor at Henan Polytechnic University.Her research interests include artificial intelligence and information security,etc.

于金霞（1974—)，女，河南博爱人，2007年于中南大学获得博士学位，现为河南理工大学教授，主要研究领域为人工智能，信息安全等。

ZHAO Cuiping was born in 1989.She is an M.S.candidate at Henan Polytechnic University.Her research interests include information security and cryptology,etc.

赵翠平（1989—），女，河南商水人，河南理工大学硕士研究生，主要研究领域为信息安全，密码学等。

ZHANG Jing was born in 1978.Now she is an associate professor at Henan Polytechnic University.Her research interests include network and information security,secure multi-party computation,etc.

张静（1978—），女，河南焦作人，河南理工大学计算机科学与技术学院副教授，主要研究领域为网络与信息安全，安全多方计算等。

TANG Yongli was born in 1972.He received the Ph.D.degree in cryptology from Beijing University of Posts and Telecommunications in 2008.Now he is an associate professor at Henan Polytechnic University.His research interests include information security and cryptology,etc.

汤永利（1972—），男，河南孟州人，2008年于北京邮电大学获得博士学位，现为河南理工大学副教授，主要研究领域为信息安全，密码学等。