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

王會(huì)勇 馮勇 趙嶺忠 唐士杰

(1．中國(guó)科學(xué)院大學(xué) 成都計(jì)算機(jī)應(yīng)用研究所， 四川 成都 610041； 2．桂林電子科技大學(xué) 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院， 廣西 桂林 541004；3．中國(guó)科學(xué)院重慶綠色智能技術(shù)研究院 自動(dòng)推理與認(rèn)知重慶市重點(diǎn)實(shí)驗(yàn)室, 重慶 400714；4．桂林電子科技大學(xué) 廣西可信軟件重點(diǎn)實(shí)驗(yàn)室， 廣西 桂林 541004)

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

王會(huì)勇1,2馮勇3趙嶺忠4唐士杰4

(1．中國(guó)科學(xué)院大學(xué) 成都計(jì)算機(jī)應(yīng)用研究所， 四川 成都 610041；
2．桂林電子科技大學(xué) 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院， 廣西 桂林 541004；
3．中國(guó)科學(xué)院重慶綠色智能技術(shù)研究院 自動(dòng)推理與認(rèn)知重慶市重點(diǎn)實(shí)驗(yàn)室, 重慶 400714；
4．桂林電子科技大學(xué) 廣西可信軟件重點(diǎn)實(shí)驗(yàn)室， 廣西 桂林 541004)

為構(gòu)造具有良好性能的多密鑰安全多方計(jì)算(SMC)協(xié)議，對(duì)Gentry-Sahai-Waters(GSW13)全同態(tài)加密(FHE)方案的密鑰同態(tài)性質(zhì)進(jìn)行了研究. 在此基礎(chǔ)上提出了一個(gè)基于GSW13方案的層次型多密鑰SMC協(xié)議，該協(xié)議構(gòu)造方式簡(jiǎn)單，只需要3輪通信，且在半誠(chéng)實(shí)與半惡意環(huán)境和公共隨機(jī)串模型下，其安全性可以歸結(jié)到容錯(cuò)學(xué)習(xí)問(wèn)題(LWE)和它的一個(gè)變種問(wèn)題；分析了該變種問(wèn)題的困難性，并給出了半惡意模型下該協(xié)議的形式化安全證明. 該協(xié)議自然構(gòu)成一個(gè)相同環(huán)境下的層次型多密鑰全同態(tài)加密方案. 對(duì)比分析表明，文中協(xié)議在整體性能上優(yōu)于已有方案.

安全多方計(jì)算；多密鑰全同態(tài)加密；密鑰同態(tài)；門(mén)限解密；GSW13

安全多方計(jì)算(SMC)概念來(lái)源于Yao[1]提出的安全兩方數(shù)據(jù)比較問(wèn)題(百萬(wàn)富翁問(wèn)題)，旨在解決多個(gè)參與者聯(lián)合保密計(jì)算某個(gè)函數(shù)的問(wèn)題.

1987年，Goldreich等[2]提出了可計(jì)算任意函數(shù)的基于密碼學(xué)安全模型的安全多方計(jì)算協(xié)議，并于1988年提出了SMC的安全性定義.目前，對(duì)SMC的研究主要集中在一般方案與特殊方案兩個(gè)方向[3]，研究?jī)?nèi)容主要包括不同環(huán)境(半誠(chéng)信、半惡意及惡意環(huán)境)和不同信道(同步或異步信道)下的方案，研究工具主要有可驗(yàn)證秘密共享(VSS)[4- 6]、不經(jīng)意傳輸(OT)[7- 8]、同態(tài)加密(HE)[9- 11]和混合匹配[12]等.其中，同態(tài)加密技術(shù)在SMC設(shè)計(jì)中顯示了良好的潛力，受到越來(lái)越多關(guān)注.

