理性安全兩方計(jì)算中的公平性研究.pdf

1、安全多方計(jì)算(Secure Multi-party Computation，SMPC)是現(xiàn)代密碼學(xué)重要的研究方向之一，它不但作為密碼學(xué)基礎(chǔ)的一部分，研究分布式情況下進(jìn)行安全計(jì)算的基本原理和方法，還是很多應(yīng)用型密碼學(xué)協(xié)議的直接基礎(chǔ)，例如合同簽署，電子投票，電子拍賣和電子簽名等。SMPC可以描述為這樣一個(gè)問題:多個(gè)相互獨(dú)立的參與者擁有各自的私有輸入，他們希望能夠使用這些輸入計(jì)算一個(gè)約定的函數(shù)?；灸繕?biāo)是，能夠得到正確輸出結(jié)果的同時(shí)不泄露自己

2、私有輸入的任何額外信息。假設(shè)存在一個(gè)可信第三方(Third Trusted Party，TTP)且每個(gè)參與者與TTP之間有一條完全保密的信道，各參與方通過保密信道將輸入交給TTP計(jì)算這個(gè)約定的函數(shù)，TTP結(jié)束計(jì)算后，將計(jì)算結(jié)果通過保密信道發(fā)送給每個(gè)參與者。至此多方計(jì)算完成并且可以實(shí)現(xiàn)基本目標(biāo)，這就是安全多方計(jì)算的理想模型。
　　多方安全計(jì)算的目的是使現(xiàn)實(shí)環(huán)境下的協(xié)議實(shí)現(xiàn)理想模型的基本目標(biāo)，這些目標(biāo)可以用幾個(gè)特性概括，即，隱私性，正

3、確性，輸入獨(dú)立性和輸出公平性。輸出公平性指的是被腐敗的參與者接收到他的輸出當(dāng)且僅當(dāng)誠(chéng)實(shí)參與者也接收到輸出。Cleve(STOC1986)證明了公平性在少數(shù)誠(chéng)實(shí)參與者的情況下是不可能實(shí)現(xiàn)的，因此在傳統(tǒng)SMPC，尤其是在安全兩方計(jì)算(Secure Two-party Computation，STPC)中，公平性經(jīng)常會(huì)被忽略。然而，公平性無論在SMPC還是在STPC中，都是非常重要的特性，尤其是在類似于合同簽署和電子拍賣這樣的現(xiàn)實(shí)協(xié)議中。最近

4、很多文獻(xiàn)給出了實(shí)現(xiàn)公平性的SMPC協(xié)議，例如，有的協(xié)議實(shí)現(xiàn)了非合作計(jì)算(Non-cooperation Computation)NCC函數(shù)的公平性，有的協(xié)議利用了物理信封和投票箱實(shí)現(xiàn)了公平性。另外很多較弱的公平性定義也相繼提出來，例如部分公平性(Partialfairness)。
　　理性安全多方計(jì)算(Rational Secure Multi-party Computation，RSMPC)作為一種新方法，為實(shí)現(xiàn)SMPC協(xié)議的公

5、平性提供了一種新的思路。所謂理性安全多方計(jì)算指的是帶有理性參與者的安全多方計(jì)算。理性參與者與傳統(tǒng)安全多方計(jì)算中參與者最大的不同之處在于他們是否遵守協(xié)議是根據(jù)他們的效用來決定的。這與傳統(tǒng)SMPC中的誠(chéng)實(shí)參與者，半誠(chéng)實(shí)參與者和惡意敵手有很大的區(qū)別，因?yàn)檫@些參與者和敵手都不依效用來行動(dòng)。理性參與者與Aumann和Lindell(JOC2010)中提到的隱蔽敵手有類似之處，他們都具有偏離協(xié)議的動(dòng)機(jī)，而且都希望通過偏離協(xié)議獲得各自的利益。RSMP

