利用LWR構(gòu)造基于身份的全同態(tài)加密方案

張興蘭 盧玉順

摘 要：針對(duì)目前基于LWE（Learn With Errors）構(gòu)造全同態(tài)加密方案普遍需要高斯函數(shù)抽樣、公鑰尺寸過大等問題，提出利用高效的LWR（Learning With Rounding）替換傳統(tǒng)的LWE，構(gòu)造基于LWR（Learning With Rounding）的身份基全同態(tài)加密方案，對(duì)方案的安全性進(jìn)行嚴(yán)格證明。LWR問題是LWE問題的變體，消除了LWE問題利用高斯函數(shù)抽樣生成噪聲的過程，具有更高的計(jì)算效率以及更小公鑰和密文尺寸。

關(guān)鍵詞：LWR；LWE；基于身份；全同態(tài)加密；高斯函數(shù)

DOIDOI：10.11907/rjdk.181219

中圖分類號(hào)：TP309.7

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2018）010-0200-04

英文摘要Abstract：In order to solve the problem that the LWE-based fully homomorphic encryption scheme generally needs samples of Gaussian function and oversized public key，a new LWR （Learning With Rounding） algorithm is proposed to replace the traditional LWE problem and construct a LWR With Rounding，and the safety of the program is strictly proved.The LWR problem is a variant of the LWE （Learn With Errors） problem，which eliminates the process of generating noise of LWE in using Gaussian function. The sampling has higher computational efficiency and public key and ciphertext is of smaller size.

英文關(guān)鍵詞Key Words：LWR； LWE； identity-based encryption； fully homomorphic encryption； Gaussian noise sampling

0 引言

隨著互聯(lián)網(wǎng)技術(shù)的快速發(fā)展和云計(jì)算的普及，人們對(duì)數(shù)據(jù)隱私的保護(hù)越來(lái)越重視。針對(duì)如何保證用戶數(shù)據(jù)的私密性有很多加密方案，其中全同態(tài)加密占據(jù)主流的研究地位。全同態(tài)加密（FHE）是一種特殊的加密方案，可以解決云計(jì)算、電子商務(wù)等安全問題。它允許第三方對(duì)加密數(shù)據(jù)進(jìn)行任何操作而無(wú)需預(yù)先解密。Craig Gentry[1]于2009年實(shí)現(xiàn)了第一個(gè)真正意義上的全同態(tài)加密（FHE）方案，該方案允許對(duì)密文數(shù)據(jù)執(zhí)行任何加法和乘法功能。

自Gentry實(shí)現(xiàn)第一個(gè)全同態(tài)加密方案后，F(xiàn)HE方案逐漸成為研究熱點(diǎn)，至今產(chǎn)生了各種方案。當(dāng)前研究全同態(tài)加密主體思路是基于LWE的安全性假設(shè)。因?yàn)長(zhǎng)WE理論上可以規(guī)約到格上求解SIVP和GapSVP問題，因此基于LWE的全同態(tài)加密方案具有牢固的安全保證。2011年Brakerski等[2-3]采用基于LWE的思想構(gòu)造全同態(tài)加密方案，方案使用“重線性化”方法實(shí)現(xiàn)密文之間的同態(tài)加法和乘法運(yùn)算。但同態(tài)過程需用到額外的同態(tài)計(jì)算公鑰evk，導(dǎo)致密文計(jì)算復(fù)雜且效果不佳；2012年Brakerski[4]基于LWE提出了模q不變的全同態(tài)方案，省略了模數(shù)轉(zhuǎn)換技術(shù)的消耗，但欲保證安全，該方案模數(shù)q的取值很大，導(dǎo)致較高的復(fù)雜度；2013年，Gentry[5]在Crypto國(guó)際會(huì)議中提出利用近似特征向量方法構(gòu)造FHE方案。該方案的優(yōu)勢(shì)是密文之間乘積不會(huì)導(dǎo)致維數(shù)擴(kuò)張，消除了秘鑰交換技術(shù)。但是密文的同態(tài)計(jì)算為向量轉(zhuǎn)換為矩陣之間的加法和乘法，計(jì)算復(fù)雜；文獻(xiàn)[6，9]分別提出利用多鍵和舍棄自舉技術(shù)等方案，在一定程度上改進(jìn)了全同態(tài)方案效率，但這些方案基于LWE問題都需高斯噪聲抽樣，時(shí)間開銷大，計(jì)算上也存在瓶頸。Bogdanov[7]提出的LWR問題是LWE問題的變體，安全性與LWE問題一樣困難，而且LWR問題消除了高斯函數(shù)抽樣，顯著提高了計(jì)算效率，F(xiàn)ang等[10]基于LWR構(gòu)造了身份基加密方案。