全同態(tài)加密(FHE)思想是由Rivest等[13]在1978年提出的.2009年，Gentry[14]構(gòu)造出第一個(gè)FHE方案.其后出現(xiàn)了多種方案，如DGHV10方案[15]、BV11方案[16]、BGV12方案[17]、GSW13方案[18]、NK15方案[19]等.目前，學(xué)界針對(duì)基于FHE技術(shù)的SMC方案開(kāi)展了大量的研究.

Lóopez-Alt等[9]提出了多密鑰全同態(tài)加密(MFHE)概念，同時(shí)給出了一個(gè)“洋蔥式”的MFHE構(gòu)造思路，并利用該思路和改進(jìn)的NTRU加密方案[20]構(gòu)造了一個(gè)可以“離線”運(yùn)行(On-the-fly)的MFHE協(xié)議.該方案的主要優(yōu)點(diǎn)是構(gòu)造過(guò)程不依賴于具體的FHE方案，缺點(diǎn)是加解密復(fù)雜度太高，且方案復(fù)雜度隨用戶數(shù)量呈指數(shù)增長(zhǎng).

文獻(xiàn)[10,21]給出了構(gòu)造MFHE方案和SMC協(xié)議的另一種方式.其基本思路是將GSW13方案的密文矩陣通過(guò)級(jí)聯(lián)方式組成聯(lián)合密文矩陣，同時(shí)將相應(yīng)密鑰組合成聯(lián)合密鑰進(jìn)行加密與解密.其主要缺點(diǎn)是通過(guò)級(jí)聯(lián)方式構(gòu)造出的密文矩陣體積很大，且構(gòu)造過(guò)程需要計(jì)算額外的掩蓋信息.

Asharov等[11]提出了門(mén)限FHE的概念，并構(gòu)造了一種只需兩輪交互的MFHE方案和對(duì)應(yīng)的SMC協(xié)議.與以前方案相比，其優(yōu)點(diǎn)是加解密運(yùn)算復(fù)雜度低.主要缺點(diǎn)是構(gòu)造過(guò)程依賴于Bv11[16]與BGV12[17]方案，而這兩個(gè)方案在進(jìn)行同態(tài)乘法時(shí)的密文膨脹率很高且需要運(yùn)行密鑰.

為充分利用GSW13方案的優(yōu)點(diǎn)，文中研究了其密鑰同態(tài)性質(zhì)，在此基礎(chǔ)上構(gòu)造了一個(gè)層次型多密鑰SMC協(xié)議.該協(xié)議使用門(mén)限式解密，在半誠(chéng)信、半惡意環(huán)境和公共隨機(jī)串(CRS)模型下的安全性可以歸結(jié)到容錯(cuò)學(xué)習(xí)問(wèn)題(LWE)及該問(wèn)題的一個(gè)變種問(wèn)題(Some-are-errorless LWE)上.研究了該問(wèn)題的困難性，并給出了半惡意環(huán)境下的形式化安全性證明.由該協(xié)議的構(gòu)造過(guò)程可以自然抽象出一個(gè)多密鑰FHE方案.

1 預(yù)備知識(shí)

1.1 符號(hào)與基礎(chǔ)概念

1.1.1 符號(hào)

(1)

故知結(jié)論成立.

1.2 安全多方計(jì)算

1.2.1 一般定義

1.2.2 計(jì)算模型

SMC的計(jì)算模型分為半誠(chéng)實(shí)、半惡意和惡意3種情況.在半誠(chéng)實(shí)模型下，參與計(jì)算者會(huì)嚴(yán)格按照協(xié)議操作，不會(huì)主動(dòng)更改協(xié)議或數(shù)據(jù).但可能保留中間計(jì)算結(jié)果，用于推算其他用戶的私有數(shù)據(jù).

半惡意模型可以被看成一個(gè)交互式圖靈機(jī)(ITM)，除擁有標(biāo)準(zhǔn)磁帶外，還擁有一個(gè)證據(jù)磁帶.在協(xié)議的任何時(shí)刻，半惡意敵手必須將它代表某個(gè)用戶發(fā)出的任何信息記錄到證據(jù)磁帶上.該敵手根據(jù)輸入和一定隨機(jī)性來(lái)決定是否忠實(shí)履行原協(xié)議.

