基于LWE的單層同態(tài)云計算方案

王旭陽　 胡愛群　 方　昊

(東南大學(xué)信息科學(xué)與工程學(xué)院, 南京 210096)

?

基于LWE的單層同態(tài)云計算方案

王旭陽 胡愛群 方昊

(東南大學(xué)信息科學(xué)與工程學(xué)院, 南京 210096)

為了實現(xiàn)安全的遠程操作,通過分析研究一次或單層的同態(tài)運算,構(gòu)造了一個基于錯誤學(xué)習(xí)(LWE)的單層同態(tài)云計算方案(sLHCC).首先,根據(jù)解密者是否知道LWE問題中所使用的隨機向量,構(gòu)造了2個不同的單層同態(tài)加密方案sLHE1和sLHE2,并得到了相應(yīng)的sLHCC方案.該方案在保持LWE問題困難性的基礎(chǔ)上,實現(xiàn)了云端單次的同態(tài)加和乘運算.根據(jù)合理的操作約定和同態(tài)結(jié)果,用戶可以在不泄露操作需求(密文)的情況下,執(zhí)行遠程操作和控制.結(jié)果表明,與其他同態(tài)加密方案相比,sLHCC的公鑰尺寸從傳統(tǒng)的矩陣降為向量,從而減小了密文尺寸和云端的存儲需求.

云計算;格密碼;錯誤學(xué)習(xí);同態(tài);遠程操作

隨著智能終端的快速發(fā)展,遠程操作和控制已經(jīng)被越來越多的用戶所接受.用戶將遠端的操作和控制對象以及相應(yīng)的操控按照特定方式命名,便可通過云端實現(xiàn)對操作和控制對象的操控.然而,在實際應(yīng)用中用戶操作和信息傳輸?shù)陌踩詤s沒有得到足夠的保障[1].隨著計算能力的日益強大,攻擊者對于密碼系統(tǒng)的攻擊能力也不斷提升.為了提高安全性,人們不得不提高安全參數(shù)的長度,并對傳統(tǒng)密碼學(xué)模型進行改進.然而,量子計算機強大的并行計算能力,使其具有解決傳統(tǒng)密碼學(xué)模型中困難問題的能力.

作為格密碼的載體,格的研究雖然有著長達200多年的歷史,但成為密碼學(xué)上的研究熱點卻僅在近來這二十多年.與傳統(tǒng)密碼學(xué)模型不同,格困難問題可以歸約為一般問題,在這一特性下,攻擊基于具體格問題構(gòu)造的密碼系統(tǒng)等同于求解相應(yīng)的格困難問題.1997年Ajtai[2]率先給出了上述特性的一個肯定性歸約結(jié)果.文獻[3-4]獲得了一系列與格困難問題歸約有關(guān)的結(jié)果,為構(gòu)造滿足相應(yīng)安全需求的格密碼系統(tǒng)提供了理論支持.

本文基于LWE問題構(gòu)造了單層同態(tài)云方案sLHCC.該方案在保持LWE問題困難性的基礎(chǔ)上,實現(xiàn)了云端單次的同態(tài)加和乘運算.根據(jù)合理的操作約定和同態(tài)結(jié)果,用戶可以在不泄露操作需求(密文)的情況下,執(zhí)行遠程操作和控制.

1　基本概念

對于任意實數(shù)r,?r?=?r+1/2?表示距離r最近的整數(shù).對于任意正整數(shù)θ,poly(θ)表示非特指的多項式函數(shù),negl(θ)表示非特指的θ階可忽略函數(shù).

1.1格

1.2高斯分布

對于任意正實數(shù)s>0,數(shù)學(xué)期望為c∈Rn、標(biāo)準(zhǔn)差為s的高斯分布定義如下:

?y∈Rnρs,c(y)=e-π‖y-c‖2/s2

當(dāng)s=1,c=0時,可將ρs,c(y)的下標(biāo)省去,用ρ(y)代替.簡單起見,下文中假設(shè)所有算法都能有效地按照高斯分布抽樣.

對于任一格空間L,離散高斯分布定義如下:

