陳智罡 宋新霞 趙秀鳳

1(浙江萬里學院電子與計算機學院 浙江寧波 315100)2(浙江萬里學院基礎學院 浙江寧波 315100)3(信息工程大學三院 鄭州 450001) (zhig.chen@foxmail.com)

?

一個LWE上的短公鑰多位全同態(tài)加密方案

陳智罡1宋新霞2趙秀鳳3

1(浙江萬里學院電子與計算機學院 浙江寧波 315100)2(浙江萬里學院基礎學院 浙江寧波 315100)3(信息工程大學三院 鄭州 450001) (zhig.chen@foxmail.com)

目前全同態(tài)加密的效率亟待提高，為了提高全同態(tài)加密的效率，提出一個LWE(learning with errors)上的短公鑰多位全同態(tài)加密方案.方案中從離散高斯分布上選取LWE樣例，并且將高斯噪音與之相加，導致LWE樣例從 2nlogq下降到n+1，使得方案的公鑰長度變短.詳細給出了該方案的噪音增長分析與安全性證明；此外，對目前密鑰交換技術進行了優(yōu)化，并且針對多位全同態(tài)加密，給出了密鑰交換優(yōu)化版本的形式化描述；最后，針對目前全同態(tài)加密的實踐應用，給出了分析全同態(tài)加密具體安全參數(shù)的方法.分析了該方案與BGH13方案的具體安全參數(shù)，數(shù)據(jù)顯示該方案的具體參數(shù)長度要優(yōu)于BGH13方案.

全同態(tài)加密；學習錯誤問題；多位明文；具體安全參數(shù)；格密碼

全同態(tài)加密能夠在不知道密鑰的情況下對密文進行任意計算，這種特殊的性質(zhì)使得全同態(tài)加密有廣泛的應用需求，例如在云計算數(shù)據(jù)隱私安全、多方計算、密文檢索等.第1個全同態(tài)加密方案是由Gentry在2009年提出的[1]，此后人們提出了一些基于不同困難問題的全同態(tài)加密方案[2-7]以及對全同態(tài)加密效率改進的一些方法[8-11].

目前全同態(tài)加密的效率是阻礙其發(fā)展的主要問題，而低效率的主要原因之一是其密文尺寸過大.例如LWE(learning with errors)上的加密方案，出于安全性考慮，其密文中包含“噪音”，每次同態(tài)計算將引起密文噪音的增長，尤其是密文乘法計算使得密文噪音增長非?？?當噪音超過正確解密所允許的界后，將無法執(zhí)行同態(tài)操作.因此，為了能夠執(zhí)行更多的密文同態(tài)操作，必須設置大的參數(shù)使得密文有足夠的空間容納噪音，這直接導致了密文尺寸的劇增.

LWE上的加密都是按位加密，即一次加密一位.為了提高全同態(tài)加密的計算效率，人們提出了“密文打包(packed ciphertext)”的方法[12]，即將多個明文裝入到一個密文中.該方法使得對密文執(zhí)行一次同態(tài)操作，相當于并行對多個明文執(zhí)行同樣的操作.對于環(huán)LWE上的全同態(tài)加密，由于其環(huán)上的特殊性質(zhì)，可以使用中國剩余定理實現(xiàn)“密文打包”的方法[12]，并且獲得了性能上的極大提升[8].此外，Brakerski等人提出了LWE上全同態(tài)加密實現(xiàn)“密文打包”的方法[9]，該方案稱之為BGH13.

1 預備知識

1.1 基本概念

1.2 LWE問題

