? ? ? ?摘??要：針對(duì)云計(jì)算環(huán)境下數(shù)據(jù)的隱私保護(hù)問(wèn)題，在研究全同態(tài)加密技術(shù)的基礎(chǔ)上設(shè)計(jì)了一個(gè)安全多方計(jì)算協(xié)議。該協(xié)議約定網(wǎng)絡(luò)類型為同步網(wǎng)絡(luò)，信道模式為可信的安全信道，敵手為半誠(chéng)實(shí)的參與者，同時(shí)有一個(gè)服務(wù)器作為計(jì)算中心。參與者通過(guò)全同態(tài)加密算法預(yù)先對(duì)輸入進(jìn)行加密并將明文發(fā)送給服務(wù)器進(jìn)行安全多方計(jì)算，服務(wù)器和其他參與者全程得不到該參與者的輸入信息，保證了所有參與者的隱私。

? ? ? ? 內(nèi)容目錄：

1　算法概述

1.1???相關(guān)定義

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

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

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

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

3　結(jié)　語(yǔ)

? ? ? ? 隨著云計(jì)算技術(shù)的飛速發(fā)展，越來(lái)越多的用戶將個(gè)人數(shù)據(jù)上傳至云服務(wù)器中交由云服務(wù)商管理，云服務(wù)商也將很多傳統(tǒng)上本地化的服務(wù)提供給用戶。智能信息化為當(dāng)今社會(huì)提供便捷的環(huán)境的同時(shí)，如用戶隱私泄露、網(wǎng)絡(luò)攻擊等安全問(wèn)題卻與日俱增。用戶在很多云計(jì)算使用環(huán)境中并不希望其他用戶和云服務(wù)商獲得自己的個(gè)人信息，這正是安全多方計(jì)算（Secure Multi-party Computing，SMC）能解決的問(wèn)題。安全多方計(jì)算最早是由文獻(xiàn)?[1]?通過(guò)百萬(wàn)富翁?問(wèn)題提出的，該研究描述的是兩個(gè)參與者在不泄露?自身信息的條件下進(jìn)行比較，而在后續(xù)的研究中，參與者拓寬為多個(gè)。因此，安全多方計(jì)算就可以定義為，多個(gè)參與者在各自輸入獨(dú)立的情況下，共同進(jìn)行一種運(yùn)算。文獻(xiàn)?[2]?將特定運(yùn)算提高為任意代?數(shù)運(yùn)算，并給出協(xié)議的完整流程。文獻(xiàn)?[3]?在對(duì)前人研究進(jìn)行概括的基礎(chǔ)上形式化地定義了安全多方?計(jì)算的安全模型。文獻(xiàn)?[4]?提出了參與者也有可能是攻擊者的概念，將參與者根據(jù)行為定義為誠(chéng)實(shí)參與者、半誠(chéng)實(shí)參與者和惡意參與者。文獻(xiàn)?[5]?在文 獻(xiàn)?[4]?提出的參與者類型上，論述了即使參與者有惡意的行為，依然可以通過(guò)完善的設(shè)計(jì)保護(hù)系統(tǒng)和?其他參與者。經(jīng)過(guò)學(xué)界專家學(xué)者們多年的研究，安全多方計(jì)?算已經(jīng)有了長(zhǎng)足的發(fā)展。目前，由于全同態(tài)加密算法可以解決云計(jì)算、大數(shù)據(jù)環(huán)境下的用戶數(shù)據(jù)隱私保護(hù)問(wèn)題，因此將全同態(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]?提出的兩方比較問(wèn)題的同態(tài)思路，并且將計(jì)算復(fù)雜度降低至 O(m)（m 為信息長(zhǎng)度）。文獻(xiàn)?[8]?基于格上容錯(cuò)學(xué)習(xí)（Learning With Error， LWE ）的困難性假設(shè)，利用同態(tài)加密的思想，不直接比較輸入是否相同，而是比較對(duì)輸入的密文是否?有映射關(guān)系來(lái)判斷安全兩方協(xié)議的正確性。針對(duì)云計(jì)算的發(fā)展速度和安全多方計(jì)算實(shí)際部 署問(wèn)題，又有許多專家學(xué)者將服務(wù)器作為第三方來(lái)進(jìn)行安全多方計(jì)算 。文獻(xiàn)?[9]?充分利用云計(jì)算的?特點(diǎn)，構(gòu)造出一種在服務(wù)器上利用求參與者之間輸?入的最大近似公因子求解問(wèn)題來(lái)進(jìn)行判斷安全多方?計(jì)算的正確性。雖然該方案降低了參與者的計(jì)算需?要；但是求解最大近似公因子本身需要的計(jì)算開(kāi)銷?很大，如果參與者數(shù)量很多的情況下，就要求服務(wù)?器擁有很大的計(jì)算能力。文獻(xiàn)?[10]?利用多編碼技術(shù)?和部分同態(tài)加密部署在云服務(wù)上達(dá)到安全多方計(jì)算的目的，但是該方案不能抵抗合謀攻擊，且計(jì)算開(kāi)?銷較大。文獻(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 和 Some- are-errorless-LWE 的三輪協(xié)議的多方計(jì)算協(xié)議，該協(xié)議較好地控制了密文的膨脹，且其計(jì)算復(fù)雜度?密文膨脹率的控制是目前較好的。充分考慮到實(shí)用性和安全性，本文首先決定采?用整數(shù)上的全同態(tài)加密算法來(lái)構(gòu)造一個(gè)由服務(wù)器作?為第三方的安全多方計(jì)算協(xié)議。該協(xié)議需要參與者使用全同態(tài)加密算法預(yù)處理輸入信息，服務(wù)器作為第三方只能對(duì)參與者的密文進(jìn)行處理，保證了所有參與者的隱私不被泄露。

? ? ? ??01?算法概述

? ? ? ??1.1???相關(guān)定義

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

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

? ? ? ??有如下兩個(gè)定義：（?1） 有界分布有，并有 滿足：式中： 是基于整數(shù)集的分布序列； 是一個(gè)可忽略函數(shù)。則稱是有界的。根據(jù) 有界分布的定理，可以有推論：設(shè) 有界分布中有服從的的獨(dú)立隨機(jī)變量，其變化出的同樣服從有界分布。（2?）稀疏子集求和問(wèn)題一個(gè)整數(shù)集合 中的子集，?找?到?一?個(gè) S 中?的?元?素，?使?得 是計(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ù)，輸出公私鑰對(duì)?(pk,sk)。（2 ）同態(tài)加密算法（ Homo.Enc ）：對(duì)于全同?態(tài)加密算法輸入的明文 m 利用pk加密變成密文 c 的過(guò)程。3）同態(tài)解密算法（Homo.Dec）：對(duì)于Homo.Enc 中產(chǎn)生的 c 利用sk還原回 m 的過(guò)程。（4 ）同態(tài)計(jì)算算法（Evaluate）：對(duì)于多個(gè)密文，利用公鑰 pk 執(zhí)行一個(gè)任意的代數(shù)運(yùn)算f 的過(guò)程。

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

? ? ? ??基于整數(shù)的全同態(tài)加密算法一般的安全性是基?于近似最大公因子問(wèn)題，本文采用的參數(shù)選擇與文 ?獻(xiàn)?[13]?相同，同時(shí)給出整數(shù)上的全同態(tài)加密算法。一個(gè)全同態(tài)加密算法包含密鑰生成算法、加密算法、解密算法和同態(tài)計(jì)算算法。（ 1 ）密鑰生成算法（KeyGen）：在密鑰生成?中心產(chǎn)生一個(gè)長(zhǎng)度為?η?的素?cái)?shù)集， μ?為選定的參數(shù)用于確定明文空間。選擇參數(shù)?α?定?義為素?cái)?shù)集中兩個(gè)元素的乘積，隨機(jī)選取一個(gè)元素 ，并令，同時(shí)有?γ=α·β。利用 有界分布確定一個(gè)整數(shù)集合X，其界限為?β，其中的元素為。再隨機(jī)選取一個(gè)δ?比特的奇正整數(shù)y，即 。令公鑰，?私鑰 sk=y。（2）?同態(tài)加密算法（Homo.Enc ）：首先以輸?入的明文為?0?得到的密文組成集合；其次取 ，計(jì)算 ，S 為 1.1 小節(jié)中定義的稀疏子集求和中的子集 S。（ 3 ）?同?態(tài)?解?密?算?法（ Homo.Dec ）：?計(jì)?算。（4 ）同態(tài)計(jì)算算法（Evaluate）：通過(guò)公式計(jì)?算，其中 t 為電路 C 的輸入。

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

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

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

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

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

