多方免密鑰協(xié)商加密計(jì)算探究

楊賓（四川大學(xué)計(jì)算機(jī)學(xué)院，成都　610065）

多方免密鑰協(xié)商加密計(jì)算探究

楊賓
（四川大學(xué)計(jì)算機(jī)學(xué)院，成都610065）

0　引言

云計(jì)算是一種全新的在線計(jì)算模式，它是基于互聯(lián)網(wǎng)服務(wù)相關(guān)的使用和交付模式。根據(jù)美國(guó)國(guó)家標(biāo)準(zhǔn)與技術(shù)研究院（NIST）定義：云計(jì)算是一種按使用量付費(fèi)的模式，這種模式提供可用的、便捷的、按需的網(wǎng)絡(luò)訪問(wèn)，進(jìn)入可配置的計(jì)算資源共享池（資源包括網(wǎng)絡(luò)、服務(wù)器、存儲(chǔ)、應(yīng)用軟件、服務(wù)），這些資源能夠被快速提供，只需投入很少的管理工作，或與服務(wù)供應(yīng)商進(jìn)行很少的交互。云計(jì)算為企業(yè)和個(gè)人帶來(lái)了福音，用戶不再需要自己搭建服務(wù)平臺(tái)，只需要向云服務(wù)提供商按需購(gòu)買(mǎi)相應(yīng)的服務(wù)（存儲(chǔ)、計(jì)算資源），只用很少的費(fèi)用就能得到巨大的計(jì)算能力。云服務(wù)減少了用戶的系統(tǒng)管理、維護(hù)成本，并且避免了安全風(fēng)險(xiǎn)，收益大。云計(jì)算模式引起了商業(yè)領(lǐng)域、企業(yè)經(jīng)營(yíng)的大變革。

雖然云計(jì)算服務(wù)發(fā)展迅速，但云端的用戶隱私數(shù)據(jù)一直令人擔(dān)憂。云服務(wù)提供商的面前，用戶一直出于弱勢(shì)地位。雖然服務(wù)商一在承諾會(huì)保護(hù)數(shù)據(jù)隱私，但是并不能排除黑客攻擊或者內(nèi)部管理人員為了一己私利販賣(mài)數(shù)據(jù)庫(kù)的用戶數(shù)據(jù)。大量企業(yè)不敢將自己的數(shù)據(jù)存儲(chǔ)到云端，擔(dān)心服務(wù)商有意無(wú)意的使用自己的企業(yè)數(shù)據(jù)，泄漏商業(yè)秘密。數(shù)據(jù)泄漏已經(jīng)嚴(yán)重阻礙到云計(jì)算服務(wù)的使用。一般的數(shù)據(jù)保護(hù)方式是采用數(shù)據(jù)加密，將數(shù)據(jù)庫(kù)的數(shù)據(jù)加密存儲(chǔ)。如果數(shù)據(jù)庫(kù)被拷貝，沒(méi)有密鑰，數(shù)據(jù)也不會(huì)被解密泄漏，但是會(huì)增加數(shù)據(jù)操作復(fù)雜性：

①每一次操作之前，需要解密數(shù)據(jù)：m=D（c）；

②操作數(shù)據(jù)：m'=F（m）；

③操作完成之后，必須再一次加密數(shù)據(jù)：c'=E （m'）。

安全永遠(yuǎn)和效率是負(fù)相關(guān)，追求數(shù)據(jù)安全性，必將導(dǎo)致數(shù)據(jù)處理效率降低。每一次操作都將進(jìn)行一次數(shù)據(jù)加密，處理時(shí)間將會(huì)嚴(yán)重浪費(fèi)在加解密算法里面，真正用于數(shù)據(jù)處理的CPU時(shí)間將會(huì)變少。另一個(gè)問(wèn)題是密鑰存儲(chǔ)問(wèn)題，密鑰必須交給服務(wù)提供商，他們可以自行決定是否對(duì)加密數(shù)據(jù)解密，“監(jiān)守自盜”的可能性并沒(méi)有被排除。直接在密文上面進(jìn)行數(shù)據(jù)處理的同態(tài)加密應(yīng)運(yùn)而生。

1　同態(tài)加密

同態(tài)加密的定義可以描述為對(duì)于明文數(shù)據(jù)m1，m2加密，可以在它們對(duì)應(yīng)的密文之上進(jìn)行如下操作⊙。操作的結(jié)果解密之后，同直接對(duì)明文的操作值一樣。

1.1同態(tài)加密的發(fā)展