LWE問題最早由Regev引入[14]，隨后產(chǎn)生了其變種問題環(huán)LWE問題[15].LWE問題有3個參數(shù)：維數(shù)n≥1、整數(shù)模q≥2以及一個或q上的概率分布χ.對于一個向量s∈，LWE分布As,χ如下方式獲得：隨機均勻地選擇一個向量a∈以及一個噪音項e←χ，輸出(a,b=〈a, s〉+emodq) ∈×q.LWE搜索問題是：給任意數(shù)量的獨立樣例(ai,bi) ←As,χ去發(fā)現(xiàn)s.在密碼學應用中，更感興趣的是LWE判定問題：從LWE分布As,χ與均勻分布中分別取出任意相同數(shù)量的獨立樣例，以不可忽略的優(yōu)勢區(qū)分LWE分布As,χ與均勻分布.

格上標準困難問題可以歸約到LWE問題，目前有2種類型的歸約：量子歸約[14]與經(jīng)典歸約[16-17].此外，如果向量a取自于分布χ，LWE問題仍然是困難的[18].

1.3 層次型同態(tài)加密

一個同態(tài)加密方案HE=(Keygen,Enc,Dec,Eval)包含4個多項式時間算法.關于全同態(tài)加密的定義，可以參考文獻[1,5,19].

有2種類型的全同態(tài)加密方案：1)層次型全同態(tài)加密方案.該方案的參數(shù)依賴于乘法電路深度，方案能夠同態(tài)執(zhí)行任意多項式深度的電路.2)“純”的全同態(tài)加密方案.該方案能夠執(zhí)行任意深度的電路.任何一個層次型全同態(tài)加密方案 ，都可以通過同態(tài)解密技術以及循環(huán)安全假設，轉換成“純”的全同態(tài)加密方案.

定義1.L-同態(tài).如果一個同態(tài)加密方案HE滿足如下條件，則稱之為L-同態(tài).對于L=L(λ), 如果對于任意深度為L的算術電路f(建立在GF(2)之上)以及任意輸入m1,m2,…,ml有：

Pr[HE.Decsk(HE.Evalevk(f,c1,c2,…,cl))≠

f(m1,m2,…,ml)]=negl(λ),

其中,(pk,evk,sk)←HE.Keygen(1λ) 以及ci←HE.Encpk(mi).

定義2. 緊湊性、全同態(tài)、層次型全同態(tài)加密.如果一個同態(tài)加密方案的解密電路獨立于所計算的函數(shù)，則稱之為是緊湊的. 對于任意多項式L，如果一個緊湊的同態(tài)加密方案是L-同態(tài)，則稱之為全同態(tài)加密.對于一個全同態(tài)加密方案，如果在密鑰生成算法中還需要輸入1L，則該方案是層次型全同態(tài)加密.

2 基本加密方案

當前所有的全同態(tài)加密方案都是建立在基本加密方案之上的.本文方案是建立在Lindner和Peikert提出的加密方案之上[13]，但是我們將其改造為多位明文的加密方案，使其一次加密更多的信息.下面我們描述該方案，更重要的是分析其加密噪音和解密噪音.

該方案基于LWE問題，整數(shù)q≥2，維數(shù)n1和n2，高斯分布D表示為χ，以及隨機均勻矩陣了進一步約減公鑰尺寸，可以使用系統(tǒng)中共用的信任源生成A.如果系統(tǒng)中沒有信任源，可以在密鑰生成階段生成A，即作為公鑰的一部分.

1) SecretKeygen(1n2).隨機選擇一個矩陣S←χt×n2，輸出密鑰sk=S′←(I|-S)，其中I是t×t單位矩陣.因此密鑰sk是一個t×(t+n2)的矩陣，其中每一行可以看成是一個密鑰，用于解密多位消息中的一位.

2) PublicKeygen(A,sk).隨機選擇E←χn1×t,計算B=AST+E∈,輸出公鑰pk=B.

3) Enc(A,pk,m).為了加密多位消息m∈，隨機選取e1←χn1,e2←χt以及e3←χn2,輸出:

4) Dec(sk,c).計算v←S′c modq，輸出:

出于安全考慮，加密時引入了噪音，而正確解密依賴于噪音值.下面我們分析加密和解密的噪音值.

