本文首發公眾號VenusBlockChain，關注公眾號后可免費閱讀！VenusBlockChain致力于區塊鏈技術研究，傳播區塊鏈技術和解決方案、區塊鏈應用落地、區塊鏈行業動態等。有興趣的小伙伴們，歡迎關注。

安全多方計算（Secure Multi-party Computa-tion，sMPC）是分布式密碼學的理論基礎，也是分布式計算研究的一個基本問題，最早由姚期智于1982年通過姚氏百萬富翁問題提出。

簡單的說，安全多方計算是指一組人，比如$P_1....P_n$ ，共同安全的計算函數$f(x_1,...,x_n)=(y_1,...,y_n)$。函數的n個輸入分別由n個參與者秘密掌握，設$P_i$的秘密輸入是$x_i$ ，并且在計算結束后，$P_i$ 得到輸出$y_i$ 。這里的安全性是要求即使在某些參與者有欺騙行為的情況下保證計算結果的正確性，即計算結束后每個誠實的參與者$P_i$ 都能得到正確的輸出$y_i$，同時還要求保證每個參與者輸入的保密性，即每個參與者$P_i$ 除了$(x_i,y_i)$外，得不到任何其他信息。

安全多方計算的一般實現方法有四種：同態加密密碼體制、不經意傳輸協議、線性密鑰共享體制、混淆電路框架。
這一篇先介紹基于同態加密密碼體制的安全多方計算協議。

1 同態門限密碼體制

具有加法同態性的門限密碼體制是構造安全多方計算協議的一個基本工具。具體來說，設$（sk,pk,M,C,E,D）$是一個公鑰密碼體制，其中$sk$是私鑰，$pk$是公鑰，$M$是明文空間，$C$是密文空間，$E$和$D$分別是加密算法和解密算法。特別是明文空間$M$和密文空間$C$都是帶有某種運算的有限交換群。對任意的明文$m\in M$，加密得到密文$c=E(m)$，解密過程為$D(c)=D(E(m))=m$。

對于任意的$m_1,m_2\in M$，滿足$E(m_1)?E(m_2)=E(m_1+m_2)$，我們就稱該密碼體制具有加法同態性，其中“+”表示明文空間的運算，“$?$”表示密文空間的運算。加法同態性質說明：可以由$m_1$和$m_2$的密文直接得到$m_1+m_2$的密文。

具有加法同態性的密碼體制有很多，經常用到的是Paillier密碼體制。門限密碼體制是把解密的權力利用門限控制，比如$(t,n)$門限就是要求只有$n$個參與者中的至少$t$個人聯合才能解密得到明文，而任何少于$t$個人都無法得到明文。Desmedt和Frankel在其文獻“Threshold Cryptosystem(1990)”中指出，任何一個公鑰密碼體制理論上都可以門限化。

門限密碼體制基本的思路是公布公鑰$pk$，但是將私鑰$sk$在$n$個人中按照Shamir$(t,n)$門限體制進行共享。設$P_i$得到子密鑰$s{k}_i$，$1\le i\le n$。解密的時候，設要聯合解密密文$m\in M$，$P_i$將自己的子密鑰作用在密文上得到$m_i=D_{s{k}_i}(c)$，$1\le i\le t$。最后由$m_1,...,m_t$就可以得到明文$m$。

注意：解密的時候并不是將私鑰$sk$重構出來，否則私鑰一旦被某個參與者知道，該門限密碼體制就變得不安全了。

2 基于Paillier加法同態密碼體制的安全多方計算協議

設$P=\{P_1,...,P_n\}$是參與者集合，他們要共同計算函數$f(x_1,...,x_n)$，其中$P_i$掌握輸入$x_i$，$1\le i\le n$。討論密碼學模型下的安全多方計算，攻擊者結構是$\Theta$。設$（sk,pk,M,C,E,D）$是一個基于Paillier加法同態性的門限密碼體制，并且$P_1,...,P_n$已經掌握了相關參數（即各自的公鑰、私鑰等）。這里用到的門限密鑰共享體制滿足對于任意的$m_1,m_2\in M$，任意的被收買集合$\theta \in \Theta$都無法區分$E(m_1)$和$E(m_2)$。

