高维空间平行四边形面积的多方保密计算*

张卫国，陈　娓，孙　嫚

(西安科技大学 计算机科学与技术学院，陕西 西安 710054)



高维空间平行四边形面积的多方保密计算*

张卫国，陈娓，孙嫚

(西安科技大学 计算机科学与技术学院，陕西 西安 710054)

几何问题的安全多方计算在保密位置判断、保密数据查询等方面有着重要的应用价值。但目前大多数几何问题的研究主要集中在平面几何，很少涉及空间几何。文章从一个军事实际问题出发，首先利用两方置换协议和同态加密算法保密计算了空间几何中2个高维向量差的范数，并用模拟范例证明了此方案的安全性。接着，利用此方案设计了空间几何中平行四边形面积的保密计算协议。不同于以往的方案，协议使用了一个有关安全两方置换问题的转化技巧，避免了以往方案中出现的高次模指数运算，因此效率较高；由于方案不局限于三维向量，适合于任何高维向量，更具有普遍意义。

安全多方计算；同态加密；高维向量；空间几何；范数；面积

0　引　言

安全多方计算最早由Yao[1]提出，是指在不泄漏各方的输入数据(隐私性)的条件下，能正确完成输入数据的函数计算(正确性)。安全多方计算的特点使得人们能够最大限度的利用私有数据完成所需的计算任务而不破坏数据的隐私性。因此它在保密的科学计算[2]、保密数据挖掘[3-4]、保密的几何计算[5-6]等方面有着广泛的应用。

Goldwasser[7]曾预言安全多方计算所处的地位就如同公钥密码学10年前所处的地位一样重要，它是计算科学一个极其重要的工具，而实际应用才刚起步。因此丰富其理论将使它成为计算科学和现实应用中一个必不可少的工具。接着，Goldreich等人[8-9]给出了安全多方计算问题的通用解决方案，从理论上证明了一般的多方保密计算问题是可解的，并引入了安全多方计算的安全性形式化定义与模拟范例。但同时他们指出，由于效率问题，利用通用的解决方案解决安全多方计算问题虽在理论上可行，而在实际中并不可行，应该具体问题研究具体的解决方案。Goldwasser的预言和Goldreich等人的工作使得针对特定领域构造安全多方计算的高效解决方案，成为了现代密码学的研究热点之一。

Du等人[10]在前人的基础上，进一步研究了一些具体的安全多方计算问题及其应用，包括几何计算、科学计算、统计分析等问题。几何问题的保密计算是安全多方计算中一个很重要的组成部分。针对此，Atallah M J等人[5]研究了安全2点包含问题和安全两方交集问题。荆巍巍[11]研究了安全两方多边形相交问题。李顺东等人[12]研究了立体几何中点面、线面、面面的位置关系问题。而面积问题的安全多方计算是计算几何的一个分支，它要求参与方保密的求出共有面积，从而对相应的事物做出判断。比如以下的一个军事场景：

在军事太空合作项目中，A、B两国想向太空发射飞行器，以收集、传递军事信息，但他们不能确保飞行器能否安全可靠的飞行，如果能拥有对方的太空碎片分布图，就可以计算出飞行器进入太空后会有多大的空间面积能够安全可靠的飞行，但是大家为了各自的利益都不会向对方公开自己的数据。因此，A、B两国如何在不泄露各自的私有信息的前提下完成合作呢？

以上场景转化成数学模型就是空间四边形面积的安全计算问题，属于安全多方计算中的空间几何问题。但目前关于这方面的研究文献并不多。因此研究其理论意义对现实问题有着重要的应用价值。

1)相关工作。针对四边形面积的安全计算问题，即参与协议的两方分别持有一个向量，如何计算以这2个向量为邻边组成的四边形的面积。以往的学者们提出了一些解决方案。Das A S，Srinathan K等人[13]利用添加随机数的方法对原始数据进行隐藏，保证了信息的隐私性，并用Paillier加法同态加密的方法，保密计算了平面上的三角形面积。但存在的缺点是，点若是三维甚至高维的话，这个方案不再适用。2009年，鲁磊纪等人[14]提出了另一种解决方案，将面积的安全计算转化为平面上3点确定的行列式值的计算，也是利用Paillier加法同态加密体制，解决了此问题。但此方案存在和文献[13]方案中同样的问题。

以上方案在进行同态加密算法时，都用到了高次模指数运算，计算量较大，方案并不高效；此外，以上方案所涉及的空间维数有所限制，并不能计算任意高维空间的面积问题，因此方案并不具有广泛性。

2)文中贡献：①利用两方置换协议，将原来问题中所涉及的运算转化。这种转化技巧减少了以往方案中的高次模指数运算次数，只用到了低次模指数运算，提高了效率。②在将原问题运算转化成其他运算的基础上，设计了2个协议：设计了空间高维向量差的范数保密计算协议1；在协议1的基础上设计了空间四边形面积的保密计算协议2，从而解决了文中的实际问题。③文中的2个协议并不局限于三维向量，而适合于空间任何高维向量，更具有普遍意义。

