安全多方计算中若干计算几何协议的分析

《安全多方计算中若干计算几何协议的分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、安全多方计算中若干计算几何协议的研究要的研究任务，这也是我们研究的目的及意义。1.2研究现状与进展安全多方计算是研究一组互不信任的参与方之间在保护私有信息的前提下的合作计算问题，是目前国际密码学界的研究热点之一。安全多方计算问题最早由A.C.Yao于1982年提出：n个参与者P1,P2,⋯Pn要以一种安全的方式共同计算一个函数，这里的安全是指输出结果的正确性与输入信息、输出信息的保密性。具体地讲，每个参与者Pi有一个自己的保密输入信息Xi,并共同计算函数f(X1,X2,⋯,Xn)=(Y1,Y2,⋯,Yn)计算结束时，每个参与者Pi只能了解Yi,同时保

2、持各自Xi的隐私权。1987年，Goldreich,Micali和Wigderson在文献[10]中提出了可以计算任意函数的安全多方计算协议。1988年，文献[11]和文献[12]都证明了在信息论安全模型中安全多方计算的可解性，并分别指出了被动攻击与主动攻击情况下串通攻[13]击者数目的理论上界。1998年，O.Goldreich对其做了比较完整的总结。O.Goldreich指出：用通用协议来解决安全多方计算问题中的特殊实例是不可行的，应该针对具体的问题设计具体的安全多方协议。目前很多学者对安全多方计算进行了深入研究，产生了一些新的研究方向：保护隐私

3、的计算几何、保护隐私的统计分析、保护隐私的数据挖掘及保护隐私的信息检索等。保护私有信息的计算几何是指在分布式几何计算过程中，参与方在不泄露自己私有信息的前提下与其他参与方相互协作计算来得到正确结果。WenliangDu、Atallah在文献[4，5，14，15]中，提出了计算几何的很多特定问[15]题，并在这个领域提出了一个研究框架。在保护私有信息的几何计算领域，他们列出了五个重要的问题，分别是：交集问题、点包含问题、范围查询问题、最近点对问题和凸包问题。虽然不少学者对保护私有信息计算几何进行了大量的研究，也取得了很大的理论价值，但是这些研究目前还仅

4、局限于少数几个领域，并且现有的计算协议还远没有达到实用的程度。这是因为在目前的研究中，理论方法还不够完善，也存在着时间、空间以及通信的代价太高的问题，还不能很好的应用于解决实际问题。本文重点讨论了最近点对、集合交集、几何对象的位置求解等问题，期待找到更加高效实用的解决方案。-2-第一章绪论1.3本文的主要研究工作(1)最近点对问题介绍了问题模型以及现有的解决方案，提出了一种新的求解方案，并对安全性和复杂度进行分析，且和现有方案进行了性能比较。(2)集合交集问题回顾了目前的解决方案，针对存在的不足，提出了新的求解两方集合交集和三方集合交集的方案，并与现

5、有方案进行了性能比较。(3)几何对象的位置求解问题罗永龙等提出了该问题及初始解决方案，但只是定性研究了几何对象的相对位置判定，本文在其基础上进一步定量研究了几何对象的相对位置求解，提出具体的求解方案。(4)几何对象的多方协作计算问题本文把目前两方参与的几何对象计算扩展到多方参与的情况，使之更具有一般性；分析了判定三角形形状、四点是否共面等以及求解三角形面积、四面体体积等问题并设计了相应协议。1.4内容安排本文主要对安全多方计算中计算几何方面的问题进行了理论研究，并探讨其在特定领域的应用问题。全文内容共分七章论述。第一章介绍了安全多方计算的研究背景与研

6、究进展，指出了目前研究中存在的问题，同时给出本文的主要工作与安排。第二章介绍了安全多方计算的基本概念、研究模型、基本工具以及基础协议，包括同态加密方案、茫然传输协议、秘密比较协议、点积协议等。第三章研究了最近点对问题。基于Paillier同态加密算法，提出了一个新的求解方案。第四章研究了集合交集问题。基于点积协议提出了新的求解两方集合交集、三方集合交集的方案。第五章研究了几何对象的位置求解问题。基于点积协议提出了求解几何对象相对位置的方案。-3-安全多方计算中若干计算几何协议的研究第六章研究了几何对象的多方协作计算问题。主要讨论了判定三角形形状、四点

7、是否共面等以及求解三角形面积、四面体体积等问题并设计了相应协议。第七章对全文做了总结，提出了今后的进一步研究方向。1.5本章小结本章主要介绍了SMC的研究背景、意义、现状、进展以及本文的主要内容和内容安排。-4-第二章安全多方计算概述第二章安全多方计算概述介绍了安全多方计算的概念、模型，对模型中的参与方、攻击者、通信信道进行定义，给出文中的标准符号说明；最后介绍了基本工具以及基础协议，包括RSA密码、同态加密方案、茫然传输协议、秘密比较协议、点积协议等。2.1基本概念及定义2.1.1安全多方计算安全多方计算(SecureMulti-PartyComp

8、utation-SMC)是研究一组互不信任的参与方在保护私有输入信息的前提下的合作计算问题，它是目前国际密码