高效安全两方计算基础理论及关键技术研究

发布时间：2018-04-05 05:18

  本文选题：安全两方计算　切入点：茫然传输　出处：《山东大学》2017年博士论文

【摘要】：近年来,随着计算机网络技术的不断发展,以及云计算、大数据、物联网等新兴技术的广泛应用,网络安全日益成为国家、政府、个人关注的热门话题。鉴于当下国内外各类隐私泄露事件的出现,人们的数据隐私保护意识日益增强,数据安全已成为全球网络化进程中必须解决的问题。值得庆幸的是,密码学为数据保护提供了丰富、强有力的手段,除机密性、隐私性外也涵盖了诸如完整性、认证性等安全因素。因此,密码学在保护网络世界的数据安全中必然起到不可替代的作用。安全多方计算(Secure Multi-Party Computation,SMPC)是现代密码学领域的一个重要理论基础和研究分支,其考虑的是分布式计算场景下的安全计算问题。分布式计算涉及到许多独立而又相互连接的计算设备,他们希望共同执行某些任务的计算。安全多方计算的目标就是使得参与方能够以一种"安全"的方式执行这样的分布式计算。这里对于安全的理解,最直观的就是保护各个参与方的输入隐私性以及输出正确性。其中,隐私性意味着每个参与方通过自己得到的输出以及自己的输入信息,不能推测出其他人的任何输入信息。而输出正确性则保证了任务是被正确计算的。就计算任务而言,安全多方计算既包括如投币、广播等简单任务,也包括如电子投票、电子拍卖、匿名交易等复杂的实际应用问题。事实上,安全多方计算可视为一般密码学协议的研究,任何密码学协议都可以包括在安全多方计算的理论模型之中。由此可见,对于安全多方计算的深入研究,无论从基础理论,亦或应用协议等,都能极大地促进密码学的发展。从1982年姚期智先生提出百万富翁问题至今,安全多方计算的发展经历了兴盛、平静、再兴盛这样一个发展历程。早期的研究主要集中于安全多方计算的可行性理论研究,密码学者们给出了许多优美的理论成果,表明任意的分布式计算任务在一定条件下均可以实现安全计算。这一时期,关于安全模型、形式化证明方法、通用协议构造的研究在理论上逐步完善,但这些理论成果距离实用相距甚远。近十年以来,安全多方计算迎来了又一个春天。主要表现在以下两个方面:其一,实用化安全多方计算协议设计的进展,使人们看到了安全多方计算应用于解决实际问题的希望,因而引起较为广泛的关注;其二,云计算环境为安全多方计算应用于隐私保护下的数据处理提供了应用背景。当前安全多方计算的研究主要包括其自身的基础理论研究、高效协议的构造以及在其他学科领域的交叉应用研究。本文主要研究高效安全两方计算(Secure Two-Party Computation,STPC)相关基础理论以及应用。安全两方计算是多方计算的一种特殊情况,其只包含两个参与方,较之于多方计算存在固有的优势,最主要的就是体现在高效性上。此外,现实世界中的诸多应用仅涉及两个实体,安全两方计算能更好地运用到这些应用中去。鉴于越来越多的人对于使用安全两方计算来解决实际问题有着浓厚的兴趣,我们的研究核心就是如何设计真正高效的安全两方协议,从而加快安全多方计算从理论走向实践的步伐。当然,本文的研究属于密码学基础理论研究,我们关心的是所设计的密码协议能够满足的密码学安全特性以及实现上的理论可行性,为实用协议的设计与实现奠定理论基础。我们不关心这些协议的具体实现以及部署,而注重严格的安全性证明,即在相应的安全模型下给出形式化的安全性证明,这也是密码学中可证明安全的基本要求。我们的研究包括安全两方计算基础协议构造、安全两方计算通用协议构造、云辅助安全两方计算协议构造以及针对具体应用的安全两方计算协议构造。在安全多方计算基础工具方面,主要研究茫然传输协议(Oblivious Transfer,OT)在标准恶意敌手模型下的高效构造;在针对任意功能函数(Functionality)的通用协议构造中,主要研究基于Yao混乱电路的两方安全计算协议与cut-and-choose技术的结合,从而抵抗恶意敌手攻击;在新型安全计算中,主要研究云辅助安全两方计算的安全模型以及协议构造;在具体应用方面,主要针对隐私保护的模式匹配问题,研究高效安全的模式匹配协议。具体地,本文的研究内容主要包括以下四个方面:1.茫然传输协议是安全多方计算以及密码学领域的基础原语之一,被广泛应用在许多密码协议中。传统的1-out-of-2茫然传输协议(OT21)涉及发送方和接收方,其中发送方持有一对秘密信息,接收方期望选择其中之一。安全性要求发送方不知道接收方的选择比特,且接收方仅获得渴望得到的一个信息。推及一般情况,k-out-of-n茫然传输协议(OTnk)则意味着接收方希望秘密地从接收方的n个消息中选择k个(当k=1时,即为OTn1)。对于茫然传输协议的研究主要在效率以及安全性。鉴于茫然传输协议被广泛用作其他密码协议的子协议,强安全性要求始终是研究的重点。本文在恶意敌手模型下,首次给出可以实现全模拟的OTn1协议,所构造的协议基于标准DDH(Decisional Diffie-Hellman)假设,且具有常数轮数,通信复杂度、计算复杂度仅与n线性相关。2.基于Yao混乱电路的通用两方安全计算协议最早仅在半诚实敌手模型下是安全的。考虑恶意敌手情况,虽然理论上有一个很完美的GMW编译器,能将一个半诚实安全的协议转变成一个抗恶意敌手的协议,但是其效率是难以忍受的。与GMW不同的,cut-and-choose技术可以避免使用复杂的零知识证明方法,构造更为高效的抵抗恶意敌手的通用两方安全计算协议。将cut-and-choose技术与Yao混乱电路结合,在这种新框架下,各种新的问题也应运而生。为了解决这些新问题,传统的密码学工具难以适用,这必然也催生出各种新型的密码学原语。本文针对cut-and-choose双向茫然传输协议(Cut-and-Choose Bilateral Oblivious Transfer,CCBOT)这一新型工具,首次在恶意敌手模型下基于标准DDH假设构造了一个安全的cut-and-choose双向茫然传输协议。该原语能实现混乱电路相关密钥一次性传输,因而可以显著提高通用两方安全计算协议的轮复杂度。本文提出的协议新构造,避免适用cut-and-choose技术以及承诺方案,轮数、通信量以及计算量均达到常数级别。3.云计算的兴起给数据处理带来了全新的形式,其庞大的存储和计算资源使得计算外包成为一种趋势。云辅助安全多方计算考虑在安全多方计算场景中增加一(或多)个没有输入和输出的云服务器,他们承担其他参与方的部分计算任务,协助协议的完成。通过这种方式,参与方实体的计算量会大大减少,协议也变得更加高效。本文主要研究云辅助安全两方计算的安全模型以及协议的构造,针对OTnk协议,首次构造了云服务器辅助的OTnk协议。所构造协议在半诚实云服务器情况下是安全的,且效率较之于以前的的协议更高效。4.隐私保护逐渐成为诸多现实应用所考虑的核心问题之一,譬如机器学习、社交网络等。这些应用所涉及到的基本算法或协议大多数都可以使用安全两方计算来描述。本文主要研究隐私保护的模式匹配协议。该协议涉及两个参与方,一方持有一个与匹配的模式,一方持有文档,协议的目的是返回成功匹配的结果,且不泄露其他任何信息。精确模式匹配的另一个变种为近似模式匹配问题,即要求两个相似的模式能够匹配成功,其被广泛应用与基因匹配、人脸识别、音乐检索等问题中。本文在半诚实敌手模型下设计了一个安全的精确模式匹配协议,主要基于秘密分享和茫然传输两个基本工具。此外,本文将上述协议在云辅助模型下扩展为近视模式匹配协议,该协议将大量的计算任务外包至云服务器,协议效率较之于之前的协议有很大提升。
[Abstract]:Security Multi - Party Computing ( SMPC ) is an important theoretical foundation and research branch in the field of modern cryptography . This paper mainly focuses on the basic theory of security two - party computing , the construction of efficient protocols and the cross - application research in other disciplines . i.e . , otn1 ) . In order to solve these new problems , this paper presents a new type of secure cut - and - choose technology , which is based on standard DDH . In this paper , the above - mentioned protocol is extended to a near - sightedness pattern matching protocol under the cloud - assisted model , and the protocol packs a large amount of computing tasks to the cloud server , and the protocol efficiency is greatly improved compared with the previous agreement .

【学位授予单位】：山东大学
【学位级别】：博士
【学位授予年份】：2017
【分类号】：TP309
，

本文编号：1713375