基于id的加密方案（IBE）是使用用戶id作為唯一的標(biāo)記來(lái)生成主公鑰，用戶的私鑰由第三方機(jī)構(gòu)利用主私鑰和身份id生成，從而消除了公鑰證書的相關(guān)計(jì)算開銷，可更加有效地管理秘鑰sk，減小sk尺寸。文獻(xiàn)[11-16]都是基于id構(gòu)造改進(jìn)的全同態(tài)加密方案，然而這些思想是LWE問題的困難性假設(shè)，時(shí)間效果存在瓶頸。COSTACHE等[8]基于LWR構(gòu)造了分級(jí)FHE方案，優(yōu)勢(shì)是更小的公鑰和密文長(zhǎng)度，以及更小的計(jì)算模數(shù)，但在密文計(jì)算同態(tài)運(yùn)算時(shí)需要運(yùn)算秘鑰evk，導(dǎo)致較高的時(shí)間代價(jià)。本文提出了利用LWR困難假設(shè)構(gòu)造基于id的全同態(tài)加密方案，首先構(gòu)造了高效的基于LWR的IBE方案，然后基于特征向量思想，將該高效LWR-IBE方案轉(zhuǎn)化為基于身份的全同態(tài)加密方案，不僅消除了高斯噪聲抽樣和運(yùn)算秘鑰，而且公鑰尺寸更小，加解密過程更加高效。

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

3 效率分析

本文提出的LWR-IBE方案比傳統(tǒng)的基于LWE問題構(gòu)造的IBE方案具有更小的公鑰尺寸和密文尺寸。借鑒Wang等[12]采用高效的陷門生成算法構(gòu)造身份id，消除了加密過程LWE進(jìn)行高斯函數(shù)抽樣的高昂時(shí)間開銷，比Wang等[12]有更高效的加解密效率。

基于LWR-IBE構(gòu)造的LWR-IBFHE方案，借鑒光焱等[16]提出的利用LWE問題構(gòu)造基于id的FHE體制，以及COSTACHE等[8]采用LWR構(gòu)造的無(wú)高斯噪聲的加密方案。但光焱等[16]的方案中，秘鑰生成過程采用了陷門矩陣的逆運(yùn)算，光焱等[16]和COSTACHE等[8]的方案中同態(tài)計(jì)算過程用到了同態(tài)運(yùn)算秘鑰evk，這些都導(dǎo)致方案的低效。本文方案利用特征向量的方法，摒棄了運(yùn)算秘鑰，使計(jì)算復(fù)雜度降低。因?yàn)楸疚姆桨傅拿芪亩际蔷仃?，因此密文的乘積不會(huì)導(dǎo)致密文維數(shù)增大，具有更低的復(fù)雜度和更高的效率。

4 結(jié)語(yǔ)

基于容錯(cuò)學(xué)習(xí)的全同態(tài)加密方案是研究熱點(diǎn)，但這類方案隱含的公鑰尺寸過大和代價(jià)高昂的高斯噪聲抽樣成為影響其效率的瓶頸。本文提出的基于LWR的LWR-IBFHE方案，依據(jù)用戶id加密，有效避免了和id相關(guān)的計(jì)算開銷，帶舍入學(xué)習(xí)問題的構(gòu)造在保證安全性的基礎(chǔ)上降低了公鑰尺寸，計(jì)算效率更高。

