信息论安全的3个基础外包计算协议及空间位置关系保密判定

陈振华 昔路琪 史晓楠 聂靖靖

摘要：现存的安全几何计算协议大多采用公钥加密方法保护数据隐私，计算成本较大。当计算能力不强的用户解决复杂问题时，效率往往较低。针对这些问题，避开公钥加密的方法，而是利用矩阵论中一些特殊函数的性质和随机数混淆的方法来保护数据隐私，并且为了进一步提高效率，将大量的用户计算外包出去。在此基础上，首先设计了常用的3个基础向量外包计算协议，分别是安全外包计算的向量模长计算协议，向量内积计算协议和向量夹角计算协议，并利用模拟范例证明了协议的安全性，然后利用这3个基础协议进一步解决了现实意义中如何保密判断空间面与面位置关系的问题，并给出了具体协议。最后，通过理论分析与实验仿真显示：由于协议没有使用公钥加密的方法，因此达到了信息论安全;并且由于外包计算的使用，为用户节省了更多的計算成本，取得了比较高的效率;此外，协议能够解决的问题也更加广泛，可作为新的云计算技术的基础协议应用到安全多方计算的其它分支中。

关键词：安全多方计算;外包计算;内积协议;空间位置;信息论安全

中图分类号：TP 309

文献标志码：A

文章编号：1672 -9315（2019）06 -1049 -08

DOI：10. 13800/j.cnki. xakjdxxb. 2019. 0618

开放科学（资源服务）标识码（OSID）：

收稿日期：2019 -05 - 20

责任编辑：高佳

基金项目：国家自然科学基金（ 61872289）;广西密码学与信息安全重点实验室开放课题（GCIS201714）

第一作者：陈振华（1976 -），女，陕西宝鸡人，博士，副教授，E-mail：chenzhenhua@ snnu.edu.cn

通信作者：黄路琪（1996 -），女，山东平阴人，硕士研究生，E-mail：huanguqi_xust@ 163.com

0 引言

安全多方计算最早由Yao提出，是指各个参与方在不泄露各自输入隐私的情况下，能正确合作计算出某个问题。保护隐私的合作计算都可归为安全多方计算[1]，例如，保护隐私的数据挖掘[2-4]，统计计算[5-7]，机器学习[8-1O]，数据聚合[11-14]，外包计算[15-17]，和数据查询[18 -19]等。

安全几何计算是安全多方计算的一个重要分支，是指各参与方在保护各自数据隐私的情况下，共同计算一个几何问题。例如：投资公司A，B想要扩展市场，A想知道自己的投资范围是否在B的范围内，但B的计划是商业机密，而A也不想告诉B自己的投资计划，在不暴露各自商业机密的前提下，双方如何解决这个问题？

若将公司的投资计划看成平面区域，对应的数学模型是：保密判定空间中2个平面是否相交。而要判定此关系，需要先解决向量安全计算问题。外包计算是目前流行的一种计算模式，但服务器作为不可信第三方，可能会泄露用户隐私。因此，在利用外包服务的同时，如何保护各参与方数据隐私解决向量计算问题并进一步解决平面判定问题，成为目前一个较新的研究方向。

针对向量安全计算，以往的学者提出了一些解决方案。周素芳等人利用哥德尔编码和同态加密解决了向量线性组合计算问题，该方案使用了公钥加密，不是信息论安全，也不适用于外包计算[20]。陈振华等人提出了基于同态加密的向量内积外包计算协议。该协议适用于外包计算，但不是信息论安全且复杂度较高[21]。张卫国等人引入不可逆矩阵来保护数据隐私，计算了向量内积[22]，Li等人借助内积运算来判定空间位置关系[23]。虽然协议都达到了信息论安全，但并不适用于外包计算。

针对以上方案的不足，文中利用矩阵论中一些特殊函数的性质和随机数混淆的方法来保护数据隐私，并利用外包计算节省成本。在此基础上，设计了安全外包计算的向量内积、向量模长和向量夹角计算协议，并解决了空间面与面的保密位置判定问题。

1 模型简介

1.1 半诚实模型

