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

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

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

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

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

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

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

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

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

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

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