本文選題：安全兩方計算 + 理性參與者　； 參考：《山東大學(xué)》2014年博士論文

【摘要】：安全多方計算(Secure Multi-party Computation,SMPC)是現(xiàn)代密碼學(xué)重要的研究方向之一,它不但作為密碼學(xué)基礎(chǔ)的一部分,研究分布式情況下進(jìn)行安全計算的基本原理和方法,還是很多應(yīng)用型密碼學(xué)協(xié)議的直接基礎(chǔ),例如合同簽署,電子投票,電子拍賣和電子簽名等。SMPC可以描述為這樣一個問題：多個相互獨(dú)立的參與者擁有各自的私有輸入,他們希望能夠使用這些輸入計算一個約定的函數(shù)�；灸繕�(biāo)是,能夠得到正確輸出結(jié)果的同時不泄露自己私有輸入的任何額外信息。假設(shè)存在一個可信第三方(Third Trusted Party, TTP)且每個參與者與TTP之間有一條完全保密的信道,各參與方通過保密信道將輸入交給TTP計算這個約定的函數(shù),TTP結(jié)束計算后,將計算結(jié)果通過保密信道發(fā)送給每個參與者。至此多方計算完成并且可以實(shí)現(xiàn)基本目標(biāo),這就是安全多方計算的理想模型。 多方安全計算的目的是使現(xiàn)實(shí)環(huán)境下的協(xié)議實(shí)現(xiàn)理想模型的基本目標(biāo),這些目標(biāo)可以用幾個特性概括,即,隱私性,正確性,輸入獨(dú)立性和輸出公平性。輸出公平性指的是被腐敗的參與者接收到他的輸出當(dāng)且僅當(dāng)誠實(shí)參與者也接收到輸出。Cleve (STOC1986)證明了公平性在少數(shù)誠實(shí)參與者的情況下是不可能實(shí)現(xiàn)的,因此在傳統(tǒng)SMPC,尤其是在安全兩方計算(Secure Two-party Computation, STPC)中,公平性經(jīng)常會被忽略。然而,公平性無論在SMPC還是在STPC中,都是非常重要的特性,尤其是在類似于合同簽署和電子拍賣這樣的現(xiàn)實(shí)協(xié)議中。最近很多文獻(xiàn)給出了實(shí)現(xiàn)公平性的SMPC協(xié)議,例如,有的協(xié)議實(shí)現(xiàn)了非合作計算(Non-cooperation Computation)NCC函數(shù)的公平性,有的協(xié)議利用了物理信封和投票箱實(shí)現(xiàn)了公平性。另外很多較弱的公平性定義也相繼提出來,例如部分公平性(Partial fairness)。 理性安全多方計算(Rational Secure Multi-party Computation, RSMPC)作為一種新方法,為實(shí)現(xiàn)SMPC協(xié)議的公平性提供了一種新的思路。所謂理性安全多方計算指的是帶有理性參與者的安全多方計算。理性參與者與傳統(tǒng)安全多方計算中參與者最大的不同之處在于他們是否遵守協(xié)議是根據(jù)他們的效用來決定的。這與傳統(tǒng)SMPC中的誠實(shí)參與者,半誠實(shí)參與者和惡意敵手有很大的區(qū)別,因?yàn)檫@些參與者和敵手都不依效用來行動。理性參與者與Aumann和Lindell(JOC2010)中提到的隱蔽敵手有類似之處,他們都具有偏離協(xié)議的動機(jī),而且都希望通過偏離協(xié)議獲得各自的利益。RSMPC的思想來源于博弈論(Game Theory),因此在分析和證明RSMPC協(xié)議時,也采取博弈論中的證明思路。首先為每個參與者設(shè)定效用函數(shù),這里效用的設(shè)定不是隨意設(shè)定的,而是根據(jù)一些經(jīng)典博弈進(jìn)行改造的。例如絕大多數(shù)參與者的效用函數(shù)來源于囚徒困境(Prisoner's Dilemma)這一經(jīng)典博弈。其次設(shè)計協(xié)議,使協(xié)議的最終結(jié)果能夠保證隱私性,正確性,輸入獨(dú)立性和輸出公平性。最后證明遵守協(xié)議是一個均衡,每個參與者都沒有偏離協(xié)議的動機(jī)。也就說,每個參與者只有遵守協(xié)議才能夠最大化他們的效用,否則就會得到一個較低的效用。從博弈論的角度來看,RSMPC協(xié)議的主要任務(wù)就是如何設(shè)計好協(xié)議,使得每個參與者都與其他參與者合作而不是背叛其他參與者。如果合作(即,遵守協(xié)議)對每一個參與者來說都是一個占優(yōu)策略,那么公平性自然可以得到保證。 本文主要研究了理性安全兩方計算中公平性的實(shí)現(xiàn)問題,也即,如何促進(jìn)參與者合作。 1.首先將重復(fù)囚徒困境博弈中為了促進(jìn)合作而使用的TFT(Tit-for-Tat)策略引入至RSMPC協(xié)議中來,因?yàn)樵赗SMPC中,為了實(shí)現(xiàn)公平性,必須保證參與者有合作的動機(jī)。利用TFT可策略,理性參與者可以至少在協(xié)議的前幾輪合作,獲得足夠的份額恢復(fù)出函數(shù)值。雖然在引入TFT策略時,聲譽(yù)作為震懾理性參與者的一個因素被考慮到效用函數(shù)中,但是在效用函數(shù)的定義中并沒有體現(xiàn)出來。 2.本文的另一個工作是將聲譽(yù)作為效用函數(shù)定義的一部分,擴(kuò)展了根據(jù)囚徒困境博弈定義的效用。根據(jù)新的效用函數(shù),重新定義了理性參與者類型。證明了,給定合適的參數(shù),雙方合作本身就是納什均衡。因此RSMPC協(xié)議只需要一輪就可以完成份額的交換和函數(shù)值的恢復(fù),這大大提高了RSMPC協(xié)議的效率。 3.本文最后討論了一個復(fù)雜但是更符合實(shí)際情況的RSMPC協(xié)議,即,在不完全信息下,參與者有私有類型的情況。在這種情況下,理性參與者的效用函數(shù)不是以囚徒困境為基礎(chǔ),而是以連鎖店博弈為基礎(chǔ),并且均衡類型也不是納什均衡而是更強(qiáng)的序貫均衡。給定合適參數(shù),公平性在理性安全兩方計算中也可以實(shí)現(xiàn)。 以上三個問題主要研究了如何有效地在兩個參與者之間實(shí)現(xiàn)公平性,可以證明,通過不同的策略和效用函數(shù)定義,公平性能夠在理性兩方計算協(xié)議中實(shí)現(xiàn)。這與傳統(tǒng)兩方安全計算中關(guān)于公平性的結(jié)論不同,這種不同源于對理性參與者的界定不同,正是因?yàn)橛辛诵в眠@一特性,使得一些傳統(tǒng)兩方安全計算中不可能的結(jié)論變?yōu)榭赡堋?除了公平性,RSMPC中還有很多公開問題,例如：如何設(shè)計更合理的策略促使每個參與者合作,如何設(shè)定更加符合實(shí)際的效用函數(shù),是否存在除囚徒困境以外的經(jīng)典博弈適合作為RSMPC的基礎(chǔ),參與者除了效用以外是否還具有其它屬性。
[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 .
【學(xué)位授予單位】：山東大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2014
【分類號】：TN918.1

【參考文獻(xiàn)】

相關(guān)期刊論文 前4條

1 田有亮;馬建峰;彭長根;姬文江;;秘密共享體制的博弈論分析[J];電子學(xué)報;2011年12期

2 張恩;蔡永泉;;基于雙線性對的可驗(yàn)證的理性秘密共享方案[J];電子學(xué)報;2012年05期

3 張恩;蔡永泉;;理性的安全兩方計算協(xié)議[J];計算機(jī)研究與發(fā)展;2013年07期

4 張志芳;劉木蘭;;理性密鑰共享的擴(kuò)展博弈模型[J];中國科學(xué):信息科學(xué);2012年01期

，

本文編號：2046031