惡意模型是指模型中的參與方可以任意篡改、泄露協(xié)議和數(shù)據(jù)，甚至可以阻止協(xié)議的正常執(zhí)行.

任意半惡意模型下的SMC協(xié)議都可以借助于非交換的零知識(shí)證明(NIZKs)等工具轉(zhuǎn)化為惡意模型下的協(xié)議[11].因此，文中只在半誠(chéng)實(shí)和半惡意模型下考慮所設(shè)計(jì)SMC協(xié)議的安全性.

2 Some-are-errorless LWE問(wèn)題

LWE問(wèn)題已經(jīng)成為多個(gè)密碼學(xué)源語(yǔ)的困難性基礎(chǔ).Regev[22]首先給出了該問(wèn)題的一個(gè)量子規(guī)約.Brakerski等[23]首次給出了該問(wèn)題的一個(gè)多項(xiàng)式規(guī)約，并討論了帶有一個(gè)等式約束的LWE問(wèn)題(被稱為First-is-errorless LWE)的困難性.將該概念進(jìn)行擴(kuò)展，考慮有多個(gè)等式約束的LWE問(wèn)題的困難性.這是構(gòu)建多密鑰SMC協(xié)議的一個(gè)安全性基礎(chǔ).

定義1 Some-are-errorless LWE

(1)利用擴(kuò)展歐幾里得算法構(gòu)造一個(gè)幺模矩陣R，滿足Ra′=(r,0,0,…,0)T.

(2)記U=R-1·diag(r,1,…,1).

由R為幺模矩陣且Ra′=(r,0,0,…,0)T，知R可逆且有：R-1Ra′=a′=R-1(r,0,0,…,0)T，即a′為矩陣R-1的最左一列乘r.

而U=R-1·diag(r,1,…,1)即為將R-1的最左一列乘r，其他元素不變.故U為滿足條件的矩陣.

均勻選取l個(gè)元素s0,s1,…,sl-1∈Zq，然后按照如下步驟構(gòu)建規(guī)約過(guò)程，其中i=0,1,2,…,l-1.

若q為素?cái)?shù)，該規(guī)約最多將成功優(yōu)勢(shì)降低q-n.若q不是素?cái)?shù)，則成功優(yōu)勢(shì)的損失最大為

(3)

這表明只要n足夠大，該規(guī)約的成功優(yōu)勢(shì)損失是可忽略的，即LWEn,l,q,χ問(wèn)題的困難性可以與LWEn-l,q,χ問(wèn)題相同.

3 GSW13方案的密鑰同態(tài)性質(zhì)

Boneh等[24]對(duì)具有密鑰同態(tài)性質(zhì)的偽隨機(jī)函數(shù)進(jìn)行了研究，其基本定義如下.

3.1 密鑰同態(tài)

定義2 (密鑰同態(tài)偽隨機(jī)函數(shù)[24]).設(shè)F:K×X→Y是一個(gè)偽隨機(jī)函數(shù)(PRF)，其密鑰空間K具有群結(jié)構(gòu)并具有某種群運(yùn)算⊕；X和Y分別是明文和密文空間.稱F是密鑰同態(tài)的，若對(duì)任意k1,k2∈K，由F(k1,x)和F(k2,x)能找到某有效算法計(jì)算F(k1⊕k2,x).

現(xiàn)對(duì)該定義進(jìn)行擴(kuò)展，并將密鑰數(shù)量擴(kuò)展到N.

定義3 對(duì)某公鑰加密方案E，設(shè)(pki,ski)為有效的公鑰/私鑰對(duì).若對(duì)pk=f(pk1,pk2,…,pkN)，能找到sk=g(sk1,sk2,…,skN)，使(pk,sk)也是E的有效密鑰對(duì)，則稱E具有密鑰同態(tài)性質(zhì)，其中f和g為可有效計(jì)算的函數(shù).特別地，若f和g都是求和(乘積)函數(shù)，稱E具有密鑰加(乘)同態(tài)性質(zhì)；若f和g都是線性函數(shù)，則稱E具有密鑰線性同態(tài)性質(zhì).

