模型和Shamir祕密共享機制

模型

安全多方計算的安全顯然是在有攻擊者狀況下的安全。在不一樣情形下，實現安全的難度也不一樣。最極端的例子是一個安全多方計算協議的全部參與者都是惡意參與者，那麼這個協議的安全性就很難保證了。要實現安全，首先應該針對不一樣的狀況創建不一樣的模型，然後針對這些模型進行研究。算法

首先假設有攻擊者（Adversary），攻擊者能夠經過各類手段收買或者控制（Corrupt）部分參與者，而參與者一旦被收買或者控制，該參與者的全部通訊歷史信息和本地信息都會被攻擊者掌握。攻擊者能夠實際理解成黑客，他經過黑客手段入侵到了參與者的計算機中，取得了參與者計算機的控制權，所以能夠掌握全部該參與者掌握的信息。攻擊者也能夠理解成競爭公司的人，經過金錢來賄賂參與者，以此取得信息。安全

那麼顯然，攻擊者可以最大收買的參與者人數，很大程度上影響了協議是否安全。（t，n）門限攻擊者結構是指參與者總數是n，攻擊者最多可以收買t個參與者。對於攻擊者結構，常常會說是圖片的攻擊者結構指攻擊者收買的參與者集合中的人數小於參與者總人數的 1/2，即𝑡 < 1/2；圖片的攻擊者結構指攻擊者收買的參與者集合中的人數小於參與者總人數的𝑡 < 1/3。函數

攻擊者模型分爲半誠實攻擊者模型和惡意攻擊者模型。在半誠實攻擊者模型下，被攻擊者收買的參與者遵照協議，不會在協議執行中途退出，也會誠實地發送本身的計算結果，不會篡改協議計算結果。可是被收買的參與者的全部信息，包括歷史通信信息、計算結果等都會被攻擊者得知。在惡意攻擊者模型下，被攻擊者收買的參與者不會再誠實地遵照協議，可能會篡改協議計算結果，其發送給其餘參與者的信息有多是虛假和僞造的。spa

攻擊者的能力還能夠根據其計算能力進行劃分，在計算意義下安全的模型中，攻擊者的計算能力是機率多項式時間的，意味着攻擊者沒法解決常見的困難問題，即便計算出來，所花費的時間也已經超過了信息的有效期，得到的信息已是過期的信息。另外一種模型爲信息論意義下安全的模型，在這種模型下，攻擊者的計算能力是無限的。設計

門限機制和Shamir祕密共享

設 t 和 n 爲兩個正整數，且 t≤n。n個須要共享祕密的參與者集合爲𝑃 = {𝑃1,… ,𝑃𝑛 }，一個(t,n)門限祕密共享體制是指：假設𝑃1,… ,𝑃𝑛要共享同一個祕密s， 將s稱爲主祕密，有一個祕密管理中心𝑃0來負責對s進行管理和分配。祕密管理中心𝑃0掌握有祕密分配算法和祕密重構算法，這兩個算法均知足重構要求和安全性要求。圖片

祕密管理中心𝑃0首先經過將主祕密s輸入祕密分配算法，生成n個值，分別爲𝑠1,… ,𝑠𝑛，稱𝑠1,… ,𝑠𝑛爲子祕密。而後祕密管理中心𝑃0分別將祕密分配算法產生的子祕密𝑠1,… ,𝑠𝑛經過𝑃0與𝑃𝑖之間的安全通訊信道祕密地傳送給參與者𝑃𝑖，參與者𝑃𝑖不得向任何人泄露本身所收到的子祕密𝑠𝑖。it

門限值t指的是任意大於或等於t個參與者𝑃𝑖，將各自掌握的子祕密𝑠𝑖進行共享，任意的一個參與者𝑃𝑖在得到其他𝑡−1個參與者所掌握的子祕密後，均可獨立地經過祕密重構算法恢復出主祕密s。而即便有任意的𝑛−𝑡個參與者丟失了各自所掌握的子祕密，剩下的 t 個參與者依舊能夠經過將各自掌握的子祕密與其餘參與者共享，再使用祕密重構算法來重構出主祕密s。安全性要求是指任意攻擊者經過收買等手段獲取了少於 t個的子祕密，或者任意少於 t 個參與者串通都沒法恢復出主祕密 s，也沒法獲得主祕密 s 的信息。io

Shamir於1979年，基於多項式插值算法設計了Shamir(t,n)門限祕密共享體制，它的祕密分配算法以下：class

首先假設𝔽𝑞爲q元有限域，q是素數且𝑞>𝑛。圖片是參與者集合，P共享主祕密𝑠,𝑠∈𝔽𝑞，祕密管理中心𝑃0按以下所述的步驟對主祕密𝑠進行分配，爲了可讀性起見，如下公式均略去了模q操做：重構

參與者𝑃0祕密的在有限域𝔽𝑞中隨機選取𝑡−1個元素，記爲圖片，並取以𝑥爲變元的多項式𝑓(𝑥)

對於1≤𝑖≤ 𝑛，𝑃0祕密計算𝑦𝑖=𝑓(𝑖)

對於1≤𝑖≤𝑛，𝑃0經過安全信道祕密地將(𝑖, 𝑦𝑖)分配給𝑃𝑖