本文提出的設(shè)計(jì)方案局限性在于僅證明了選擇明文下的安全性，而在云計(jì)算越來(lái)越普及的環(huán)境下，如何設(shè)計(jì)滿足密文安全的加密方案尤為重要，文獻(xiàn)[17]、[18]提出了CCA1下安全的FHE方案構(gòu)想。本方案實(shí)現(xiàn)了滿足同一身份id的同態(tài)計(jì)算，今后將進(jìn)一步研究多身份id的密文同態(tài)計(jì)算，以及構(gòu)造CCA1安全的身份基全同態(tài)加密方案。

參考文獻(xiàn)：

[1] GENTRY C.A fully homomorphic encryption scheme[M].Stanford： Stanford University Press，2009.

[2] BRAKERSKI Z，VAIKUNTANATHAN V.Fully homomorphic encryption from ring-LWE and security for key dependent messages[C].Cryptology Conference，2011：505-524.

[3] BRAKERSKI Z，VAIKUNTANATHAN V.Efficient fully homomorphic encryption from （Standard） LWE[C].Foundations of Computer Science.IEEE，2011：97-106.

[4] BRAKERSKI Z.Fully homomorphic encryption without modulus switching from classical gapSVP[J].Lecture Notes in Computer Science，2012（7417）：868-886.

[5] GENTRY C，SAHAI A，WATERS B.Homomorphic encryption from learning with errors：conceptually-simpler，asymptotically-faster，attribute-based[C].Advances in Cryptology-CRYPTO 2013.Springer Berlin Heidelberg，2013：75-92.

[6] CLEAR M，MCGOLDRICK C.Multi-identity and multi-key leveled FHE from learning with errors[C].Advances in Cryptology -- CRYPTO 2015.Springer Berlin Heidelberg，2015：630-656.

[7] BOGDANOV A，GUO S，MASNY D，et al.On the hardness of learning with rounding over small modulus[C].Proceedings，Part I，of the 13th International Conference on Theory of Cryptography，2016：209-224.

[8] COSTACHE A，SMART N P.Homomorphic encryption without Gaussian noise[EB/OL].[2017-03-16].https：//eprint.iacr.org/2017/163.pdf.

[9] BRAKERSKI Z，GENTRY C，VAIKUNTANATHAN V.（Leveled） Fully homomorphic encryption without bootstrapping[J].Acm Transactions on Computation Theory，2014，6（3）：1-36.

[10] FANG F，LI B，LU X，et al.Hierarchical identity-based encryption from learning with rounding over small modulus[C].ACM on Asia Conference on Computer & Communication Security，2016：907-912.

[11] AGRAWAL S，DAN B，BOYEN X.Efficient lattice （H）IBE in the standard model[C].International Conference on Theory and Application of Cryptographic Techniques ，2010：553-572.

[12] WANG J，WANG C.Full secure identity-based encryption scheme over lattices in the standard model[C].International Conference on P2p，Parallel，Grid，Cloud and Internet Computing，2016：412-415.

[13] 王威力，胡斌，趙秀鳳.一種高效的多身份全同態(tài)加密方案[J].山東大學(xué)學(xué)報(bào)：理學(xué)版，2017，52（5）：85-94.

[14] 湯永利，胡明星，劉琨，等.新的格上基于身份的全同態(tài)加密方案[J].通信學(xué)報(bào)，2017，38（5）：39-47.

[15] HE J，LI B，LU X，et al.KDM and selective opening secure IBE based on the LWE problem[C].ACM International Workshop on Asia Public-Key Cryptography.ACM，2017：31-42.

[16] 光焱，祝躍飛，費(fèi)金龍，等.利用容錯(cuò)學(xué)習(xí)問題構(gòu)造基于身份的全同態(tài)加密體制[J].通信學(xué)報(bào)，2014（2）：111-117.

[17] YASUDA S，KITAGAWA F，TANAKA K.Constructions for the IND-CCA1 secure fully homomorphic encryption[EB/OL].http：//www.doc88.com/p-6803897907202.html

[18] RAN C，RAGHURAMAN S，RICHELSON S，et al.Chosen-ciphertext secure fully homomorphic encryption[EB/OL].http：//www.docin.com/p-1518991708.html

（責(zé)任編輯：杜能鋼）