一種基于LWE的BGN加密及門限加密方案

李菊雁，馬春光,2，袁 琪,3

(1. 哈爾濱工程大學計算機科學與技術學院 哈爾濱 150001; 2. 中國科學院信息工程研究所信息安全國家重點實驗室 北京 西城區(qū) 100093;3. 齊齊哈爾大學通信與電子工程學院 黑龍江 齊齊哈爾 161006)

基于容錯學習(learning with error problem, LWE)的密碼是一類備受關注的抗量子計算攻擊的公鑰密碼體制[1]。BGN加密方案[2]描述了一種允許任意次加法和一次乘法的密文運算的加密系統(tǒng)，并且在密文的運算中，密文的規(guī)模沒有增長。文獻[3]基于LWE構造了一種簡單的BGN加密方案GHV10，GHV10的解密算法需要用到陷門技術[4]。文獻[5]構造了一種BGN加密方案，但是基于雙線性配對和子集判定假設的。

加密方案BGV12[6]是一種全同態(tài)加密方案，加密的明文是比特，密文是向量。因為密文的乘法運算是向量的張量積，所以密文在運算后規(guī)模擴大。BGV12利用密鑰交換、模轉換等技術來控制噪音的增長和密文的規(guī)模，從而實現(xiàn)了全同態(tài)加密運算。如果為了實現(xiàn)密文的一次乘法運算仍然需要使用這些技術，那么BGV12就顯得有些差強人意。本文利用BGV12的加密方案設計了一種變形的加密方案。加密的明文為矩陣(明文打包運算[7])，密文也為矩陣。因為密文的乘法運算是矩陣的乘法，而不是矩陣的張量積，所以密文的規(guī)模在運算后沒有增大。

文獻[8]基于RLWE構造了一種全同態(tài)加密算法ZXJXZ14，并擴展成一種門限加密方案。本文依據ZXJXZ14，也將設計BGN加密方案擴展成一種門限加密方案，并且同樣能抵抗密鑰泄露攻擊。

1 預備知識

本文中的數、向量、矩陣分別記為x、x、X，向量的內積記為＜v,u＞，Ik表示k階單位矩陣，AT表示矩陣A的轉置，[k]表示集合{1,2,…,k}。對于概率分布D而言，x←D表示x依概率分布D選取，對于集合S，x←S表示x在集合S上均勻隨機選取。||v||∞、||A||∞分別表示向量v及矩陣A中元素最大的量級。表示對數x向下和向上取整，[x]q表示x(modq)，[A]q表示對矩陣A的每一個元素分別模q。規(guī)定?q=(-q/2,q/2]∩?。

定義 1(LWE問題[9])對于整數q=q(n)，向量上的誤差分布χ=χ(n)，選取輸出該分布記為As,χ。LWEn,m,q,χ的判定問題為：以不可忽略的優(yōu)勢來區(qū)分m個來自As,χ的取樣和m個上的均勻隨機取樣。文獻[9]在2005年證明了在量子歸約下，LWE問題至少與worst-case的近似因子為(n/α)的SVP、SIVP 的變體一樣困難，其中α是LWE實例中與擾動分布的方差有關的參數。文獻[10-11]分別給出了從GapSVP到LWE一個經典歸約。

定義 2(B界分布[12])對于一個定義在整數上的分布全體{χn}n∈N，如果是可忽略的，則{χn}n∈N稱為B界的。

定理 1[12]設q=q(n)∈?為素數的冪或者為不同poly(n)大小的素數的乘積，那么存在一個有效的取樣B界分布χ，使得如果存在一個有效的算法解決參數為n,q,χ的一般情況的LWE困難問題，那么：

1)存在一個有效的量子算法在n維格上解決GapSVPO?(nq/B)；

2)如果q≥(2n/2)，那么存在一個有效的經典算法在n維格上解決GapSVPO?(nq/B)。

對于這兩種情況，如果考慮以亞多項式的優(yōu)勢來區(qū)分，那么需要B≥(n)，并且最后的近似因子比(n1.5q/B)略大。

2 BGN加密方案

本節(jié)利用BGV12的加密方案設計了一種變形的加密方案。加密的明文為矩陣，密文也為矩陣。因為密文的乘法運算是矩陣的乘法，所以密文的規(guī)模在運算后沒有增大。又因為該加密方案也支持任意次密文加法運算，所以為BGN加密方案。

2.1 BGN加密方案

BGN加密方案由五元組(E.Setup,E.SecretKeygen, E.PublicKeygen, E.Enc, E.Enc,E.Dec)構成。

初始化階段E.Setup(1λ,1μ)：適應性地選擇μ比特的模q，及參數

引理 1 (安全性)[5]：設參數m,n,q,χ，使得LWEm,n,q,χ成立，那么對任意的如果R∈{0,1}n×n，則(BR,AR)與上的均勻分布計算不可區(qū)分。

2.2 同態(tài)性

設密文：

則：

1)加法

對于適合的參數有：

2)乘法

2.3 參數設定

定理 2令n為安全參數，任意的設q＞6n2c+6為素數，那么上述加密方案支持密文的nc次加法和一次乘法運算。

證明：先考慮密文C為l≤nc個密文的和，記

因為

下面考慮密文C′為兩個密文的乘積，這兩個密文分別為l1,l2個密文的和，其中l(wèi)1+l2≤nc，記

因為：

注：本方案與GHV10[3]相比較，對于任意的c=c(n)＞0，僅要求q＞6n2c+6為素數，而GHV10要求q＞220(c+4)3n3c+4log5n為素數。這意味著如果q的范圍擴大，則能支持比c=c(n)＞0更大的運算。

