理性安全两方计算中的公平性研究

发布时间：2018-06-20 23:05

本文选题：安全两方计算 + 理性参与者　；参考：《山东大学》2014年博士论文

【摘要】：安全多方计算(Secure Multi-party Computation,SMPC)是现代密码学重要的研究方向之一,它不但作为密码学基础的一部分,研究分布式情况下进行安全计算的基本原理和方法,还是很多应用型密码学协议的直接基础,例如合同签署,电子投票,电子拍卖和电子签名等。SMPC可以描述为这样一个问题：多个相互独立的参与者拥有各自的私有输入,他们希望能够使用这些输入计算一个约定的函数。基本目标是,能够得到正确输出结果的同时不泄露自己私有输入的任何额外信息。假设存在一个可信第三方(Third Trusted Party, TTP)且每个参与者与TTP之间有一条完全保密的信道,各参与方通过保密信道将输入交给TTP计算这个约定的函数,TTP结束计算后,将计算结果通过保密信道发送给每个参与者。至此多方计算完成并且可以实现基本目标,这就是安全多方计算的理想模型。多方安全计算的目的是使现实环境下的协议实现理想模型的基本目标,这些目标可以用几个特性概括,即,隐私性,正确性,输入独立性和输出公平性。输出公平性指的是被腐败的参与者接收到他的输出当且仅当诚实参与者也接收到输出。Cleve (STOC1986)证明了公平性在少数诚实参与者的情况下是不可能实现的,因此在传统SMPC,尤其是在安全两方计算(Secure Two-party Computation, STPC)中,公平性经常会被忽略。然而,公平性无论在SMPC还是在STPC中,都是非常重要的特性,尤其是在类似于合同签署和电子拍卖这样的现实协议中。最近很多文献给出了实现公平性的SMPC协议,例如,有的协议实现了非合作计算(Non-cooperation Computation)NCC函数的公平性,有的协议利用了物理信封和投票箱实现了公平性。另外很多较弱的公平性定义也相继提出来,例如部分公平性(Partial fairness)。理性安全多方计算(Rational Secure Multi-party Computation, RSMPC)作为一种新方法,为实现SMPC协议的公平性提供了一种新的思路。所谓理性安全多方计算指的是带有理性参与者的安全多方计算。理性参与者与传统安全多方计算中参与者最大的不同之处在于他们是否遵守协议是根据他们的效用来决定的。这与传统SMPC中的诚实参与者,半诚实参与者和恶意敌手有很大的区别,因为这些参与者和敌手都不依效用来行动。理性参与者与Aumann和Lindell(JOC2010)中提到的隐蔽敌手有类似之处,他们都具有偏离协议的动机,而且都希望通过偏离协议获得各自的利益。RSMPC的思想来源于博弈论(Game Theory),因此在分析和证明RSMPC协议时,也采取博弈论中的证明思路。首先为每个参与者设定效用函数,这里效用的设定不是随意设定的,而是根据一些经典博弈进行改造的。例如绝大多数参与者的效用函数来源于囚徒困境(Prisoner's Dilemma)这一经典博弈。其次设计协议,使协议的最终结果能够保证隐私性,正确性,输入独立性和输出公平性。最后证明遵守协议是一个均衡,每个参与者都没有偏离协议的动机。也就说,每个参与者只有遵守协议才能够最大化他们的效用,否则就会得到一个较低的效用。从博弈论的角度来看,RSMPC协议的主要任务就是如何设计好协议,使得每个参与者都与其他参与者合作而不是背叛其他参与者。如果合作(即,遵守协议)对每一个参与者来说都是一个占优策略,那么公平性自然可以得到保证。本文主要研究了理性安全两方计算中公平性的实现问题,也即,如何促进参与者合作。 1.首先将重复囚徒困境博弈中为了促进合作而使用的TFT(Tit-for-Tat)策略引入至RSMPC协议中来,因为在RSMPC中,为了实现公平性,必须保证参与者有合作的动机。利用TFT可策略,理性参与者可以至少在协议的前几轮合作,获得足够的份额恢复出函数值。虽然在引入TFT策略时,声誉作为震慑理性参与者的一个因素被考虑到效用函数中,但是在效用函数的定义中并没有体现出来。 2.本文的另一个工作是将声誉作为效用函数定义的一部分,扩展了根据囚徒困境博弈定义的效用。根据新的效用函数,重新定义了理性参与者类型。证明了,给定合适的参数,双方合作本身就是纳什均衡。因此RSMPC协议只需要一轮就可以完成份额的交换和函数值的恢复,这大大提高了RSMPC协议的效率。 3.本文最后讨论了一个复杂但是更符合实际情况的RSMPC协议,即,在不完全信息下,参与者有私有类型的情况。在这种情况下,理性参与者的效用函数不是以囚徒困境为基础,而是以连锁店博弈为基础,并且均衡类型也不是纳什均衡而是更强的序贯均衡。给定合适参数,公平性在理性安全两方计算中也可以实现。以上三个问题主要研究了如何有效地在两个参与者之间实现公平性,可以证明,通过不同的策略和效用函数定义,公平性能够在理性两方计算协议中实现。这与传统两方安全计算中关于公平性的结论不同,这种不同源于对理性参与者的界定不同,正是因为有了效用这一特性,使得一些传统两方安全计算中不可能的结论变为可能。除了公平性,RSMPC中还有很多公开问题,例如：如何设计更合理的策略促使每个参与者合作,如何设定更加符合实际的效用函数,是否存在除囚徒困境以外的经典博弈适合作为RSMPC的基础,参与者除了效用以外是否还具有其它属性。
[Abstract]:Secure Multi - party Computing ( SMPC ) is one of the important research directions of modern cryptography . It is not only a part of cryptography , but also the direct basis of many applied cryptography protocols , such as contract signing , electronic voting , electronic auction and electronic signature .

The aim of multi - party security calculation is to make the agreement in real environment the basic goal of ideal model . These goals can be summarized by several characteristics , i.e . , privacy , correctness , input independence and output fairness . The fairness refers to the fairness of non - cooperative computing NCC function .

Rational Security Multi - party Computing ( RSMPC ) , as a new approach , provides a new way to achieve the fairness of the SMPC protocol .

This paper mainly studies the realization of fairness in rational and safe two - party computing , that is , how to promote the cooperation of participants .

1 . First , the TFT ( Tit - for - tat ) strategy used to promote cooperation is introduced into the RSMPC protocol in order to promote cooperation . In RSMPC , in order to achieve fairness , it is necessary to guarantee the motivation of cooperation . By using the TFT strategy , the rational participator can cooperate at least in the first few rounds of the protocol to get enough shares to recover the function value . Although the reputation is considered as a factor of the deterrent rational participant in the introduction of the TFT strategy , it is not reflected in the definition of the utility function .

2 . Another work of this paper is to extend the reputation as part of the definition of utility function , and expand the utility according to the definition of the prisoner ' s dilemma game . According to the new utility function , the rationality participant type is redefined . It is proved that given the appropriate parameters , the cooperation of both parties itself is Nash equilibrium . Therefore , the RSMPC protocol only needs a round to complete the exchange of shares and the restoration of function values , which greatly improves the efficiency of RSMPC protocol .

3 . In this paper , the RSMPC protocol , which is more complex but more realistic , is discussed . In this case , the participants have the private type . In this case , the utility function of the rational participants is not based on the prisoner ' s dilemma , but the equilibrium type is not Nash equilibrium but stronger sequential equilibrium . Given the appropriate parameters , fairness can also be realized in rational and safe two - party computing .

The above three questions mainly study how to achieve fairness among the two participants . It can be proved that the fairness can be realized in the rational two - party computing agreement through different strategies and utility functions . This is different from the conclusion about fairness in the traditional two - party security calculation , which is the characteristic of utility , which makes some impossible conclusions in traditional two - party security calculation possible .

In addition to fairness , there are many public issues in RSMPC , such as how to design a more reasonable strategy to motivate each participant , how to set a more realistic utility function , whether there is a classic game other than the prisoner ' s dilemma is suitable as the basis for RSMPC , and whether the participants have other attributes than utility .
【学位授予单位】：山东大学
【学位级别】：博士
【学位授予年份】：2014
【分类号】：TN918.1

【参考文献】