1　预备知识

1.1安全多方计算的安全性定义

1.1.1半诚实参与者

安全多方计算的协议运行环境分为半诚实参与者模型和恶意攻击者模型[8-9]，半诚实参与者指协议方将诚实地执行协议，不会篡改输入和输出信息，但可能会保留计算的中间结果，试图推导出协议之外的信息或者他人的信息。

1.1.2半诚实模型下的安全性定义

Goldreich[8-9]利用比特承诺和零知识证明理论设计了一个编译器，这个编译器可以将在半诚实参与者条件下保密计算函数f的协议π自动生成在恶意参与者条件下也能保密计算f的协议π′.新的协议π′可以迫使恶意参与者以半诚实方式参与协议的执行，否则就会被发现。因此大多数情况下，我们只设计半诚实模型下的协议。当我们设计出所需要的半诚实模型下的安全多方协议时，只要按照Goldreich[8-9]的通用转化方法就可以将原协议转化为恶意模型下的新协议。基于这一结论，文中也只给出半诚实模型下的协议和相应的安全性模拟范例。

设f(x,y)为概率多项式函数，π是计算f的协议，设Alice拥有x，Bob拥有y，他们要在不暴露x,y的前提下，合作计算函数f(x,y)=(f1(x,y),f2(x,y))。计算的目的是为了让Alice和Bob分别得到函数f的2个分量f1(x,y),f2(x,y)。Alice在执行协议π的过程中所得到的视图记为view1(x,y)，输出记作output1(x,y)；同理，Bob的视图记为view2(x,y)，输出记作output2(x,y)。Goldreich在文献[9]中给出计算不可区分性的半诚实参与者的安全两方计算的定义，表述如下。

定义1我们说协议π保密地计算了f(x,y)，如果存在概率多项式时间模拟器S1与S2使得以下2式同时成立

(1)

(2)

此定义说明了任何一方参与者视图中的信息只能从自己输入和所获得的输出中得到，即说明任何一方参与者视图中不包含额外的信息，这样就保证了在协议执行过程中，任何一方得不到其他方的私有信息。因此要证明一个两方计算协议是保密的，就必须构造使得式(1)和式(2)成立的模拟器S1与S2.

1.2同态加密

同态加密的概念是Rivest，R.L.，Adleman，L.，Dertouzos，M.L.等人[15]1978年提出的。同态加密的特殊性质使我们可以直接对密文进行某些运算来代替对明文的运算取得同样的效果，这样不影响明文数据的机密性。同态加密方法在云计算和多方保密计算中都将发挥重要作用。

Paillier同态加密算法在文献[16]中给出。该算法具有下述性质

E(x,y)=E(x)+E(y)，

E(x·y)=(E(x)y)，

1.3两方安全置换协议

两方安全置换问题(SecureTwo-PartyPermutationProblem)：Alice有一个秘密向量X=(x1,x2,…,xn)，Bob有一个置换函数π和一个秘密向量Y=(y1,y2,…,yn).Alice需要得到π(X+Y)，Alice不能了解π与Y的任意值yi，Bob不能了解X的任意值xi.

文献[17]给出一个基于同态加密方案的两方安全置换协议

图1安全置换协议

Fig.1Secure two-party permutation protocol

2　空间高维向量差的范数

2.1问题的描述及转化

2.1.12个向量差的范数

Alice持有n维向量A=(a1,a2,…,an)，Bob持有n维向量B=(b1,b2,…,bn).Alice和Bob在不告诉对方向量的情况下，要计算出个向量差的范数

‖A-B‖=

2.1.2问题的转化和解决

于是得到2个向量差范数的平方

2.2具体协议

以下协议假设所有的参与者都是在半诚实模型下，网络之间传输都是公开信道。

输入：Alice保密输入n维向量A=(a1,a2,…,an)，Bob保密输入n维向量B=(b1,b2,…,bn)

输出：Alice得到‖A-B‖

1)Alice和Bob调用2.3小节的基本两方置换协议使Alice得到π(A+B)=(ai+bi,an+bn,…,aj+bj)，π是Bob拥有的置换函数。

2)Alice可以计算出

3)Bob将计算的结果发送给Alice，Alice将会计算出‖A-B‖2，从而得到‖A-B‖.

虽然国库集中支付制度推行了十几年，但是还有一些高校在财务管理体系上面不能与时俱进，在观念上仍停留在传统的阶段。在新的集中支付制度下，高校应长远发展考虑，充分认识我国进行国库集中支付改革的意义及国库集中支付制度的优越性，注重财务管理体系的重新构建，加强财务管理人员对新政策的学习，提升专业实践操作，从而对国库集中支付流程有很好的掌握。此外，政府主管部门要加强国库集中支付制度的宣传力度，引导高校在工作上的协调和配合，共同构建完善的财务管理系统，促进我国教育事业的健康发展。