3 擴展成門限加密方案

本節(jié)首先介紹密鑰同態(tài)，然后構造門限加密方案，最后證明該方案能抵抗密鑰泄露攻擊。

3.1 密鑰同態(tài)

因為：

3.2 門限加密方案

類似于文獻[8]，本文也假設存在一個可信第三方F，F(xiàn)計算結合公鑰、密鑰，然后把計算后的結果發(fā)送給各個參與者(假設共k個參與者)，并同時保證密鑰的安全性。為了保證語義安全，本文同樣加入了干擾噪音。

密鑰生成算法TE.SecretKeygen(1n)：取Si←輸出

公鑰生成算法 TE.PublicKeygen(S)：取計算Bi=[SiA+2Xi]q，輸出

當F從k個參與者中接收到pki后誠實地計算故結合公鑰為：

加密算法TE.Enc(pk，M)：對于明文M∈{0,1}n×n及公鑰均勻取R∈{0,1}n×n及干擾噪音X*，輸出密文

解密算法TE.Dec(sk,C)：各參與者把解密共享發(fā)送給F，F(xiàn)誠實地計算并輸出明文M。

正確性可由以下運算得出。

3.3 結合密鑰的安全性

可以仿照文獻[8]的游戲來證明結合密鑰的安全性，即攻擊者不能以顯著優(yōu)勢區(qū)分在誠實公鑰下的加密密文與均勻選取的假密文，證明省略。

4 結 束 語

本文基于BGV12，設計了一種基于LWE的BGN加密方案。與GHV10比較，有較好的參數規(guī)模，即對于任意的c=c(n)＞0，GHV10要求q＞220(c+4)3n3c+4log5n為素數，而本文僅要求q＞6n2c+6為素數。與BGV12比較，因為不再需要用到密鑰交換、模轉換等技術，一次乘法同態(tài)運算更高效。與ZXJXZ14類似，將BGN加密也擴展成一種門限加密方案，允許所有參與者共同解密一個密文而沒有泄露明文的任何信息，并且能抵抗密鑰泄露攻擊。最后值得注意的是，類似于GHV10中的擴展及應用，同樣可以把本文的加密方案擴展成身份基加密(也需要利用陷門T)、Two-Out-of-Two加密等。

本文得到信息安全國家重點實驗室開放課題(2016-MS-10)的資助，在此表示感謝。

[1]王小云, 劉明潔. 格密碼學研究[J]. 密碼學報, 2014, 1(1)：13-27.WANG Xiao-yun, LIU Ming-jie. Survey of lattice-based cryptography[J]. Journal of Cryptologic Research, 2014,1(1)： 13-27.

[2]BONEH D, GOHE J, NISSIM K. Evaluating 2-DNF formulas on ciphertexts[C]//Proceedings of Second Theory of Cryptography Conference, TCC 2005. Cambridge, MA,USA： Springer, 2005： 325-341.

[3]GENTRY C, HALEVI S, VAIKUNTANATHAN V. A simple bgn-type cryptosystem from LWE[C]//Proceedings of Advances in Cryptology-EUROCRYPT 2010. Riviera,French： Springer, 2010： 506-522.

[4]MICCIANCIO D, PEIKERT C. Trapdoors for lattices：Simpler, tighter, faster, smaller[C]//Proceedings of Advances in Cryptology-EUROCRYPT 2012. Cambridge, UK：Springer, 2012： 700-718.

[5]ZHANG Wei. A BGN-type multiuser homomorphic encryption scheme[C]//Proceedings of 2015 International Conference on Intelligent Networking and Collaborative Systems. Taipei, Taiwan, China： IEEE, 2005： 268-271.

[6]BRAKERSHI Z, GENTRY C, VAIKUNTANATHAN V.(Leveled)fully homomorphic ncryption without bootstrapping[C]//Proceedings of the 3rd Innovations in Theoretical Computer Science Conference. Cambridge,Massachusetts： ACM. 2012： 309-325.

[7]HIROMASA R, ABE M, OKAMATO T. Packing messages and optimizing bootstrapping in GSW-FHE[C]//Proceedings of Public-Key Cryptography-PKC 2015.Gaithersburg, MD, USA： Springer, 2015： 699-715.

[8]ZHANG Xiao-jun, XU Chun-xiang, JIN Chun-hua, et al.Efficient fully homomorphic encryption from RLWE with an extension to a threshold encryption scheme[J]. Future Generation Computer Systems, 2014(36)： 180-186.

[9]REGEV O. On lattices, learning with errors, random linear codes, and cryptography[C]//Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing.Baltimore, MD, USA： ACM, 2005： 84-93.

[10]PEIKERT C. Public-key cryptosystems from the worst-case shortest vector problem[C]//Proceedings of the 41st Annual ACM Symposium on Theory of Computing.New York： ACM, 2009： 333-342.

[11]BRAKERSKI Z, LANGLOIS A, PEIKERT C, et al.Classical hardness of learning with errors[C]//Proceedings of the 45th Annual ACM Symposium on Symposium on Theory of Computing. New York： ACM, 2013： 575-584.

[12]GENTRY C, SAHAIY A, WATERS B. Homomorphic encryption from learning with errors： Conceptually-simpler,asymptotically-faster, attribute-based[C]//Proceedings of Advances in Cryptology-CRYPTO 2013. Santa Barbara,CA, USA： Springer, 2013： 75-92.