3.2 GSW13方案的密鑰同態(tài)性質(zhì)

3.2.1 GSW13方案

GSW13方案是基于容錯(cuò)學(xué)習(xí)(LWE)問(wèn)題的FHE方案.文中將利用該方案作為構(gòu)造多密鑰SMC協(xié)議的基礎(chǔ).為了敘述的簡(jiǎn)潔性，文中使用文獻(xiàn)[25]的方式來(lái)描述該方案.

GSW.Encrypt：對(duì)明文μ，構(gòu)造均勻隨機(jī)矩陣R∈{0,1}m×m，計(jì)算C=AR+μG.

GSW.Evaluation：對(duì)兩個(gè)輸入密文C1和C2，其同態(tài)加法、乘法和與非門(mén)(NAND)運(yùn)算可以定義為：

NAND(C1,C2): OutputG-C1G-1(C2).

正確性：由公鑰的構(gòu)造方式可知有tA=e≈0成立.故tC=tAR+μtG≈μtG.故有：

3.2.2 密鑰同態(tài)性質(zhì)

證明：可知有

成立.故仍有tC=tAR+μtG≈μtG.因此按原方案解密可得到明文μ.故在B不變的情況下，該方案是密鑰線性同態(tài)的.

4 基于GSW13的SMC方案

4.1 基于層次型GSW13方案的SMC協(xié)議

GSW13方案的基礎(chǔ)方案是層次型的，即只能做有限次同態(tài)運(yùn)算.要去除此限制，目前只能借助于自舉技術(shù)，但自舉技術(shù)會(huì)破壞GSW13方案的大部分優(yōu)勢(shì).因此文中將構(gòu)造基于層次型GSW13方案的SMC協(xié)議.以下敘述中，i∈[N].

協(xié)議πf：分布式半誠(chéng)實(shí)及半惡意環(huán)境和CRS模式下，安全計(jì)算單值函數(shù)f的協(xié)議.

輸入：用戶數(shù)量N(其中第i個(gè)用戶的標(biāo)識(shí)為Pi)；用戶Pi擁有隱私數(shù)據(jù)μi∈{0,1}.一個(gè)確定性PPT可計(jì)算函數(shù)f:{0,1}N→{0,1}，被表示為一個(gè)僅包含與非門(mén)(NAND)的布爾電路Cir，其與非門(mén)電路最大深度為d.

輸出：μ=f(μ1,μ2,…,μN(yùn)).

步驟1 參數(shù)設(shè)置Setup(1λ,1d)，包含兩個(gè)操作.

步驟2 密鑰生成：用戶Pi執(zhí)行如下算法.

步驟3 聯(lián)合公鑰生成及加密：每個(gè)用戶公開(kāi)自己的公鑰pki并接收他人公鑰，執(zhí)行如下操作：

(1)生成聯(lián)合公鑰.所有用戶計(jì)算：

步驟4 同態(tài)運(yùn)算：所有用戶在得到其他用戶的密文矩陣Ci后，執(zhí)行同態(tài)計(jì)算：

其同態(tài)加法、乘法和與非門(mén)(NAND)運(yùn)算定義與GSW13方案相同.

步驟5 門(mén)限式(Threshold)解密：所有用戶執(zhí)行如下操作.

(2)得到所有ωi之后，計(jì)算：

其中t為隱含的公用私鑰，不顯式出現(xiàn).

上述過(guò)程同時(shí)給出了一個(gè)MFHE方案.

4.2 正確性

該協(xié)議的正確性主要依賴于兩個(gè)方面.