3　高维空间平行四边形面积

3.1问题的描述及转化

3.1.1问题的描述

Alice有一个n维向量A=(a1,a2,…,an)，Bob有一个n维向量B=(b1,b2,…,bn)，由向量A与向量B可以构成一个空间平行四边形(如图2，为了直观，这里只给出平面图)。Alice和Bob在不告诉对方向量的情况下，要求此空间平行四边形的面积。

图2　空间向量形成的平行四边形Fig.2　Parallelogram formed by spatial vector

3.1.2问题的转化和解决

由于平行四边形可以分为2个全等的三角形，因此我们只需求出其中一个三角形的面积，即可得平行四边形的面积。

3.2具体协议

协议2保密计算高维空间平行四边形的面积

输入：Alice保密输入n维向量A=(a1,a2,…,an)，Bob保密输入n维向量B=(b1,b2,…,bn)

输出：由向量A与向量B构成的空间高维平行四边形的面积S

1)Alice和Bob调用协议1使Alice得到2个向量差的范数‖A-B‖，即c.

3)Alice计算出p(p-a)(p-b)(p-c)，开根号即得S△，此时可得S=2S△.

4)Alice把结果告诉Bob.

分析：在执行协议的过程中，Alice在调用协议1时得到了c，即‖A-B‖，又得到了b=‖B‖，这2个方程中，有n个未知数(b1,b2,…,bn)(n≥3)，因此，Alice不能推出Bob的信息。

4　安全性分析

本节应用2.1节的安全性模拟范例证明文中2个协议的安全性。由于协议2和协议1证明过程相似，并且协议2是以协议1为基本协议设计得到，安全性依靠协议1保障，因此以证明协议1安全性为主，对于协议2，只给出了安全性结论。

定理1协议1保密计算高维空间向量差的范数。

证明：通过构造满足(1)和(2)的模拟器S1,S2来证明本定理。S1工作过程如下

3)计算

在本协议中：view1(A,B)={A,π(A+B),‖A+B‖,‖A‖,‖B‖,‖A-B‖}

令S1(A,‖A+B‖)={A,π(A+B),‖A+B′‖,‖A‖,‖B′‖,‖A-B′‖}

因为‖A-B′‖=‖A-B‖，所以，

定理2协议2保密计算高维空间平行四边形的面积。

用类似的方法可以证明定理2，这里不再赘述。

5　效率分析与比较

由于协议1是协议2的基础协议，因此本节只给出协议2和引言中的相关文献[13-14]在计算复杂性、通信复杂性以及性能方面的分析和比较。

计算复杂度：由于这些方案使用的都是公钥加密算法，而公钥加密算法中运算较高的是模指数运算，因此以模指数运算的个数作为衡量计算复杂性的指标。为了便于比较，统一其它方案中模指数运算的规模为Me，文中方案进行的是二次模指数运算，因此记模指数运算规模为M2.文献[13]中进行了2次高次模指数运算，记作2Me；文献[14]进行了4次高次模指数运算，记作4Me；而协议2进行了3n次二次模指数运算，记作3nM2.由于文献[13-14]中的向量都是二维，而文中向量是n维(n≥3)。若文献[13-14]也进行了高维计算，那么需要的运算分别为2nMe和4nMe，一般情况下，Me≥M2.因此协议2的计算复杂度较低。

通信复杂度：衡量通信复杂度的指标用协议交换信息的比特数，或者用通信轮数，在多方保密计算研究中通常用轮数。文中方案和所比较的方案[13-14]通信复杂度相同。

性能：在文中中以各个协议是否适合于空间几何作为衡量性能的指标。

表1　文中协议与现有方案的比较

从表1可以看出，以往方案都用到了高次模指数运算，高次指数运算的运算量很高，而文中协议用到的是二次模指数运算，运算量大降低，因此文中方案效率较高。此外，文中协议不仅在立体几何里适用，也能应用到任何高维空间里，因此更具有普遍意义。

6　结　论

几何问题是安全多方计算中很重要的组成部分，而面积计算又是几何问题中一个具体的问题，现实中很多场景都能归结于此。针对面积问题，已存在的方案中都用到了高次模指数运算，效率比较低下。此外，当信息(点的坐标)是高维(大于二维)的时候，以往的方案不再适用。针对于此，首先设计了高维向量差范数的安全多方计算协议，然后基于此协议，设计了空间平行四边形面积保密计算协议，从而解决了场景中的军事问题。设计的协议仅使用了二次模指数运算，避免了高次模指数运算，因此方案效率较高；由于文中方案不局限于三维向量，适合于任何高维向量，更具有普遍意义。