同態(tài)加密的概念的首次提出是1978年，Rivest，Adleman，Dertouzos在文獻(xiàn)[1]中為了解決明文的泄露問(wèn)題，采用的一種同時(shí)具有加法同態(tài)和乘法同態(tài)的算法。但是該方案和隨后的改進(jìn)方案都不能有效克制密文膨脹，導(dǎo)致復(fù)雜度升高，效率和安全性較低，不能抗已知明文攻擊。之后全同態(tài)加密成為了密碼學(xué)一個(gè)研究熱點(diǎn)，一個(gè)開(kāi)放的難題。直到2009年，由Gentry在文獻(xiàn)[2]構(gòu)造了第一個(gè)在格上的完備理論的全同態(tài)加密方案。通過(guò)“稀疏子集和”問(wèn)題的假設(shè)，從而在進(jìn)行各種密文操作的之后依靠自己的解密函數(shù)進(jìn)行同態(tài)解密，降低了密文噪聲的增長(zhǎng)，最終在這種假設(shè)下獲得全同態(tài)加密的理論基礎(chǔ)。Gentry為全同態(tài)加密開(kāi)啟了一扇大門(mén)，根據(jù)他的理論產(chǎn)生了多種改進(jìn)方案[3-4]。但是由于同態(tài)解密無(wú)論怎么改進(jìn)，效率依然十分低下，產(chǎn)生了基于LWE和RLWE的問(wèn)題的同態(tài)加密方案[5-8]，不再需要進(jìn)行同態(tài)解密技術(shù)，使用密鑰交換技術(shù)和模交換技術(shù)就能很好地控制密文的維數(shù)增長(zhǎng)和密文的噪聲增長(zhǎng)。

1.2NTRU 同態(tài)加密

NTRU最先由Jeffrey，Jill等人提出的一種公鑰加密[9]。它的困難問(wèn)題是在格中尋找最短向量（SVP）的數(shù)學(xué)難題。格是一組在Rm中n個(gè)線性無(wú)關(guān)向量的整系數(shù)集合。表示為：

其中b1，b2，b3…bn是在Rn空間中一組線性無(wú)關(guān)向量，它們共同構(gòu)成了格L的一組基。格可以有不同的基表示，一個(gè)格的基并不唯一。

最短向量問(wèn)題[10]：B∈Zn×m是格L的一組基，在格L （B）中的尋找一個(gè)非零向量Bx，使得||Bx||≤||By||，對(duì)任意的向量y∈Zm均成立。

NTRU是構(gòu)建在環(huán)上，通過(guò)多項(xiàng)式在環(huán)上進(jìn)行各類(lèi)操作。它只涉及了簡(jiǎn)單的模乘法運(yùn)算和模求逆運(yùn)算，沒(méi)有大數(shù)因式分解和離散對(duì)數(shù)等大量運(yùn)算，所以NTRU的效率更高，加、解密運(yùn)算速度顯著。它的困難問(wèn)題又是格上最短向量問(wèn)題，在維數(shù)較大的格里，具有抗量子計(jì)算能力。另外在全同態(tài)技術(shù)還不具有實(shí)用意義的時(shí)候，NTRU作為部分同態(tài)加密方案（somewhat

homomorphic encryption or partially homomorphic en-cryption），針對(duì)加法乘法的同態(tài)操作有天然優(yōu)勢(shì)。

1.3安全多方計(jì)算

安全多方計(jì)算（SMC）是一種協(xié)同計(jì)算模式，希望在各個(gè)互不信任的參與方共同參加一種計(jì)算，但是不會(huì)把自己的輸入泄露給其他參與者。每個(gè)參與者將輸入數(shù)據(jù)提交給可信的第三方進(jìn)行計(jì)算，計(jì)算完成之后，將結(jié)果返回給所有參與者，但是參與共同計(jì)算的時(shí)候不止要對(duì)其他參與者保密，同時(shí)也要對(duì)第三方計(jì)算平臺(tái)保密。因?yàn)楝F(xiàn)實(shí)里，并沒(méi)有完全可信的第三方。多方計(jì)算的SMC模型由以下四個(gè)方面組成：參與方、安全性定義、通信網(wǎng)模型、信息論安全與密碼學(xué)安全。

