《安全多方計算》

第十二章平安多方計算楊秋偉湖南大學(xué)計算機(jī)與通信學(xué)院平安多方計算：密碼學(xué)家晚餐問題DavidChaum的密碼學(xué)家晚餐問題場景描述三個密碼學(xué)家(AliceBobCarol)坐在他們最喜歡的三星級餐館準(zhǔn)備吃晚餐業(yè)務(wù)邏輯侍者通知他們晚餐需匿名支付賬單其中一個密碼學(xué)家可能正在付賬可能已由美國國家平安局NSA付賬他們彼此尊重匿名付賬的權(quán)利，但又需要知道是不是NSA在付賬系統(tǒng)目標(biāo)如何確定三者之一在付賬同事又要保護(hù)付賬者的匿名性？？？？？平安多方計算：密碼學(xué)家晚餐問題DavidChaum的密碼學(xué)家晚餐問題一個簡單有效的解決方案每個密碼學(xué)家將菜單放置于左邊而互相隔離開來每個人只能看到自己和右邊密碼學(xué)家的結(jié)果每個密碼學(xué)家在他和右邊密碼學(xué)家之間拋擲一枚硬幣每個密碼學(xué)家播送她能看到的兩枚硬幣是同一面還是不同的一面如果有一個密碼學(xué)家付賬，那么他說相反的結(jié)果判定結(jié)果桌上說“不同〞的人數(shù)為奇數(shù)——某個密碼學(xué)家在付賬桌上說“不同〞的人數(shù)為偶數(shù)——NSA在付賬如果某個密碼學(xué)家在付賬，另兩人不能精確定位到該密碼學(xué)家平安多方計算：密碼學(xué)家晚餐問題假設(shè)密碼學(xué)家Alice試圖弄清其他哪個密碼學(xué)家在付賬如果她看見兩個不同的硬幣那么另外兩個密碼學(xué)家或者都說“相同〞、或者都說“不同〞付賬者是最靠近與未看見的硬幣不同的那枚硬幣的密碼學(xué)家如果她看見兩個相同的硬幣那么另外兩個密碼學(xué)家一個說“相同而另一個說“不同〞如果未看見的硬幣與她看到的兩枚硬幣相同說“不同〞的密碼學(xué)家是付賬者如果未看見的硬幣與她看到的兩枚硬幣不同說“相同〞的密碼學(xué)家是付賬者平安多方計算：密碼學(xué)家晚餐問題假設(shè)密碼學(xué)家Alice試圖弄清其他哪個密碼學(xué)家在付賬無論如何Alice都需要知道Bob與Carol拋擲硬幣的結(jié)果Crypt(i),Coin(i)分別表示密碼學(xué)家和擲幣結(jié)果Crypt(i)付款輸出=Coin(i-1)⊕Coin(i)Crypt(i)沒付款輸出=Coin(i-1)⊕Coin(i)⊕1平安多方計算：密碼學(xué)家晚餐問題Crypt(0)Crypt(1)Crypt(2)Coin(0)Coin(2)Coin(1)平安多方計算：密碼學(xué)家晚餐問題“晚餐問題〞的延伸兩個密碼學(xué)家的“晚餐問題〞協(xié)議他們會知道誰付的賬旁觀者只知道其中某個人付賬或者NSA付賬，不能精確定位任意數(shù)量的密碼學(xué)家“晚餐問題〞協(xié)議全部坐成一個圈并在他們中拋擲硬幣平安多方計算：密碼學(xué)家晚餐問題“晚餐問題〞的應(yīng)用——匿名消息播送用戶把他們自己排進(jìn)一個邏輯圓圈構(gòu)造飯桌在一定的時間間隔內(nèi)，相鄰的每對用戶對他們之間拋擲硬幣使用一些公正的硬幣拋擲協(xié)議防止竊聽者在每次拋擲之后每個用戶說“相同〞或“不同〞無條件的發(fā)送方和接受方不可追蹤性惡意的參與者不能讀出報文，但他能通過在第三步撒謊來破壞系統(tǒng)平安多方計算：平均工資問題平均工資問題場景描述Alice、Bob、Carol和Dave四人在一起組織工作業(yè)務(wù)需求他們想了解平均工資無仲裁者系統(tǒng)目標(biāo)任何人不想讓其他人知道自己的工資平安多方計算：平均工資問題平均工資問題的一種有效解決方案Alice生成一個隨機(jī)數(shù)，將其與自己的工資相加，用Bob的公鑰加密發(fā)送給BobBob用自己的私鑰解密，加進(jìn)自己的工資，然后用Carol的公鑰加密發(fā)送給CarolCarol用自己的私鑰解密，加進(jìn)自己的工資，然后用Dave的公鑰加密發(fā)送給Dave平安多方計算：平均工資問題平均工資問題的一種有效解決方案Dave用自己的私鑰解密，加進(jìn)自己的工資，然后用Alice的公鑰加密發(fā)送給AliceAlice用自己的私鑰解密，減去原來的隨機(jī)數(shù)得到工資總和Alice將工資總和除以人數(shù)得到平均工資，宣布結(jié)果協(xié)議假定所有的參與者是老實的，如果不老實那么平均工資錯誤Alice可以謊報結(jié)果〔她作為了“名義上〞的集成者〕平安多方計算：平均工資問題平均工資問題的一種有效解決方案比特承諾可以解決“Alice謊報〞缺陷運(yùn)用比特承諾協(xié)議讓Alice向Bob傳送他的隨機(jī)數(shù)協(xié)議結(jié)束后，Bob可以獲知Alice的工資平安多方計算：終身伴侶問題終身伴侶問題場景描述Alice、Bob都在尋找終身伴侶——相親(非誠勿擾、我們約會吧)業(yè)務(wù)需求(興趣愛好)Alice：KTV、逛街、勁樂團(tuán)Bob：NBA、足球、聚會、宅系統(tǒng)目標(biāo)對自己的擇偶要求難為情——含蓄表達(dá)、意會、不表達(dá)找一個趣味相投的終身伴侶平安多方計算：終身伴侶問題終身伴侶問題的一種有效解決方案使用一個單向函數(shù)，Alice將她的擇偶要求m，HASH得到一個8位數(shù)字的字符串h(m)Alice用這8位數(shù)字作為號碼撥號，并留言如果號碼無效，Alice給這個號碼申請一個單向函數(shù)直到她找到一個與她有相同擇偶要求的人Alice告訴Bob她為她的擇偶要求申請一個單向函數(shù)的次數(shù)Bob用和Alice相同次數(shù)的HASH他的擇偶要求他也用這個8位數(shù)字作為號碼，試圖聽取留言有留言，那么配對成功平安多方計算：終身伴侶問題終身伴侶問題的一種有效解決方案Bob可以進(jìn)行“選擇明文攻擊〞可以HASH一般的擇偶要求撥打所得的號碼，以竊聽留言只有在不可能得到足夠多的明文消息的情況下該協(xié)議平安平安多方計算：其它幾個經(jīng)典應(yīng)用場景例如一Alice認(rèn)為自己得了某種遺傳疾病，想驗證自己的想法她知道Bob有一個關(guān)于疾病的DNA模型的數(shù)據(jù)庫如果她把自己的DNA樣品寄給BobBob可以給出她的DNA的診斷結(jié)果Alice又不想別人知道——這是她的隱私平安多方計算：其它幾個經(jīng)典應(yīng)用場景例如二A公司決定擴(kuò)展在某些地區(qū)的市場份額來獲取豐厚的回報A公司也注意到B公司也在擴(kuò)展一些地區(qū)的市場份額兩個公司都不想在相同地區(qū)互相競爭信息的泄露可能會導(dǎo)致公司很大的損失比方另一家對手公司知道A和B公司的擴(kuò)展地區(qū)，提前行動占領(lǐng)市場又比方房地產(chǎn)公司知道A和B公司的擴(kuò)展方案，提前提高當(dāng)?shù)氐姆孔獾鹊仍诓恍孤妒袌龅貐^(qū)位置信息的情況下知道市場是否有重疊平安多方計算：其它幾個經(jīng)典應(yīng)用場景例如三兩個金融組織方案為了共同的利益決定互相合作一個工程每個組織都想自己的需求獲得滿足他們的需求都是他們自己專有的數(shù)據(jù)，沒人愿意透露給其它方，甚至是“信任〞的第三方那么他們?nèi)绾卧诒Ｗo(hù)數(shù)據(jù)私密性的前提下合作工程呢？平安多方計算：根本概念多方計算問題一組參與者希望共同計算某個約定的函數(shù)函數(shù)的輸入?yún)?shù)有多個每個參與者提供函數(shù)的一個輸入平安多方計算問題(SecureMulti-partyComputation)引入平安因素其中每個人都知道這個函數(shù)的值除了函數(shù)的輸出外，沒有人知道關(guān)于任何其它成員輸入的任何事情平安多方計算：根本概念來自于經(jīng)典應(yīng)用場景的啟發(fā)平安多方計算的根本特征兩方或多方參與者基于他們各自私密輸入的