1.3LWE困難問題

定義1(誤差學(xué)習(xí)(LWE))給定Zq上一概率分布χ和Ax,χ上任意多個抽樣,求解x.

1.4同態(tài)

公鑰體制的加密方案ε通常由密鑰生成算法KeyGen、加密算法Encrypt、評估算法Evaluate和解密算法Decrypt四個算法組成[5-10].密鑰生成算法和加解密算法與傳統(tǒng)加密方案類似.評估算法中,通過輸入公鑰pk、密文組(c1,c2,…,ct)和某一電路C,得到一個新的密文c,其中t≥2為同態(tài)運算涉及的明文數(shù)量.

定義3(同態(tài)算法的正確性)給定密鑰生成算法KeyGen,支持t個以上輸入的電路C和t明文(m1,m2,…,mt),如果對于任意生成的密鑰對(pk,sk)和通過ci=Encrypt(pk,mi)加密得到的密文組(c1,c2,…,ct),等式Decrypt(sk,Evaluate(pk,C,(c1,c2,…,ct)))=C(m1,m2,…,mt)成立,則稱同態(tài)公鑰加密方案ε=(KeyGen,Encrypt,Evaluate,Decrypt)正確.

2　單層同態(tài)加密方案

目前,研究者們已構(gòu)造出大量的同態(tài)乃至全同態(tài)加密方案[5-10].在構(gòu)造同態(tài)方案的過程中,通常遵循2個研究方向:① 強化方案的自我修正能力,加強方案在同態(tài)運算層數(shù)方面的能力直至實現(xiàn)真正的全同態(tài)運算;但這會導(dǎo)致方案復(fù)雜化,公共參數(shù)、公私鑰和密文等數(shù)量都可能急劇增大[5,7-10].② 在保證足夠安全性和同態(tài)運算層數(shù)的情況下,盡量減小各種參數(shù)數(shù)量,從而使得方案簡單化[6-7].

2) sLHE1.Encrypt(pk,sk,m1,m2,…,mt):給定加密信息mi∈GF(p1),根據(jù)分布χ隨機選擇高斯參量ei∈Zq,輸出密文ci=mi+aix+ei(modq)和相應(yīng)的同態(tài)計算需求.

3) sLHE1.Evaluate(c1,c2,…,ct):通過同態(tài)加 (可以一次多個密文) 和同態(tài)乘(一次2個密文),計算并輸出同態(tài)加結(jié)果cA和同態(tài)乘結(jié)果cM.

4) sLHE1.Decrypt(sk,cA,cM):根據(jù)不同評估情況進行解密.

顯然,sLHE1方案實現(xiàn)了單次的同態(tài)加和同態(tài)乘運算.由于加密方和解密方為同一用戶,加、解密方擁有了方案使用過程中的所有隨機數(shù),從而使得sLHE1方案擁有比其他格密碼方案更高的解密成功率.

結(jié)論1當(dāng)mi∈GF(p1)時,sLHE1方案的密文可以被正確解密.

證明為簡單起見,假定僅有2個密文參與同態(tài)加和同態(tài)乘運算(即t=2),則

(cA-(a1+a2)x)-e1-e2)(modq)=

(m1+m2)(modq)

(cM+a1xa2x-a1c2x-a2c1x-e1m2-e2m1-e1e2)(modq)=

(m1m2)(modq)

事實上,當(dāng)同態(tài)加密文數(shù)不大于t時,仍有(m1+m2)≤q-1,則

(cA-(a1+a2+…+at)x)-e1-e2-…-et)(modq)=

(m1+m2+…+mt)(modq)

式中,cA=c1+c2+…+ct.證畢.

值得注意的是,sLHE1方案并不是一個標(biāo)準(zhǔn)的加密方案.sLHE1加密和解密都是由同一用戶進行的,故公、私鑰可以互換或者同時作為加密密鑰.用戶可以通過預(yù)處理來簡化運算過程中的計算復(fù)雜度.