6、C的思想來源于博弈論(Game Theory)，因此在分析和證明RSMPC協(xié)議時(shí)，也采取博弈論中的證明思路。首先為每個(gè)參與者設(shè)定效用函數(shù)，這里效用的設(shè)定不是隨意設(shè)定的，而是根據(jù)一些經(jīng)典博弈進(jìn)行改造的。例如絕大多數(shù)參與者的效用函數(shù)來源于囚徒困境(Prisoner's Dilemma)這一經(jīng)典博弈。其次設(shè)計(jì)協(xié)議，使協(xié)議的最終結(jié)果能夠保證隱私性，正確性，輸入獨(dú)立性和輸出公平性。最后證明遵守協(xié)議是一個(gè)均衡，每個(gè)參與者都沒有偏離協(xié)議的動(dòng)機(jī)。也就說

7、，每個(gè)參與者只有遵守協(xié)議才能夠最大化他們的效用，否則就會(huì)得到一個(gè)較低的效用。從博弈論的角度來看，RSMPC協(xié)議的主要任務(wù)就是如何設(shè)計(jì)好協(xié)議，使得每個(gè)參與者都與其他參與者合作而不是背叛其他參與者。如果合作（即，遵守協(xié)議）對(duì)每一個(gè)參與者來說都是一個(gè)占優(yōu)策略，那么公平性自然可以得到保證。
　　本文主要研究了理性安全兩方計(jì)算中公平性的實(shí)現(xiàn)問題，也即，如何促進(jìn)參與者合作。
　　1.首先將重復(fù)囚徒困境博弈中為了促進(jìn)合作而使用的TFT(T

8、it-for-Tat)策略引入到RSMPC協(xié)議中來，因?yàn)樵赗SMPC中，為了實(shí)現(xiàn)公平性，必須保證參與者有合作的動(dòng)機(jī)。利用TFT策略，理性參與者可以至少在協(xié)議的前幾輪合作，獲得足夠的份額恢復(fù)出函數(shù)值。雖然在引入TFT策略時(shí)，聲譽(yù)作為震懾理性參與者的一個(gè)因素被考慮到效用函數(shù)中，但是在效用函數(shù)的定義中并沒有體現(xiàn)出來。
　　2.本文的另一個(gè)工作是將聲譽(yù)作為效用函數(shù)定義的一部分，擴(kuò)展了根據(jù)囚徒困境博弈定義的效用。根據(jù)新的效用函數(shù)，重新定義了

9、理性參與者類型。證明了，給定合適的參數(shù)，雙方合作本身就是納什均衡。因此RSMPC協(xié)議只需要一輪就可以完成份額的交換和函數(shù)值的恢復(fù)，這大大提高了RSMPC協(xié)議的效率。
　　3.本文最后討論了一個(gè)復(fù)雜但是更符合實(shí)際情況的RSMPC協(xié)議，即，在不完全信息下，參與者有私有類型的情況。在這種情況下，理性參與者的效用函數(shù)不是以囚徒困境為基礎(chǔ)，而是以連鎖店博弈為基礎(chǔ)，并且均衡類型也不是納什均衡而是更強(qiáng)的序貫均衡。給定合適參數(shù)，公平性在理性安全兩

10、方計(jì)算中也可以實(shí)現(xiàn)。
　　以上三個(gè)問題主要研究了如何有效地在兩個(gè)參與者之間實(shí)現(xiàn)公平性，可以證明，通過不同的策略和效用函數(shù)定義，公平性能夠在理性兩方計(jì)算協(xié)議中實(shí)現(xiàn)。這與傳統(tǒng)兩方安全計(jì)算中關(guān)于公平性的結(jié)論不同，這種不同源于對(duì)理性參與者的界定不同，正是因?yàn)橛辛诵в眠@一特性，使得一些傳統(tǒng)兩方安全計(jì)算中不可能的結(jié)論變?yōu)榭赡堋?br>　　除了公平性，RSMPC中還有很多公開問題，例如:如何設(shè)計(jì)更合理的策略促使每個(gè)參與者合作，如何設(shè)定更加符合實(shí)