References

[1]Yao A C.Protocols for secure computations[C]//Proceedings of 23rd IEEE Symposium on Foundations of Computer Science，1982： 160-164.

[2]Du W L，Atallah M J.Privacy-preserving cooperative scientific computations[C]//Proceedings of 14th IEEE Computer Security Foundations Workshop Lecture，2001： 273-282.

[3]Agrawal R，Srikant R.Privacy-preserving data mining[C]//Proceedings of ACM International Conference on Management of Data and Symposium on Principles of Database Systems，2000：439-450.

[4]杨高明，杨静，张健沛.聚类的(A，k)-匿名数据发布[J].电子学报，2011，39(8)：1 941-1 946.

YANG Gao-ming，YANG Jing，ZHANG Jian-pei.Achieving(alpha，k)-anonymity via clustering in data publishing[J].Acta Electronica Sinica，2011，39(8)： 1 941-1 946.

[5]Atallah M J，Du W L.Secure multi-party computational geometry[C]//Lecture Notes in Computer Science 2125.NY：Springer，2001：165-179.

[6]Shundong L，Yiqi D.Secure two-party computational geometry[J].Journal of Computer Science and Technology，2005，20(2)：258-263.

[7]Goldwasser.Multi-party computations： past and present[C]//Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing，1997： 1-6.

[8]Goldreich O，Micali S，Wigderson A.How to play ANY mental game[C]//Proceedings of the 19th Annual ACM Conference on Theory of Computing，1987： 218-229.

[9]Goldreich O.Foundations of cryptography：basic applications[M].London： Cambridge University Press，2004.

[10]Du W L，Atallah M J.Secure multi-party computation problems and their applications： A review and open problems[C]//Proceedings of New Security Paradigms Workshop 2001，2001： 11-20.

[11]荆巍巍.安全多方计算中若干基础协议及应用的研究[D].合肥：中国科学技术大学，2008.

JING Wei-wei.Research on several basic protocols and applications of secure multi-party computation[D].Hefei：University of Science and Technology of China，2008.

[12]Shundong L，Chunying W，Daoshun W，et al.Secure multiparty computation of solid geometric problems and their applications[J].Information Sciences，2014，282： 401-413.

[13]Das A S，Srinathan K.Privacy preserving cooperative clustering service[C]//Advanced Computing and Communications，2007.ADCOM 2007.International Conference on.IEEE，2007：435-440.

[14]鲁磊纪，黄宏升，方治.隐私保护的计算三角形面积协议[J].电脑知识与技术，2009，33(5):9 168-9 170.

LU Lei-ji，HUANG Hong-sheng，FANG Zhi.A privacy-preserving protocol on calculating the area of triangle[J].Computer Knowledge and Technology，2009，33(5):9 168-9 170.

[15]Rivest R L，Adleman L，Dertouzos M L.On data banks and privacy homomorphisms[J].Foun-dations of Secure Computation，1978，4(11)： 169-180.

[16]Paillier P.Public-key cryptosystems based on composite degree residuosity classes[C]//Lecture Notes in Computer Science 1592.NY： Springer，1999： 223-238.

[17]Du W，Atallah M J.Privacy-preserving cooperative statistical analysis[C]//Computer Security Applications Conference，2001.ACSAC 2001.Proceedings 17th Annual.IEEE，2001：102-110.

Secure multi-party computation of high-dimensional spatial parallelogram area

ZHANG Wei-guo，CHEN Wei，SUN Man

(CollegeofComputerScienceandEngineering,Xi’anUniversityofScienceandTechnology,Xi’an710054,China)

Secure multi-party computation of the geometric problems is significant to privacy-preserving location estimation，data query，etc.But most of the existing literatures of geometric problems have focused on plane geometry，while few have addressed spatial geometry.In this paper，motivated from a military problem，we first compute securely the norm of high-dimensional vector difference using homomorphic encryption and secure two-party permutation protocol，and further prove the security of this scheme with simulation paradigm.Then，we design the privacy-preserving protocol of the area of parallelogram in spatial geometry using this scheme，so as to solve our real problem.Unlike the previously known，our scheme adopts a technique of conversion about secure two-party permutation protocol，which avoids high-order modular exponentiation in other known schemes.It makes our scheme efficient；In addition，our scheme is suitable for any high-dimensional vector except three-dimensional one，which makes our scheme more universal than others.

secure multiparty computation；homomorphic encryption；high-dimensional vector；spatial geometry；norm；area

10.13800/j.cnki.xakjdxxb.2016.0515

1672-9315(2016)05-0697-06

2016-01-19责任编辑：高佳

国家自然科学基金(U1261114)

张卫国(1964-)，男，陕西渭南人，教授，E-mail:chenwei_xust@163.com

TP 309

A