由于解密方知道加密方加密時所使用的高斯隨機向量,因此在解密過程中不會因為相應(yīng)的隨機向量產(chǎn)生誤差.但在實際應(yīng)用中,解密方難以同時獲得這些信息.為了解決這一問題,給定公共參數(shù)p2=p1/2,將sLHE1方案改進為單層同態(tài)加密方案sLHE2.sLHE2方案由以下4個算法組成.

3) sLHE2.Evaluate(c1,c2,…,ct,M,N):通過同態(tài)加 (可以一次多個密文) 和同態(tài)乘(一次2個密文),計算并輸出同態(tài)加結(jié)果cA和同態(tài)乘結(jié)果cM.

4) sLHE2.Decrypt(sk,cA,cM):根據(jù)不同評估情況進行解密.

證明證明方法與結(jié)論1類似.需要注意的是,解密時需要成功消去高斯隨機向量帶來的密文噪音,即M(e1+e2+…+et)≤q/2和N(e1m2+e2m1+Ne1e2)≤q/2.

M(e1+e2+…+et)≤q/2

2N(e1m2+e2m1+Ne1e2)≤

證畢.

3　單層同態(tài)云計算方案

遠程操作和控制問題描述如圖1所示.首先,用戶將遠程操作和控制對象按照特定方式命名得到明文,并通過不同的運算定義不同操控.加密方將得到的明文和運算需求發(fā)送到云端.云端通過同態(tài)運算將相應(yīng)結(jié)果發(fā)送給解密方,解密方解密后便可通過運算結(jié)果實現(xiàn)對操作對象的操控.

圖1　遠程操作和控制問題描述

給定公共參數(shù)p={p1(sLHE1),p2(sLHE2)},并用op={+,·}表示同態(tài)運算集合,根據(jù)方案sLHE1或sLHE2構(gòu)造出安全單層同態(tài)云計算方案(sLHCC).需要注意的是,選定了sLHE方案后,整個sLHCC方案須依據(jù)同一sLHE方案構(gòu)造.sLHCC方案由以下4個算法組成.

1) sLHCC.KeyGen(1n):用戶通過sLHE1.KeyGen或sLHE2.KeyGen得到相應(yīng)的公私鑰(pk,sk).

2) sLHCC.Encrypt(sk,pk,m):用戶根據(jù)云同態(tài)計算明文信息m∈GF(p)確定參數(shù)t,q和p.通過sLHE1.Encrypt或sLHE2.Encrypt,按同態(tài)計算順序輸出密文(c1,c2,…,ct,ο),其中ο∈op表示某種同態(tài)運算.

3) sLHCC.Evaluate(c1,c2,…,ct,ο):根據(jù)用戶需求,服務(wù)器端通過sLHE1.Evaluate或sLHE2.Evaluate計算同態(tài)加 (可以一次多個密文) 或者同態(tài)乘(一次2個密文),并輸出結(jié)果cA和cM.

4) sLHCC.Decrypt(sk,cA,cM):用戶根據(jù)不同同態(tài)情況通過sLHE1.Decrypt或sLHE2.Decrypt進行解密.

結(jié)論3當(dāng)m∈GF(p)時,sLHCC方案的密文可以被正確解密.

容易發(fā)現(xiàn)sLHCC方案的公、私鑰是相互獨立抽取的,因此即使用戶重復(fù)使用同一私鑰,云端也難以得到相應(yīng)的私鑰.事實上,云端破解方案獲取私鑰的困難等同于求解相應(yīng)的LWE困難問題.根據(jù)文獻[2,5,11-15]中關(guān)于格困難問題和一般問題相互歸約的結(jié)論可知,LWE問題在給定參數(shù)下的復(fù)雜度為NP∩coNP[2,14-15].這意味著在多項式時間內(nèi)求解相應(yīng)的LWE問題是不可能的,攻擊者也不可能在多項式時間內(nèi)破解相應(yīng)的方案.

為了討論sLHCC方案的安全性,下面給出不可區(qū)分選擇明文安全(IND-CPA)的定義[5].

結(jié)論4單層同態(tài)云計算方案sLHCC是IND-CPA的.

