安全多方计算中的理性公平研究毕业论文.doc 29页

'II贵州大学本科毕业论文（设计）第页安全多方计算中的理性公平研究毕业论文目录摘要IIIAbstractIV第一章绪论11.1研究的目的与意义11.2研究现状及发展趋势21.3论文章节安排3第二章基础知识42.1安全多方计算42.1.1基本定义42.1.2公平性52.2博弈论72.2.1标准式博弈72.2.2纳什均衡72.3基本工具82.3.1ShareGen函数82.3.2秘密共享9第三章基于ShareGen函数的理性公平多方计算113.1基于ShareGen函数的理性公平两方计算113.1.1ShareGen函数113.1.2协议公平性分析123.2基于ShareGen函数的理性公平多方计算133.2.1ShareGen函数133.2.2协议描述143.2.2协议公平性分析15第四章基于秘密共享的理性公平多方计算17 II贵州大学本科毕业论文（设计）第页4.1经典方案介绍174.1.1Shamir的秘密共享方案174.1.2Peterson可验证秘密共享方案174.1.3Gennaro的VSS协议184.2基于秘密共享的理性公平多方计算194.2.1协议描述194.2.2协议公平性分析21第五章结束语23参考文献24致谢25 IV贵州大学本科毕业论文（设计）第页安全多方计算中的理性公平研究摘要安全多方计算方面的研究目前在国内外都比较成熟了，从基本定义、概念到诸多安全计算协议的设计，很多学者都设计出了相应的协议。安全多方计算是由多方参与方通过信息交互来实现的，公平性是安全多方计算的一个必不可少的性质，是安全多方计算研究的一个重大课题。目前，在对安全多方计算的公平性的研究中，基于信息逐渐释放方法的研究方案相继被提出。但是，这些方案也只是或多或少地考虑了部分公平性，完全公平性仍然是当前的一大难题。安全多方计算正是在这样的背景之下日益引起人们的关注。安全多方计算中的理性公平是基于协议的公平性和参与者的理性趋利性研究。本文中所讨论的参与者皆为理性趋利参与者，并先后讨论了标准式博弈下基于ShareGen函数的安全多方计算协议和基于秘密共享的安全多方计算协议中的理性公平性，文章采用了给予不诚实行为者踢出协议交互的惩罚，促使参与者朝着合作共赢的方向做出选择。文中还给出了参与者部分不诚实的概念，给出了强公平性、部分公平性以及弱公平性的证明。关键词：安全多方计算,纳什均衡,ShareGen函数，秘密共享，公平性 IV贵州大学本科毕业论文（设计）第页Rationalfairnessresearchofsecuremulti-partycomputationAbstractSecuremulti-partycomputationresearchatpresent,bothathomeandabroadaremoremature,frombasicdefinitions,concepts,toalotofsecurityprotocoldesigncalculation,manyscholarshavedesignedthecorrespondingagreement.Securemulti-partycomputationisimplementedbythevariousparticipantsthroughinformationinteraction,fairnessisanindispensablepropertiesofsecuremulti-partycomputation,isanimportantsecuremulti-partycomputationresearchtopic.Atpresent,inthestudyofthefairnessofsecuremulti-partycomputation,thestudyofthemethodbasedoninformationgraduallyreleaseschemeshavebeenproposed.However,thesesolutionsaremoreorlessconsidersomeofthefairness,fairnessisstillabigproblemtothecurrentcompletely.Securemulti-partycomputationisagainstthisbackground,increasinglyarousedpeople"sconcern.Securemulti-partycomputationfairisbasedontheagreementoffairnessandrationalityintherationalficklekindsofstudyparticipants.Discussedinthisarticleoftheparticipantsarerational,participants,andhasdiscussedthestandardtypeofgameofsecuremulti-partycomputationprotocolbasedonShareGenfunctionandsecuremulti-partycomputationprotocolbasedonsecretsharingtherationalfairness,thearticleadoptedfordishonestbehaviorinteractionsplaydealpunishment,promptingtheparticipantsinthedirectionofthewin-wincooperationtomakeachoice.Thispaperalsogivesparticipantstheconceptofpartialdishonesty,givestheproofofstrongfairness,theweakpartsoffairnessandimpartiality.Keywords:Securemulti-partycomputation,Nashequilibrium,ShareGenfunction,secretsharing,fairness 第25页贵州大学本科毕业论文（设计）第一章绪论1.1研究的目的与意义随着信息技术和安全多方计算协议的兴起，使得人们的工作方式更具博弈选择性。人们在商业活动中都是为追求各自的利益，然而今天的发展需要合作共赢，有些商业信息也需要保密。但某些人为了追求利益的最大化而选择背叛合作协议，则安全多方计算协议是运用奖惩机制或其他机制促使大家共同选择合作以达到共赢的目的，同时更重要的是安全多方协议要确保各参与方的信息保密。安全多方计算是由多方参与方者通过信息交互来实现的，公平性是安全多方计算的一个必不可少的性质，是安全多方计算研究的一个重大课题。目前，在对安全多方计算的公平性的研究中，基于信息逐渐释放方法的研究方案相继被提出。但是，这些方案也只是或多或少地考虑了部分公平性，完全公平性仍然是当前的一大难题，所有这些公平性很大程度上受参与者的理性控制。因此安全多方计算协议执行过程中参与者的理性选择是实现公平交互以达到共赢的关键所在。但是如何设计安全多方协议才能促使参与者选择合作以达到共赢目的，以及对安全多方计算中理性公平的探讨，是本文的切入点和写作目的所在。博弈纳什均衡是研究理性公平的主要工具之一，分析参与者安全多方计算协议模型的理性公平，以此为基础，采用纳什均衡对协议进行理性公平判定；本文只讨论完全信息下的纳什均衡，并主要分析安全多方计算协议是否达到完全信息下的纳什均衡状态，即协议是否公平。通过对安全多方计算中的理性公平研究，探索出促使人们选择合作的安全多方计算协议对促使多方互利共赢具有重大意义。本协议需要参与者理性的做出选择，才能达到合作的结果。本文的前提是所有参与者必须在理性的状态下做出选择，这样比较符合现实商场的理性选择。本文探究意义重在通过对密码学和博弈论的研究并设计出安全的多方计算协议，促使参与者输入的值都能计算出理性公平的结果以达到共赢的目的，并能对各方输入的信息进行保密。而纳什均衡是判断协议是否达到公平的主要依据，从而在理论上分析协议的公平性，以此预测实际生活中的公平性。研究的主要意义在于探究出如何使协议的理论公平性越来越接近实际并促使安全多方计算的实际公平的方法，从而保证参与者选择的公平性以达到互利共赢的目的。 第25页贵州大学本科毕业论文（设计）1.2研究现状及发展趋势安全多方计算方面的研究目前在国内外都比较成熟了，从基本定义、概念到诸多安全计算协议的设计，很多学者都设计出了相应的协议。传统安全多方计算方面：文献[3]给出了安全多方计算协议要解决的问题，即一组参与者希望共同计算某个约定的函数，每个参与者提供函数的一个输入，出于安全考虑，要求参与者提供的输入对其他人保密，有可能不是最早提出的。至少关于安全多方计算的的前提就在于此，此外，该文献还给出了几种常见的安全多方计算协议，基于OT的安全多方计算协议、使用vss子协议的安全乡方计算协议、签于同态加密的安全多方计算协议、使用Mix-Match的安全多方计算协议。也给出了研究方向：（1)一般化的安全多方计算协议:这类研究的目的是设计一种高效的、安全的、能够计算任意函数的安全多方计算协议，希望能够通过这样一种协议一劳永逸地解决所有的涉及到安全多方计算的问题。(2)对一般化的安全多方计算协议进行剪裁:这类研究意到如果一个协议是广泛适用的，那么必然会牺牲一些性能士的代价来满足其广泛使用性；文献[1]则给出了诸多概念、定义，是本文的概念、定义主要依据。理性安全多方计算方面：文献[2]基于博弈论研究了秘密共享问题，详细分析在博弈论环境下秘密共享体制并提出理性秘密分发机制和密码重构机制，在理性秘密共享中，局中人仅关心自己的收益，无论在秘密分发协议还是在秘密重构协议中，做决策的依据都依赖于其效用。文献[4]利用双线性对的知识提出了一个可验证的理性秘密共享方案。理性公平方面：文献[6]、文献[9]分别对理性公平做了研究，其中文献[6]研究了基于囚徒困境、矩阵、线性空间的理性公平研究；文献[7]则研究了基于博弈论的理性公平。文献[6]、文献[9]是本文安全多方计算中理性公平研究的重要理论依据。文献[12]主要以博弈论、通用可组合理论和双线性对技术为工具，对分布式密码协议及公平性展开研究，研究内容主要涉及可验证秘密共享协议、秘密共享体制的博弈论分析、群组通信的通用可组合机制、安全通信协议的博弈论模型及具有公平性质的秘密共享协议等。从诸多文献研究成果来看，到目前为止，关于安全多方计算的研究都朝着公平性和安全性的方向研究，因此，对安全多方计算中的理性公平研究具有时代和重要意义。本文将采用惩罚机制设计并研究安全多方计算中的理性公平协议；用基于ShareGen 第25页贵州大学本科毕业论文（设计）函数的多方计算协议和基于秘密共享的理性公平多方计算协议，分析在完全信息下是否达到什均衡，即协议是否达到公平。并给出公平性的分析过程。1.3论文章节安排第一章介绍论文研究的目的、意义以及现状及发展趋势；并对文章结构进行安排。第二章介绍本文研究所需要的基础知识与基本概念如安全多方计算、完全信息下的纳什均衡、公平问题、博弈树等基本概念、秘密共享等基础知识。第三章设计ShareGen函数多方计算协议，对协议进行描述、分析和公平性证明。第四章首先介绍3种经典秘密共享方案，然后设计基于秘密共享的多方计算协议，同样对协议进行描述、分析和公平性证明。第五章对论文主要内容作简要的概括，并提出论文研究的不足和有待进一步研究的地方。 第25页贵州大学本科毕业论文（设计）第二章基础知识2.1安全多方计算2.1.1基本定义2.1.1.1安全多方计算安全多方计算：是指参与者利用自己的秘密输入联合计算函数，最后参与者得到，并且除了及其推出的信息外，得不到任何额外信息。安全多方计算的理想模型：在安全多方计算中，由计算函数充当一个完全诚实可信的第三方T，T通过计算参与者输入值计算出结果。在协议执行中，所有参与者将自己的值输入通过安全信道传送给T，T计算函数，然后将通过安全信道秘密地发送给。安全多方计算要求满足以下安全性质：(1)隐私性：要求不泄露参与者的秘密输入信息。(2)正确性：参与者得到正确的输出。安全性：在协议最后阶段，所有参与者都能得到自己的输出。2.1.1.2参与者参与者：所谓参与者，就是提供输入、得到输出并且执行实际计算的各方。执行实际计算的参与者集合表示为，所有参与者(包括输入、输出和计算)的集合表示为。defdef和没必要一定相等，但是一定有。本文中所指的参与者通常是执行实际计算的参与者。参与者的联合表示为，执行协议的所有参与者表示为，其余参与者表示，其中，。我们用表示第个参与者。安全多方计算协议的参与者的行为，决定了安全多方计算协议设计的难易程度，根据参与者在协议中的行为，我们将参与者分为三种类型。 第25页贵州大学本科毕业论文（设计）诚实参与者：在协议的执行过程中，诚实参与者完全按照协议的要求完成协议的各个步骤，同时保密自己的所有输入、输出及中间结果。注意，诚实参与者可以根据自己的输入、输出及中间结果推导另外的参与者的信息。诚实参与者与半诚实参与者的区别仅在于：诚实参与者不会被攻击者腐败。半诚实参与者：在协议的执行过程中，半诚实参与者完全按照协议的要求完成协议的各个步骤，同时可能将自己的所有输入、输出及中间结果泄露给攻击者。恶意参与者：在协议过程中，恶意参与者完全按照攻击者的意志执行协议的各个步骤，他不但将自己的所有输入、输出及中间结果泄露给攻击者，还可以根据攻击者的意图改变输入信息、中间结果信息，甚至终止协议。安全多方计算协议，需要保护诚实的各种安全需求；不保护(或者不关心)半诚实参与者的安全；并且，需要及时发现恶意参与者并给予剔除计算协议处罚。2.1.1.3安全多方计算模型安全多方计算模型：安全多方计算一般分为两种模型：半诚实模型与恶意模型。半诚实模型：如果所有参与者都是半诚实或诚实的，称此模型为半诚实模型。半诚实模型中的攻击者是被动的。恶意模型：在攻击者的腐败集中，有恶意参与者的模型称为恶意模型。即攻击者能完全控制腐败方的模型。恶意模型中的攻击者是主动的。半诚实模型安全多方计算较恶意模型的安全多方计算要容易得多，大多数情况下，如果协议中有恶意行为，协议得不到正确结果。要保证在恶意模型的计算中得到正确结果，需要使用较多的密码学技术。2.1.2公平性公平性是安全多方计算的重要研究内容和目标，尤其是面向多方参与的安全多方计算协议。随着现代网络计算的发展，密码技术被广泛的应用到电子商务、数字签约(Digitalcontactsigning)等方面。为保证这些业务的安全性，安全多方计算协议的保密性、不可否认性是非常重要的方面。同时，公平性在这类应用中显得尤为重要。通俗的说协议的公平性指协议的所有的参与方要么都获取所需要的信息，要么都不能获取。在诸多公平交换协议中，为实现公平性需设计出安全多方计算协议制约着参与方选择合作的方式。众多学者对安全多方计算的研究较多，而对安全多方计算中的理性公平研究涉及较少，特别是对秘密共享[57,71,100]、理性秘密共享[83]、安全多方计算等。然而，对于安全多方计算协议来说，无论是在协议本身还是在协议应用方面，研究公平性均具有至关重要的意义和价值。 第25页贵州大学本科毕业论文（设计）一直以来，对安全多方计算的研究，大家更多的是关注安全多方计算协议的安全性，对其公平性的研究涉及较少。通俗地讲，安全多方计算的安全性是在一个仿真范例(Simulationparadigm)下定义的，即在现实环境(Realworld)下，参与者执行安全计算协议π，现实中的敌手A控制通信信道和贿赂某些参与者；在理想环境(Idealprocess)下，由充当可信第三方角色的函数(Functionality)F执行计算协议。若任何环境Z都不能区分这两种情况，那么就认为协议π安全实现函数F。该安全性定义是Goldreich[49]于1987年提出的。2000年Canetti[20]提出的安全多方计算协议的通用可组合安全性。其它不同的安全性定义可参阅[8,50,51,77,88]。可见，若安全多方协议满足安全，则意味着当协议执行结束后，各参与方得到协议的结果及中间数据及其通过中间数据推导出得一些信息。若安全多方协议满足公平性，则当协议执行结束后仅能有两种结果：要么所有参与者都得到协议的正确输出，要么都得不到协议输出的任何信息。所以，安全多方计算协议的安全性和公平性不仅不同，而且具有交叉性。在多方计算协议中，设有位参与者，其中有位参与者是不诚实的。当时，Goldreich[49]的工作表明，在计算安全假定下，存在点对点通信信道，则协议满足公平性；Ben-Or[9]等的工作和Chaum[26]等的工作表明在点对点通信条件下信息论安全的多方安全计算协议也满足公平性。当时，Goldreich等[49]证明在广播信道下，计算安全的协议满足公平性；Rabin和Ben-Or[90]证明在广播信道下信息论安全的协议也满足公平性。非常不幸的是，当时，公平的安全多方计算协议是不可能实现的。直观的说，在两方的情况，参与者可能过早的终止最后一轮信息的发送，从而导致协议不满足公平性。Cleve[28]证明不存在公平的两方随机置币协议(Coin-tossingprotocol)。也就是说，对于任何协议，都存在敌手，使得敌手的攻击行为让协议π不满足公平性。因此，后续的许多工作都不考虑其公平性问题，即使考虑也仅是研究其部分公平(Partialfairness)的情形[42][50][52]。在Cleve的工作[28]表明两方公平计算是不可能实现的，但在实际应用中，用户需要满足公平性质的这类计算协议，如公平签约、公平交换协议等。通过归纳后续的研究工作可见，主要有两种方法来实现安全计算协议的(部分)公平性。一个是乐观方法(Optimistic 第25页贵州大学本科毕业论文（设计）approach)[6][19][78]，该方法需要一个可信第三方，当协议出现有争议时，需要该可信第三方了仲裁。从某种程度上来说，可信第三方的引入制约了该方法的发展前景。另一个是渐进方法(Gradualreleaseapproach),该方法的思想始于Blum[11]，系列工作可见文献[13,29,47,89]等。渐进方法不需要引入一个额外的可信参与方；在协议执行过程中，各参与方采用逐步释放交互信息而达到渐进公平性(Little-by-little)；尽管如此，有时该方法亦能出现协议不公平的情况，但这种情况能够被量化和控制。这两种实现协议公平性的方法都各自适用于不同的应用场景，相比乐观方法，渐进方法的优势是明显的，因其不需要可信第三方的参与。可见，分布式密码协议的公平性具有非常广泛的应用，特别是公平秘密共享和公平安全多方计算协议。而目前对公平性的研究略显不足，无论是在实现方法上，还是在公平协议的应用方面都如此。非常值得我们进一步深入去探讨。公平性：在协议的最后，每个参与者都能得到自己的的输出。2.2博弈论2.2.1标准式博弈完全信息是指所有参与者各自选择的行动的不同组合所决定的各参与者的收益对所有参与者来说是共同知识，即所有的参与人对博弈问题的信息结构有完全的了解，在博弈开始之前所有的参与人对博弈问题本身没有任何不确定性。标准式博弈又称为战略是表述。标准式表述含有以下三个要素：（1）博弈参与者集合,；（2）每个参与者的战略空间；（3）每个参与者的收益函数。定义：在一个有个参与者的博弈中，参与者的战略空间为，收益函数为，标准式表述用表示此博弈。2.2.2纳什均衡纳什均衡，又称为非合作博弈均衡，是博弈论的一个重要术语，以约翰·纳什命名。假设有n个局中人参与博弈，给定其他人策略的条件下，每个局中人选择自己的纳什均衡最优策略（个人最优策略可能依赖于也可能不依赖于他人的 第25页贵州大学本科毕业论文（设计）战略），从而使自己利益最大化。所有局中人策略构成一个策略组合（StrategyProfile）。纳什均衡指的是这样一种战略组合，这种策略组合由所有参与人最优策略组成。即在给定别人策略的情况下，没有人有足够理由打破这种均衡。纳什均衡，从实质上说，是一种非合作博弈状态。纳什均衡达成时，并不意味着博弈双方都处于不动的状态，在顺序博弈中这个均衡是在博弈者连续的动作与反应中达成的。纳什均衡也不意味着博弈双方达到了一个整体的最优状态。纳什均衡定义：在个参与者标准式博弈中，如果对于每一个参与者，是针对其他个参与者所选战略的最优反应战略，即对于中所有都成立，亦即是最优化问题的解，则战略组合称为该博弈的一个纳什均衡。2.3基本工具2.3.1ShareGen函数ShareGen函数模型首先由ShareGen提出，现在ShareGen函数计算协议已经有了成熟的实现方案。ShareGen函数计算协议的主要思想是通过或与函数将输出值分成份，再分发给，又将自己收到的结果分成份，先后分别发送给其他个参与者，以达到公平交换信息的目的。 第25页贵州大学本科毕业论文（设计）输入：参与者分别输入到ShareGen函数，如果输入的值是无效的，函数将（中止符号）发给2个参与者。计算：计算如下：1.根据几何分布的参数选择；2.设置保存的值，如下所示：·if，choose.·if，set.3.将异或成，计算函数是：.输出：将传送给,将传送给。ShareGen函数（图1ShareGen函数2.3.2秘密共享秘密共享方案是一种分发、保存和恢复秘密信息的方法，是研究如何在一组参与者之间分配或共享一个秘密信息，而该共享秘密信息只有在规定数量的授权用户共同参与才能用特定的方法恢复，其中能够恢复秘密信息的成员子集称为授权集(Authorizedset)，而其它子集称为非授权集(Unauthorizedset)，若一个秘密共享方案中的每个非授权集都不能得到该秘密的任何有用信息，则称其为完美秘密共享(Perfectsecretsharing)。秘密共享方案实现的主要方法有：Shamir的Lagrange插值方法[93]、Blakley的基于矢量空间的几何方法[10]、Asmuth和Bloom的中国剩余定理方法[5]等，其中最常用的是Shamir基于Lagrange插值方法的门限秘密共享方案，该方法简单、实用而被广泛应用。下面介绍Shamir方案：Shamir的门限秘密共享方案中的参与者共个，记为，授权集的成员数最小值为，称为门限值。 第25页贵州大学本科毕业论文（设计）理性秘密共享是为了在位理性参与者(记为)间实现秘密分享任务。准确的说，每位参与者有一个效用函数，代表实数空间。向量记为秘密重构的一个结果，这里当且仅当最终得到共享秘密。为了简单，我们也选取大家广泛采用的效用函数假设。即对,的效用函数满足：(1)对任意的,,若则；希望自己活得最多；（2）如果和,则。希望别人活得最多。也会是说，的秘密重构结果，当满足（即要优于），则有对应的效用函数优于对应的效用函数（即）；另外，如果两个重构结果相等，当对应的重构空间总和要比对应的重构空间总和校时，则也有对应的效用函数优于对应的效用函数。 第25页贵州大学本科毕业论文（设计）第三章基于ShareGen函数的理性公平多方计算3.1基于ShareGen函数的理性公平两方计算3.1.1ShareGen函数输入：参与者分别输入到ShareGen函数，如果输入的值是无效的，函数将（中止符号）发给2个参与者。计算：计算如下：1.根据几何分布的参数选择；2.设置保存的值，如下所示：·if，choose.·if，set.3.将异或成，计算函数是：.输出：将传送给,将传送给。ShareGen函数输入阶段图2ShareGen函数输入：参与者使用他们的输入来执行计算的安全协议ShareGen，分别获得的信息是、，计算：这里一共有次迭代，在每次迭代中，ifdo：1.发送给，计算得到。2.发送给，计算得到。输出：if在计算的值之前中止协议，then通过如选择输出；if在其他任何时候中止协议，或协议成功完成,那么没有更多消息被发送。获得最后收到的的值。3.1.2协议描述 第25页贵州大学本科毕业论文（设计）图3ShareGen函数两方计算协议3.1.2协议公平性分析两个参与者通过分裂获得部分信息，再交换信息。再通过获得剩余信息。在该理性模型下,协议的正确性可通过通信协议博弈的规则来保障，其保密性主要体现在博弈中的两主要参与方的效用函数中，对于公平性,我们有如下结果：定义3.1.2.1在安全ShareGen函数协议博弈中,如果,在传送时都是诚实的,都能获得相同的结果，则称协议博弈是公平的。分析:如果交换协议是公平的,则该协议也是理性的，反之则不成立。这里将给出上述命题的证明。在我们的模型下，如果安两方协议博弈满足公平性，则意味着以相近的概率确认得到相关秘密信息。例如，假设发送给，要确保的正确性，同时，也要确保的正确性。是公平的⇒得到的结果是相同的。证明：根据博弈定义3.1.2.1的定义知,如果错误信息是可忽略的,对得到结果的正确性没任何影响，则是公平的。事实上,博弈也是公平的，如果,在传输是都是错的，很容易看出都得不到正确结果。如果博弈满足公平性，根据上述分析，下面我们将给出协议公平性的等价条件及近似公平性定义。如果是真实的，而是虚假的，则得到的结果是正确的，而得到的结果是错误的，与定义中的都能获得相同的结果相矛盾，则不公平，协议无效。综上所述，ShareGen函数协议是公平的。 第25页贵州大学本科毕业论文（设计）3.2基于ShareGen函数的理性公平多方计算输入：参与者各自分别输入到ShareGen函数，如果输入的值是无效的，函数将（中止符号）发给个参与者。计算：计算如下：1.根据几何分布的参数选择；2.设置保存的值，如下所示·if，choose.·if，set.3.将异或成，计算函数是：.输出：将传送给，将传送给将传送给。3.2.1ShareGen函数图4将ShareGen函数扩展到多方计算 第25页贵州大学本科毕业论文（设计）输入：个参与者各自用他们的输入来计算ShareGen函数协议，分别获得的信息是，。计算：这里一共有次迭代，ifdo：1.发送给，发送给；发送给发送给，计算得到。2.发送给，发送给；发送给发送给，计算得到。3.发送给，发送给；发送给发送给，计算得到。k.发送给，发送给；发送给发送给，计算得到。n.发送给，发送给；发送给发送给，计算得到。输出：如果他们的输入都是诚实的，则他们都能得到正确的结果，如果他们中有人不诚实，则他们得不到相同正确的结果。3.2.2协议描述 第25页贵州大学本科毕业论文（设计）图4基于ShareGen函数的理性公平多方计算协议描述3.2.3协议公平性分析多方参与者通过分裂获得部分信息，再交换信息。再通过获得剩余信息。在该理性模型下,协议的正确性可通过通信协议博弈的规则来保障。其保密性主要体现在博弈中的两主要参与方的效用函数中，对于公平性,我们有如下结果：定义3.2.2.1在安全ShareGen函数多方计算协议博弈中,如果在传送时都是诚实的,都能获得相同的结果，策略组合满足纳什均衡，则称协议博弈是公平的。分析:如果交换协议是公平的,则该协议也是理性的，反之则不成立。这里将给出上述命题的证明。证明:在我们的模型下，如果安多方协议博弈满足公平性，则意味着以相近的概率确认得到相关秘密信息。例如,假设发送给.要确保的正确性，同时，也要确保所发信息的正确性。是公平的⇒得到的结果是相同的。根据博弈定义3.2.2.1的定义知,如果错误信息是可忽略的,对得到结果的正确性没任何影响，则是公平的。事实上,博弈也是公平的，如果在传输是都是错的，很容易看出都得不到正确结果。 第25页贵州大学本科毕业论文（设计）如果博弈满足公平性，根据上述分析，下面我们将给出协议公平性的等价条件及近似公平性定义。如果发的信息是虚假的，则得到的结果是错误的，而得到的结果是正确的，与定义中的都能获得相同的结果相矛盾，则不公平，协议无效。综上所述，ShareGen函数协议是公平的。此外，每个参与方都只能得到部分信息进行交换，再通过获得的信息计算得到完全的信息，对于参与方来说都有各自的保密信息，所以ShareGen函数计算协议本身是安全的。 第25页贵州大学本科毕业论文（设计）第四章基于秘密共享的理性公平多方计算4.1经典方案介绍4.1.1Shamir的秘密共享方案这是一个有个参与者的门限秘密共享方案。在该方案中，通过一个多项式对秘密(有限域上的一个元素，且)进行共享。其中，是门限值。参与者的子秘密为，其中是一个参与者相关的上的公开元素，如。给定个或更多个子秘密，以及多项式，就可以将点带入lagrange插值公式，从而计算出。4.1.2Peterson可验证秘密共享方案假定为个参与者。令为大素数，为的一个大素因子，且为阶循环群的一个元素。首先，每个随机选取多项式。然后通过保密信道将发送给，并广播。对于接收到的每个，都验证其有效性，验证方法是检验以下等式是否成立：若所有的都通过验证，每个计算作为自己的秘密份额于是。因此，每个可以通过如下等式进行验证：这样，给定任意个秘密份额就可以利用Lagrange插值公式轻易重构出秘密，重构方法如下： 第25页贵州大学本科毕业论文（设计）重构出的秘密可根据以下等式验证：。需要强调的是，秘密被个参与者所共享，且是由参与者随机选取的。4.1.3Gennaro的VSS协议秘密分享阶段：1．秘密的分发者需要将秘密在分享者中分享。随机选择次多项式对于，计算，将交与参与者；对于，计算并将承诺广播；2．检查承诺是否正确。如果正确则接受分享的子秘密，否则广播对的不信任。3。如果有广播对的不信任，则应该公开如下的值：使得。4．如果不按照上述的步骤执行，显然是不可信任的，于是协议终止。如果能成功地执行以上的步骤则一个秘密被成功地在所有参与者中分享了。恢复秘密阶段：1．每个协议参与者广播得到的子秘密；2．每个协议参与者任取个子秘密，并验证其承诺是否正确。如果正确则利用这个点构造次多项式和；3．每个协议参与者计算，并验证对于所有的，承诺是 第25页贵州大学本科毕业论文（设计）否正确。如果正确则输出即是被分享的秘密。Gennaro的协议效率较高的原因在于Gennaro的协议只是对需要分享的秘密进行了承诺，也就是说只承诺了一个秘密，而其他的协议不只是对一个秘密进行了承诺，而是对一个分享秘密的多项式进行了承诺。4.2基于秘密共享的理性公平多方计算4.2.1协议描述（1）初始阶段Step1：n个参与者，分别记为,每个参与者拥有一个公开的值,以及一个秘密数据（战略组合），，为有限域。现在各个参与者共同计算函数:Step2：输入各自的博弈最优值，并用函数计算输出博弈结果，并使用gennaro的VSS协议进行秘密分享。图5基于秘密共享的理性安全多方计算协议初始阶段 第25页贵州大学本科毕业论文（设计）（2）计算阶段是使用DL-VSS协议分享的2个秘密，分享秘密的多项式分别是和。协议参与者需要计算。拥有子秘密和，还有和承诺有关的子秘密和，其中r(x)和s(x)是t次随机多项式。承诺和是公开的。因为也是一个随机的t次多项式协议参与者只需计算，即是所持有的分享的子秘密，分享这个秘密的多项式是。同时所有参与者都可以计算对的承诺。每个协议参与者的输入：。公开的承诺：，对于1≤i≤nStep1：协议参与者Pi使用DL-VSS协议将在每个协议参与者中分享。即传送给：其中和是t次的随机多项式，且。秘密信息：和公开信Step2：每个协议参与者都检查秘密分发者分享秘密时使用的VSS协议是否满足VSPS，性质如果不满足，则公开该秘密分发者分享的子秘密。Step3：使用零知识证明方法证明是对的正确承诺。如果证明失败，其他参与者公开分享的子秘密。Step4：每个协议参与者在自己本地计算：，并公开。秘密信息：是对乘积分享得到的子秘密。公开信息，对于1≤i≤n；图6基于秘密共享的理性安全多方计算协议计算阶段 第25页贵州大学本科毕业论文（设计）（3）输出阶段Step1：秘密的分发者需要将秘密在分享者中分享。随机选择次多项式对于，计算，将交与参与者对于，计算并将承诺广播Step2：检查承诺是否正确。如果正确则接受分享的子秘密，否则广播对的不信任。Step3：如果有广播对的不信任，则应该公开如下的值：使得。Step4:如果不按照上述的步骤执行，显然是不可信任的，剔除，协议继续。如果能成功地执行以上的步骤则一个秘密被成功地在所有参与者中分享了。图4.2.1.3基于秘密共享的理性安全多方计算协议输出阶段4.2.2协议公平性分析基于基于秘密共享协议的安全多方计算强公平性是在标准式博弈、理性参与者和完全信息条件下研究的，基于秘密共享的安全多方计算公平性定义。C定义4.4.1：在完全信息下，如果所有诚实参与策略组合方案能满足纳什均衡，即对于中所有都成立，亦即是最优化问题的解，则战略组合称为该博弈的一个纳什均衡。则协议是公平的。证明：由强公平性知参与者都是诚实的，再根据定义4.4.1个参与者。每个随机选取多项式。然后通过保密信道将 第25页贵州大学本科毕业论文（设计）发送给，并广播。先检查承诺是否正确。如果正确则接受分享的子秘密，否则广播对的不信任。协议终止。协议满足公平性。如果参与者部分不诚实。且不管输入何值都能得出结果，不管怎样输入对协议的结果正确性没有影响，则战略组合同样满足纳什均衡，所得结果基本相同，则战略协议具有弱公平性。定义：4.4.2在4.4.1的基础上，部分参与者输入有误，但对战略均衡没有影响仍然满足4.4.1，则称战略组合具有弱公平性。协议将对部分不诚实者给予提出处理，因此协议对于部分人具有公平性。定义：4.4.3基于定义4.4.1、定义4.4.2。协议若对不诚实者给予提出或重新输入处理，对于诚实方可以得到正确结果，不诚实方得到相应惩罚，则战略具有部分公平性。证明若有广播对的不信任，则应该公开如下的值：使得。于是。因此，每个可以通过如下等式进行验证：这样，给定任意个秘密份额就可以利用Lagrange插值公式轻易重构出秘密，重构方法如下：重构出的秘密可根据以下等式验证：。需要强调的是，秘密被个参与者所共享，且是由参与者随机选取的。从而都能得到正确一致的结果，战略协议是部分公平的。 第25页贵州大学本科毕业论文（设计）第五章结束语文章总结了目前安全多方计算协议的研究现状，介绍并分析了两类安全多方计算协议：基于ShareGen函数的安全多方计算协议、基于秘密共享的安全多方计算协议。本文重点研究了安全多方计算的理性公平性并给予证明。本文仅研究了标准式博弈下的安全多方计算中的理性公平。论文没有对标准式博弈下的安全多方计算没有涉及。在进行本文的研究工作中，作者觉得在以下两方面需要更多的人去研究和探讨：1．对于不完全信息下的多方安全多方计算协议的研究，而实际生活中的信息往都是在不完全的，参与者得到的信息并不完整，在不完全信息下的理性公平研究更贴近生活，处理起来难度大。2．实际应用研究。安全多方计算在电子拍卖、联合译码、入侵监测等方面都有应用。由于本人水平有限，文中一定存在不少的不足之处，敬请评审专家和读者不吝指正。 第25页贵州大学本科毕业论文（设计）参考文献[1]刘木兰,张志芳.密钥共享和安全多方计算[M].北京：电子工业出版社，2008.11.161~179.[2]田有亮,马建峰,彭长根,姬文江.秘密共享体制的博弈论分析[J].电子学报，2011,39(12):2790~2795.[3]李强,颜浩,陈克非.安全多方计算协议的研究与应用[J].计算机科学,2003,30(08):52~55.[4]田有亮,彭长根.基于双线性对的可验证秘密共享方案[J].计算机应用,2007,4（38）：125~127.[5]J.Halpern,V.Teague.RationalSecretSharingandMultipartyComputation[C]。STOC"04Proceedingsofthe6thannualACMsymposiumonTheoryofcomputing,2004.pp:623-632[6]A.Groce,J.Katz.FairComputationwithRationalPlayers[J]．LectureNotesinComputerScienceVolume7237，2012,pp:81-98[7]S.Gordon,C.Hazay,J.Katz,Y.Indel.CompleteFairnessinSecureTwo-PartyComputation[C]．JournaloftheACM，2011.[8]S.DovGordon,J.Katz.PartialFairnessinSecureTwo-PartyComputation[J]．JournalofCryptologyVolume25,Issue1，2010，pp:14-40。[9]G.Asharov,G.Canetti,C.Hazay.TowardsaGameTheoreticViewofSecureComputation[J]．LectureNotesinComputerScience,2011,6632:426-445.[10]罗云峰.博弈论教程[M].北京：清华大学出版社，2007.[11]李光久.博弈论基础教程[M].北京：化学工业出版社，2005.[12]田有亮.分布式密码协议及公平性研究[D].西安电子科技大学博士论文，2004.[13]谢曹明，彭长根，徐滨.一个完全公平的安全多方计算协议[J].贵阳电子技术学院，2013,32（1）：183-185.[14]徐滨，彭长根，顾崇旭.公平的安全多方计算协议[J].贵州大学理学院，2012,38（7）：116-121. 第25页贵州大学本科毕业论文（设计）致谢在我的毕业论文设计将要完成之际,衷心感谢我的导师彭长根教授和辅助老师刘荣飞师兄！在学术研究上,刘师兄耐心的指导和严谨求实的辅导态度深深影响着我,使我受益菲浅。从论文选题、构思、研究乃至定稿,刘师兄进行了精心指导,倾注了大量心血.。在大学四年中，尤其是大学最后两年里，彭老师除了在学业上对我严格要求、耐心指导之外,彭老师还一直关心着我的未来发展,一直激励着我不断奋发向上。从彭老师身上和他平时所讲的每一个故事案例中,我学到不仅是做学问的态度和方法,还有严谨务实的人生态度和不断进取的奋斗精神。这一切将在更深的层面上影响和指导着我未来的职业道路.。感谢彭老师的谆谆教诲，在彭老师那里所获得的经历都将使我终生受益。在此,谨向彭老师表示最诚挚的谢意和最深的敬意！我要特别感谢我的指导老师彭长根教授和刘荣飞师兄，一直给予我很大的帮助。四年的大学生涯转眼即逝，将要走向社会的我，面对的是一个新的起点。在这四年中我从学校不但学到了谋生的技能，更学到了人与人之间交流沟通的方法以为为人处世的分寸。在这大学生活四年期间，老师，同学，朋友，亲人都给予我很多帮助，在此，谨对帮助过我的老师，同学，朋友，亲人表示感谢。张胜2014年5月10日'