首先，GSW13方案的正確性已經(jīng)得到證明，故只需考察所用參數(shù)是否正確.其次，由原方案知，按上述參數(shù)設(shè)置，該方案在進(jìn)行d層與非門(mén)同態(tài)運(yùn)算之后的噪音不超過(guò)((n+1)·l+1)dBχ.因此，只要q/Bχ>8((n+1)·l+1)d，就能保證進(jìn)行d層與非門(mén)同態(tài)運(yùn)算后的誤差(由v=ωG-1(wT)得到的v與μ的距離)不超過(guò)q/8，從而可以通過(guò)模q得到正確結(jié)果.

其次，協(xié)議的加解密正確性主要涉及3個(gè)問(wèn)題.

(1)公用密鑰對(duì)的正確性.協(xié)議πf所用密鑰對(duì)的有效性已經(jīng)由定理1.1得到證明.

(3)聯(lián)合解密的正確性.首先，聯(lián)合密鑰對(duì)的合法性已經(jīng)得到證明，即若有C=Enc(pk,μ)，則必有μ=Dec(sk,C).其次，由步驟5知：

由此可得：

ωG-1(wT)=(tC+σ)G-1(wT)=

tCG-1(wT)+σG-1(wT)=

4.3 安全性

4.3.1 半誠(chéng)實(shí)模型下的安全性

在半誠(chéng)實(shí)模型和公共隨機(jī)串(CRS)模式下，文中協(xié)議的安全性基于以下幾個(gè)問(wèn)題.

(1)在上述設(shè)置下，GSW13基本方案的安全性可以歸結(jié)為容錯(cuò)學(xué)習(xí)問(wèn)題LWEn,q,χ.

(2)部分解密結(jié)果的安全性.由步驟5可知，在等式ωi=ti·C+σi與ω=tC+σ中，ti和t為私鑰，ti·C和t·C運(yùn)算等價(jià)于向量?jī)?nèi)積運(yùn)算，且σi和σ的前l(fā)個(gè)分量是服從Bχ-有界分布的，因此這兩個(gè)等式構(gòu)成了Some-are-errorless LWE問(wèn)題，從而公布部分解密結(jié)果不會(huì)泄露用戶隱私數(shù)據(jù)及私鑰ti和隱含密鑰t.

4.3.2 半惡意模型下的安全性

半惡意模型下的安全威脅主要來(lái)自于合謀(串謀)攻擊，即多個(gè)用戶合作利用其私有數(shù)據(jù)和公有數(shù)據(jù)，試圖獲得其他用戶的私有數(shù)據(jù).以下將考慮極端情況，即所有N個(gè)用戶中只有一個(gè)誠(chéng)實(shí)用戶Ph，其他N-1個(gè)半惡意用戶合作攻擊Ph.

定理5 設(shè)f為一個(gè)具有N個(gè)輸入和1個(gè)輸出的多項(xiàng)式時(shí)間(PPT)可計(jì)算的確定性函數(shù).則上述協(xié)議πf能夠在存在一個(gè)俘獲了N-1個(gè)用戶的靜態(tài)半惡意敵手A的情況下實(shí)現(xiàn)f.

證明：首先設(shè)計(jì)一個(gè)針對(duì)上述半惡意敵手A的PPT模擬器S.設(shè)唯一的誠(chéng)實(shí)用戶為Ph,該模擬器代表Ph執(zhí)行如下操作.

最后，模擬器S將上述模擬部分解密結(jié)果公布.

游戲REALπ,A,Z：該游戲即在具有一個(gè)半惡意敵手A的真實(shí)環(huán)境Z中對(duì)協(xié)議πf的忠實(shí)執(zhí)行過(guò)程.

游戲IDEALF,S,Z：在該游戲中，用戶Ph將對(duì)0加密得到的密文代替其私有數(shù)據(jù)的密文進(jìn)行公布，其它操作與HYBπ,A,Z一樣.