證明由引理1可知,sLHE1.Encrypt和sLHE2.Encrypt加密得到的密文與Zq上的隨機均勻抽樣是計算不可區(qū)分的.在信息傳輸過程中沒有泄露任何與密文有關(guān)的信息,因此,云端得到的密文仍與Zq上的隨機均勻抽樣是計算不可區(qū)分的.對于均勻抽樣,易知pr[φ(pk,Evaluate,Encryptpk(0))=1≈pr[φ(pk,Evaluate,Encryptpk(1))=1,即任意多項式敵手φ獲得的優(yōu)勢AdvCPA(φ)=negl(n),因此sLHCC是IND-CPA的.

4　復(fù)雜度分析

執(zhí)行一輪sLHCC方案所需的計算復(fù)雜度見表1.與常見的同態(tài)方案[5-7]只能支持GF(2)計算不同,sLHCC方案支持更大范圍(GF(p))內(nèi)數(shù)據(jù)的計算.由于一次減操作所需的計算量與一次加操作相同,故此處將其視為同一操作.

表1　單輪sLHCC方案的復(fù)雜度分析

在sLHCC方案中,將加、解密兩方視為同一用戶,擁有共同的私鑰,因此當(dāng)解密者知道進行加密操作的高斯向量值時,解密者可以通過直接計算成功解密,而不用擔(dān)心其他格密碼體制中由于隨機參數(shù)導(dǎo)致的解密成功率問題.由此可知,本方案不需要通過多次運行來增加解密成功率.故而采用本方案可以減少相應(yīng)的參數(shù)尺寸.表2給出了本方案與一般LWE加密方案時的參數(shù)尺寸比較.由表可知,與LWE加密方案相比,雖然sLHCC的私鑰尺寸沒有明顯變化,但是公鑰尺寸從傳統(tǒng)的矩陣降為向量,從而減小了密文尺寸和云端的存儲需求.同時,執(zhí)行一次sLHCC方案所能加密的明文數(shù)量大于普通LWE加密方案.因此,在對非單個明文進行加密運算時,sLHCC方案較一般LWE加密方案擁有更高效的執(zhí)行效率.

表2　參數(shù)尺寸比較

5　結(jié)語

本文以格困難問題LWE為基礎(chǔ),構(gòu)造了一個單層同態(tài)云計算方案sLHCC.與基于傳統(tǒng)密碼學(xué)方案相比,sLHCC在理論上擁有更好的安全性和抗攻擊能力.在實際應(yīng)用中,除去密文使用到了私鑰外,公、私鑰之間互信息為零,這使得用戶不需要頻繁更新用戶私鑰.此外,該方案每次只需執(zhí)行單層同態(tài)運算,相比一般LWE加密方案,sLHCC擁有更小的參數(shù)尺寸.這些優(yōu)勢增加了方案的效率,減小了云端存儲的空間占用,為構(gòu)造安全可存儲的單層同態(tài)云計算方案提供了基礎(chǔ).

References)

[1]Aguilar-Melchor C, Fau S, Fontaine C, et al. Recent advances in homomorphic encryption: A possible future for signal processing in the encrypted domain[J].IEEESignalProcessMag, 2013, 30(2): 108-117. DOI:10.1109/msp.2012.2230219.

[2]Ajtai M. Generating hard instances of lattice problems[C]//ProceedingsoftheTwenty-EighthAnnualACMSymposiumonTheoryofComputing. New York: ACM, 1996: 99-108. DOI:10.1145/237814.237838.

[3]Wang X Y, Hu A Q. Complexity analysis of lattice hard problems[J].JournalofCryptologicResearch, 2015, 2(1): 1-16.

[4]Micciancio D, Regev O. Lattice-based cryptography[M]//Post-quantumcryptography. Berlin: Springer, 2009: 147-191. DOI:10.1007/978-3-540-88702-7_5.

[5]Brakerski Z, Vaikuntanathan V. Efficient fully homomorphic encryption from (standard) LWE[J].SIAMJournalonComputing, 2014, 43(2): 831-871.

[6]Boneh D, Gentry C, Halevi S, et al. Private database queries using somewhat homomorphic encryption[M]//AppliedCryptographyandNetworkSecurity. Berlin: Springer, 2013: 102-118. DOI:10.1007/978-3-642-38980-1_7.

[7]Van Dijk M, Gentry C, Halevi S, et al. Fully homomorphic encryption over the integers[C]//Advancesincryptology—EUROCRYPT2010. Berlin: Springer, 2010: 24-43.

[8]Brakerski Z, Gentry C, Vaikuntanathan V. (Leveled) fully homomorphic encryption without bootstrapping[C]//Proceedingsofthe3rdInnovationsinTheoreticalComputerScienceConference. New York: ACM, 2012: 309-325.

[9]Brakerski Z. Fully homomorphic encryption without modulus switching from classical GapSVP[C]//AdvancesinCryptology—CRYPTO2012. Berlin: Springer, 2012: 868-886. DOI:10.1007/978-3-642-32009-5_50.

[10]Gentry C, Sahai A, Waters B.Homomorphic encryption from learning with errors: Conceptually-simpler,asymptotically-faster,attribute-based[C]//AdvancesinCryptology—CRYPTO2013. Berlin: Springer, 2013: 75-92. DOI:10.1007/978-3-642-40041-4_5.

[11]Micciancio D, Peikert C. Hardness of SIS and LWE with small parameters[C]//AdvancesinCryptology—CRYPTO2013. Berlin: Springer, 2013: 21-39. DOI:10.1007/978-3-642-40041-4-2.

[12]Brakerski Z, Langlois A, Peikert C, et al. Classical hardness of learning with errors[C]//Proceedingsofthe45thAnnualACMSymposiumonTheoryofComputing. New York: ACM, 2013: 575-584. DOI:10.1145/2488608.2488680.

[13]Aharonov D, Regev O. Lattice problems in NP ∩ coNP[J].JournaloftheACM, 2005, 52(5): 749-765. DOI:10.1145/1089023.1089025.

[14]Peikert C. Limits on the hardness of lattice problems in lpnorms[J].ComputationalComplexity, 2008, 17(2): 300-351. DOI:10.1007/s00037-008-0251-3.

[15]Regev O. The learning with errors problem[C]//ProceedingsofIEEEConferenceonComputationalComplexity. Berlin: Springer, 2010: 191-204.

Single-layer homographic cloud computing scheme based on LWE

Wang Xuyang Hu Aiqun Fang Hao

(School of Information Science and Engineering, Southeast University, Nanjing 210096, China)

To achieve safe remote operation, a single-layer homographic cloud computing scheme(sLHCC) based on learning with errors(LWE) is constructed by analyzing one-time-layer or single-layer homomorphic operation. First, according to whether the decryption accesses the random vector in LWE problem or not, two different single-layer homographic encryption schemes, named sLHE1 and sLHE2, are proposed, and the corresponding sLHCC schemes are put forward. The sLHCC schemes can realize one-time homomorphic addition and one-time homomorphic multiplication in cloud with maintaining the difficulty of LWE problem. According to the reasonable operation agreement and homomorphism results, users can execute the remote operation and control without leaking operation requirements (ciphertexts). The results show that compared with other homomorphic encryption schemes, the size of the public key of the sLHCC schemes reduces from matrix to vector, inducing the decrease of the ciphertext size and the demands of the cloud storage.

cloud computing; lattice-based cryptography; learning with errors(LWE); homographic; remote operation

10.3969/j.issn.1001-0505.2016.05.008

2016-01-21.作者簡介: 王旭陽(1985—),男,博士生;胡愛群(聯(lián)系人),男,博士,教授,博士生導(dǎo)師,aqhu@seu.edu.cn.

國家重點基礎(chǔ)研究發(fā)展計劃(973計劃)資助項目(2013CB338003).

TP309.7

A

1001-0505(2016)05-0945-05

引用本文: 王旭陽,胡愛群,方昊.基于LWE的單層同態(tài)云計算方案[J].東南大學(xué)學(xué)報(自然科學(xué)版),2016,46(5):945-949. DOI:10.3969/j.issn.1001-0505.2016.05.008.