安全多方计算的协议运行环境分为半诚实参与者模型和恶意参与者模型[24-29]。文中协议都建立在半诚实模型下，因此这里只给出半诚实模型定义。半诚实参与者是指协议方诚实地执行协议，不会篡改输入和输出信息，但可能会保留计算的中间结果，试图从中间结果和最后输出推导出协议之外的信息或者他人的信息。

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

外包计算中半诚实模型下的安全两方计算的模拟范例定义如下：设Alice拥有x，Bob拥有y，Server是外包服务器，f（x，y）为概率多项式函数;π是计算f的协议。Alice，Bob和Server要在不泄露x，y给任何一方的前提下，合作计算函数f（x，y）=

分析：在协议1中，Alice和Bob利用函数f的正交性，将对向量X和Y的内积计算转换成fX和fY的内积计算。又利用f的单向性对向量X和Y保护隐私，得到fX和fX，由于f具有单向性，因此任何人都不能得到初始输入X和Y.又因为随机数的加入，所以数据r1X，数据r2Y和随机数具有了不可区分性，因此保护了X和Y的隐私。此外，Alice和Bob利用随机数r1和r2混淆了fX和fy内积结果，由于结果中含有Alice和Bob的随机数乘积r1 r2，因此外包服务器无法获得真正的内积值。即使考虑合谋，由于Alice和Bob不可能合谋，因此外包服务器无法同时获得两方的随机数r1和r2，从而无法获得合谋条件下内积结果。即协议

1 保密地计算了向量的内积。

类似的方法可以分析协议2和协议3，得到类似结论。

3 安全性证明

在本节，应用2.2节的模拟范例我们给出以上3个协议的安全性证明，先证明协议1.

定理1协议1保密地外包计算了2个向量X和Y的内积。

证明 按照2.2节外包计算中半诚实模型下安全两方计算安全性的定义，需要构造表1中的5个模拟器Sl，S2，S3，S4和S5，由于文章篇幅有限，因此安全性证明只给出了模拟器S1的详细过程，其他模拟器可按同样的道理得到。

以上过程证明了Alice和Server合谋的视图只能从自身输入X，E（X），E（ Y）和所获得的输出fi（X，Y），E（X，Y）中得到，并没有包含Bob的信息。同理，Bob和Server合谋的视图也只能从自身的输入和输出中得到，并没有包含Alice的信息。因此证明了在外包计算过程中，即使Server与其中任何一方参与者合谋，也得不到另一方的信息。

证毕。

类似的方法可证明协议2和协议3的安全性，得到以下定理。

定理2协议2保密地外包计算了向量长度。

定理3协议3保密地外包计算了向量夹角。

4 效率分析与比较

本节给出在外包计算的模式下，保密判断空间面与面位置关系的协议及其效率分析比较。

协议4保密判断空间面与面的位置关系

由于协议4是依靠文中的协议1，协议3设计的，而第3节的安全性证明已经证明了协议1，协议3都是安全的，因此可以得到协议4也是安全的，这里不再详细证明。

由于文中和文献[21-23]都处理了空间面面位置关系问题，而文献[20]并没有处理该问题。因此就文献[21-23]处理的共同的面面位置保密判定协议做出比较和分析。为了方便比较，将模幂运算记为M_，模乘运算记为MN，乘法运算记为M，向量维数记为n，统一使用文献[21]的模数Ⅳ.整个协议执行过程中，计算开销比较大的是模幂运算，模乘运算，乘法运算，因此把这些运算总个数作为衡量计算复杂度的指标，其他忽略不计。

4.1 理论分析与比较

4.1.1 計算复杂度

文献[21]的面面位置关系保密判定（协议6），整个协议计算过程中调用了2次内积协议，用户加解密过程中使用了模幂和模乘运算，其运算总个数为2MN +18Me.

文献[22]的安全计算面与面的位置关系（协议5），整个协议计算过程中调用了4次内积协议，每调用一次内积协议，用户进行2次矩阵相乘，需16次乘法，因此运算总个数为64M.