證明：模擬器S利用除Ph的真實(shí)部分解密結(jié)果之外的信息(包括最終計(jì)算結(jié)果μ)來(lái)模擬計(jì)算Ph的部分解密結(jié)果，因此若設(shè)v=μ「q/2?+e′，則其模擬算法應(yīng)該為

(4)

ρh=ωhG-1(wT)+δh=vh+δh

ρh=vh+δh=

(5)

證明：這兩個(gè)游戲的唯一區(qū)別在于Ph公布的密文Ch是對(duì)其真實(shí)私有數(shù)據(jù)的加密還是對(duì)0的加密.但其加密方式的語(yǔ)義安全性已經(jīng)被證明[18]，故在這兩種情況下的加密結(jié)果是計(jì)算上不可區(qū)分的，從而可以推斷這兩個(gè)游戲也是計(jì)算上不可區(qū)分的.

4.4 協(xié)議性能分析及對(duì)比

文中協(xié)議只需要3輪交互操作:第一輪是個(gè)人密鑰對(duì)的生成、發(fā)布與接收； 第二輪是公用密鑰對(duì)的生成、密文的發(fā)布與接收；第三輪是聯(lián)合解密.

在空間效率上，由于GSW13方案的密文是矩陣，故在同態(tài)乘法中的密文膨脹率較小.而文獻(xiàn)[11]方案的密文是向量，同態(tài)乘法會(huì)造成密文維數(shù)膨脹，對(duì)其空間效率造成極大影響.文獻(xiàn)[10, 21]雖然也采用了GSW13方案作為基礎(chǔ)，但其聯(lián)合密文是用密文級(jí)聯(lián)的方式構(gòu)造的，因此需占用很大空間.

表1為幾個(gè)基于FHE的SMC方案的性能對(duì)比.可以看出，文中方案在時(shí)間、空間效率等主要性能上優(yōu)于已有方案.表中ε∈(0,1)，n為所用格的維數(shù)，q∈Z為模，Bχ∈Z為誤差分布邊界，N為參與計(jì)算的用戶數(shù)，l=?logq」+1，U=(n+1)·l+1.

表1 幾個(gè)基于全同態(tài)加密技術(shù)的安全多方計(jì)算方案主要性能對(duì)比

5 結(jié)語(yǔ)

基于GSW13全同態(tài)加密方案構(gòu)造了一個(gè)層次型多密鑰安全多方計(jì)算協(xié)議.該協(xié)議構(gòu)造簡(jiǎn)單，只需要3輪通訊，且在半誠(chéng)實(shí)與半惡意環(huán)境和公共隨機(jī)串(CRS)模型下，其安全性可以歸結(jié)到容錯(cuò)學(xué)習(xí)問(wèn)題和它的一個(gè)變種問(wèn)題(記為Some-are-errorless LWE)；將該協(xié)議與已有協(xié)議進(jìn)行了對(duì)比，結(jié)果表明：該協(xié)議具有加解密復(fù)雜度低、密文膨脹率小、且不需要運(yùn)行密鑰等優(yōu)點(diǎn)，整體性能優(yōu)于現(xiàn)有基于FHE技術(shù)的SMC方案.

但該方案仍存在以下不足，值得深入研究.首先，GSW13方案的效率仍未達(dá)到實(shí)用要求，故可對(duì)其進(jìn)行并行化處理[26]，以提高整體效率；其次，在網(wǎng)絡(luò)協(xié)議的執(zhí)行過(guò)程中，應(yīng)采用合適的方式[27]保證數(shù)據(jù)的安全傳輸和會(huì)話的協(xié)同性要求.

[1] YAO A.Protocols for secure computations [C]∥Proceedings of the 23rd Annual Symposium on Foundations of Computer Science.New York:IEEE Computer Society,1982:160- 164.

[2] GOLDREICH O,MICALI S,WIGDERSON A.How to play any mental game [C]∥Proceedings of the 19th Annual ACM Symposium on Theory of Computing.New York:ACM,1987:218- 229.