下面的安全多方計算協議分為輸入階段、計算階段和輸出階段。

(1)輸入階段

每個參與者$P_i$，$1\le i\le n$，將自己的輸入$x_i$用公鑰$p{k}_i$進行加密得到密文$E(x_i)$，然后把密文$E(x_i)$公開。

(2)計算階段

假設要計算的函數$f$已經表示成某個有限域上$K$的多項式，這里取$K=Z_p$，$p$是$N$的素因子。因此，在計算階段的每一步依然是處理一個$x+y$或$xy$，其中$x,y\in K$。并采用加密體制進行隱藏，即每個參與者得到的只是輸入和輸出的密文。由于經過輸入階段，可以假設每個參與者已經得到輸入的密文$E(x)$和$E(y)$，于是計算階段的每一步就是使所有參與者最后得到$E(x+y)$或$E(xy)$，然后作為下一步計算的輸入計算。

計算$“x+y”$：由于采用的密碼體制具有加法同態性質，那么每個參與者由$E(x)$和$E(y)$，不需要交互只進行直接計算$E(x)?E(y)$就可以得到$E(x+y)$。

計算$“xy”$：每個參與者$P_i$，$1\le i\le n$，秘密選取隨機數$d_i\in M$，將用公鑰$pk$加密，公開$E(d_i)$。根據加法同態性，將所有參與者都得到$c^{\prime }=E(d_1+...+d_n+x)=E(d_1)?...?E(d_n)?E(x)$，然后聯合對$c^{\prime }$進行解密，得到$d=D(c^{\prime })=d_1+...+d_n+x$。參與者$P_1$計算$z_1=d?d_1$，$P_i$計算$a_i=?d_i$，$2\le i\le n$，顯然有$x={\sum }_{i=1}^n{a}_i$。根據加密體制的加法同態性，每個參與者$P_i$，$1\le i\le n$，計算得到$E((a_{i}y)$并將結果公開。例如，如果密文空間對應的運算時乘法，那么$E((a_{i}y)=(E((y){)}^{a_i}$。最后，所有參與者計算$E((a_{1}y)?...?E((a_{n}y)=E({\sum }_{i=1}^n{a}_{i}y)=E(xy)$。

(3)輸出階段

由于到計算階段的最后，所有參與者都已經得到最后函數值的密文$E(f(x_1,...,x_n))$，因此輸出階段就是所有參與者聯合對$E(f(x_1,...,x_n))$進行解密得到最后的函數值。

3 往期回顧

數字簽名系列

• 圖解 ECDSA 簽名與驗簽基本原理
• 圖解 BLS 簽名與驗簽基本原理
• BLS 簽名理論原理和工程實現
• 基于 RSA 的實用門限簽名算法
• 門限密鑰共享技術原理
• 隱私保護利器之環簽名實現原理
• 多重簽名 MultiSig：Schnorr 協議與 ECDSA 協議
• 一種高效的數字簽名算法ED25519
• Schnorr 協議：零知識身份證明和數字簽名

智能合約隱私計算

• 智能合約隱私計算：開篇
• 智能合約隱私計算：同態加密應用舉例
• 智能合約隱私計算：再談Paillier同態加密算法
• 智能合約隱私計算：基于FO承諾的零知識證明
• 智能合約隱私計算：基于FO承諾的零知識承諾相等性證明和平衡驗證

密碼學承諾系列

• Pedersen commitment

同態加密系列

• 智能合約隱私保護技術之同態加密
• 智能合約隱私計算之再談Paillier同態加密算法

4 參考資源

[1] 密鑰共享體制和安全多方計算[M]，劉木蘭、張志芳著。

總結

以上是生活随笔為你收集整理的基于同态加密体制的安全多方计算的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。