文献[23]的保密判定面与面的位置关系协议（协议4），整个协议计算过程没有调用内积协议，而是进行了3个3阶矩阵行列式运算，和3个3维向量内积运算，即9个乘法运算，因此运算总个数为36M.

文中面面位置关系保密判定（协议4），整个协议计算过程需要调用1次保密计算夹角和1次保密计算内积协议，用户运算总个数8MN +6M.

4.1.2 通信复杂度

衡量通信复杂度的指标用协议交换信息的比特数，或者用通信轮数，在多方保密计算研究中通常使用轮数。

文献[21]的面面位置关系保密判定（协议6），整个协议计算过程中调用了2次保密计算内积协议和1次比较协议，内积协议每调用一次需要3轮交互，比较协议需要2次交互。则用户和外包服务器总共进行了8轮交互。

文献[22]的安全计算面与面的位置关系（协议5），整个协议计算过程中调用了4次内积协议，内积协议每调用一次需要2轮交互，用户之间总共进行了8轮交互。

文献[23]的保密判定面与面的位置关系协议（协议4），整个协议计算过程中没有调用内积协议，用户之间总共进行了2轮交互。

文中面面位置关系保密判定（协议4），整个协议计算过程调用了1次保密计算夹角协议和1次保密计算内积协议，分别需要进行5轮和3轮交互。则用户和外包服务器之间的总轮数为8轮。

4.1.3性能

以各个协议取得的安全性级别，是否适用于外包计算和能够解决的空间位置问题作为衡量性能的标准。以“√”代表协议能够解决的空间位置问题。

综合以上，得到文中协议4和文献[ 21 - 23]的效率比较见表2，性能比较见表3.

由文献[30]可知，1个模幂运算等价于logN个模乘运算。假设这里所有协议都采用和文献[30]同样的操作平台，可将表2中文献[21]方案的计算个数换算为2MN +36logNM.因此由表2可以看到，相比于文中协议4，以往的方案[21-23]计算开销较大。由于文中利用矩阵论中一些特殊函数心基础，为了方便其他复杂安全多方计算问题架构于此，因此文中协议1提供了外包模式下简洁的保密内积计算方案。这里仍采用和上文相同的标记符号，计算复杂度记为0，得到协议1在传统模式（非外包）下的计算成本为3MN +M，计算复杂度为0（1）;外包模式下计算成本为2MN+（n+1）M，计算复杂度为O（n），得到协议1在2种计算模式下的计算复杂性对比如图1所示。

从图1可以看出，未借助外包计算的内积协议（曲线1）不仅用户计算成本较大，且计算复杂度随着向量维数的增大呈线性增长，因此为了节省用户的计算成本，以按需付费的方式将保密内积计算外包出去。由于该部分的计算量已经由外包服务器计算，因此不再包含在用户计算成本之内，那么架构于此基础协议（即文中协议1）的协议4也的性质保护数据，并没有使用公钥加密的方法，因此计算复杂度和通信复杂度较低，更具有实践意义。从表3可以看出，方案相比以往的方案，不仅实现了信息论安全，也适合外包计算，并且所能处理的空间位置关系也更加广泛。

4.1.4 传统模式和外包模式下计算成本比较

由于保密内积计算是整个安全外包计算的核不需要保密计算内积，这样就极大地节省了用户的计算成本。

4.2 仿真实验

为了直观呈现以上协议的理论效率分析结果，在Java语言环境下将表2的4个协议编程实现。采用的计算机运行环境如下：操作系统为Windows 7旗舰版，CPU为Intel i5 - 5200U 2.20CHz，内存为4.00 GB.文中协议4和文献[21]协议6主要运算为模运算，而文献[22]协议5和[23]协议4的主要运算为乘法运算。因此分为2种情况进行分析比较，第一种是将文中协议4和文献[21]协议6进行效率比较（不同模数下的耗时）;第二种是将文中协议4和文献[22]协议5，文献[23]协议4进行效率比较（判断不同位置关系的耗时）。

1）將文中协议4和文献[21]协议6在不同模式下进行耗时比较。在实验中分别取不同的模数Ⅳ为143，437，899，1 517 bits，得到2个协议的平均耗时，如图2所示。