[3] 范紅,馮登國(guó).安全協(xié)議理論與方法 [M].北京:科學(xué)出版社,2003.

[4] CRAMER R,DAMGARDI,MAURER U.General secure multi-party computation from any linear secret-sharing scheme [C]∥Proceedings of the 19th International Conference on Theory and Application of Cryptographic Techniques.Bengaluru:Springer-Verlag,2000:316- 334.

[5] 唐韶華,馬衛(wèi)華.一種安全的分布式用戶認(rèn)證方案 [J].華南理工大學(xué)學(xué)報(bào)(自然科學(xué)版),1999,27(6):1- 5.

TANG Shao-hua,MA Wei-hua.A Distributed user authhentication schemes for security [J].Journal of South China University of Technology(Natural Science Edition),1999,27(6):1- 5.

[6] CHEN H,CRAMER R.Algebraic geometric secret sharing schemes and secure multi-party computations over small fields[C]∥Advances in Cryptology-CRYPTO 2006.California:Springer,2006:521- 536.

[7] CREPEAU C,vAN DE Graaf,TAPP A.Committed oblivious transfer and private multi-party computation [C]∥Advances in Cryptology-CRYPT0’ 95.California:Sprin-ger,1995:110- 123.

[8] DU W,ZHAN Z.A practical approach to solve Secure Multi-party Computation problems [C]∥Proceedings of the 2002 Workshop on New Security Paradigms.Virginia:ACM,2002:127- 135.

[10] CLEAR M,MCGOLDRICK C.Multi-identity and Multi-key leveled FHE from learning with errors [C]∥Advances in CRYPTO 2015.Berlin:Springer,2015:630- 656.

[11] ASHAROV G,JAIN A,LOPEZ-Alt A, et al Multiparty computation with low communication,computation and interaction via threshold FHE [C]∥Advances in Cryptology-EUROCRYPT 2012.Berlin:Springer,2012:483- 501.

[12] PANG L,SUN J F,LUO S S,et al.A research of the privacy preserving architecture of electronic auction [J].Journal of Convergence Information Technology,2012,7(1):172- 179.

[13] RIVEST R L,ADIEMAN L,DERTOUZOS M L.On data banks and privacy homomorphisms [J].Foundations of Secure Computation,1978,4(11):169- 180.

[14] GENTRY C.Fully homomorphic encryption using ideal lattices [C]∥The 41st ACM Symposium on Theory of Computing.Washington:ACM,2009:169- 178.

[15] VAN DIJK M,GENTRY C,HALEVI S,et al.Fully homomorphic encryption over the integers [C]∥Advances in Cryptology-EUROCRYPT 2010.Riviera:Springer,2010:24- 43.

[16] BRAKERSKI Z,VAIKUNTANATHAN V.Efficient fully homomorphic encryption from(standard) LWE [J].SIAM Journal on Computing,2014,43(2):831- 871.

[17] BRAKERSKI Z,GENTRY C,VAIKUNTANATHEAN V.(Leveled) Fully homomorphic encryption without bootstrapping [C]∥Proceedings of the 3rd Innovations in Theoretical Computer Science Conference.Massachusetts:ACM,2012:309- 325.

[18] GENTRY C,SAHAI A,WATERS B.Homomorphic encryption from learning with errors:conceptually-simpler,asymptotically-faster,attribute-based [C]∥Advances in CRYPTO 2013.California:Springer,2013:75- 92.

[19] NUIDA K,KUROSAWA K.(Batch) Fully homomorphic encryption over Integers for non-binary message spaces [C]∥Advances in Cryptology-EUROCRYPT 2015.Berlin:Springer,2015:537- 555.

[20] STEHLE D,STEINFELD R.Making NTRU as secure as worst-case problems over ideal lattices [C]∥Advances in Cryptology-EUROCRYPT 2011.Tallinn:Springer,2011:27- 47.