成立.

證明. 由解密定義可知:

證畢.

我們稱e是密文c中的噪音,以上引理給出了“新鮮”密文中的噪音值的上界.

引理2. 解密噪音.隨機選擇一個矩陣S←χt×n2，令c∈是一個向量,使得：

該解密形式與Regev加密方案[14]的解密形式相同，我們略去其證明.注意，為了恢復消息，|e|應該小于12，因此正確解密的條件是2. 由于2，我們這里取噪音的上界為.下面我們研究該方案的同態(tài)性.

3 同態(tài)操作

文c1和c2的加法或乘法計算結果c滿足:

或

其中,e的值是小的，m1⊙m2表示向量按相應的位乘積，則稱密文c在密鑰S+下獲得了加法同態(tài)性，或者密文c在密鑰S*下獲得了乘法同態(tài)性.

3.1 加法同態(tài)性

第3節(jié)中的基本加密方案本身具有加法同態(tài)性.根據(jù)定義有:

e1+e2(modq).

3.2 乘法同態(tài)性

3.3 密鑰交換

盡管通過上述乘法定義獲得了乘法同態(tài)屬性，但是它導致了密文與密鑰的維數(shù)擴張，因此需要使用密鑰交換技術[3-4]，將一個高維密文(對應于高維密鑰)轉換為一個正常維數(shù)的密文(對應于正常維數(shù)的密鑰).但是LWE上密鑰交換的效率是不高的.為了約減密鑰交換過程中的噪音增長，需要將密文表示為二進制的形式，這導致了密鑰交換矩陣的維數(shù)擴張.這里我們將引入一個提高密鑰交換效率的技巧，并且針對多位全同態(tài)加密，對優(yōu)化的密鑰交換過程進行了形式化.

此外，如果僅僅是將密鑰ST中的每一行對應的密鑰交換矩陣放在一起，形成一個新的密鑰交換矩陣的話，這將導致密鑰交換的結果是一堆正常維數(shù)的密文，而不是一個密文.因此，這里我們需要解決這個問題，必須整體生成一個密鑰交換矩陣，使得密鑰交換的結果是一個正常維數(shù)的密文.

密鑰交換包含2個算法:SwitchKeyGen算法用于生成密鑰交換矩陣；SwitchKey算法用于將對應于密鑰S1的密文轉換為對應于密鑰[I|S2]的密文.注意在SwitchKeyGen算法中，第2個參數(shù)輸入的是S2，而不是[I|S2].

我們稱W是密鑰交換矩陣.下面我們證明上述密鑰交換過程的正確性.

引理3. 令S1,S2,q,A,W是如上在Switch-KeyGen中描述的參數(shù).令c1∈ns，c2←SwitchKey(W,c1)，則有[I|S2]c2=et+S1c1(modq)，其中et=2-lEc1+[I|S2]ew是密文c2中的噪音.

[I|S2]Wc1+[I|S2]ew(modq)=

2-lEc1+[I|S2]ew+S1c1(modq)=

et+S1c1(modq).

由此得證.

證畢.

下面證明密鑰交換的安全性.

引理4. 選取S1←χt×ns,生成S2←SecretKeygen(1nt)和W←SwitchKeyGen(S1,S2).假設判定性LWE問題是困難的，則W與(t+nt)×ns上的均勻分布是計算上不可區(qū)分的.

證畢.

4 層次型全同態(tài)加密方案

深度為L的層次性全同態(tài)加密，電路的每一層有一個獨立的密鑰.同態(tài)計算從第L層到第1層，最后一層第0層僅僅是做密鑰交換.注意每一次執(zhí)行同態(tài)操作后，需要將密文計算的結果轉換為下一層電路的密文(即該密文對應于下一層電路的密鑰)，而每一次同態(tài)操作前需要2個密文擁有相同的密鑰，即“站”在電路的同一層上，否則需要將高層級密文轉換為低層級密文.

