基于全同態(tài)加密的安全多方計(jì)算協(xié)議*

涂 航

（海軍參謀部，北京 100841）

0 引言

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

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

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

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

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

1 算法概述

1.1 相關(guān)定義

本文的符號(hào)及其代表的含義如表1 所示。

表1 符號(hào)對應(yīng)表

有如下兩個(gè)定義：

（1）Bχ-有界分布

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

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

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

（2）稀疏子集求和問題

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

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

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

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

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

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

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

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

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

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

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

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

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

1.4 安全多方計(jì)算模型

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

圖1 安全多方計(jì)算模型

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

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

研究安全多方計(jì)算協(xié)議，需要考慮到實(shí)際網(wǎng)絡(luò)類型、信道模式以及敵手攻擊等問題。為了便于討論，本文中約定網(wǎng)絡(luò)類型為同步網(wǎng)絡(luò)，即參與者之間不存在異步時(shí)鐘，且信道模式為可信的安全信道，敵手為半誠實(shí)的參與者，同時(shí)有一個(gè)服務(wù)器充當(dāng)?shù)谌阶鳛橛?jì)算中心。本文設(shè)計(jì)的協(xié)議模型架構(gòu)如圖2 所示。

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

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

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

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

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

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

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

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

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

3 結(jié)語

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

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