涂 航

（海軍參謀部，北京 100841）

0 引言

隨著云計算技術的飛速發(fā)展，越來越多的用戶將個人數據上傳至云服務器中交由云服務商管理，云服務商也將很多傳統(tǒng)上本地化的服務提供給用戶。智能信息化為當今社會提供便捷的環(huán)境的同時，如用戶隱私泄露、網絡攻擊等安全問題卻與日俱增。用戶在很多云計算使用環(huán)境中并不希望其他用戶和云服務商獲得自己的個人信息，這正是安全多方計算（Secure Multi-party Computing，SMC）能解決的問題。

安全多方計算最早是由文獻[1]通過百萬富翁問題提出的，該研究描述的是兩個參與者在不泄露自身信息的條件下進行比較，而在后續(xù)的研究中，參與者拓寬為多個。因此，安全多方計算就可以定義為，多個參與者在各自輸入獨立的情況下，共同進行一種運算。文獻[2]將特定運算提高為任意代數運算，并給出協(xié)議的完整流程。文獻[3]在對前人研究進行概括的基礎上形式化地定義了安全多方計算的安全模型。文獻[4]提出了參與者也有可能是攻擊者的概念，將參與者根據行為定義為誠實參與者、半誠實參與者和惡意參與者。文獻[5]在文獻[4]提出的參與者類型上，論述了即使參與者有惡意的行為，依然可以通過完善的設計保護系統(tǒng)和其他參與者。

經過學界專家學者們多年的研究，安全多方計算已經有了長足的發(fā)展。目前，由于全同態(tài)加密算法可以解決云計算、大數據環(huán)境下的用戶數據隱私保護問題，因此將全同態(tài)加密（Fully Homomorphic Encryption，FHE）算法與安全多方計算結合是一個新的研究熱點。第一次真正意義上實現全同態(tài)加密算法的研究是Gentry 于2009 年發(fā)表的博士論文[6]，該論文提出了基于ideal latte的全同態(tài)加密算法。文獻[7]利用門限加密與全同態(tài)加密相結合的構想，實現了文獻[1]提出的兩方比較問題的同態(tài)思路，并且將計算復雜度降低至O(m)（m為信息長度）。文獻[8]基于格上容錯學習（Learning With Error，LWE）的困難性假設，利用同態(tài)加密的思想，不直接比較輸入是否相同，而是比較對輸入的密文是否有映射關系來判斷安全兩方協(xié)議的正確性。

針對云計算的發(fā)展速度和安全多方計算實際部署問題，又有許多專家學者將服務器作為第三方來進行安全多方計算[9-12]。文獻[9]充分利用云計算的特點，構造出一種在服務器上利用求參與者之間輸入的最大近似公因子求解問題來進行判斷安全多方計算的正確性。雖然該方案降低了參與者的計算需要；但是求解最大近似公因子本身需要的計算開銷很大，如果參與者數量很多的情況下，就要求服務器擁有很大的計算能力。文獻[10]利用多編碼技術和部分同態(tài)加密部署在云服務上達到安全多方計算的目的，但是該方案不能抵抗合謀攻擊，且計算開銷較大。文獻[11]將全同態(tài)加密算法轉化為多比特并行加密，構造出困難性基于LWE的多比特全同態(tài)加密安全多方計算方案。文獻[12]在文獻[11]的基礎上設計了一個困難性基于Ferr-LWE 和Someare-errorless-LWE的三輪協(xié)議的多方計算協(xié)議，該協(xié)議較好地控制了密文的膨脹，且其計算復雜度和密文膨脹率的控制是目前較好的。

充分考慮到實用性和安全性，本文首先決定采用整數上的全同態(tài)加密算法來構造一個由服務器作為第三方的安全多方計算協(xié)議。該協(xié)議需要參與者使用全同態(tài)加密算法預處理輸入信息，服務器作為第三方只能對參與者的密文進行處理，保證了所有參與者的隱私不被泄露。

1 算法概述

1.1 相關定義

本文的符號及其代表的含義如表1 所示。

表1 符號對應表

有如下兩個定義：

（1）Bχ-有界分布

有Bχ∈Z+，并有{χn}n∈N滿足：

式中：{χn}n∈N是基于整數集的分布序列；negl(n)是一個可忽略函數。則稱Bχ是有界的。

根據Bχ有界分布的定理，可以有推論：設Bχ有界分布中有服從的ei(i∈[N])的獨立隨機變量，其變化出的同樣服從Bχ有界分布。

（2）稀疏子集求和問題

一個整數集合Z={x1,x2,…,xn}中的子集S={1,2,…,n}，找到一個S中的元素si(1 ≤i≤n)，使得i∈∑si·xi=0 是計算困難的。

1.2 全同態(tài)加密算法

全同態(tài)加密算法一般是由密鑰生成算法、同態(tài)加密算法、同態(tài)解密算法和同態(tài)計算算法組成，分別記為：KeyGen、Homo.Enc、Homo.Dec、Evaluate。

（1）密鑰生成算法（KeyGen）：隨機選擇一個參數，輸出公私鑰對(pk,sk)。

（2）同態(tài)加密算法（Homo.Enc）：對于全同態(tài)加密算法輸入的明文m利用pk加密變成密文c的過程。

（3）同態(tài)解密算法（Homo.Dec）：對于Homo.Enc中產生的c利用sk還原回m的過程。

（4）同態(tài)計算算法（Evaluate）：對于多個密文c1,c2,…,cn，利用公鑰pk執(zhí)行一個任意的代數運算f的過程。

1.3 基于整數全同態(tài)加密算法