? ? ? ??研究安全多方計(jì)算協(xié)議，需要考慮到實(shí)際網(wǎng)絡(luò)?類型、信道模式以及敵手攻擊等問(wèn)題。為了便于討?論，本文中約定網(wǎng)絡(luò)類型為同步網(wǎng)絡(luò)，即參與者之?間不存在異步時(shí)鐘，且信道模式為可信的安全信道，?敵手為半誠(chéng)實(shí)的參與者，同時(shí)有一個(gè)服務(wù)器充當(dāng)?shù)?三方作為計(jì)算中心。本文設(shè)計(jì)的協(xié)議模型架構(gòu)如圖 2 所示。設(shè)基于整數(shù)全同態(tài)加密技術(shù)的安全多方計(jì)算協(xié)議中有 n 個(gè)參與者，分別持有各自的輸入，經(jīng)過(guò)服務(wù)器計(jì)算后再得到處理后的信息。由于全同態(tài)加密的性質(zhì)，可以將還原為安全多方計(jì)算的結(jié)果y。具體流程如圖 3 所示。

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

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

? ? ? ??具體的流程為分為 4 步，如下文所述。（ 1 ）?初?始?化?流?程：??參?與?方 使?用密鑰生成算法 KeyGen(·)?計(jì)算公私鑰對(duì)?(pk,sk) 。（2）加密處理流程：參與方分別將各?自的輸入使用全同態(tài)加密算法Homo.Enc 進(jìn)行加密，得到各自的密文，?并將其發(fā)送給服務(wù)器。（ 3 ）安全多方計(jì)算流程：服務(wù)器接收到各個(gè)?參與者發(fā)送到的密文 ci 后，使用安全多方計(jì)算協(xié)議?進(jìn)行處理，得到。（4 ）同態(tài)計(jì)算流?程：服務(wù)器在對(duì)安全多方計(jì)算流程中計(jì)算的結(jié)果進(jìn)行同態(tài)計(jì)算得到，并將結(jié)果返還給各個(gè)參與者。經(jīng)過(guò)上述 4個(gè)步驟，參與者將各自輸入的密文?上傳至服務(wù)器進(jìn)行安全多方計(jì)算處理，從服務(wù)器得?到返回的計(jì)算結(jié)果。整個(gè)過(guò)程中服務(wù)器并不知道參?與者的原始輸入，只能對(duì)參與者上傳的密文進(jìn)行處 理。這樣能保證其他參與者和服務(wù)器并不知道其原?始輸入信息，從而保護(hù)了各個(gè)參與者的隱私。

? ? ? ??03?結(jié)　語(yǔ)

? ? ? ??本文基于整數(shù)上的全同態(tài)加密算法構(gòu)造了一個(gè)安全多方計(jì)算協(xié)議，該協(xié)議約定網(wǎng)絡(luò)類型為同步網(wǎng)絡(luò)，信道模式為可信的安全信道，敵手為半誠(chéng)實(shí)的參與者。該協(xié)議分為 4 個(gè)步驟，充分利用了全同態(tài)加密的性質(zhì)，所有的參與者所得到的只有經(jīng)過(guò)服務(wù)器處理后的對(duì)應(yīng)輸入的信息，同時(shí)該協(xié)議構(gòu)造簡(jiǎn)潔，只需要兩輪通信。本文提出協(xié)議仍有需要改進(jìn)的地方。由于全同態(tài)加密需要較大的計(jì)算能力，因此協(xié)議是將這部分交由參與者處理，這時(shí)如果有惡意的參與者混入其中，則最后可能無(wú)法還原回安全多方計(jì)算過(guò)程得到?的結(jié)果。后續(xù)研究工作中將針對(duì)這一問(wèn)題進(jìn)一步完善該協(xié)議。