2) FHE.KeyGen(n1,n2,L).對于i=L,L-1,…,1,0，做如下操作:

④ 當i=0時,忽略此步.生成Wi→i-1←Switch-KeyGen(STi,Si-1).令pk2={Wi→i-1}.

3) FHE.Enc(pk1,m).消息m∈，執(zhí)行Enc(pk1,m).

5) FHE.Add(pk2,c1,c2).執(zhí)行下列步驟：

② 否則，如果密文c1,c2有不同的密鑰，則調(diào)用FHE.RefreshNextLevel算法將高層級密文轉換為低層級密文，直到2個密文擁有相同的密鑰.然后執(zhí)行步驟①.

6) FHE.Mult(pk2,c1,c2).執(zhí)行下列步驟：

② 否則，如果密文c1,c2有不同的密鑰，則調(diào)用FHE.RefreshNextLevel算法將高層級密文轉換為低層級密文，直到2個密文擁有相同的密鑰.然后執(zhí)行步驟①.

7) FHE.RefreshNextLevel(i,c,Wi→i-1).計算c′=c?(1,0,…,0)，輸出SwitchKey(Wi→i-1,c′).

下面證明上述方案的安全性.

引理5. 令參數(shù)n1,n2,q,χ使得判定性LWE問題是困難的，L是多項式深度.對于任意消息m∈，有(pk1,pk2,sk)←FHE.KeyGen(n1,n2,L),c←FHE.Enc(pk1,m),則(pk1,pk2,c)分布與均勻分布是計算上不可區(qū)分的.

證明. 由于pk2={WL→L-1,WL-1→L-2,…,W1→0}和pk1={BL}，考慮分布(BL,WL→L-1,WL-1→L-2,…,W1→0,c)，使用文獻[3]中的混合證明方式.首先，根據(jù)引理4，W1→0與均勻分布是不可區(qū)分的.然后所有Wi→i-1按照降序的方式用均勻分布替換.最后剩下(BL,c)，由于(BL,c)是基本加密方案的公鑰和密文，所以(BL,c)是與均勻分布不可區(qū)分的.因此，聯(lián)合分布 (pk1,pk2,c)與均勻分布在計算上是不可區(qū)分的.

證畢.

5 噪音分析

同態(tài)加法和乘法增長了密文的噪音，尤其是同態(tài)乘法極大地增長了噪音.同態(tài)加法的噪音就是2個密文的噪音之和，下面重點分析同態(tài)乘法的噪音增長.

(2)

則結果密文可以正確解密，即可以同態(tài)執(zhí)行深度為L的電路，因此獲得了一個層次型全同態(tài)加密方案.

6 具體安全參數(shù)

由于全同態(tài)加密方案的具體安全參數(shù)能夠反映方案的性能以及在實踐應用中非常重要[24-25]，下面我們分析方案的具體安全參數(shù)，并且將我們的方案與BGH13方案的參數(shù)進行分析比較.選取BGH13方案作為比較的對象，是因為該方案與我們的方案是屬于同一類型的全同態(tài)加密，具有可比性.

6.1 參數(shù)屬性

表1列出了我們方案和BGH13方案的參數(shù)屬性，參數(shù)長度用位表示.我們方案的LWE樣例的個數(shù)是n1，而BGH13方案的樣例個數(shù)是N=2nlogq. 假設電路深度是L，因此有L+1個密鑰和L+1個密鑰交換矩陣.注意，密鑰交換矩陣視為公鑰的一部分，稱為計算公鑰.如果假設循環(huán)安全，計算公鑰的個數(shù)將是1而不是L+1.本文并不做循環(huán)安全假設.顯然在我們方案中，公鑰長度要小于BGH13方案公鑰的logq倍.

Table 1 Some Properties of Two Schemes

6.2 具體參數(shù)

