張興蘭 盧玉順

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

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

DOIDOI：10.11907/rjdk.181219

中圖分類號：TP309.7

文獻標識碼：A 文章編號：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ā)展和云計算的普及，人們對數(shù)據(jù)隱私的保護越來越重視。針對如何保證用戶數(shù)據(jù)的私密性有很多加密方案，其中全同態(tài)加密占據(jù)主流的研究地位。全同態(tài)加密（FHE）是一種特殊的加密方案，可以解決云計算、電子商務等安全問題。它允許第三方對加密數(shù)據(jù)進行任何操作而無需預先解密。Craig Gentry[1]于2009年實現(xiàn)了第一個真正意義上的全同態(tài)加密（FHE）方案，該方案允許對密文數(shù)據(jù)執(zhí)行任何加法和乘法功能。

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

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

1 預備知識

3 效率分析

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

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

4 結(jié)語

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

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

參考文獻：

[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].山東大學學報：理學版，2017，52（5）：85-94.

[14] 湯永利，胡明星，劉琨，等.新的格上基于身份的全同態(tài)加密方案[J].通信學報，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] 光焱，祝躍飛，費金龍，等.利用容錯學習問題構(gòu)造基于身份的全同態(tài)加密體制[J].通信學報，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

（責任編輯：杜能鋼）