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

本科毕业论文（设计） 安全多方计算中的理性公平研究学 院： 理学院 专 业： 信息与计算科学 班 级： 101 学 号： 1007010162 学生姓名： 指导教师： 2014年 5月 10 日贵州大学本科毕业论文（设计） 诚信责任书本人郑重声明：本人所呈交的毕业论文（设计），是在导师的指导下独立进行研究所完成。毕业论文（设计）中凡引用他人已经发表或未发表的成果、数据、观点等，均已明确注明出处。特此声明。论文（设计）作者签名： 日 期： 安全多方计算中的理性公平研究Rational fairness research of secure multi-party computation张 胜Zhang sheng目 录摘 要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.1 ShareGen函数82.3.2秘密共享9第三章 基于ShareGen函数的理性公平多方计算113.1基于ShareGen函数的理性公平两方计算113.1.1 ShareGen函数113.1.2 协议公平性分析123.2基于ShareGen函数的理性公平多方计算133.2.1 ShareGen函数133.2.2 协议描述143.2.2协议公平性分析15第四章 基于秘密共享的理性公平多方计算174.1经典方案介绍174.1.1 Shamir的秘密共享方案174.1.2 Peterson可验证秘密共享方案174.1.3 Gennaro的VSS协议184.2基于秘密共享的理性公平多方计算194.2.1协议描述194.2.2 协议公平性分析21第五章 结束语23参考文献24致谢25安全多方计算中的理性公平研究摘 要安全多方计算方面的研究目前在国内外都比较成熟了，从基本定义、概念到诸多安全计算协议的设计，很多学者都设计出了相应的协议。安全多方计算是由多方参与方通过信息交互来实现的，公平性是安全多方计算的一个必不可少的性质，是安全多方计算研究的一个重大课题。目前，在对安全多方计算的公平性的研究中，基于信息逐渐释放方法的研究方案相继被提出。但是，这些方案也只是或多或少地考虑了部分公平性，完全公平性仍然是当前的一大难题。安全多方计算正是在这样的背景之下日益引起人们的关注。 安全多方计算中的理性公平是基于协议的公平性和参与者的理性趋利性研究。本文中所讨论的参与者皆为理性趋利参与者，并先后讨论了标准式博弈下基于ShareGen函数的安全多方计算协议和基于秘密共享的安全多方计算协议中的理性公平性，文章采用了给予不诚实行为者踢出协议交互的惩罚，促使参与者朝着合作共赢的方向做出选择。文中还给出了参与者部分不诚实的概念，给出了强公平性、部分公平性以及弱公平性的证明。关键词：安全多方计算, 纳什均衡, ShareGen函数，秘密共享，公平性Rational fairness research of secure multi-party computation Abstract Secure multi-party computation research at present, both at home and abroad are more mature, from basic definitions, concepts, to a lot of security protocol design calculation, many scholars have designed the corresponding agreement. Secure multi-party computation is implemented by the various participants through information interaction, fairness is an indispensable properties of secure multi-party computation, is an important secure multi-party computation research topic. At present, in the study of the fairness of secure multi-party computation, the study of the method based on information gradually release schemes have been proposed. However, these solutions are more or less consider some of the fairness, fairness is still a big problem to the current completely. Secure multi-party computation is against this background, increasingly aroused people's concern. Secure multi-party computation fair is based on the agreement of fairness and rationality in the rational fickle kinds of study participants. Discussed in this article of the participants are rational, participants, and has discussed the standard type of game of secure multi-party computation protocol based on ShareGen function and secure multi-party computation protocol based on secret sharing the rational fairness, the article adopted for dishonest behavior interactions play deal punishment, prompting the participants in the direction of the win-win cooperation to make a choice. This paper also gives participants the concept of partial dishonesty, gives the proof of strong fairness, the weak parts of fairness and impartiality.Keywords: Secure multi-party computation, Nash equilibrium, ShareGen function, secret sharing, fairness 第一章 绪论1.1研究的目的与意义随着信息技术和安全多方计算协议的兴起，使得人们的工作方式更具博弈选择性。人们在商业活动中都是为追求各自的利益，然而今天的发展需要合作共赢，有些商业信息也需要保密。但某些人为了追求利益的最大化而选择背叛合作协议，则安全多方计算协议是运用奖惩机制或其他机制促使大家共同选择合作以达到共赢的目的，同时更重要的是安全多方协议要确保各参与方的信息保密。安全多方计算是由多方参与方者通过信息交互来实现的，公平性是安全多方计算的一个必不可少的性质，是安全多方计算研究的一个重大课题。目前，在对安全多方计算的公平性的研究中，基于信息逐渐释放方法的研究方案相继被提出。但是，这些方案也只是或多或少地考虑了部分公平性，完全公平性仍然是当前的一大难题，所有这些公平性很大程度上受参与者的理性控制。因此安全多方计算协议执行过程中参与者的理性选择是实现公平交互以达到共赢的关键所在。但是如何设计安全多方协议才能促使参与者选择合作以达到共赢目的，以及对安全多方计算中理性公平的探讨，是本文的切入点和写作目的所在。博弈纳什均衡是研究理性公平的主要工具之一，分析参与者安全多方计算协议模型的理性公平，以此为基础，采用纳什均衡对协议进行理性公平判定；本文只讨论完全信息下的纳什均衡，并主要分析安全多方计算协议是否达到完全信息下的纳什均衡状态，即协议是否公平。通过对安全多方计算中的理性公平研究，探索出促使人们选择合作的安全多方计算协议对促使多方互利共赢具有重大意义。本协议需要参与者理性的做出选择，才能达到合作的结果。本文的前提是所有参与者必须在理性的状态下做出选择，这样比较符合现实商场的理性选择。本文探究意义重在通过对密码学和博弈论的研究并设计出安全的多方计算协议，促使参与者输入的值都能计算出理性公平的结果以达到共赢的目的，并能对各方输入的信息进行保密。而纳什均衡是判断协议是否达到公平的主要依据，从而在理论上分析协议的公平性，以此预测实际生活中的公平性。研究的主要意义在于探究出如何使协议的理论公平性越来越接近实际并促使安全多方计算的实际公平的方法，从而保证参与者选择的公平性以达到互利共赢的目的。1.2研究现状及发展趋势 安全多方计算方面的研究目前在国内外都比较成熟了，从基本定义、概念到诸多安全计算协议的设计，很多学者都设计出了相应的协议。 传统安全多方计算方面：文献3给出了安全多方计算协议要解决的问题，即一组参与者希望共同计算某个约定的函数，每个参与者提供函数的一个输入，出于安全考虑，要求参与者提供的输入对其他人保密，有可能不是最早提出的。至少关于安全多方计算的的前提就在于此，此外，该文献还给出了几种常见的安全多方计算协议，基于OT 的安全多方计算协议、 使用vss子协议的安全乡方计算协议、签于同态加密的安全多方计算协议、使用M ix-M atch 的安全多方计算协议。也给出了研究方向：（1)一般化的安全多方计算协议:这类研究的目的是设计一种高效的、安全的、能够计算任意函数的安全多方计算协议，希望能够通过这样一种协议一劳永逸地解决所有的涉及到安全多方计算的问题。(2)对一般化的安全多方计算协议进行剪裁:这类研究意到如果一个协议是广泛适用的，那么必然会牺牲 一些性能士的代价来满足其广泛使用性；文献1则给出了诸多概念、定义，是本文的概念、定义主要依据。理性安全多方计算方面：文献2基于博弈论研究了秘密共享问题，详细分析在博弈论环境下秘密共享体制并提出理性秘密分发机制和密码重构机制，在理性秘密共享中，局中人仅关心自己的收益，无论在秘密分发协议还是在秘密 重构协议中，做决策的依据都依赖于其效用。文献4利用双线性对的知识提出了一个可验证的理性秘密共享方案。理性公平方面：文献6、文献9分别对理性公平做了研究，其中文献6研究了基于囚徒困境、矩阵、线性空间的理性公平研究；文献7则研究了基于博弈论的理性公平。文献6、文献9是本文安全多方计算中理性公平研究的重要理论依据。文献12主要以博弈论、通用可组合理论和双线性对技术为工具，对分布式密码协议及公平性展开研究，研究内容主要涉及可验证秘密共享协议、秘密共享体制的博弈论分析、群组通信的通用可组合机制、安全通信协议的博弈论模型及具有公平性质的秘密共享协议等。从诸多文献研究成果来看，到目前为止，关于安全多方计算的研究都朝着公平性和安全性的方向研究，因此，对安全多方计算中的理性公平研究具有时代和重要意义。 本文将采用惩罚机制设计并研究安全多方计算中的理性公平协议；用基于ShareGen函数的多方计算协议和基于秘密共享的理性公平多方计算协议，分析在完全信息下是否达到什均衡，即协议是否达到公平。并给出公平性的分析过程。1.3论文章节安排第一章 介绍论文研究的目的、意义以及现状及发展趋势；并对文章结构进行安排。第二章 介绍本文研究所需要的基础知识与基本概念如安全多方计算、完全信息下的纳 什均衡、公平问题、博弈树等基本概念、秘密共享等基础知识。第三章 设计ShareGen函数多方计算协议，对协议进行描述、分析和公平性证明。第四章 首先介绍3种经典秘密共享方案，然后设计基于秘密共享的多方计算协议，同样对协议进行描述、分析和公平性证明。第五章 对论文主要内容作简要的概括，并提出论文研究的不足和有待进一步研究的地 方。 第二章 基础知识2.1安全多方计算2.1.1基本定义2.1.1.1安全多方计算安全多方计算：是指参与者 利用自己的秘密输入 联合计算函数，最后参与者得到，并且除了及其推出的信息外，得不到任何额外信息。安全多方计算的理想模型：在安全多方计算中，由计算函数充当一个完全诚实可信的第三方T，T通过计算参与者输入值计算出结果。在协议执行中，所有参与者将自己的值输入通过安全信道传送给T，T计算函数，然后将通过安全信道秘密地发送给。安全多方计算要求满足以下安全性质：(1)隐私性：要求不泄露参与者的秘密输入信息。(2)正确性：参与者得到正确的输出。安全性：在协议最后阶段，所有参与者都能得到自己的输出。2.1.1.2 参与者参与者：所谓参与者，就是提供输入、得到输出并且执行实际计算的各方。执行实际计算的参与者集合表示为，所有参与者(包括输入、输出和计算)的集合表示为。def def和没必要一定相等，但是一定有。本文中所指的参与者通常是执行实际计算的参与者。参与者的联合表示为，执行协议的所有参与者表示为，其余参与者表示，其中，。我们用表示第个参与者。安全多方计算协议的参与者的行为，决定了安全多方计算协议设计的难易程度，根据参与者在协议中的行为，我们将参与者分为三种类型。 诚实参与者：在协议的执行过程中，诚实参与者完全按照协议的要求完成协议的各个步骤，同时保密自己的所有输入、输出及中间结果。注意，诚实参与者可以根据自己的输入、输出及中间结果推导另外的参与者的信息。诚实参与者与半诚实参与者的区别仅在于：诚实参与者不会被攻击者腐败。 半诚实参与者：在协议的执行过程中，半诚实参与者完全按照协议的要求完成协议的各个步骤，同时可能将自己的所有输入、输出及中间结果泄露给攻击者。恶意参与者：在协议过程中，恶意参与者完全按照攻击者的意志执行协议的各个步骤，他不但将自己的所有输入、输出及中间结果泄露给攻击者，还可以根据攻击者的意图改变输入信息、中间结果信息，甚至终止协议。安全多方计算协议，需要保护诚实的各种安全需求；不保护(或者不关心)半诚实参与者的安全；并且，需要及时发现恶意参与者并给予剔除计算协议处罚。2.1.1.3 安全多方计算模型安全多方计算模型：安全多方计算一般分为两种模型：半诚实模型与恶意模型。半诚实模型：如果所有参与者都是半诚实或诚实的，称此模型为半诚实模型。半诚实模型中的攻击者是被动的。恶意模型：在攻击者的腐败集中，有恶意参与者的模型称为恶意模型。即攻击者能完全控制腐败方的模型。恶意模型中的攻击者是主动的。半诚实模型安全多方计算较恶意模型的安全多方计算要容易得多，大多数情况下，如果协议中有恶意行为，协议得不到正确结果。要保证在恶意模型的计算中得到正确结果，需要使用较多的密码学技术。2.1.2公平性公平性是安全多方计算的重要研究内容和目标，尤其是面向多方参与的安全多方计算协议。 随着现代网络计算的发展，密码技术被广泛的应用到电子商务、数字签约(Digital contact signing) 等方面。 为保证这些业务的安全性，安全多方计算协议的保密性、不可否认性是非常重要的方面。 同时，公平性在这类应用中显得尤为重要。通俗的说协议的公平性指协议的所有的参与方要么都获取所需要的信息，要么都不能获取。 在诸多公平交换协议中，为实现公平性需设计出安全多方计算协议制约着参与方选择合作的方式。 众多学者对安全多方计算的研究较多，而对安全多方计算中的理性公平研究涉及较少，特别是对秘密共享57, 71, 100、理性秘密共享83、安全多方计算等。 然而，对于安全多方计算协议来说，无论是在协议本身还是在协议应用方面，研究公平性均具有至关重要的意义和价值。一直以来，对安全多方计算的研究，大家更多的是关注安全多方计算协议的安全性，对其公平性的研究涉及较少。 通俗地讲，安全多方计算的安全性是在一个仿真范例 (Simulation paradigm) 下定义的，即在现实环境 (Real world)下，参与者 执行安全计算协议 ，现实中的敌手 A 控制通信信道和贿赂某些参与者；在理想环境 (Ideal process) 下，由充当可信第三方角色的函数 (Functionality) F执行计算协议。 若任何环境 Z 都不能区分这两种情况，那么就认为协议 安全实现函数F。 该安全性定义是Goldreich49于1987年提出的。 2000年Canetti20提出的安全多方计算协议的通用可组合安全性。 其它不同的安全性定义可参阅 8, 50, 51, 77, 88。 可见，若安全多方协议满足安全，则意味着当协议执行结束后，各参与方得到协议的结果及中间数据及其通过中间数据推导出得一些信息。 若安全多方协议满足公平性，则当协议执行结束后仅能有两种结果：要么所有参与者都得到协议的正确输出，要么都得不到协议输出的任何信息。 所以，安全多方计算协议的安全性和公平性不仅不同，而且具有交叉性。在多方计算协议中，设有 位参与者，其中有 位参与者是不诚实的。 当 时，Goldreich49的工作表明，在计算安全假定下，存在点对点通信信道，则协议满足公平性；Ben-Or9等的工作和Chaum26等的工作表明在点对点通信条件下信息论安全的多方安全计算协议也满足公平性。 当时，Goldreich等49证明在广播信道下，计算安全的协议满足公平性；Rabin和Ben-Or90证明在广播信道下信息论安全的协议也满足公平性。 非常不幸的是，当 时，公平的安全多方计算协议是不可能实现的。直观的说，在两方的情况，参与者可能过早的终止最后一轮信息的发送，从而导致协议不满足公平性。 Cleve28证明不存在公平的两方随机置币协议 (Coin-tossing protocol)。也就是说，对于任何协议，都存在敌手，使得敌手 的攻击行为让协议不满足公平性。因此，后续的许多工作都不考虑其公平性问题，即使考虑也仅是研究其部分公平 (Partial fairness)的情形425052。在 Cleve 的工作28表明两方公平计算是不可能实现的，但在实际应用中，用户需要满足公平性质的这类计算协议，如公平签约、公平交换协议等。通过归纳后续的研究工作可见，主要有两种方法来实现安全计算协议的(部分)公平性。一个是乐观方法(Optimistic approach)61978，该方法需要一个可信第三方，当协议出现有争议时，需要该可信第三方了仲裁。 从某种程度上来说，可信第三方的引入制约了该方法的发展前景。 另一个是渐进方法 (Gradual release approach), 该方法的思想始于 Blum11，系列工作可见文献 13, 29, 47, 89等。 渐进方法不需要引入一个额外的可信参与方；在协议执行过程中，各参与方采用逐步释放交互信息而达到渐进公平性 (Little-by-little)；尽管如此，有时该方法亦能出现协议不公平的情况，但这种情况能够被量化和控制。 这两种实现协议公平性的方法都各自适用于不同的应用场景，相比乐观方法，渐进方法的优势是明显的，因其不需要可信第三方的参与。可见，分布式密码协议的公平性具有非常广泛的应用，特别是公平秘密共享和公平安全多方计算协议。 而目前对公平性的研究略显不足，无论是在实现方法上，还是在公平协议的应用方面都如此。 非常值得我们进一步深入去探讨。 公平性：在协议的最后，每个参与者都能得到自己的的输出。2.2博弈论2.2.1标准式博弈 完全信息是指所有参与者各自选择的行动的不同组合所决定的各参与者的收益对所有参与者来说是共同知识，即所有的参与人对博弈问题的信息结构有完全的了解，在博弈开始之前所有的参与人对博弈问题本身没有任何不确定性。 标准式博弈又称为战略是表述。标准式表述含有以下三个要素：（1） 博弈参与者集合,；（2） 每个参与者的战略空间；（3） 每个参与者的收益函数。 定义：在一个有个参与者的博弈中，参与者的战略空间为，收益函数为，标准式表述用表示此博弈。2.2.2纳什均衡纳什均衡，又称为非合作博弈均衡，是博弈论的一个重要术语，以约翰·纳什命名。假设有n个局中人参与博弈，给定其他人策略的条件下，每个局中人选择自己的纳什均衡最优策略（个人最优策略可能依赖于也可能不依赖于他人的战略），从而使自己利益最大化。所有局中人策略构成一个策略组合（Strategy Profile）。纳什均衡指的是这样一种战略组合，这种策略组合由所有参与人最优策略组成。即在给定别人策略的情况下，没有人有足够理由打破这种均衡。纳什均衡，从实质上说，是一种非合作博弈状态。纳什均衡达成时，并不意味着博弈双方都处于不动的状态，在顺序博弈中这个均衡是在博弈者连续的动作与反应中达成的。纳什均衡也不意味着博弈双方达到了一个整体的最优状态。 纳什均衡定义：在个参与者标准式博弈中，如果对于每一个参与者，是针对其他个参与者所选战略的最优反应战略，即 对于中所有都成立 ，亦即是最优化问题的解，则战略组合称为该博弈的一个纳什均衡。2.3基本工具2.3.1 ShareGen函数ShareGen函数模型首先由ShareGen提出，现在ShareGen函数计算协议已经有了成熟的实现方案。ShareGen函数计算协议的主要思想是通过或与函数将输出值分成份，再分发给，又将自己收到的结果分成份，先后分别发送给其他个参与者，以达到公平交换信息的目的。输入：参与者分别输入到ShareGen函数，如果输入的值是无效的，函数将（中止符号）发给2个参与者。计算：计算如下： 1.根据几何分布的参数选择； 2.设置保存的值，如下所示： ·if，choose . ·if， set . 3.将异或成，计算函数是：.输出：将传送给,将传送给。 ShareGen函数（ 图1 ShareGen函数 2.3.2秘密共享秘密共享方案是一种分发、保存和恢复秘密信息的方法，是研究如何在一组参与者之间分配或共享一个秘密信息，而该共享秘密信息只有在规定数量的授权用户共同参与才能用特定的方法恢复，其中能够恢复秘密信息的成员子集称为授权集(Authorized set)，而其它子集称为非授权集 (Unauthorized set)，若一个秘密共享方案中的每个非授权集都不能得到该秘密的任何有用信息，则称其为完美秘密共享 (Perfectsecret sharing)。秘密共享方案实现的主要方法有：Shamir 的 Lagrange 插值方法93、Blakley的基于矢量空间的几何方法10、Asmuth 和 Bloom 的中国剩余定理方法5等，其中最常用的是Shamir 基于 Lagrange 插值方法的 门限秘密共享方案，该方法简单、实用而被广泛应用。 下面介绍 Shamir 方案：Shamir的 门限秘密共享方案中的参与者共个，记为，授权集的成员数最小值为，称为门限值。 理性秘密共享是为了在位理性参与者(记为)间实现秘密分享任务。 准确的说，每位参与者有一个效用函数，代表实数空间。向量记为秘密重构的一个结果，这里 当且仅当 最终得到共享秘密。 为了简单，我们也选取大家广泛采用的效用函数假设。 即对 , 的效用函数 满足：(1) 对任意的 , 若 则 ；希望自己活得最多； （2）如果 和, 则。希望别人活得最多。 也会是说，的秘密重构结果，当满足（即要优于），则有对应的效用函数优于对应的效用函数（即）；另外，如果两个重构结果相等，当对应的重构空间总和要比对应的重构空间总和校时，则也有对应的效用函数优于对应的效用函数。第三章 基于ShareGen函数的理性公平多方计算3.1基于ShareGen函数的理性公平两方计算3.1.1 ShareGen函数输入：参与者分别输入到ShareGen函数，如果输入的值是无效的，函数将（中止符号）发给2个参与者。计算：计算如下： 1.根据几何分布的参数选择； 2.设置保存的值，如下所示： ·if，choose . ·if， set . 3.将异或成，计算函数是：.输出：将传送给,将传送给。 ShareGen函数 输入阶段 图2 ShareGen函数输入：参与者使用他们的输入来执行计算的安全协议ShareGen，分别获得的信息是、，计算：这里一共有次迭代，在每次迭代中，ifdo： 1.发送给，计算得到。 2.发送给，计算得到。输出：if在计算的值之前中止协议，then通过如选择输出； if在其他任何时候中止协议，或协议成功完成,那么没有更多消息被发送。获得最后收到的的值。3.1.2协议描述 图3 ShareGen函数两方计算协议3.1.2 协议公平性分析两个参与者通过分裂获得部分信息，再交换信息。再通过获得剩余信息。在该理性模型下,协议的正确性可通过通信协议博弈的规则来保障，其保密性主要体现在博弈中的两主要参与方的效用函数中，对于公平性,我们有如下结果：定义 3.1.2.1 在安全ShareGen函数协议博弈 中, 如果,在传送时都是诚实的,都能获得相同的结果，则称协议博弈是公平的。分析: 如果交换协议是公平的,则该协议也是理性的，反之则不成立。这里将给出上述命题的证明。在我们的模型下，如果安两方协议博弈满足公平性，则意味着以相近的概率确认得到相关秘密信息。 例如， 假设 发送给 ， 要确保 的正确性，同时，也要确保的正确性。是公平的 得到 的结果是相同的。证明：根据博弈定义 3.1.2.1的定义知, 如果错误信息是可忽略的, 对得到结果的正确性没任何影响，则是公平的。事实上,博弈也是公平的，如果,在传输是都是错的，很容易看出 都得不到正确结果。如果博弈满足公平性，根据上述分析，下面我们将给出协议公平性的等价条件及近似公平性定义。如果是真实的，而是虚假的，则得到的结果是正确的，而得到的结果是错误的，与定义中的都能获得相同的结果相矛盾，则不公平，协议无效。综上所述，ShareGen函数协议是公平的。3.2基于ShareGen函数的理性公平多方计算输入：参与者各自分别输入到ShareGen函数，如果输入的值是无效的，函数将（中止符号）发给个参与者。计算：计算如下： 1.根据几何分布的参数选择； 2.设置保存的值，如下所示 ·if，choose . ·if， set . 3.将异或成，计算函数是：.输出：将传送给，将传送给将传送给。3.2.1 ShareGen函数 图4 将ShareGen函数扩展到多方计算输入：个参与者各自用他们的输入来计算ShareGen函数协议，分别获得的信息是， 。计算：这里一共有次迭代，ifdo： 1.发送给，发送给；发送给发送给，计算得到。 2.发送给，发送给；发送给发送给，计算得到。 3.发送给，发送给；发送给发送给，计算得到。 k.发送给，发送给；发送给发送给，计算得到。 n.发送给，发送给；发送给发送给，计算得到。输出：如果他们的输入都是诚实的，则他们都能得到正确的结果，如果他们中有人不诚实，则他们得不到相同正确的结果。3.2.2 协议描述 图4 基于ShareGen函数的理性公平多方计算协议描述3.2.3协议公平性分析 多方参与者通过分裂获得部分信息，再交换信息。再通过获得剩余信息。在该理性模型下,协议的正确性可通过通信协议博弈的规则来保障。其保密性主要体现在博弈中的两主要参与方的效用函数中，对于公平性,我们有如下结果：定义 3.2.2.1 在安全ShareGen函数多方计算协议博弈 中, 如果 在传送时都是诚实的,都能获得相同的结果，策略组合满足纳什均衡，则称协议博弈是公平的。分析: 如果交换协议是公平的, 则该协议也是理性的， 反之则不成立。这里将给出上述命题的证明。 证明:在我们的模型下，如果安多方协议博弈 满足公平性，则意味着以相近的概率确认得到相关秘密信息。 例如, 假设 发送给 . 要确保 的正确性，同时，也要确保所发信息的正确性。是公平的 得到 的结果是相同的。根据博弈定义 3.2.2.1的定义知, 如果错误信息是可忽略的, 对得到结果的正确性没任何影响，则是公平的。事实上,博弈也是公平的，如果在传输是都是错的，很容易看出都得不到正确结果。如果博弈满足公平性，根据上述分析，下面我们将给出协议公平性的等价条件及近似公平性定义。如果发的信息是虚假的，则得到的结果是错误的，而得到的结果是正确的，与定义中的都能获得相同的结果相矛盾，则不公平，协议无效。综上所述，ShareGen函数协议是公平的。此外，每个参与方都只能得到部分信息进行交换，再通过获得的信息计算得到完全的信息，对于参与方来说都有各自的保密信息，所以ShareGen函数计算协议本身是安全的。第四章 基于秘密共享的理性公平多方计算4.1经典方案介绍4.1.1 Shamir的秘密共享方案 这是一个有个参与者的门限秘密共享方案。在该方案中，通过一个多项式对秘密(有限域上的一个元素，且)进行共享。其中，是门限值。参与者的子秘密为，其中是一个参与者相关的上的公开元素，如。给定个或更多个子秘密，以及多项式，就可以将点带入lagrange插值公式，从而计算出。4.1.2 Peterson可验证秘密共享方案 假定为个参与者。令为大素数，为的一个大素因子，且为阶循环群的一个元素。首先，每个随机选取多项式。然后通过保密信道将发送给，并广播。对于接收到的每个，都验证其有效性，验证方法是检验以下等式是否成立：若所有的都通过验证，每个计算作为自己的秘密份额于是。因此，每个可以通过如下等式进行验证：这样，给定任意个秘密份额就可以利用Lagrange插值公式轻易重构出秘密，重构方法如下：重构出的秘密可根据以下等式验证：。需要强调的是，秘密被个参与者所共享，且是由参与者随机选取的。4.1.3 Gennaro的VSS协议秘密分享阶段：1秘密的分发者需要将秘密在分享者中分享。随机选择次多项式对于，计算，将交与参与者；对于，计算并将承诺广播；2检查承诺是否正确。如果正确则接受分享的子秘密，否则广播对的不信任。3。如果有广播对的不信任，则应该公开如下的值：使得。4如果不按照上述的步骤执行，显然是不可信任的，于是协议终止。如果能成功地执行以上的步骤则一个秘密被成功地在所有参与者中分享了。恢复秘密阶段：1每个协议参与者广播得到的子秘密；2每个协议参与者任取个子秘密，并验证其承诺是否正确。如果正确则利用这个点构造次多项式和；3每个协议参与者计算，并验证对于所有的，承诺是否正确。如果正确则输出即是被分享的秘密。Gennaro的协议效率较高的原因在于Gennaro的协议只是对需要分享的秘密进行了承诺，也就是说只承诺了一个秘密，而其他的协议不只是对一 个秘密进行了承诺，而是对一个分享秘密的多项式进行了承诺。4.2基于秘密共享的理性公平多方计算4.2.1协议描述（1）初始阶段Step1：n个参与者，分别记为,每个参与者拥有一个公开的值,以及一个秘密数据（战略组合），为有限域。现在各个参与者共同计算函数: Step2：输入各自的博弈最优值，并用函数 计算输出博弈结果，并使用gennaro的VSS协议进行秘密分享。 图5 基于秘密共享的理性安全多方计算协议初始阶段 （2）计算阶段是使用DL-VSS协议分享的2个秘密，分享秘密的多项式分别是和。协议参与者需要计算。拥有子秘密和，还有和承诺有关的子秘密和，其中r(x)和s(x)是t次随机多项式。承诺和是公开的。因为也是一个随机的t次多项式协议参与者只需计算，即是所持有的分享的子秘密，分享这个秘密的多项式是。同时所有参与者都可以计算对的承诺。 每个协议参与者的输入：。公