目前分析LWE上加密方案的具體安全參數(shù)的方法，采用的是區(qū)分攻擊.區(qū)分攻擊意味著敵手能夠以不可忽略的優(yōu)勢區(qū)分LWE實例與均勻實例.區(qū)分攻擊的本質(zhì)是在格Λ⊥(A)上發(fā)現(xiàn)一個非零的短向量.根據(jù)文獻[18]，使用目前已知的格基約減算法發(fā)現(xiàn)一個長度為β的短向量，需要是δ=2(log2β)(4n log q).對于隨機的LWE實例，計算一個root-Hermite因子為δ的約減基的時間(單位為秒)至少為：log(time)≥1.8logδ-110[13].因此給定安全等級λ、模q以及高斯參數(shù)r，維數(shù)n的下界為

n≥log(qr)(λ+110)7.2.

表2列出了安全等級λ=80，高斯參數(shù)r=8，對于不同的模q，其相應的維數(shù)最小值.

層次性全同態(tài)加密方案需要提前給出所需計算的電路深度L，然后根據(jù)電路深度L，從式(2)計算出所需的模q，該模q使得執(zhí)行深度為L的電路計算后，噪音增長不會超過正確解密的界，從而保證同態(tài)性的獲得.BGH13方案中沒有給出具體的噪音增長分析，我們采用第5節(jié)噪音增長分析的方法，獲得了執(zhí)行深度為L的電路計算后，噪音增長為

Table 2 Minimal Values of Dimension n

(3)

其中,t3=4(n+t)logq，t4=2(n+t)2Blog3q，“新鮮”密文的噪音是E′=2nBlogq.

表3、表4給出了安全等級是80位，在電路深度L取值0,1,5,10時，模q和維數(shù)n的具體取值.注意，公鑰長度、密鑰長度以及密文長度都是用千比特為單位.數(shù)據(jù)顯示在相同安全等級λ和電路深度L下，我們方案的模q和維數(shù)n小于BGH13方案的，其原因是我們方案的噪音增長要小于BGH13方案，從式(2)和式(3)的比較即可知道.由于公鑰長度、密鑰長度以及密文長度都依賴于模q和維數(shù)n的值，而我們方案的公鑰和密鑰長度的參數(shù)屬性都比BGH13方案小logq倍，所以直接導致了表3中公鑰長度、密鑰長度以及密文長度的具體值都要小于BGH13方案.

Table 3 The Sizes of Parameters in Our Scheme

Table 4 The Sizes of Parameters in BGH13

7 結 論

本文提出了一個短公鑰的多位全同態(tài)加密方案，詳細給出了該方案的噪音增長分析與安全性證明.此外，對目前密鑰交換技術進行了優(yōu)化，并且針對多位全同態(tài)加密，給出了密鑰交換優(yōu)化版本的形式化描述.最后，針對目前全同態(tài)加密的實踐應用，給出了分析全同態(tài)加密具體安全參數(shù)的方法.分析了本文方案與BGH13方案的具體安全參數(shù).數(shù)據(jù)顯示本文方案的具體參數(shù)長度要優(yōu)于BGH13方案.

[1]Gentry C. Fully homomorphic encryption using ideal lattices[C] //Proc of the 41st Annual ACM Symp on Theory of Computing (STOC). New York: ACM, 2009: 169-178

[2]van Dijk M, Gentry C, Halevi S, et al. Fully homomorphic encryption over the integers[G] //LNCS 6110: Advances in Cryptology (Eurocrypt 2010). Berlin: Springer, 2010: 24-43

[3]Brakerski Z, Vaikuntanathan V. Efficient fully homomorphic encryption from (Standard) LWE[C] //Proc of the 52nd IEEE Annual Symp on Foundations of Computer Science. Los Alamitos, CA: IEEE Computer Society, 2011: 97-106