為了保護(hù)在云端的數(shù)據(jù)安全，不希望透露給任何人，包括參與者和第三方云服務(wù)商。所有存放在云端的數(shù)據(jù)采用同態(tài)加密，云服務(wù)商只能對(duì)密文進(jìn)行計(jì)算。參與方產(chǎn)生自己的密鑰，將自己的數(shù)據(jù)進(jìn)行加密之后，交給第三方進(jìn)行計(jì)算。計(jì)算完畢之后，得到結(jié)果。在公鑰加密體制內(nèi)，參與方在加密之前需要進(jìn)行密鑰協(xié)商，密鑰協(xié)商會(huì)導(dǎo)致一系列問(wèn)題。（1）密鑰協(xié)商需要花費(fèi)額外的時(shí)間。（2）在互聯(lián)網(wǎng)上海量的參與者進(jìn)行密鑰協(xié)商會(huì)增加許多不確定的因素。針對(duì)以上問(wèn)題，本文提出了多方免協(xié)商加密計(jì)算，來(lái)破除密鑰協(xié)商增加的時(shí)間復(fù)雜度。

2　多方免協(xié)商加密計(jì)算

通過(guò)NTRU的同態(tài)特性將云端數(shù)據(jù)加密之后進(jìn)行有效的計(jì)算，利用經(jīng)典的SHA-1哈希算法對(duì)參與方生成自己的數(shù)據(jù)計(jì)算哈希值，使得密文具有自己的獨(dú)立特性。對(duì)明文數(shù)據(jù)進(jìn)行雙重加密，一層是NTRU，保護(hù)數(shù)據(jù)的安全性和同態(tài)性。另外一層是哈希算法，增加數(shù)據(jù)的身份特性，這樣對(duì)參與計(jì)算的用戶，擁有獨(dú)立的解密權(quán)，沒(méi)有參與的用戶無(wú)法解密結(jié)果。

2.1數(shù)據(jù)解密過(guò)程

典型的NTRU方案參考文獻(xiàn)[11]，NTRU是構(gòu)建在商環(huán)Ζ[χ]/（χN-1）。公鑰是Η=αFa*Β（mod β），私鑰Α∈Lf，Β∈Lg，Lf，Lg是整系數(shù)多項(xiàng)式。N，α，β取整數(shù)，β為2的冪次方且β>>α。

①密鑰生成：隨機(jī)任意選擇3個(gè)多項(xiàng)式A，B和D，A和 B分別關(guān)于 mod α，mod β的可逆多項(xiàng)式 Fα，F(xiàn)β，D∈Lg。

2.2多方計(jì)算過(guò)程

每一個(gè)參與方必須使用一樣的加密和解密策略來(lái)處理數(shù)據(jù)。加密之后將發(fā)送給第三方進(jìn)行計(jì)算處理。先假設(shè)第三方收到了兩個(gè)參與者的數(shù)據(jù)，。每一個(gè)加密數(shù)據(jù)都含有每一個(gè)參與者的身份痕跡，所以每一次的數(shù)據(jù)計(jì)算之前都需要將痕跡抹去。

①暫時(shí)抹去身份痕跡：c1=c1-s1；c2=c2-s2

②計(jì)算數(shù)據(jù)：c3=c1⊙c2（⊙在NTRU加密方案中可以為加法同態(tài)或者乘法同態(tài)），s3=s1*s2，c3=c3+s3

③返回結(jié)果：，參與方利用自己的SHA-1值將c3解密。

上例中只有參與者有查看的權(quán)利，其他任何人都不能正確地解密結(jié)果，包括云計(jì)算提供商。

2.3正確性證明我們分別以加法同態(tài)和乘法同態(tài)進(jìn)行驗(yàn)證。（1）加法同態(tài)性證明

3　結(jié)語(yǔ)

多方免密鑰協(xié)商加密計(jì)算能夠?qū)⑼耆珜⑤斎牒洼敵黾用堋］斎胫挥幸粋€(gè)參與方能夠正確解密，所有參與方可以解密輸出。通過(guò)哈希函數(shù)為每一個(gè)參與方設(shè)置身份標(biāo)識(shí)，身份標(biāo)識(shí)不需要和其他參與方進(jìn)行協(xié)商，加密過(guò)程的時(shí)候，為每一個(gè)加密數(shù)據(jù)保留自己身份痕跡。只要輸出存在自己的身份痕跡，參與方就能正確解密數(shù)據(jù)。本文的加密安全性來(lái)自于格的SVP問(wèn)題，能夠?qū)沽孔佑?jì)算。云計(jì)算方只能按部就班進(jìn)行同態(tài)運(yùn)算，完全不了解參與運(yùn)算的數(shù)據(jù)和運(yùn)算結(jié)果，保護(hù)了存放在云端的隱私數(shù)據(jù)。同時(shí)參與方之間根本不知道對(duì)方的輸入值，達(dá)到了安全多方計(jì)算的根本要求。但是本方案存在一些不足之處，1）SHA-1最大的抗沖突性為280，如果在大量的參與方存在的情況下，由于生日悖論存在，攻擊者的哈希值猜測(cè)的哈希沖突會(huì)得到很大的提升，使得沒(méi)有查看計(jì)算結(jié)果的攻擊者，有機(jī)會(huì)查看計(jì)算結(jié)果。2）哈希函數(shù)的增加會(huì)導(dǎo)致一定的數(shù)據(jù)膨脹。