基于整數的全同態(tài)加密算法一般的安全性是基于近似最大公因子問題，本文采用的參數選擇與文獻[13]相同，同時給出整數上的全同態(tài)加密算法。一個全同態(tài)加密算法包含密鑰生成算法、加密算法、解密算法和同態(tài)計算算法。

（1）密鑰生成算法（KeyGen）：在密鑰生成中心產生一個長度為η的素數集pi,j(1 ≤i,j≤μ)，μ為選定的參數用于確定明文空間。選擇參數α定義為素數集中兩個元素的乘積，隨機選取一個元素β←Z∩[0,2γ/α]，并令β<2λ2，同時有γ=α·β。利用Bχ有界分布確定一個整數集合X，其界限為β，其中的元素為xi。再隨機選取一個δ比特的奇正整數y，即。令公鑰pk=〈x1,x2,…,xβ〉，私鑰sk=y。

（2）同態(tài)加密算法（Homo.Enc）：首先以輸入的明文為0 得到的密文組成集合C? {1 ,2,…,β}；其次取r∈(-2β,2β)∩Z，計算c←m+2r+，S為1.1 小節(jié)中定義的稀疏子集求和中的子集S。

（3）同態(tài)解密算法（Homo.Dec）：計 算m←(cmodp)mod 2。

（4）同態(tài)計算算法（Evaluate）：通過公式計算Evaluate(pk,C,c1,…,ct)，其中t為電路C的輸入。

1.4 安全多方計算模型

一個安全多方計算的模型為有n個參與者P={P1,P2,…,Pn}，參與者共同使用f(·)對輸入xi(i=1,2,…,n)進行計算，得到一個計算結果y，并且參與者對于其他參與者的輸入并不知情，如圖1所示。

圖1 安全多方計算模型

一般在模型中執(zhí)行協(xié)議的操作步驟，并且不去獲取其他參與者輸入信息的參與者被稱為誠實參與者。然而，在實際的應用場景中并不是所有的參與者都是“安分守己”的，有一些參與者雖然會執(zhí)行協(xié)議的步驟，但是同時也會通過各種方法刺探其他參與者的輸入信息，將這種參與者稱為半誠實參與者。還存在一種參與者，他們不僅不會正常執(zhí)行協(xié)議的步驟，而且還可能向協(xié)議無關者泄露協(xié)議執(zhí)行中獲得的信息，甚至破壞協(xié)議的運行，將這種參與者稱為惡意參與者。模型中的攻擊者用A來表示，攻擊者一般是一個或多個參與者，故有A?2p。雖然半誠實的參與者不會主動對協(xié)議發(fā)起攻擊，但是也存在著半誠實的參與者被收買等情況，所以在很多研究中除了將惡意參與者看作是攻擊者，也將半誠實參與者看為攻擊者。

2 基于整數全同態(tài)加密技術的安全多方計算協(xié)議

研究安全多方計算協(xié)議，需要考慮到實際網絡類型、信道模式以及敵手攻擊等問題。為了便于討論，本文中約定網絡類型為同步網絡，即參與者之間不存在異步時鐘，且信道模式為可信的安全信道，敵手為半誠實的參與者，同時有一個服務器充當第三方作為計算中心。本文設計的協(xié)議模型架構如圖2 所示。

圖2 基于整數全同態(tài)加密技術的安全多方計算協(xié)議

設基于整數全同態(tài)加密技術的安全多方計算協(xié)議中有n個參與者P={P1,P2,…,Pn}，分別持有各自的輸入xi(i=1,2,…,n)，經過服務器計算后再得到處理后的信息(y′1,y′2,…,y′n)。由于全同態(tài)加密的性質，可以將(y′1,y′2,…,y′n)還原為安全多方計算的結果y。具體流程如圖3 所示。

圖3 基于同態(tài)加密的多方安全計算流程

具體的流程為分為4 步，如下文所述。

（1）初始化流程：參與方P1,P2,…,Pn使用密鑰生成算法KeyGen(·)計算公私鑰對(pk,sk)(i=1,2,…,n)。

（2）加密處理流程：參與方P1,P2,…,Pn分別將各自的輸入xi(i=1,2,…,n)使用全同態(tài)加密算法Homo.Enc進行加密，得到各自的密文ci→Homo.Enc(xi)，并將其發(fā)送給服務器。

（3）安全多方計算流程：服務器接收到各個參與者發(fā)送到的密文ci后，使用安全多方計算協(xié)議進行處理，得到y(tǒng)→f(c1,c2,…,ci)。

（4）同態(tài)計算流程：服務器在對安全多方計算流程中計算的結果進行同態(tài)計算得到Eval(y′)→(y′1,y′2,…,y′n)，并將結果返還給各個參與者。

經過上述4 個步驟，參與者將各自輸入的密文上傳至服務器進行安全多方計算處理，從服務器得到返回的計算結果。整個過程中服務器并不知道參與者的原始輸入，只能對參與者上傳的密文進行處理。這樣能保證其他參與者和服務器并不知道其原始輸入信息，從而保護了各個參與者的隱私。

3 結語

本文基于整數上的全同態(tài)加密算法構造了一個安全多方計算協(xié)議，該協(xié)議約定網絡類型為同步網絡，信道模式為可信的安全信道，敵手為半誠實的參與者。該協(xié)議分為4 個步驟，充分利用了全同態(tài)加密的性質，所有的參與者所得到的只有經過服務器處理后的對應輸入的信息，同時該協(xié)議構造簡潔，只需要兩輪通信。

本文提出協(xié)議仍有需要改進的地方。由于全同態(tài)加密需要較大的計算能力，因此協(xié)議是將這部分交由參與者處理，這時如果有惡意的參與者混入其中，則最后可能無法還原回安全多方計算過程得到的結果。后續(xù)研究工作中將針對這一問題進一步完善該協(xié)議。