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

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

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

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

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

文獻[8]基于RLWE構造了一種全同態加密算法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。規定?q=(-q/2,q/2]∩?。

定義 1(LWE問題[9])對于整數q=q(n)，向量上的誤差分布χ=χ(n)，選取輸出該分布記為As,χ。LWEn,m,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)。

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

2 BGN加密方案

本節利用BGV12的加密方案設計了一種變形的加密方案。加密的明文為矩陣，密文也為矩陣。因為密文的乘法運算是矩陣的乘法，所以密文的規模在運算后沒有增大。又因為該加密方案也支持任意次密文加法運算，所以為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)與上的均勻分布計算不可區分。

2.2 同態性

設密文：

則：

1)加法

對于適合的參數有：

2)乘法

2.3 參數設定

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

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

因為

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

因為：

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

3 擴展成門限加密方案

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

3.1 密鑰同態

因為：

3.2 門限加密方案

類似于文獻[8]，本文也假設存在一個可信第三方F，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誠實地計算并輸出明文M。

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

3.3 結合密鑰的安全性

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

4 結 束 語

本文基于BGV12，設計了一種基于LWE的BGN加密方案。與GHV10比較，有較好的參數規模，即對于任意的c=c(n)＞0，GHV10要求q＞220(c+4)3n3c+4log5n為素數，而本文僅要求q＞6n2c+6為素數。與BGV12比較，因為不再需要用到密鑰交換、模轉換等技術，一次乘法同態運算更高效。與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.