參考自 Ivan Damgård BRICS （Århus University） 的主題演講，Ivan Damgård是丹麥著名的密碼學家，SPDZ協議的主要開創者。
作者：六三
日期：2021年4月
摘要：本篇文章帶來的是MPC的入門級介紹。
寫在前面
我們的OpenMPC（開放隱私計算）社群已初具規模， 如有想加入我們的小夥伴， 可以私信我或OpenMPC的創始人@開放隱私計算 ，我們拉您進群。
如果心揣夢想， 想更在這個領域進一步做點事情， 那麼請聯絡我們， 我們將會熱烈歡迎您成為我們的一份子。
接著上篇文章：安全多方計算入門級介紹一 - 知乎 （zhihu。com）
二、定義MPC的安全性
方法：定義我們想要的理想版本。如果它 “相當於” 理想 說明協議是好的。
優點：從等效性來看，我們知道協議具有理想版本的所有良好屬性。
我們將為通用可組合（UC）安全性提供 Canetti 定義的變體。（變體主要區別： 明確考慮同步網路，原始UC用於非同步情況）。
2。1 敵手活動
定義前的重要說明：一般情況下，敵手可能會比腐蝕參與方和控制他們的行為更有能力。 - 大多數協議都是作為一個更大的系統的一部分來執行的，比如金鑰交換協議或電子支付方案。 - 現實生活中的敵手會攻擊整個系統，而不僅僅是協議。 - 因此，敵手可能會對誠實的參與方所提供的輸入產生一定的影響，甚至可能控制它們。 - 另外，敵手可能會得到一些關於誠實參與方從協議中獲得的結果的資訊，甚至可能是全部資訊。
在我們的定義中，敵手應該被允許為誠實參與方選擇輸入，並看到他們的結果。
問題：這是非常奇怪的，我們不是說過，敵手不應該得到誠實玩家的結果資訊嗎？
回答：我們說的是協議不應該釋出這種資訊。如果敵手從其他渠道，比如周圍的系統瞭解到一些資訊，協議也無能為力。所以我們要要求協議按照它應該的方式工作，不管敵手知道什麼，或者能透過協議外部的手段控制什麼。
2。2 定義中的概念
所有的實體（參與方、敵手、可信方）從形式上講都是互動式的、機率的圖靈機。每個實體都得到作為輸入的安全引數
，
得到輔助輸入
。
理想正規化（或可信方）
。
模擬我們希望協議實現的正規化。
不能被腐蝕
可以與所有參與方和敵手進行交流。
接收來自所有參與方的輸入，根據其程式進行計算並將結果返回給參與方。
有記憶體，可以多次呼叫，因此可以用來模擬我們能想象到的任何合理的基元。
當然，現實生活中不存在這樣的
，只是用了一個我們希望擁有的規範。定義基本上說，如果一個協議在現實生活中創造了相當於有
可用的情況，那麼這個協議就是好的（w。r。t。
）。
定義兩個過程。 - 真實過程 - 理想過程
在真實過程中，我們有敵手
和執行協議
的參與方（沒有可信方）。
在理想過程中，我們仍然有
，但
被可信方
（加上後面要解釋的模擬器
）代替。
如果
無法判斷自己是在真實過程中還是在理想過程中，我們將說
安全地實現了
。
下面圖中顯示了真實過程。
下面圖中顯示了理想過程。
為了讓
在真實中的事情和理想過程中的事情看起來是一樣的，我們引入模擬器
。
2。3 定義
我們說，如果存在一個模擬器
，使得對於所有的敵手
只在
中腐壞集合，並滿足：
則
安全地完美地實現了
。
Intuition：我們認為
的輸出 bit 是它對自己是在現實世界還是理想世界的猜測。兩個機率相等意味著它無法分辨。注意我們說的是對所有
而言，所以這裡沒有對
的計算能力進行約束。
如果以下計算成立，則說明 實現了統計上的
：
其中，
表示在
中的可忽略值（對於任意選擇
）。
Intuition on Definition
它確保現實過程繼承了理想過程的自然安全屬性，例如：
協議確保誠實的參與方計算出正確的結果：在理想過程中，透過對
的定義，總是真實的，如果協議產生不一致的結果，
可 以很容易地區分。
協議不釋放不該釋放的資訊：
能夠令人信服地模擬
攻擊協議的觀點，只根據
願意透露給腐壞參與方的內容。
問題：考慮計算
的 trivial 協議，顯示它滿足定義（假設為被動腐壞）。假設我們嘗試用同樣的 trivial 方案來計算兩個位元的AND。解釋為什麼在這種情況下證明會失敗。
Secret Sharing
Dealer 在
中持有一個秘密值
，
Dealer 在
上選擇一個階最多為
的隨機多項式
，使得
。
Dealer 私下發送
至
。
Properties：
任何最多
個參與方的子集都沒有
的資訊。
任何至少
個玩家的子集都可以很容易地計算出
，可以透過取他們所知道的 share 的線性組合來完成。
為了便於理解，我將shamir演算法貼在這裡
shamir是一種秘密共享的實現，利用了拉格朗日插值公式。詳細原理見參考文獻。下面補充一個shamir演算法的有用的性質： 加同態。 已知已有兩個用於秘密共享的多項式
以及素數
。 透過秘密共享分享的分片形式是
。 將分片中的多項式結果求和，得到
。 根據shamir演算法中的定義，
是原秘密。因此透過恢復演算法對求和後的分片進行恢復，將會得到
。這就實現了秘密求和。在雙方求和的情況下，沒有意義，但在參與者數目大於等於3時，就會有用。
拉格朗日插值：
https：//
blog。csdn。net/shenwansa
ngz/article/details/88682785
重構向量
重構向量
是這樣的：對於階數小於
的任何多項式
被動腐壞案例的協議，i。t。 情景
門限敵手，最多可腐蝕
個玩家，
。
通常協議包含以下四個階段：
電路和給定的輸入
建立代表輸入的 ”物件“，由參與方共同持有，value 不被對手獲取。
計算階段：計算新物件。
開啟輸出
建立物件(秘密分享階段)
每個
用最多
階的隨機多項式分享他的每個輸入值，將每個輸入的 share 傳送給每個計算方。
Notation：
意味著：值
已經被使用多項式
共享，結果共享
，其中玩家
持有
。
計算過程
加法門
輸入：
期望輸出：
。
每個參與方計算
。
那麼我們就有了我們想要的：
因為將兩個階數
的隨機多項式相加，會產生階數
的隨機多項式。
問題： 如何透過公共常量
安全地乘以共享值
。
有了這個加法，我們可以安全地計算任何線性函式。
乘法門
輸入：
和
。
希望的輸出：
。
每個參與方設定
。如果我們設定
，那麼
。同時
。
不幸的是，
的階數可能高達
，甚至不是一個階數最多為
的隨機多項式。怎麼辦呢？
我們有公共重構向量
可以得到
， 因為
每個參與方
建立
，所以我們有
現在使用多項式
共享，其中
。
輸出開啟階段
透過電路，我們對每個輸出值
。
如果
需要被計算方
接收，則每個
將
傳送給
。
進行重構。
Security， intuitively：
因為所有的參與方都遵守協議，所以輸出是非常正確的。
對於誠實參與方的每一個輸入、中間結果和誠實參與方的輸出，
最多看到
份。這些總是
個隨機欄位元素，所以不透露任何資訊。