2）将文中协议4和文献[22]协议5，文献[23]协议4判断不同位置关系进行耗时比较，分别得到3个协议平行、相交、垂直、重合情况下的平均耗时，见表4.

从图2和表4可以看出，文中协议4的平均耗时低于文献[21]协议6，文献[22]协议5和文献[23]协议4的平均耗时。此外，从表4还可以看出文中协议4能判断的面面位置关系更多（文献[22]协议5不能判断面面重和，文献[23]协议4既不能判断面面重和，也不能判断面面垂直）。

综合以上实验结果，得到如下结论：无论理论分析还是实验分析，本文协议效率较高，而且能判断的空间位置关系更加广泛。

5 结论

1）利用矩阵论中一些特殊函数的性质和随机数混淆方法在外包计算下设计了3个基础的信息论安全向量计算协议，分别是安全外包计算的向量内积，向量模长和向量夹角计算协议。

2）利用这些基础协议解决了空间面与面位置关系保密判断问题，可进一步解决金融投资等实际问题。

3）将提出的保密判定面与面的位置关系协议与其他已有方案进行了理论分析和仿真实验比较。结果显示文中提出的方案效率更高，可判断的空间位置关系更加广泛。

参考文献（ References）：

[1]

Yao A C.Protocols for secure computations[Cl//Pro-ceedings of 23rd IEEE Symposium on Foundations ofComputer Science， Chicago， USA， 1982： 160 - 164.

[2]

Kantarciogu M ， Clifton C. Privacy-preserving distributedmining of association rules on horizontally partitioneddata[J] IEEE Transactions on Knowledge and DataEngineering ， 2004 ， 16 （ 9） ： 1026 - 1037.

[3]杨静，赵家石，张健沛，一种面向高维数据挖掘的隐私保护方法 [J]电子学报 ， 2013 （ 11 ） ： 2187 -

2192.

YANC Jing， ZHAO Jia-shi ， ZHANC Jian-pei. A privacypreservation method for high dimensional data mining[J] . Acta Electronica Sinica ， 2013 （ 11） ：2187 - 2192.

[4]

Kenthapadi K， Mironov I， Thakurta A. Privacy-preser-ving data mining in industry [ C ] //Companion Proceed-ings of the 2019 World Wide Web Conference. ACM，2019 ：1308 - 1310.

[5]

Kamm L， Bogdanov D ， Pankova A ， et al. Statistical anal- ysis methods using secure multi-party computation [ J ] .Cryptology and Information Security Series ，2015 ， （ 13 ） ：58 - 80.

[6] Duverle D A ， Kawasaki s ， Yamada Y ， et al. Privacy-pre- serving statistical analysis by exact logistic regression [C] //IEEE Symposium on Security and Privacy ， 2015.

[7]

Wen L D， Atallah M J. Secure multi-party computation problems and their applications ： a review and open prob-lems [C]//New Security Paradigms Workshop， ACM，2001 ：13 - 22.

[8]

Mohassel P ， Zhang Y. Secure M L ： A system for scalable privacy-preserving machine learning [ C ]//IEEE Sym- posium on Security and Privacy ， 2017 ： 19 - 38.

[9]

Dowlin N ， Giladbachrach R，Laine K ， et al. CryptoNets ： applying neural networks to encrypted data with highthroughput and accuracy [ C ] //International Conferenceon Machine Learning ， 2016 ： 201 - 210.

[10] Mohassel P， Rindal P. ABY3 ： a mixed protocol frame-work for machine learning [ C l//Proceedings of the2018 ACM SIGSAC Conference on Computer and Com-munications Security ， ACM ，2018 ：35 - 52.

[11]

Jung T， Mao X F， Li X Y， et al. Privacy-preserving dataagggregation without secure channel ： Multivariate polyno-mial evaluation [ C l//INFOCOM， 2013 ProceedingsIEEE. IEEE ， 2013 ： 2634 - 2642.

[12]

Groat M M ， Hey W ， Forrest S. KIPDA ： k-indistinguisha-ble privacy-preserving data aggre-gation in wireless sen-sor networks [ C ] //INFOCOM ， 2011 Proceedings IEEE.IEEE ，2011 ：2024 - 2032.

[13]

Ozdemir S， Peng M ， Xiao Y. PRDA ： polynomial re～7es-sion-based privacy-preserving data ag～Tegation for wire-less sensor networks [J] . Wireless Communications andMobile Computing ， 2015 ，15 （4） ：615 - 628.

[14]

Liu Y， Guo W， Fan C I ， et al. A practical privacy - pre-serving data aggregation （3PDA） scheme for smart grid[J] . IEEE Transactions on Industrial Informatics ， 2018 ，15 （3） ：1767 -1774.

[15]

Huang J J ， Juang W S， Fan C I， et al. Robust and priva-cy protection authentication in cloud computing [ J ] . In-temational Joumal of Innovative Computing ， Informationand Contr01，2013 ，9 （ 11） ：4247 - 4261.

[16] Wei L， Zhu H， Cao Z， et al. Security and privacy forstorage and computation in cloud computing [ J] . Infor-mation Sciences ， 2014 ，258 ：371 - 386.

[17]

Yang D ， Chen Y C ， Ye S. Privacy-preserving outsourcecomputing for binary vector similarity [ C ] //Internation-al Conference on Security with Intelligent Computingand Big-data Services. Springer， Cham， 2017： 161 - 169.

[18]

Samanthula B K， Elmehdwi Y， Howser C ， et al. A securedata sharing and query processing framework via federa- tion of cloud computing[ J] . Information Systems ， 2015 ，48 ：196 - 212.

[19]

Campos R， Dias G， Jorge A M， et al. Survey of temporalinformation retrieval and relatd applications [J] . ACMComputing Surveys（ CSUR） ， 2015 ，47 （ 2） ： 15.

[20]周素芳，竇家维，郭奕旻，等，安全多方向量计算[J].计箅 机学报 ， 2017 （ 5 ） ：1134 - 1150.

ZHOU Su-fang， DOU Jia-wei ， GUO Yi-min ， et al. Securemultiparty vector computation [ J ] . Chinese Journal ofComputers ，2017 ，40 （ 5） ：1134 - 1150.

[21]陈振华，李顺东，黄琼，等，云外包计算中空间位置关的保密判定[J] .计算机学报，2017，40 （2） ：351 - 363.

CHEN Zhen-hua， LI Shun-dong， HUANC Qiong， et al.Privacy-preserving determination of spatial location-rela-tion in cloud computing[ J] . Chinese Journal of Comput-ers ，2017 ，40（2） ：351 - 363.

[22]张卫国，孙嫂，陈振华，等.空间位置关系的安全多方计算及其应用[J].电子与信息学报，2016，38（9）：2294 - 2300.

ZHANG Wei-guo， SUN Man， CHEN Zhen-hua， et al.Se-cure multi-party computation of spatial relationship andits application[J].Journal of Electronics&InformationTechnology， 2016 ，38（9）：2294 - 2300.

[23]

LiS D，Wu C Y，Wang D S.Secure multiparty computa-tion of solid geometric problems and their applications [J]. Information Sciences， 2014 ，282（ 10）：401 - 413.

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

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

[ 25]

Katz J，LindellY.Introduction to modern cryptography[M].BocaRaton Florida： Chapman and Hall/CRC， 2014.

[26] Guo F，Susilo W， Mu Y.Introduction to security reduc-tion[M].Springer，2018.

[27]

Coldreich 0.Foundations of crypto～7aphy： basic applica-tions[M].London： Cambridge University Press， 2004.

[28]

Goldreich 0， Micali S，Wigderson A.How to play anymental game[C]//Proceedings of the nineteenth annualACM symposium on Theory of computing. ACM， 1987：218 - 229.

[29]

Hazay C， LindellY.Efficient secure two-party protocols：Techniques and constructions[M].Springer Science&Business Media.2010.

[30]

Lin H Y， Tzeng W G.An efficient solution to the mil-lionaires' problem based on homomorphic encryption[Cl//International Conference on Applied CryptogTa-phy and Network Security， Springer， Berlin， Heidelberg，2005 ，3531：456 -466.