[4]Brakerski Z, Gentry C, Vaikuntanathan V. (Leveled) Fully homomorphic encryption without bootstrapping[C] //Proc of the 3rd Innovations in Theoretical Computer Science Conf. New York: ACM, 2012: 309-325

[5]Brakerski Z. Fully homomorphic encryption without modulus switching from classical gapsvp[G] //LNCS 7417: Advances in Cryptology (Crypto 2012). Berlin: Springer, 2012: 868-886

[6]López-Alt A, Tromer E, Vaikuntanathan V. On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption[C] //Proc of the 44th Symp on Theory of Computing. New York: ACM, 2012: 1219-1234

[7]Gentry C, Sahai A, Waters B. Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based[G] //LNCS 8042: Advances in Cryptology (Crypto 2013). Berlin: Springer, 2013: 75-92

[8]Gentry C, Halevi S, Smart N. Fully homomorphic encryption with polylog overhead[G] //LNCS 8042: Advances in Cryptology (Eurocrypt 2012). Berlin: Springer, 2012: 465-482

[9]Brakerski Z, Gentry C, Halevi S. Packed Ciphertexts in LWE-Based Homomorphic Encryption[G] //Public-Key Cryptography (PKC 2013). Berlin: Springer, 2013: 1-13

[10]Alperin-Sheriff J, Peikert C. Faster bootstrapping with polynomial error[G] //LNCS 8616: Advances in Cryptology (CRYPTO 2014). Berlin: Springer, 2014: 297-314

[11]Hiromasa R, Abe M, Okamoto T. Packing messages and optimizing bootstrapping in GSW-FHE faster bootstrapping[G] //LNCS 9020: Public-Key Cryptography (PKC 2015). Berlin: Springer, 2015: 699-715[12]Smart N P, Vercauteren F. Fully homomorphic SIMD operations[J]. Designs, Codes and Cryptography, 2014, 71(1): 57-81

[13]Lindner R, Peikert C. Better key sizes (and attacks) for LWE-based encryption[G] //LNCS 6558: Topics in Cryptology (CT-RSA 2011). Berlin: Springer, 2011: 319-339

[14]Regev O. On lattices, learning with errors, random linear codes, and cryptography[C] //Proc of the 37th Annual ACM Symp on Theory of Computing. New York: ACM, 2005: 84-93

[15]Lyubashevsky V, Peikert C, Regev O. On ideal lattices and learning with errors over rings[G] //LNCS 6110: Advances in Cryptology (Eurocrypt 2010). Berlin: Springer, 2010: 1-23

[16]Peikert C. Public-key cryptosystems from the worst-case shortest vector problem: Extended abstract[C] //Proc of the 41st Annual ACM Symp on Theory of Computing. New York: ACM, 2009: 333-342

[17]Brakerski Z, Langlois A, Peikert C, et al. Classical hardness of learning with errors[C] //Proc of the 45th Annual ACM Symp on Theory of Computing. New York: ACM, 2013: 575-584

[18]Micciancio D, Regev O. Lattice-based cryptography[G] //Post-Quantum Cryptography. Berlin: Springer, 2009: 147-191

[19]Gentry C, Halevi S, Smart N. Homomorphic evaluation of the AES circuit[G] //LNCS 7417: Advances in Cryptology (CRYPTO 2012). Berlin: Springer, 2012: 850-867

[20]Chen Zhigang, Wang Jian, Zhang Zengnian, et al. A fully homomorphic encryption scheme with better key size[J]. China Communications, 2014, 11(9): 82-92

[21]Chen Zhigang, Song Xinxia, Zhang Yanhong. A fully homomorphic encryption scheme based on binary-LWE and analysis of security parameters[J]. Journal of Sichuan University: Engineering Science Edition, 2015, 47(2): 75-81 (in Chinese)(陳智罡, 宋新霞, 張延紅. 基于Binary-LWE噪音控制優(yōu)化的全同態(tài)加密方案與安全參數(shù)分析[J]. 四川大學學報: 工程科學版, 2015, 47(2): 75-81)

