第十二章 安全多方計算

第十二章安全多方計算楊秋偉湖南大學(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ù)數(shù)得到工資資總和Alice將工資總和和除以人數(shù)數(shù)得到平均均工資，宣宣布結(jié)果協(xié)議假定所所有的參與與者是誠實實的，如果果不誠實則則平均工資資錯誤Alice可以謊報結(jié)結(jié)果（她作作為了“名義上”的集成者者）安全多方計計算：平均工資問問題平均工資問問題的一種種有效解決決方案比特承諾可以解決““Alice謊報”缺陷運用用比比特特承承諾諾協(xié)協(xié)議議讓讓Alice向Bob傳送送他他的的隨隨機(jī)機(jī)數(shù)數(shù)協(xié)議議結(jié)結(jié)束束后后，，Bob可以以獲獲知知Alice的工工資資安全全多多方方計計算算：：終身身伴伴侶侶問問題題終身身伴伴侶侶問問題題場景景描描述述Alice、Bob都在在尋尋找找終終身身伴伴侶侶————相親親(非誠誠勿勿擾擾、、我我們們約約會會吧吧)業(yè)務(wù)務(wù)需需求求(興趣趣愛愛好好)Alice：KTV、逛逛街、勁樂團(tuán)團(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ù)的次數(shù)Bob用和Alice相同次數(shù)的HASH他的擇偶要求求他也用這個8位數(shù)字作為為電話號碼，，試圖聽取留留言有留言，則配配對成功安全多方方計算：：終身伴侶侶問題終身伴侶侶問題的的一種有有效解決決方案Bob可以進(jìn)行行“選擇明文文攻擊”可以HASH一一般的擇擇偶要求求撥打所得得的電話話號碼，，以竊聽聽留言只有在不不可能得得到足夠夠多的明明文消息息的情況況下該協(xié)協(xié)議安全全安全多方方計算：：其它幾個個經(jīng)典應(yīng)應(yīng)用場景景示例一Alice認(rèn)為自己己得了某某種遺傳傳疾病，，想驗證證自己的的想法她知道Bob有一個關(guān)關(guān)于疾病病的DNA模型型的數(shù)據(jù)據(jù)庫如果她把把自己的的DNA樣品寄寄給BobBob可以給出出她的DNA的的診斷結(jié)結(jié)果Alice又不不想別人人知道———這是是她的隱隱私安全多方方計算：：其它幾個個經(jīng)典應(yīng)應(yīng)用場景景示例二A公司決定定擴(kuò)展在在某些地地區(qū)的市市場份額額來獲取取豐厚的的回報A公司也注注意到B公司也在在擴(kuò)展一一些地區(qū)區(qū)的市場場份額兩個公司司都不想想在相同同地區(qū)互互相競爭爭信息的泄泄露可能能會導(dǎo)致致公司很很大的損損失比如另一一家對手手公司知知道A和和B公司司的擴(kuò)展展地區(qū)，，提前行行動占領(lǐng)領(lǐng)市場又比如房房地產(chǎn)公公司知道道A和B公司的的擴(kuò)展計計劃，提提前提高高當(dāng)?shù)氐牡姆孔獾鹊鹊仍诓恍孤堵妒袌龅氐貐^(qū)位置置信息的的情況下下知道市市場是否否有重疊疊安全多方方計算：：其它幾個個經(jīng)典應(yīng)應(yīng)用場景景示例三兩個金融融組織計計劃為了了共同的的利益決決定互相相合作一一個項目目每個組織織都想自自己的需需求獲得得滿足他們的需需求都是是他們自自己專有有的數(shù)據(jù)據(jù)，沒人人愿意透透露給其其它方，，甚至是是“信任任”的第第三方那么他們們?nèi)绾卧谠诒Ｗo(hù)數(shù)數(shù)據(jù)私密密性的前前提下合合作項目目呢？安全多方計計算：基本概念多方計算問問題一組參與者者希望共同同計算某個個約定的函函數(shù)函數(shù)的輸入入?yún)?shù)有多多個每個參與者者提供函數(shù)數(shù)的一個輸輸入安全多方計計算問題(SecureMulti-partyComputation)引入安全因因素其中每個人人都知道這這個函數(shù)的的值除了函數(shù)的的輸出外，，沒有人知知道關(guān)于任任何其它成成員輸入的的任何事情情安全多方計計算：基本概念來自于經(jīng)典典應(yīng)用場景景的啟發(fā)安全多方計計算的基本本特征兩方或多方方參與者基基于他們各各自私密輸輸入的計算算彼此都不想想其它方知知道自己的的輸入信息息問題變成了了在保