【作者】 张恩；

【导师】 蔡永泉；

【作者基本信息】 北京工业大学 ， 计算机应用技术， 2013， 博士

【摘要】 理性信息交换密码协议结合了密码算法和博弈理论，针对经典秘密共享和安全多方计算协议不能预防参与者欺诈的问题进行了改进，为弥补经典密码学的缺陷提供了新的解决思路，是密码学领域的研究热点。目前对理性信息交换密码协议的研究方兴未艾，尚存在一些问题急需解决，诸如：在消除参与者欺诈动机的同时，分发者不能离线或需要诚实者参与的问题；成员合谋的问题；标准点对点通信网络的需求性问题；计算结果的不公平性问题；缺乏严格的安全性证明等问题。针对上述问题，本文对理性信息交换密码协议的模型及应用进行了研究。首先研究了参与者遵守和背离协议的策略、效用和动机，然后对预防欺诈模型、预防合谋模型、标准点对点通信模型、理性的电路计算模型进行了构建，最后将所建立的模型和方法应用于具体的秘密共享和安全多方计算协议中，所设计的协议，可以预防成员欺诈和合谋，成员能在对点通信网络下，公平地得到计算结果，并且协议的安全性都经过了分析和证明。本文的研究成果和创新点如下：(1)提出了预防成员欺诈的策略和概率效用设计方法，构建了可预防参与者欺诈的博弈模型。对欺诈者进行了效用惩罚，使得参与者在执行协议时，没有欺骗的动机，达到了事先预防参与者欺诈的目的，解决了分发者无法离线的问题，弥补了固定有限轮博弈模型的缺陷。在设计的博弈模型中，也无需有诚实者或可信者参与的硬性条件。(2)提出了可计算防合谋均衡的设计方法，构建了预防参与者合谋的博弈模型。分析了成员合谋行为及防范对策，使得参与者所采取的策略满足可计算防合谋均衡，合谋成员不清楚当前轮是真秘密所在轮，还是检验参与者诚实度的测试轮，参与者采取合谋策略的期望收益没有遵守算法的收益大，因此，理性的参与者没有动机合谋偏离策略。从而解决了参与者合谋问题。(3)针对标准点对点通信网络提出了理性信息交换密码协议的博弈模型，模型摆脱了广播通信的束缚，不会出现单点崩溃，并且维护容易、具有良好的鲁棒性及较佳的并发处理能力，同时也达到了模拟广播通信的效果，解决了广播通信网络下所设计的理性密码协议不能在互联网络中实现的问题，从而更加符合实际。(4)提出了电路计算模型和博弈论相融合的方法，构建了理性的电路计算模型。该模型可以在没有大多数诚实者参与前提下，使得参与者根据自己的利益得失，有动机发送正确数据。遵守电路计算的每一步都是其利益驱动的，最终达到计算公平性的目的。从而解决了传统的电路计算模型计算不公平的问题。(5)将以上研究所建立的模型应用于秘密共享协议和安全多方计算协议中，以验证模型的正确性：首先，在标准点对点通信网络下，设计了一种可证明安全的理性多秘密共享协议，解决了理性单秘密共享协议效率低下问题，消除了参与者合谋动机，摆脱了广播通信的束缚；然后，设计了一种理性百万富翁协议，解决了传统百万富翁协议都建立在半诚实模型下的缺陷；最后，基于电路计算设计了一种理性安全多方求和协议，解决了参与者合谋问题，达到了计算公平的目的。更多还原

【Abstract】 Rational information exchange cryptographic protocols, combined cryptographyand game theory, were developed to address the problems that classical secret sharingand secure multiparty computation protocols can not take precautions against cheating.These protocols provide a new ideal for solving the defect of classical cryptography,and have become a research focus of cryptography. At present the research aboutrational information exchange cryptographic protocols is in the ascendant, and someproblems need to be resolved urgently as follows: the demand of the on-line dealer orhonest parties, the threatening of the participants’ conspiracy, the demand of thestandard point-to-point communication networks, the unfairness of the calculations,and the lack of strict proof of security, etc.To address the above problems, we study the models of rational informationexchange cryptographic protocols and applications in this dissertation. First andforemost, the game strategies, utilities, and motivations that participants deviate fromor abide by the protocol are analyzed. Besides, the fraud prevention model, thecoalition-proof model, the standard point-to-point communication model, and therational circuit computation model are designed. Last but not least, the models andmethods are applied to specific secret sharing protocols and secure multipartycomputation protocols. These protocols can prevent cheating and collusion of parties,and every party can learn the result of the computation fairly in point-to-pointcommunication networks. Furthermore, the security of these protocols has beenanalyzed and proved.Specifically, the contributions and innovations of this dissertation are as follows.(1) Design methods of strategies and probabilistic payoffs for preventingparticipants’ fraud are proposed, and the game model of fraud prevention is developed.In this model, cheaters will be punished, and every participant has no incentive tocheat, so that the purpose of preventing cheating is achieved. Moreover, the problemof the on-line dealer is addressed. Without the participation of the trusted party orhonest parties, this model, also makes up the defect of the fixed finite round gamemodel that is sensitive to reverse induction.(2) Design methods of computational coalition-proof Nash equilibrium areproposed, and the game model of coalition-proof is developed. The coalition behaviorof participants and the countermeasures have been analyzed. The strategies of participants satisfy the computational coalition-proof Nash equilibrium, and themembers of coalition do not know whether the current round is a real round or a fakeround to test participants’ honesty. The payoff of abiding by the protocol is more thanthe expected payoff of conspiring to deviate from the protocol. As a result, rationalparticipants have no incentive to deviate from the protocol. Therefore, the problem ofcollusion is resolved.(3) The game models of rational information exchange cryptographic protocolsare proposed in the standard point-to-point communication networks. With betterrobustness and concurrent processing capability, the models not only get rid of theshackles of broadcast communication but also simulate the effect of the broadcastcommunication. In addition, the models are easy to be implemented, and do notcollapse to a single point. Thus, the problem that the game models in the broadcastnetworks can not be implemented on the Internet is addressed, which makes theporposed models more practical and realistic.(4) One integrated approach of circuit evaluation model and game theory isproposed，and the rational circuit calculation model is designed. In the model, thepremise that a majority of participants are honest does not need to be concerned, andthe participants have an incentive to send the correct data according to their ownpayoffs. Complying with every step of the circuit evaluation is to maximize theirbenefits. Therefore, the issue of the unfairness in traditional circuit evaluation modelis solved.(5) The correctness of the models is investigated by applying these models to thesecret sharing and secure multiparty computation protocols. Firstly, a provably secureprotocol for rational multi-secret sharing in the standard point-to-pointcommunication networks is proposed, which is coalition-proof and avoids theinefficiency of the rational single secret sharing protocol. In addition, the defect of thesimultaneous broadcast communication mode has been successfully addressed. Then,a rational protocol to millionaire problem is proposed, and the problem that traditionalmillionaire protocols are designed in the semi-honest model has been resolved. Finally,based on circuit evaluation, a rational secure sum protocol is proposed, the problem ofcoalition is addressed and the purpose of fairness is achieved.更多还原