[1]Rivest R，Adleman L，Dertouzos M.On Data Banks and Privacy Homomorphisms[M].[S.l.]:Academic Press，1978:169-177.

[2]GENTRY C.Fully Homomorphic Encryption Using Ideal Lattices［C］.ACM，2009:169-178．

[3]van Dijk M，Gentry C，Halevi S，et al.Fully Homomorphic Encryption over the Integers[C].Proc.of Cryptology-CRYPTO'11.[S.l.]: Springer-Verlag，2011:24-43.

[4]Gentry C，Halevi S.Fully Homomorphic Encryption Without Squashing Using Depth-3 Arithmetic Circuits[C].Proc.of FOCSIEEE'11. [S.l.]:Springer-Verlag，2011.

[5]ZvikaBrakerski and Viod Vaikuntanathan.Efficient Fully Homoorphic Encryption from（Standard）lwe.In 2011 52nd Annual IEEE Symposium on Foundations of Computer Science，2011:97-106

[6]Vadim Lyubashevsky，Chris Peikert，Oded Regev.On Ideal Lattices and Learning with Errors Over Rigns.In EUROCRYPT-2010，volume 6110 of LNCS，2010:1-20

[7]Zvika Brakerski,Craig Gentry,Vinod Vaikuntanathan.Fully Homomorphic Encryption without Bootstrapping[C].ACM Transactions on Computation Theory，2014.7:[13:1]-[13:36]

[8]Ruan de Clercq，Sujoy Sinha Roy，F(xiàn)rederik Vercauteren.Efficient Software Implementation of Ring-LWE Encryption[C].EDA Consortium，2015.3:339-344

[9]J.Hoffstein，J.Pipher，J.H.Silverman.NTRU:A Ring-Based Public Key Cryptosystem[C].In:Algorithmic Number Theory（ANTS-III），LNCS 1423，Berlin:Springer-Verlag，June 1998:267-288.

[10]Goldreich o，Goldwasser S，Halevi S.Collision-Free Hashing from Lattice Problems[C].Electronic Colloquium on ComputationalComplexity（ECCC），1996，3（42）:236-241

[11]胡予濮.一個(gè)新型的NTRU類(lèi)數(shù)字簽名方案[J].計(jì)算機(jī)學(xué)報(bào)，2008，31（9）:1661-1666.

Cloud Security;Secure Multi Party Computation;Homomorphic Encryption;NTRU

Research on Encryption Computation of Multi-Party Free-Key Negotiation

YANG Bin
（College of Computer Science，Sichuan University，Chengdu 610065）

1007-1423（2016）07-0012-04

10.3969/j.issn.1007-1423.2016.07.003

楊賓（1989-），男，四川浦江人，碩士研究生，研究方向?yàn)樾畔踩?/p>

2016-01-21

2016-02-21

為了保護(hù)在云端的隱私數(shù)據(jù)，改變用戶的弱勢(shì)地位，安全多方計(jì)算得到廣泛關(guān)注。而安全多方計(jì)算是需要各方提前進(jìn)行密鑰協(xié)商，增加整個(gè)多方計(jì)算的復(fù)雜度和不安全因素。為了解決上述問(wèn)題，設(shè)計(jì)一種基于NTRU同態(tài)加密的多方免協(xié)商計(jì)算模型，縮短整個(gè)計(jì)算的步驟，降低風(fēng)險(xiǎn)。保護(hù)隱私數(shù)據(jù)和計(jì)算結(jié)果不被云服務(wù)商泄露，同時(shí)也不會(huì)被沒(méi)有參與過(guò)計(jì)算的用戶知曉計(jì)算結(jié)果。

云安全；安全多方計(jì)算；同態(tài)加密；NTRU

In order to protect the privacy of data in the cloud,to change the user's weak position,secure multi-party computation has been widely concerned.Secure multi-party computation is required for all parties for key agreement in advance,which increases the complexity and the unsafe factors of the whole multi-party computation.In order to solve the above problems,designs a method based on NTRU,which is based on the computation model of multi-party free-key negotiation,which shortens the calculation steps and reduces the risk.Privacy preserving data and computing results are not revealed by the cloud service provider,at the same time the user who not be involved in calculating not known results.