學號：19011110177
/p/68116569
/p/25770963
/p/59108808
多方安全計算 （MPC：Secure Muti-Party Computation）理論是姚期智先生為解決壹組互不信任的參與方之間在保護隱私信息以及沒有可信第三方的前提下協同計算問題而提出的理論框架。多方安全計算能夠同時確保輸入的隱私性和計算的正確性，在無可信第三方的前提下通過數學理論保證參與計算的各方成員輸入信息不暴露，且同時能夠獲得準確的運算結果。
早在1982年，姚期智先生在其發表的文章《安全計算協議》（Protocols for Secure Computation）裏提出了著名的姚氏百萬富翁問題，同時也首次引入了雙方安全計算的概念來解決問題，並對其可行性進行了驗證。兩個百萬富翁Alice和Bob在無任何可信第三方，同時不暴露自己的財產的情況下，希望得出誰更富有的結論。
我們下面來介紹姚老師的精妙解法 ---
假設富翁王有i億資產，李有j億資產。王選取壹個公鑰，使得李可以傳遞加密的信息。
首先，李選取壹個隨機的大整數x，把用王的公鑰加密，得到密文K。 李 發送k-j給王。
王收到密文c=k-j之後， 對c+1，c+2，...，c+10進行解密，得到十個數字。再選取壹個適當大小的素數p,? 把這十個數字除以p的余數記作d1，d2，...，d10。
.註意: 這十個數字看起來應該是完全隨機的，關鍵是等式dj=x mod p 成立。
最後，王對這壹串數字作如下操作：前面 i 個數不動，後面的數字每個加壹，然後發回給李。
這樣壹通復雜的操作之後，李檢查第j個數字。如果等於x mod p 的話，說明這個數字沒有被加壹，所以 i >= j. 反之，則 i < j。
這個過程的絕妙之處在於：在協議完成之後，王不知道j的具體值，而李也不知道 i 的值， 但是雙方都知道誰的財富更多，這就是多方 安全計算 。壹般來說，在甲只知道x，乙只知道y的情況下，雙方可以合作計算壹個函數 f(x,y)。協議完成時，只有函數值是公開的，而彼此都不知道對方的輸入值。
從前面的舉例發現，多方安全計算的特點：
1、兩方或者多方參與基於他們各自隱私或秘密數據輸入的計算。
2、參與壹方都不願意讓其他任何第三方知道自己的輸入信息。
在多方安全計算出現以前，解決上述問題的策略是假設有可信任的服務提供者或是假設存在可信任的第三方。但是在目前多變和充滿惡意的環境中，這是極具風險的。因此，作為能夠解決壹組互不信任的參與方之間保護隱私的協同計算問題的技術，安全多方計算變的日益重要。
目前互聯網已經完成了從IT時代向DT時代的轉變，數據已經成為DT時代企業的核心競爭力。數據作為壹種新能源，只有流動起來才能產生價值。不過，大多數企業考慮到數據安全和個人隱私等問題，對數據***享都非常謹慎。而MPC對打破數據孤島，實現數據的可控***享，具有重要的理論和現實意義。
MPC方案主要可分為基於混淆電路(Garbled Circuit，GC)和基於秘密***享兩種。
不經意傳輸(Oblivious Transfer)
首先介紹壹種基礎的安全多方計算協議：不經意傳輸(Oblivious Transfer, OT)。
來看壹個例子：假設某旅行社擁有N個景點的旅遊資料，小淘想去其中的A景點遊玩，希望向旅行社購買相關資料做好出遊功課。但是小淘非常在意自己的隱私，不希望向旅行社泄露自己的目的地是哪裏。因此雙方希望這筆交易能夠滿足以下隱私條件：
小淘不希望向旅行社泄露“我準備去A景點”這壹信息；
旅行社只希望出售小淘出錢購買的那份資料，而不泄露小淘未購買的N-1份資料；
粗看起來這種隱私條件似乎是無法滿足的：旅行社只要把景點A的資料給到小淘，就必然了解了“小淘正在關註A景點”這壹信息；除非旅行社把所有N份資料都給出，但是這又違背了旅行社的利益；
但是神奇的OT可以讓交易在這種“不可能的條件”下達成。簡而言之，在OT協議中，旅行社把他擁有的N份資料使用某種雙方協商同意的加密算法和參數進行加密，然後發送給小淘；小淘可以從密文中解密出A的資料，而無法解密出其他N-1份資料。
OT除了可以直接用於構造MPC方案之外，也是GC等許多MPC方案的基石。
混淆電路
我們知道，任意函數最後在計算機語言內部都是由加法器、乘法器、移位器、選擇器等電路表示，而這些電路最後都可以僅由AND和XOR兩種邏輯門組成。壹個門電路其實就是壹個真值表，例如AND門的真值表就是：
例如其中右下格表示兩根輸入線(wire)都取1時，輸出wire=1：即 1 AND 1 = 1。
假設我們把每個wire都使用不同的密鑰加密，把真值表變成這樣：
例如其中右下格表示如果門的輸入是b和d，那麽輸出加密的f(密鑰是b和d)。這個門從控制流的角度來看還是壹樣的，只不過輸入和輸出被加密了，且輸出必須使用對應的輸入才能解密，解密出的f又可以作為後續門的輸入。這種加密方式就稱為“混淆電路(Garbled Circuit，GC)”。
將電路中所有的門都按順序進行這樣的加密，我們就得到了壹個GC表示的函數。這個函數接收加密的輸入，輸出加密的結果。
假設有兩個參與方A和B各自提供數據a、b，希望安全的計算約定的函數F(a,b)，那麽壹種基於GC的安全兩方計算協議過程可以非正式的描述如下：
細心的同學壹定會指出：第4步中A怎麽可以接觸B的輸入b呢？這不是違背了安全多方計算的假設嗎？這裏就需要使用OT，A扮演Sender，B扮演Receiver，讓B從A處得到Encrypt( b)，卻不向A透露b的內容。如圖所示：
需要註意的是，上述流程只是最原始的GC方法的不嚴謹描述，GC後續還有Point & Permute、Free XOR、Half Gates等多種細節優化，隨著最近幾年的研究進展，GC的性能已經差不多可以實用了。以求兩個百萬維向量的漢明距離(Hamming Distance)為例（應用場景是兩份數據求相似度，卻互相不泄露數據內容），這樣的安全兩方計算已經可以在1.5秒左右完成。
安全多方計算的安全模型
半誠實行為模型與惡意行為模型
更細心的同學還會進壹步提出問題：“怎麽確保A給B的
就是壹個正確的GC呢？例如A和B商定要比a和b的大小，商定了F(a,b)=a>b?1:0，但是A可以制作壹個別的函數的GC，例如F(a,b)=b的第1個比特，這樣顯然是會侵害B的隱私的，但是由於函數是以GC形式發給B的，B是沒有辦法發現這個問題?”
這確實是壹個安全問題，事實上，GC還存在如selective failure等其他更多的安全問題。在介紹解決方案之前，我們需要先定義安全多方計算的安全模型。
安全多方計算的安全模型包含多個角度的內容，在上述上下文中，我們關註的是其中的“行為模型”，即參與方可能進行何種行為以獲取其他方的隱私。常見的行為模型包括“半誠實(Semi Honest)”和“惡意(Malicious)”兩種。前者假設所有參與方都是忠實的按照協議步驟進行執行，只是想通過協議內容推測其他方的隱私，而後者假設惡意參與方為了獲取其他方的隱私可以不遵循協議內容。
用撲克牌打個不嚴謹的比方，半誠實的牌友會試圖從自己的手牌和已經打出的牌來推測他人的手牌，但是還是遵循撲克牌規則的；而壹個惡意的牌友則換牌、偷牌等手段無所不用。
可見，本節開始提出的問題屬於惡意行為的範疇，而原始的GC只能說在半誠實行為模型下是安全的，無法抵禦惡意行為攻擊。有許多對GC方案的改進方案可以達到惡意行為模型下的安全性，但是它們都需要付出很大的性能代價：仍然以求兩個百萬維向量的漢明距離為例，其中最快的方法也需要10秒+，比同等的半誠實方案慢7倍以上。事實上，經過我們的調研，若想真正的實現支持大規模數據的MPC產品，基本上只能考慮半誠實方案。這嚴重影響了安全多方計算的實用性。
多方安全計算的壹些應用
在電子選舉、電子投票、電子拍賣、秘密***享、門限簽名等場景中有著重要的作用。
結束語
百萬富翁問題的提出和解答形象地說明了多方安全計算面臨的挑戰和解決問題的思路，引發了學術界極大的關註。時隔4年，姚期智先生再次取得重大突破，於1986年提出了基於混淆電路的通用解決方案，進壹步驗證了多方安全計算的通用可行性，同時也奠定了現代計算機密碼學的理論基礎。此後，經Oded Goldreich、Shafi Goldwasser等學者進壹步的研究和創新，多方安全計算逐漸發展成為現代密碼學的壹個重要分支。