【文章內(nèi)容簡介】 00年Canetti[20]提出的安全多方計算協(xié)議的通用可組合安全性。 其它不同的安全性定義可參閱 [8, 50, 51, 77, 88]。 可見，若安全多方協(xié)議滿足安全，則意味著當協(xié)議執(zhí)行結(jié)束后，各參與方得到協(xié)議的結(jié)果及中間數(shù)據(jù)及其通過中間數(shù)據(jù)推導出得一些信息。 若安全多方協(xié)議滿足公平性，則當協(xié)議執(zhí)行結(jié)束后僅能有兩種結(jié)果：要么所有參與者都得到協(xié)議的正確輸出，要么都得不到協(xié)議輸出的任何信息。 所以，安全多方計算協(xié)議的安全性和公平性不僅不同，而且具有交叉性。在多方計算協(xié)議中，設有 位參與者，其中有 位參與者是不誠實的。 當 時，Goldreich[49]的工作表明，在計算安全假定下，存在點對點通信信道，則協(xié)議滿足公平性；BenOr[9]等的工作和Chaum[26]等的工作表明在點對點通信條件下信息論安全的多方安全計算協(xié)議也滿足公平性。 當時，Goldreich等[49]證明在廣播信道下，計算安全的協(xié)議滿足公平性；Rabin和BenOr[90]證明在廣播信道下信息論安全的協(xié)議也滿足公平性。 非常不幸的是，當 時，公平的安全多方計算協(xié)議是不可能實現(xiàn)的。直觀的說，在兩方的情況，參與者可能過早的終止最后一輪信息的發(fā)送，從而導致協(xié)議不滿足公平性。 Cleve[28]證明不存在公平的兩方隨機置幣協(xié)議 (Cointossing protocol)。也就是說，對于任何協(xié)議，都存在敵手，使得敵手 的攻擊行為讓協(xié)議π不滿足公平性。因此，后續(xù)的許多工作都不考慮其公平性問題，即使考慮也僅是研究其部分公平 (Partial fairness)的情形[42][50][52]。在 Cleve 的工作[28]表明兩方公平計算是不可能實現(xiàn)的，但在實際應用中，用戶需要滿足公平性質(zhì)的這類計算協(xié)議，如公平簽約、公平交換協(xié)議等。通過歸納后續(xù)的研究工作可見，主要有兩種方法來實現(xiàn)安全計算協(xié)議的(部分)公平性。一個是樂觀方法(Optimistic approach)[6][19][78]，該方法需要一個可信第三方，當協(xié)議出現(xiàn)有爭議時，需要該可信第三方了仲裁。 從某種程度上來說，可信第三方的引入制約了該方法的發(fā)展前景。 另一個是漸進方法 (Gradual release approach), 該方法的思想始于 Blum[11]，系列工作可見文獻 [13, 29, 47, 89]等。 漸進方法不需要引入一個額外的可信參與方；在協(xié)議執(zhí)行過程中，各參與方采用逐步釋放交互信息而達到漸進公平性 (Littlebylittle)；盡管如此，有時該方法亦能出現(xiàn)協(xié)議不公平的情況，但這種情況能夠被量化和控制。 這兩種實現(xiàn)協(xié)議公平性的方法都各自適用于不同的應用場景，相比樂觀方法，漸進方法的優(yōu)勢是明顯的，因其不需要可信第三方的參與?？梢?，分布式密碼協(xié)議的公平性具有非常廣泛的應用，特別是公平秘密共享和公平安全多方計算協(xié)議。 而目前對公平性的研究略顯不足，無論是在實現(xiàn)方法上，還是在公平協(xié)議的應用方面都如此。 非常值得我們進一步深入去探討。 公平性：在協(xié)議的最后，每個參與者都能得到自己的的輸出。 完全信息是指所有參與者各自選擇的行動的不同組合所決定的各參與者的收益對所有參與者來說是共同知識，即所有的參與人對博弈問題的信息結(jié)構(gòu)有完全的了解，在博弈開始之前所有的參與人對博弈問題本身沒有任何不確定性。 標準式博弈又稱為戰(zhàn)略是表述。標準式表述含有以下三個要素：（1） 博弈參與者集合,；（2） 每個參與者的戰(zhàn)略空間；（3） 每個參與者的收益函數(shù)。 定義：在一個有個參與者的博弈中，參與者的戰(zhàn)略空間為，收益函數(shù)為，標準式表述用表示此博弈。納什均衡，又稱為非合作博弈均衡，是博弈論的一個重要術(shù)語，以約翰納什命名。假設有n個局中人參與博弈，給定其他人策略的條件下，每個局中人選擇自己的納什均衡最優(yōu)策略（個人最優(yōu)策略可能依賴于也可能不依賴于他人的戰(zhàn)略），從而使自己利益最大化。所有局中人策略構(gòu)成一個策略組合（Strategy Profile）。納什均衡指的是這樣一種戰(zhàn)略組合，這種策略組合由所有參與人最優(yōu)策略組成。即在給定別人策略的情況下，沒有人有足夠理由打破這種均衡。納什均衡，從實質(zhì)上說，是一種非合作博弈狀態(tài)。納什均衡達成時，并不意味著博弈雙方都處于不動的狀態(tài)，在順序博弈中這個均衡是在博弈者連續(xù)的動作與反應中達成的。納什均衡也不意味著博弈雙方達到了一個整體的最優(yōu)狀態(tài)。 納什均衡定義：在個參與者標準式博弈中，如果對于每一個參與者，是針對其他個參與者所選戰(zhàn)略的最優(yōu)反應戰(zhàn)略，即 對于中所有都成立 ，亦即是最優(yōu)化問題的解，則戰(zhàn)略組合稱為該博弈的一個納什均衡。 ShareGen函數(shù)ShareGen函數(shù)模型首先由ShareGen提出，現(xiàn)在ShareGen函數(shù)計算協(xié)議已經(jīng)有了成熟的實現(xiàn)方案。ShareGen函數(shù)計算協(xié)議的主要思想是通過或與函數(shù)將輸出值分成份，再分發(fā)給，又將自己收到的結(jié)果分成份，先后分別發(fā)送給其他個參與者，以達到公平交換信息的目的。輸入：參與者分別輸入到ShareGen函數(shù)，如果輸入的值是無效的，函數(shù)將（中止符號）發(fā)給2個參與者。計算：計算如下： ； ，如下所示： if，choose . if， set . ，計算函數(shù)是：.輸出：將傳送給,將傳送給。 ShareGen函數(shù)（ 圖1 ShareGen函數(shù) 秘密共享方案是一種分發(fā)、保存和恢復秘密信息的方法，是研究如何在一組參與者之間分配或共享一個秘密信息，而該共享秘密信息只有在規(guī)定數(shù)量的授權(quán)用戶共同參與才能用特定的方法恢復，其中能夠恢復秘密信息的成員子集稱為授權(quán)集(Authorized set)，而其它子集稱為非授權(quán)集 (Unauthorized set)，若一個秘密共享方案中的每個非授權(quán)集都不能得到該秘密的任何有用信息，則稱其為完美秘密共享 (Perfectsecret sharing)。秘密共享方案實現(xiàn)的主要方法有：Shamir 的 Lagrange 插值方法[93]、Blakley的基于矢量空間的幾何方法[10]、Asmuth 和 Bloom 的中國剩余定理方法[5]等，其中最常用的是Shamir 基于 Lagrange 插值方法的 門限秘密共享方案，該方法簡單、實用而被廣泛應用。 下面介紹 Shamir 方案：Shamir的 門限秘密共享方案中的參與者共個，記為，授權(quán)集的成員數(shù)最小值為，稱為門限值。 理性秘密共享是為了在位理性參與者(記為)間實現(xiàn)秘密分享任務。 準確的說，每位參與者有一個效用函數(shù)，代表實數(shù)空間。向量記為秘密重構(gòu)的一個結(jié)果，這里 當且僅當 最終得到共享秘密。 為了簡單，我們也選取大家廣泛采用的效用函數(shù)假設。 即對 , 的效用函數(shù) 滿足：(1) 對任意的 , 若 則 ；希望自己活得最多； （2）如果 和, 則。希望別人活得最多。 也會是說，的秘密重構(gòu)結(jié)果，當滿足（即要優(yōu)于），則有對應的效用函數(shù)優(yōu)于對應的效用函數(shù)（即）；另外，如果兩個重構(gòu)結(jié)果相等，當對應的重構(gòu)空間總和要比對應的重構(gòu)空間總和校時，則也有對應的效用函數(shù)優(yōu)于對應的效用函數(shù)。第三章 基于ShareGen函數(shù)的理性公平多方計算 ShareGen函數(shù)輸入：參與者分別輸入到ShareGen函數(shù)，如果輸入的值是無效的，函數(shù)將（中止符號）發(fā)給2個參與者。計算：計算如下： ； ，如下所示： if，choose . if， set . ，計算函數(shù)是：.輸出：將傳送給,將傳送給。 ShareGen函數(shù) 輸入階段