[22]Chen Zhigang, Wang Jian, Chen Liqun, et al. Review of how to construct a fully homomorphic encryption scheme[J]. International Journal of Security and its Applications, 2014, 8(2): 221-230

[23]Chen Zhigang, Wang Jian, Chen Liqun, et al. A regev-type fully homomorphic encryption scheme using modulus switching[J/OL]. Scientific World Journal, 2014 [2016-06-01]. https://www.hindawi.com/journals/tswj/2014/983862/abs/

[24]Yang Xiaoyuan, Zhou Tanping, Zhang Wei, et al. Application of a circular secure variant of LWE in the homomorphic encryption[J]. Journal of Computer Research and Develoment, 2015, 52(6): 1389-1393 (in Chinese)(楊曉元, 周潭平, 張薇, 等. 具有循環(huán)安全性的同態(tài)加密方案的設計[J]. 計算機研究與發(fā)展, 2015, 52(6): 1389-1393)

[25]Liu Mingjie, Wang An. Fully homomorphic encryption and its applications[J]. Journal of Computer Research and Develoment, 2014, 51(12): 2593-2603 (in Chinese)(劉明潔, 王安. 全同態(tài)加密研究動態(tài)及其應用概述[J]. 計算機研究與發(fā)展, 2014, 51(12): 2593-2603)

Chen Zhigang, born in 1972. Associate professor at Zhejiang Wanli University. Received his PhD degree from Nanjing University of Aeronautics and Astronautics. His main research interests include fully homomorphic encryption and lattice-based cryptography.

Song Xinxia, born in 1973. Associate professor at Zhejiang Wanli University. Received her MSc degree in mathematic theory from Zhejiang Normal University. Her main research interests include cryptography and algebra.

Zhao Xiufeng, born in 1977. Associate professor. Received her PhD degree from Shandong University. Her main research interests include cryptography protocols and fully homomorphic encryption.

A Multi-Bit Fully Homomorphic Encryption with Better Key Size from LWE

Chen Zhigang1, Song Xinxia2, and Zhao Xiufeng3

1(CollegeofElectronicandComputer,ZhejiangWanliUniversity,Ningbo,Zhejiang315100)2(CollegeofJunior，ZhejiangWanliUniversity,Ningbo,Zhejiang315100)3(TheThirdSchool,InformationEngineeringUniversity,Zhengzhou450001)

The efficiency of fully homomorphic encryption is a big question at present. To improve the efficiency of fully homomorphic encryption, we use the technique of packed ciphertexts to construct a multi-bit fully homomorphic encryption based on learning with errors (LWE) problem. Our scheme has a short public key. Since our fully homomorphic encryption scheme builds on the basic encryption scheme that chooses learning with errors samples from Gaussian distribution and add Gaussian error to it, which results in that the number of learning with errors samples decrease from 2nlogqton+1. We prove that our fully homomorphic encryption scheme is feasible and its security relies on the hardness of learning with errors problem. In addition, we adapt the optimization for the process of key switching from BGH13 and formal this new process of key switching for multi-bit fully homomorphic encryption. At last, we analyze the concert parameters and compare these parameters between our scheme and BGH13 scheme. The data show that our scheme has smaller public key by a factor of about logqthan the one in BGH13 scheme.

fully homomorphic encryption; learning with errors (LWE); multi-bit plaintext; concert security parameters; lattice-based cryptography

2016-06-16；

2016-08-17

浙江省自然科學基金項目(LY17F020002)；NSFC-浙江兩化融合聯(lián)合基金項目(U1509219)；寧波市自然科學基金項目(2016A610226)

TP309

This work was supported by the Natural Science Foundation of Zhejiang Province of China (LY17F020002), the NSFC-Zhejiang Joint Fund for the Integration of Industrialization Informatization (U1509219), and the Ningbo Natural Science Foundation (2016A610226).