[21] MUKHERJEE P,WICHS D.Two round multiparty computation via multi-key FHE [C]∥Annual International Conference on the Theory and Applications of Cryptographic Techniques.Berlin:Springer,2016:735- 763.

[22] REGEV O.On lattices,learning with errors,random linear codes,and cryptography [J].Journal of the ACM,2009,56(6):1- 40.

[23] BRAKERSKI Z,LANGLOIS A,PEIKERT C.Classical hardness of learning with errors [C]∥ACM Symposium on Theory of Computing.New York:ACM,2013:575- 584.

[24] BONEH D,LEWI K,MONTGOMERY H,et al.Key homomorphic PRFs and their applications [C]∥Advances in Cryptology-CRYPTO 2013.California:Springer,2013:410- 428.

[25] ALPERIN-SHERIFF J,PEIKERT C.Faster bootstrapping with polynomial error [C]∥Advances in Cryptology-CRYPTO 2014.California:Springer,2014:297- 314.

[26] HIROMASA R,ABE M,OKAMOTO T.Packing messages and optimizing bootstrapping in GSW-FHE [C]∥Public-Key Cryptography-PKC 2015.Gaithersburg:Springer,2015:699- 715.

[27] 劉巍巍,周來(lái)水,莊海軍,等.一種基于Internet的同步協(xié)同CAD/CAM系統(tǒng)的安全機(jī)制 [J].華南理工大學(xué)學(xué)報(bào)(自然科學(xué)版),2005,33(9):20- 24.

LIU Wei-wei,ZHOU Lai-shui,ZHUANG Hai-jun,et al.A security mechanism for internet-based synchronous collaborative CAD/CAM system [J].Journal of South China University of Technology(Natural Science Edition),2005,33(9):20- 24.

ASecureMulti-PartyComputationProtocolontheBasisofMulti-KeyHomomorphism

WANGHui-yong1,2FENGYong3ZHAOLing-zhong4TANGShi-jie4

(1. Chengdu Institute of Computer Applications, University of Chinese Academy of Sciences, Chengdu 610041, Sichuan, China; 2. School of Mathematics and Computing Science, Guilin University of Electronic Technology, Guilin 541004, Guangxi, China; 3. Chongqing Key Laboratory of Automatic reasoning and Cognition, Chongqing Institute of Green Intelligent Technology, Chinese Academy of Sciences, Chongqing 400714, China; 4. Guangxi Key Laboratory of Trusted Software, Guilin University of Electronic Technology, Guilin 541004, Guangxi, China)

In order to build a multi-key secure multi-party computation (SMC) protocol with high performance, the key homomorphic properties of Gentry-Sahai-Waters (GSW13) fully-homomorphic encryption (FHE) scheme is investigated. Afterwards, a general multi-key SMC protocol with simple structure, which needs only 3 rounds of interactions, is proposed on the basis of leveled GSW13. In the semi-honesty and semi-malicious setting as well as in the common random string model, the security of the protocol relies on the learning with errors (LWE) problem and a variant of LWE. Then, the difficulty in solving the variant is analyzed, and a formalized security proof in semi-malicious setting is given. The proposed SMC protocol naturally constitutes a leveled multi-key FHE scheme in the same setting. Comparative analysis results show that the proposed protocol is superior to the existing schemes in terms of overall performance.

secure multi-party computation; multi-key fully-homomorphic encryption; key homomorphism; threshold decryption; GSW13

2016- 06- 05

國(guó)家自然科學(xué)基金資助項(xiàng)目(61262008,61462017)；廣西密碼學(xué)與信息安全重點(diǎn)實(shí)驗(yàn)室開(kāi)放課題(GCIS201622)

*Foundationitems: Supported by the National Natural Science Foundation of China (61262008，61462017)

王會(huì)勇(1977-),男,博士,講師，主要從事網(wǎng)絡(luò)信息安全研究.E-mail:why608@163.com

1000- 565X(2017)07- 0069- 08

TP 309.7

10.3969/j.issn.1000-565X.2017.07.010