基于全同態加密的安全多方計算協議
摘 要：針對云計算環境下數據的隱私保護問題，在研究全同態加密技術的基礎上設計了一個安全多方計算協議。該協議約定網絡類型為同步網絡，信道模式為可信的安全信道，敵手為半誠實的參與者，同時有一個服務器作為計算中心。參與者通過全同態加密算法預先對輸入進行加密并將明文發送給服務器進行安全多方計算，服務器和其他參與者全程得不到該參與者的輸入信息，保證了所有參與者的隱私。
內容目錄：
1 算法概述
1.1 相關定義
1.2 全同態加密算法
1.3 基于整數全同態加密算法
1.4 安全多方計算模型
2 基于整數全同態加密技術的安全多方計算協議
3 結 語
隨著云計算技術的飛速發展，越來越多的用戶將個人數據上傳至云服務器中交由云服務商管理，云服務商也將很多傳統上本地化的服務提供給用戶。智能信息化為當今社會提供便捷的環境的同時，如用戶隱私泄露、網絡攻擊等安全問題卻與日俱增。用戶在很多云計算使用環境中并不希望其他用戶和云服務商獲得自己的個人信息，這正是安全多方計算（Secure Multi-party Computing，SMC）能解決的問題。
安全多方計算最早是由文獻 [1] 通過百萬富翁 問題提出的，該研究描述的是兩個參與者在不泄露 自身信息的條件下進行比較，而在后續的研究中，參與者拓寬為多個。因此，安全多方計算就可以定義為，多個參與者在各自輸入獨立的情況下，共同進行一種運算。文獻 [2] 將特定運算提高為任意代 數運算，并給出協議的完整流程。文獻 [3] 在對前人研究進行概括的基礎上形式化地定義了安全多方 計算的安全模型。文獻 [4] 提出了參與者也有可能是攻擊者的概念，將參與者根據行為定義為誠實參與者、半誠實參與者和惡意參與者。文獻 [5] 在文 獻 [4] 提出的參與者類型上，論述了即使參與者有惡意的行為，依然可以通過完善的設計保護系統和 其他參與者。
經過學界專家學者們多年的研究，安全多方計 算已經有了長足的發展。目前，由于全同態加密算法可以解決云計算、大數據環境下的用戶數據隱私保護問題，因此將全同態加密（Fully Homomorphic Encryption，FHE ）算法與安全多方計算結合是一個新的研究熱點。第一次真正意義上實現全同態加密 算法的研究是 Gentry 于 2009 年發表的博士論文 [6]， 該論文提出了基于 ideal latte 的全同態加密算法。 文獻[7]利用門限加密與全同態加密相結合的構想， 實現了文獻 [1] 提出的兩方比較問題的同態思路，并且將計算復雜度降低至 O(m)（m 為信息長度）。文獻 [8] 基于格上容錯學習（Learning With Error， LWE ）的困難性假設，利用同態加密的思想，不直接比較輸入是否相同，而是比較對輸入的密文是否 有映射關系來判斷安全兩方協議的正確性。
針對云計算的發展速度和安全多方計算實際部 署問題，又有許多專家學者將服務器作為第三方來進行安全多方計算 。文獻 [9] 充分利用云計算的 特點，構造出一種在服務器上利用求參與者之間輸 入的最大近似公因子求解問題來進行判斷安全多方 計算的正確性。雖然該方案降低了參與者的計算需 要；但是求解最大近似公因子本身需要的計算開銷 很大，如果參與者數量很多的情況下，就要求服務 器擁有很大的計算能力。文獻 [10] 利用多編碼技術 和部分同態加密部署在云服務上達到安全多方計算的目的，但是該方案不能抵抗合謀攻擊，且計算開 銷較大。文獻 [11] 將全同態加密算法轉化為多比特 并行加密，構造出困難性基于 LWE 的多比特全同 態加密安全多方計算方案。文獻 [12] 在文獻 [11] 的基礎上設計了一個困難性基于 Ferr-LWE 和 Some- are-errorless-LWE 的三輪協議的多方計算協議，該協議較好地控制了密文的膨脹，且其計算復雜度 密文膨脹率的控制是目前較好的。
充分考慮到實用性和安全性，本文首先決定采 用整數上的全同態加密算法來構造一個由服務器作 為第三方的安全多方計算協議。該協議需要參與者使用全同態加密算法預處理輸入信息，服務器作為第三方只能對參與者的密文進行處理，保證了所有參與者的隱私不被泄露。
01算法概述
1.1 相關定義
本文的符號及其代表的含義如表 1 所示。
表 1 符號對應表
有如下兩個定義：
（ 1）
有界分布
有
，并有 
滿足：
式中： 是基于整數集的分布序列；
是一個可忽略函數。則稱
是有界的。
根據 有界分布的定理，可以有推論：設 有界分布中有服從的
的獨立隨機變量，其變化出的
同樣服從
有界分布。
（2 ）稀疏子集求和問題
一個整數集合
中的子集
， 找 到 一 個 S 中 的 元 素
， 使 得
是計算困難的。
1.2 全同態加密算法
全同態加密算法一般是由密鑰生成算法、同態加密算法、同態解密算法和同態計算算法組 成，分別記為：KeyGen、Homo.Enc、Homo.Dec、 Evaluate。
（ 1 ）密鑰生成算法（KeyGen）：隨機選擇一 個參數，輸出公私鑰對 (pk,sk)。（2 ）同態加密算法（ Homo.Enc ）：對于全同 態加密算法輸入的明文 m 利用pk加密變成密文 c 的過程。3）同態解密算法（Homo.Dec）：對于Homo.Enc 中產生的 c 利用sk還原回 m 的過程。（4 ）同態計算算法（Evaluate）：對于多個密文
，利用公鑰 pk 執行一個任意的代數運算f 的過程。
1.3 基于整數全同態加密算法
基于整數的全同態加密算法一般的安全性是基 于近似最大公因子問題，本文采用的參數選擇與文 獻 [13] 相同，同時給出整數上的全同態加密算法。一個全同態加密算法包含密鑰生成算法、加密算法、解密算法和同態計算算法。
（ 1 ）密鑰生成算法（KeyGen）：在密鑰生成 中心產生一個長度為 η 的素數集
， μ 為選定的參數用于確定明文空間。選擇參數 α 定 義為素數集中兩個元素的乘積，隨機選取一個元素 
，并令
，同時有 γ=α·β。利用
有界分布確定一個整數集合X，其界限為 β，其中的元素為
。再隨機選取一個δ 比特的奇正整數y，即
。令公鑰
， 私鑰 sk=y。（2） 同態加密算法（Homo.Enc ）：首先以輸 入的明文為 0 得到的密文組成集合
；其次取 
，計算
，S 為 1.1 小節中定義的稀疏子集求和中的子集 S。（ 3 ） 同 態 解 密 算 法（ Homo.Dec ）： 計 算
。（4 ）同態計算算法（Evaluate）：通過公式計 算
，其中 t 為電路 C 的輸入。
1.4 安全多方計算模型
一個安全多方計算的模型為有 n 個參與 者
，參與者共同使用 f(·) 對輸入
進行計算，得到一個計算結果y，并且參與者對于其他參與者的輸入并不知情，如圖 1 所示。
圖 1 安全多方計算模型
一般在模型中執行協議的操作步驟，并且不去 獲取其他參與者輸入信息的參與者被稱為誠實參與者。然而，在實際的應用場景中并不是所有的參與 者都是“安分守己”的，有一些參與者雖然會執行 協議的步驟，但是同時也會通過各種方法刺探其他參與者的輸入信息，將這種參與者稱為半誠實參與 者。還存在一種參與者，他們不僅不會正常執行協議的步驟，而且還可能向協議無關者泄露協議執行中獲得的信息，甚至破壞協議的運行，將這種參與者稱為惡意參與者。模型中的攻擊者用
來表示，攻擊者一般是一個或多個參與者，故有
。雖然半誠實的參與者不會主動對協議發起攻擊，但是也存在著半誠實的參與者被收買等情況，所以在 很多研究中除了將惡意參與者看作是攻擊者，也將半誠實參與者看為攻擊者。
02 基于整數全同態加密技術的安全多方計算協議
研究安全多方計算協議，需要考慮到實際網絡 類型、信道模式以及敵手攻擊等問題。為了便于討 論，本文中約定網絡類型為同步網絡，即參與者之 間不存在異步時鐘，且信道模式為可信的安全信道， 敵手為半誠實的參與者，同時有一個服務器充當第 三方作為計算中心。本文設計的協議模型架構如圖 2 所示。設基于整數全同態加密技術的安全多方計算協議中有 n 個參與者
，分別持有各自的輸入
，經過服務器計算后再得到處理后的信息
。由于全同態加密的性質，可以將
還原為安全多方計算的結果y。具體流程如圖 3 所示。
2 基于整數全同態加密技術的安全多方計算協議
圖 3 基于同態加密的多方安全計算流程
具體的流程為分為 4 步，如下文所述。
（ 1 ） 初 始 化 流 程： 參 與 方
使 用密鑰生成算法 KeyGen(·) 計算公私鑰對 (pk,sk) 
。（2）加密處理流程：參與方
分別將各 自的輸入
使用全同態加密算法Homo.Enc 進行加密，得到各自的密文
， 并將其發送給服務器。（ 3 ）安全多方計算流程：服務器接收到各個 參與者發送到的密文 ci 后，使用安全多方計算協議 進行處理，得到
。（4 ）同態計算流 程：服務器在對安全多方計算流程中計算的結果進行同態計算得到
，并將結果返還給各個參與者。
經過上述 4個步驟，參與者將各自輸入的密文 上傳至服務器進行安全多方計算處理，從服務器得 到返回的計算結果。整個過程中服務器并不知道參 與者的原始輸入，只能對參與者上傳的密文進行處 理。這樣能保證其他參與者和服務器并不知道其原 始輸入信息，從而保護了各個參與者的隱私。
03 結 語
本文基于整數上的全同態加密算法構造了一個安全多方計算協議，該協議約定網絡類型為同步網絡，信道模式為可信的安全信道，敵手為半誠實的參與者。該協議分為 4 個步驟，充分利用了全同態加密的性質，所有的參與者所得到的只有經過服務器處理后的對應輸入的信息，同時該協議構造簡潔，只需要兩輪通信。
本文提出協議仍有需要改進的地方。由于全同態加密需要較大的計算能力，因此協議是將這部分交由參與者處理，這時如果有惡意的參與者混入其中，則最后可能無法還原回安全多方計算過程得到 的結果。后續研究工作中將針對這一問題進一步完善該協議。