Shamir(t,n)門限共享體制的祕密重構可使用通俗的解方程法，即t個方程能夠肯定t個未知數，而這t個未知數即爲包括主祕密𝑠在內的多項式𝑓(𝑥)的各項係數。如參與者𝑃1,… ,𝑃𝑡掌握了子祕密𝑓(1),…,𝑓(𝑡)，解方程：

便可求解出係數。
另外一種方式是使用多項式插值法進行重構主祕密。假設這 t 個子祕鑰分別爲(𝑥𝑖 ,𝑦𝑖) ，其中𝑦𝑖=𝑓(𝑥𝑖)，𝑖=1,…, 𝑡且𝑖 ≠ 𝑗 時 𝑥𝑖 ≠ 𝑥𝑗。參與者𝑃1,… ,𝑃𝑡共同計算

顯然，ℎ(𝑥)是一個𝑡−1次的多項式，且由於𝑖≠𝑗時𝑥𝑖≠𝑥𝑗，每一個加式的分母均不爲零，所以對於𝑖=1,…,𝑡，𝑦𝑖=ℎ(𝑥𝑖)=𝑓(𝑥𝑖) 。又根據多項式的性質，若是存在兩個最高次均爲𝑡−1次的多項式，這兩個多項式在𝑡個互不相同的點所取的值均相同，那麼這兩個多項式相同。即ℎ(𝑥)=𝑓(𝑥)，進而參與者𝑃𝑖計算ℎ(0)=𝑓(0)=𝑠，便可恢復主祕密𝑠。

對於有限域𝔽𝑞上n-1次的多項式，設爲𝑓(𝑥)，存在有限域𝔽𝑞上的n個元，記爲𝜆1,…,𝜆𝑛，使得：

稱(𝜆1,…,𝜆𝑛)爲重組向量(recombinationn vector)，由於證實過程較爲繁瑣，所以具體證實過程寫在最後。

對於矩陣M：
設祕密分配多項式爲𝑓(𝑥)，參與者𝑃𝑖掌握的子祕密爲𝑓(𝑖)，由於存在重組向量(𝜆1,…,𝜆𝑛)，所以有：

若要計算重組向量，可經過計算矩陣𝑀的逆矩陣圖片來計算重組向量(𝜆1,…,𝜆𝑛)：

在得到重組向量後，可構建基於Shamir門限體制的安全多方計算協議。首先假設𝑃={𝑃1,…,𝑃𝑛 }是參與者集合，𝑃𝑖掌握輸入𝑥𝑖(1≤𝑖≤𝑛)，須要共同計算的函數爲𝑓(𝑥1,…, 𝑥𝑛)。在有限域𝔽𝑞上的𝑆ℎ𝑎𝑚𝑖𝑟(𝑡+1,𝑛)門限體制主要流程爲：

輸入階段，每一個參與者𝑃𝑖將本身的輸入𝑥𝑖，利用𝑆ℎ𝑎𝑚𝑖𝑟(𝑡+1, 𝑛)門限祕密共享體制，祕密選取最高 t 次的隨機多項式𝑓𝑖(𝑥)，知足𝑓𝑖(0)=𝑥𝑖 。而後𝑃𝑖將𝑓𝑖(𝑗)發送給參與者𝑃𝑗。

計算階段，假設輸入的𝑎和𝑏已經經過至多 t 次的隨機多項式𝑓𝑎(𝑥)和𝑓𝑏(𝑥)經過Shamir門限體制共享給了各個參與者，其中是隨機的多項式係數。參與者𝑃𝑖掌握輸入𝑎的子祕密𝑎𝑖和輸入𝑏的子祕密𝑏𝑖。至多t次的緣由是多項式的係數是隨機產生的，所以t次的係數也有多是0。

多方計算𝑎+𝑏：每一個參與者𝑃𝑖獨立計算𝑐𝑖 =𝑎𝑖+𝑏𝑖, 1≤𝑖 ≤𝑛 。𝑐1,…, 𝑐𝑛 即爲𝑎+𝑏經過隨機多項式共享後的結果，經過多項式插值法或者解方程便可恢復祕密s。子祕密能夠直接相加，是由於對於𝑐𝑖=𝑎𝑖+𝑏𝑖=𝑓𝑎(𝑖)+𝑓𝑏(𝑖)= (𝑚𝑡+𝑛𝑡)圖片+⋯+ (𝑚1+𝑛1 )𝑖+𝑎+𝑏，多項式的次數並無發生變化，新的多項式𝑓𝑎(𝑥)+𝑓𝑏(𝑥)的最高次數依舊爲 t，t+1 個參與者共享他們所掌握的𝑐𝑖，便可根據t+1個方程解t+1個未知數，解出𝑎+𝑏。或者也可直接使用拉格朗日插值法求解出𝑎+𝑏。

𝑎𝑏：首先每一個參與者計算
接着每一個𝑃𝑖 獨自選取次數爲t次的隨機𝑛多項式ℎ
。向各個參與者分配𝑑𝑖，且全部參與者分配結束後，𝑃𝑖掌握了信息同時𝜆1,…,𝜆𝑛是公開的重組向量，即(𝜆1,…,𝜆𝑛)知足，所以𝑃𝑖可計算
，再利用多項式插值法，便可得到𝑎𝑏。

對於重組向量存在性的證實過程爲：設，則，且可被表示爲：

考慮一個n階矩陣

因爲矩陣𝑀是滿秩矩陣，所以存在𝜆1,…,𝜆𝑛∈𝔽𝑞，使得

所以有：