安全多方計算技術(shù)(Security Multi-Party Computation, SMC) 收藏
一、 什么是安全多方計算?
為了說明什么是安全多方計算，首先我們先介紹幾個實際生活中的例子。
1． Alice認為她的了某種遺傳疾病，想驗證自己的想法。正好她知道Bob有一個關(guān)于疾病的DNA模型的數(shù)據(jù)庫。如果她把自己的DNA樣品寄給Bob，那么Bob可以給出她的DNA的診斷結(jié)果。但是Alice又不想別人知道，這是她的隱私。所以，她請求Bob幫忙診斷自己DNA的方式是不可行的。因為這樣Bob就知道了她的DNA及相關(guān)私人信息。
2． 經(jīng)過一次花費昂貴的市場調(diào)查后，A公司決定擴展在某些地區(qū)的市場份額來獲取豐厚的回報。同時，A公司也注意到B公司也在擴展一些地區(qū)的市場份額。在策略上，兩個公司都不想在相同地區(qū)互相競爭，所以他們都想在不泄露市場地區(qū)位置信息的情況下知道他們的市場地區(qū)是否有重疊。(信息的泄露可能會導(dǎo)致公司很大的損失。比如另一家對手公司知道A和B公司的擴展地區(qū)，提前行動占領(lǐng)市場；又比如房地產(chǎn)公司知道A和B公司的擴展計劃，提前提高當(dāng)?shù)氐姆孔獾鹊?所以他們需要一種方法在保證私密的前提下解決這個問題。
3． 兩個金融組織計劃為了共同的利益決定互相合作一個項目。每個組織都想自己的需求獲得滿足。然而，他們的需求都是他們自己專有的數(shù)據(jù)，沒人愿意透露給其他方，甚至是“信任”的第三方。那么他們?nèi)绾卧诒Ｗo數(shù)據(jù)私密性的前提下合作項目呢？
以上三個例子的共有特點是：
<1>. 兩或更多方參與基于他們各自私密輸入的計算。
<2>. 而且他們都不想其他方知道自己的輸入信息。
問題變成了在保護輸入數(shù)據(jù)私密性的前提下如何實現(xiàn)這種計算? 我們稱之為“安全多方計算(Secure Multi-party Computation)”問題。 通常講，一個安全多方計算問題在一個分布網(wǎng)絡(luò)上計算基于任何輸入的任何概率函數(shù),每個輸入方在這個分布網(wǎng)絡(luò)上都擁有一個輸入，而這個分布網(wǎng)絡(luò)要確保輸入的獨立性，計算的正確性，而且除了各自的輸入外，不透露其他任何可用于推導(dǎo)其他輸入和輸出的信息。 當(dāng)前，解決上述問題的策略是假設(shè)有可信任的服務(wù)提供者或是假設(shè)存在可信任的第三方。但是在目前多變和充滿惡意的環(huán)境中，這是極具風(fēng)險的。因此，可以支持聯(lián)合計算并保護參與者私密的協(xié)議變的日益重要。理論上講，通用的安全多方計算問題是可解決的。但是，正如Goldreich所指出的，源于針對特殊例子的安全多方計算的通用結(jié)果的安全多方計算方案是不切實際的。 最后，我們給出安全多方計算的定義：SMC是解決一組互不信任的參與方之間保護隱私的協(xié)同計算問題，SMC要確保輸入的獨立性，計算的正確性，同時不泄露各輸入值給參與計算的其他成員。
姚氏百萬富翁問題
姚氏百萬富翁問題是由華裔計算機科學(xué)家、圖靈獎獲得者姚啟智教授首先提出的。該問題表述為：兩個百萬富翁Alice和Bob想知道他們兩個誰更富有，但他們都不想讓對方知道自己財富的任何信息。該問題有一些實際應(yīng)用：假設(shè)Alice希望向Bob購買一些商品，但她愿意支付的最高金額為x元；Bob希望的最低賣出價為y元。Alice和Bob都非常希望知道x與y哪個大。如果x>y，他們都可以開始討價還價；如果z<y，他們就不用浪費口舌。但他們都不想告訴對方自己的出價，以免自己在討價還價中處于不利地位。
1982年，姚啟智教授在提出百萬富翁問題后就給出了該問題的一種解決方案。該方案用于對兩個數(shù)進行比較，以確定哪一個較大。Alice知道一個整數(shù)i；Bob知道一個整數(shù)j, Alice與B0b希望知道究竟i>=j還是j>i，但都不想讓對方知道自己的數(shù)。為簡單起見，假設(shè)j與i的范圍為[1，100】。Bob有一個公開密鑰Eb和私有密鑰Db。
百萬富翁問題協(xié)議一
(1)Alice選擇一個大隨機數(shù)x，并用Bob的公開密鑰加密c=Eb(x)；
(2)Alice計算c—i，并將結(jié)果發(fā)送給Bob：
(3)Bob計算下面的100個數(shù)：Yu=Db(c-i+w), u=1，2，．．．，100 其中Db是Bob的私有解密密鑰。B0b選擇一個大素數(shù)p(p應(yīng)該比x稍小一點，Bob不知道x，但Alice能容易地告訴他x的大小)，然后計算下面的100個數(shù)：Zu=(Yu mod p), u=1，2，．．．，100。然后驗證對所有的u≠v, |Zu-Zv|>=2，并對所有的u驗證：0<Zu<p—1。如果不成立，Bob就選擇另一個素數(shù)并重復(fù)驗證；
(4)Bob將以下數(shù)列發(fā)送給Alice：Z1，Z2，．．．，Zj，Zj+1+1．．．，Z100+1，p；
(5)Alice驗證這個數(shù)列的第i個數(shù)是否與x模p同余。如果同余，她得出的結(jié)論是i<=j;如果不同余，她得出的結(jié)論是i>j;
(6)Alice把這個結(jié)論告訴Bob。
