利用RLWE构造基于身份的全同态加密体制

2017-01-10顾纯祥郑永辉康元基

电子学报 2016年12期

关键词：同态明文私钥

辛丹，顾纯祥，郑永辉，光焱，康元基

(1.信息工程大学，河南郑州 450002； 2.数学工程与先进计算国家重点实验室，江苏无锡 214125)

利用RLWE构造基于身份的全同态加密体制

辛丹1，顾纯祥1，郑永辉2，光焱1，康元基1

(1.信息工程大学，河南郑州 450002； 2.数学工程与先进计算国家重点实验室，江苏无锡 214125)

全同态加密为云计算中数据全生命周期隐私保护等难题的解决都提供了新的思路.公钥尺寸较大是现有全同态加密体制普遍存在的问题.本文将基于身份加密的思想和全同态加密体制相结合，利用环上容错学习问题(Ring Learning With Errors，RLWE)，其中将环的参数m扩展到任意正整数，提出了一种基于身份的全同态加密体制.体制以用户身份标识作为公钥，在计算效率和密钥管理方面都具有优势，安全性在随机喻示模型下可规约为判定性RLWE问题难解性假设.

全同态加密；基于身份加密；环上容错学习问题

1 引言

全同态加密(fully homomorphic encryption)允许用户在不解密的情况下，对密文进行任意次的运算，从而得到相对应明文进行运算后加密的结果.这种新型加密技术，为很多难题的解决都提供了新的思路，例如云计算的隐私保护问题、密文检索等.2009年，Craig Centry[1]基于“理想格”(ideal lattice)成功构造出第一个真正意义上的全同态加密体制，这一成果使该领域研究取得突破性进展.

参考Gentry的设计模式和理念，学术界基于不同的代数结构和数学难题提出了一系列的同态加密算法[2～4]，但现有体制公钥尺寸通常比较大，密钥的有效管理一直是体制应用面临的一个难题.基于身份加密[5](identity-based encryption)利用用户的唯一身份标识(如E-mail地址等)作为公钥，用户私钥由可信第三方生成，具有不依赖公钥证书进行密钥管理的优势.2010年美密会上，Naccache[6]将基于身份的全同态加密体制设计列为待解决的重要问题之一.

Gentry等人[7]基于格上容错学习问题[8](Learning With Errors，LWE)设计了一种基于身份的同态加密体制，仅支持有限次加法和一次乘法的同态运算.文献[9]提出基于对偶Regev 体制构造全同态加密体制，并借助对偶Regev体制的加解密密钥的特点实现基于身份加密，在计算效率上有所提升，但运算公钥(evaluation key)尺寸过大.2013年，Gentry 等人[10]提出了一种利用近似特征向量构造基于身份的全同态加密方案，并使满足一定条件的基于身份加密体制(如文献[11])增加全同态运算能力，但该方案密文扩张严重.光焱等人[12]利用前像可采样陷门单向函数[11]提取私钥的方式和重线性化方法[13]，设计了一个基于身份的全同态加密体制，简称GZG14体制.但该体制不能进行多比特加密.

Brakerski和Vaikuntanathan[14]提出了一个基于环上容错学习问题的全同态加密体制.以该体制为首的一些体制[15,16]在环的参数m的选择上更偏爱选用m=2k(n=m/2仍然是2的方幂)，此时多项式Φm(X)=Xn+1分布稀疏，模多项式运算可以高效得通过快速傅里叶变换技术[17](Fast Fourier Transform，FFT)进行.但这一特点也导致了在相同安全级别下，由于m只能取2的方幂，体制公钥尺寸以及计算时间大都比实际需要高得多，并且这种多项式也影响了单指令多数据(Single Instruction Multiple Data,SIMD)技术[18]的运用.但是当环的参数m取任意正整数时，分圆多项式是不规则的，分布较密集，且多项式系数较大，并且多项式模运算存在很大的扩张系数[19](expansion factor)，从而影响体制加解密效率.Lyubashevsky等人[20]提出的标准嵌入(canonical embedding)将分圆域上的元素映射成复数域上的向量，则域上元素的加法和乘法运算便转换成向量的逐比特计算.同时，通过张量分解技术[21](tensorial decomposition)将分圆域分解为素数子域的张量积，多项式模运算可以转换到较简单的素数子域中进行.

本文根据Gentry等人[11]提出的前像可采样陷门单向函数，设计了环上基于身份的私钥提取算法，对每一个身份标识，生成对应的用户私钥，通过“密钥转换”技术使基于身份的半全同态加密体制实现多级(leveled)同态运算.和一般全同态加密体制相比，无须使用公钥证书进行身份认证，能够有效克服公钥尺寸对于体制应用效率的影响.与现有基于身份的全同态加密体制相比，本文体制可以进行多比特加密，支持SIMD技术.最后，证明体制在随机喻示模型，判定性RLWE问题假设的前提下选择明文安全的(Chosen Plaintext Attack，CPA).

2 基础知识

2.1 符号说明及相关基础定义

表1 代数结构的描述

2.2 RLWE问题

Lyubashevsky等人[21]给出了环R上理想格最坏情况下最短向量近似问题(worst-case approximate Shortest Vector Problem，SVP)到计算性环上容错学习问题的量子规约，接着给出了计算性环上容错学习问题到判定性环上容错学习问题(Decision Ring Learning With Errors，DRLWE)的一般性规约.

定义2(RLWE分布)

定义3(RLWE问题)

定义4(DRLWE问题)

定理5(DRLWE问题难解性假设)

χ=⎣p·ψ⎤ω+pR∨分布是通过连续高斯分布p·ψ上的点离散到pR∨的陪基上生成的.由于分解基的最大特征值至多为1，在离散化过程中对高斯分布参数影响较小，所以当噪声取自R∨时，一般选择分解基进行高斯采样.

2.3 前像可采样陷门单向函数

文献[12]给出了一般格上的前像可采样陷门单向函数，将离散正态分布映射到近似均匀分布上，且满足在拥有陷门的情况下，能够从近似均匀分布上将原始离散正态分布恢复出来.首先给出陷门的生成方式.

(1)

在命题6的基础上定义函数fA：

定义7(前像可采样陷门单向函数)

3 基于身份的全同态加密体制模型

本小节根据光焱等人提出的基于身份的全同态加密体制模型[13]，该模型结合了基于身份加密和全同态加密两种特点.在格上构造一般全同态加密体制时，密钥生成的顺序是首先随机选择私钥，然后根据格上困难(例如LWE问题)计算生成用户公钥.而在基于身份加密体制中，公私钥对的产生顺序恰好相反，首先根据身份标识id得到公钥pkid，随后以id或pkid作为私钥提取算法的输入，计算出相应的身份私钥.例如，文献[12]提出了一种格上基于身份的公钥加密体制，通过引入哈希函数和前像可采样陷门单向函数，分别实现从身份信息到公钥的转换以及提取私钥的功能.

定义9(基于身份的全同态加密体制模型)

基于身份的全同态加密体制IBFHE由5个算法组成，分别是初始化、私钥提取、加密、解密和密文运算，即IBFHE={Setup，Extract，Enc，Dec，Eval}.

初始化算法Setup：输入安全参数1λ，算法输出加密体制的一对公开参数param、主私钥msk.

私钥提取算法Extract：输入公开参数param、主私钥msk和身份标识id，为每一个身份标识id输出一个身份私钥skid.

加密算法Enc：输入公开参数param、身份标识id和明文消息μ，输出与身份标识id相关的密文c.

解密算法Dec：输入与身份标识id相关的密文c和id对应的身份私钥skid，输出明文消息μ.

密文运算算法Eval：输入运算f:{0,1}t→{0,1}和属于同一身份标识id加密的一组密文c1,c2,…,ct，输出新的密文c，且满足Decskid(c)=f(Decskid(c1),…,Decskid(ct)).

定义10(基于身份的全同态加密体制的IND-CPA安全性)

由于密文同态运算属性，因此任何全同态加密体制都不可能抵抗适应性选择密文攻击(CCA2)，IBFHE体制采用传统的选择明文攻击下的不可区分性(IND-CPA).IND-CPA攻击游戏如下：

初始化：挑战者C调用IBFHE.Setup算法，输出体制的公开参数param和主私钥，将param交给攻击者A.

阶段1：A任意选择身份标识idi∈{0,1}*访问私钥提取喻示，得到对应的私钥skidi，并将idi加入到身份列表P.

阶段2：攻击者A自由选择身份id′∈{0,1}*，要求id′≠id*，获得相应的私钥skid′.

猜测过程：A猜测目标密文c*所对应的明文，输出猜测结果b′，若b′=b，则攻击者在游戏中获胜.

4 体制构造

4.1 基础同态加密体制

解密算法IBSHE.Dec(c,e)：输入密文c、私钥e，计算x=(ρ+ve)modp，输出明文消息μ=t·xmodpR.

有两个明文消息μ,μ′∈Rp，噪声x←⎣p·ψ⎤t-1μ+pR∨，x′←⎣p·ψ⎤t-1μ′+pR∨，加密结果分别为c=(ρ,v)，c′=(ρ′,v′).对应变量Y的多项式分别为c(Y)=ρ+vY，c′(Y)=ρ′+v′Y.

同态加法IBSHE.Add：

c(Y)+c′(Y)=ρ+vY+ρ′+v′Y=ρ+ρ′+(v+v′)Y

(2)

将私钥e代入：

Dece[c(Y)+c′(Y)] =ρ+ve+ρ′+v′e

=x+x′+pxe+px′e

(3)

同态乘法IBSHE.Mult：

c(Y)·c′(Y) =(ρ+vY)×(ρ′+v′Y)

=ρρ′+(ρv′+ρ′v)Y+vYv′Y

(4)

将私钥e代入：

Dece[c(Y)·c′(Y)] =(ru+x-rpTAe+pxe)

×(r′u+x′-r′pTAe+px′e)

=x·x′+2p2xex′e+xpx′e+x′pxe

(5)

4.2 密钥转换技术

通过一次同态乘法，密文向量维数从l+1增加到l2+l+1，可以预见，随着同态乘法的继续进行，密文元素乘指数增长，下面介绍密钥转换技术可以使密文的元素个数保持不变.

(3)对于i∈[bj]，ρ=(ρ(i))i∈[bj]，V=(v1,…,vbj)，计算IBSHE.Enc(A,id,0)=(ρ(i),vi)，并满足c(s′) modp=f(i)←⎣p·ψ⎤pR∨，f=(f(i))i∈[bj]，且〈x,f〉足够小；

(6)

4.3 基于身份的全同态加密体制

初始化算法IBFHE.Setup(1λ,1L)：输入安全参数λ，以及电路层数L.调用IBFHE.Setup(1λ)算法输出公开参数param，主私钥msk.

加密算法IBFHE.Enc(A,id,μ)：利用R-IBSHE.Enc(A,id,μ)，输出得到初始密文c=(ρ,v),使用额外的信息来标识密文所处的电路层，例如ci=(ρi,vi,i)，其中i表示密文所处的层级.

解密算法IBFHE.Dec(ci,ei)：对于密文ci=(ρi,vi,i)，私钥为ei由密文所在的层级决定，计算xi=(ρi+viei)modp，恢复明文消息μ=ti·ximodpR.

密文运算算法IBFHE.Eval(f,c1,…,ct,evkid)：任意f运算都可以表示为同态乘法与任意次的加法运算的组合形式.同态加法直接调用IBSHE.Add算法.在进行同态乘法时，必须先获得此层级的运算密钥δi→i+1，再调用IBSHE.Mult算法进行运算.

5 体制分析

5.1 正确性与安全性分析

(7)

则解密正确，c(ei)模p得到噪声xi，利用μ=ti·ximodpR恢复出明文.

定理11 设m=λ，n=φ(m)，q=poly(n)≥2，l≥5nlogq，在随机喻示模型，DRLWEn,l,q,χ问题假设的前提下IBFHE体制是IND-CPA安全的.

证明使用基于游戏的证明方法，用AdvGame[A]来定义攻击者A在下列游戏中的优势.

AdvCPA[A]=

(8)

|AdvGame1[A]-AdvCPA[A]|=0

(9)

|AdvGame2[A]-AdvGame1[A]|

(10)

|AdvGame3[A]-AdvGame2[A]|=DRLWEn,l,q,χAdv[A]

(11)

(12)

在Game 4中，挑战者C公钥和密文都是均匀随机选取的，与明文空间无关，所以在Game 4中A的优势为零，即AdvGame4[A]=0.

在上述游戏中，C在挑战阶段之外的其他阶段中的行为均与Game 0相同.因此，在DRLWEn,l,q,χ假设成立的情况下，AdvCPA[A]可忽略，IBFHE体制是IND-CPA安全的.

5.2 效率分析

本文提出的IBFHE体制将基于身份的思想引入全同态加密体制中，相比之下，Brakerski[14]提出的方案在实际应用过程中，必须借助公钥证书进行合法性认证，还包括公钥证书分发、管理等开销，且参数m的选择必须是2的方幂.与现有的基于身份的全同态加密体制GZG14相比，IBFHE体制支持Rp上的多比特加密.

选取GZG14体制作为参照对象，体制在实现L级同态运算的情况下，通过以下三个方面综合比较IBFHE体制的优势.

计算复杂度方面：GZG14体制加密时主要进行5n2logq+n乘法和5n2logq+n次加法，解密时进行5nlogq乘法和5nlogq次加法；IBFHE体制主要进行5n2logq+5n3logqlogn乘法和5n2logq+5nlogq次加法，解密时进行5n2logqlogn乘法和nlogq次加法.如表2所示.

表2 效率分析对比

综合以上从三个方面对IBFHE体制进行分析，同GZG14体制相比，虽然体制的计算复杂度稍高，但是体制的优势主要集中体现加密的明文空间上，实现了多比特加密.

6 结束语

全同态加密为解决云计算数据隐私保护问题、密文检索等难题提供了一个新的思路.本文在任意分圆环的代数特性上，利用RLWE构造了一种基于身份的全同态加密体制，将身份标识作为用户公钥，从而使身份认证和管理不依靠公钥证书，并且具备全同态运算的能力.与利用LWE构造的同类体制相比，支持多比特加密以及SIMD技术.最后，给出了体制在随机喻示模型下的安全性证明，将安全性规约到判定性RLWE问题的难解性上.

[1]Gentry C.Fully homomorphic encryption using ideal lattices[A].Proceedings of 41rd ACM Symposium on Theory of Computing(STOC2009)[C].Bethesda,Maryland,USA:Springer Berlin Heidelberg,2009.169-178.

[2]Coron J S,Naccache D,Tibouchi M.Public key compression and modulus switching for fully homomorphic encryption over the integers[A].Proceedings of the 31st Annual Eurocrypt Conference[C].Cambridge,United Kingdom:Springer Berlin Heidelberg,2012.446-464.

[3]Brakerski Z，Vaikuntanathan V.Efficient fully homomorphic encryption from (standard) LWE[J].SIAM Journal on Computing,2014,43(2):831-871.

[4]López-Alt A,Tromer E,Vaikuntanathan V.On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption[A].Proceedings of the 44th Annual ACM Symposium on Theory of Computing[C].New York,USA:ACM,2012.1219-1234.

[5]Shamir A.Identity-based cryptosystems and signature schemes[A].Advances in Cryptology[C].Santa Barbara,USA:Springer Berlin Heidelberg,1985.47-53.

[6]Naccache D.Is theoretical cryptography any good in practice? Invited talk at Crypto/CHES 2010[EB/OL].http://www.iacr.org/workshops/ches/ches2010,2010-08-17.

[7]Gentry C,Halevi S,Vaikuntanathan V.A simple BGN-type cryptosystem from LWE[A].Advances in Cryptology-EUROCRYPT 2010[C].French Riviera:Springer Berlin Heidelberg,2010.506-522.

[8]Regev O.On lattices,learning with errors,random linear codes,and cryptography[A].Proceeding of 37th Annual ACM Symposium on the Theory of Computing[C].Baltimore,MD,USA:ACM,2005.84-93.

[9]Brakerski Z.Fully homomorphic encryption without modulus switch-ing from classical GapSVP[A].Advances in Cryptology-CRYPTO 2012[C].Santa Barbara,CA,USA:Springer Berlin Heidelberg，2012.868-886.

[10]Gentry C,Sahai A,Waters B.Homomorphic encryption from learning with errors:Conceptually-simpler,asymptotically-faster,attribute-based[A].Proceedings of the 33th Annual International Cryptology Conference[C].Santa Barbara,USA:Springer Berlin Heidelberg,2013.75-92.

[11]Gentry C,Peikert C,Vaikuntanathan V.Trapdoors for hard lattices and new cryptographic constructions[A].Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing[C].Victoria,British Columbia,Canada:ACM,2008.197-206.

[12]光焱,祝跃飞,顾纯祥，等.利用容错学习问题构造基于身份的全同态加密体制[J].通信学报,2014,35(2):111-117. Guang Yan,Zhu Yue-fei,Gu Chun-xiang，et al.Identity-based fully homomorphic encryption from LWE problem[J].Journal on Communications,2014,35(2):111-117.

[13]Zvika Brakerski,Vinod Vaikuntanathan.Efficient fully homomorphic encryption from (standard) LWE[A].Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science[C].Palm Springs,California,USA:IEEE,2011.97-106.

[14]Brakerski Z,Vaikuntanathan V.Fully homomorphic encryption from ring-LWE and Security for key dependent messages[A].Advances in Cryptology-CRYPTO 2011[C].Santa Barbara,CA,USA:Springer Berlin Heidelberg，2011.505-524.

[15]Lyubashevsky V,Peikert C,Regev O.On Ideal Lattices and Learning with Errors over Rings[A].Advances in Cryptology-EUROCRYPT 2010[C].French Riviera:Springer Berlin Heidelberg,2010.1-23.

[16]Peikert C,Rosen A.Lattices that admit logarithmic worst-case to average-case connection factors[A].Proceedings of the 39th Annual ACM Symposium on Theory of Computing[C].San Diego,CA:ACM,2007.478-487.

[17]Lyubashevsky V,Micciancio D,Peikert C,et al.SWIFFT:A modest proposal for FFT hashing[A].Fast Software Encryption,15th International Workshop,FSE 2008[C].Lausanne,Switzerland:Springer Berlin Heidelberg,2008.54-72.

[18]Smart N P,Vercauteren F.Fully homomorphic SIMD operations[J].Designs,Codes and Cryptography ,2014,71(1):57-81.

[19]Lyubashevsky V,Micciancio D.Generalized compact knapsacks are collision resistant[A].33rd International Colloquium,ICALP 2006,Automata,Languages and Programming[C].Venice,Italy：Springer,2006.144-155.

[20]Lyubashevsky V,Peikert C,Regev O.On ideal lattices and learning with errors over rings[J].Journal of the ACM (JACM),2013,60(6):43.

[21]Lyubashevsky V,Peikert C,Regev O.A toolkit for ring-LWE cryptography[A].EUROCRYPT,2013[C].Athens,Greece:Springer,2013.35-54.

辛丹女，1991年8月出生于陕西西安.现为信息工程大学硕士研究生.主要研究方向为全同态加密,在国内外期刊发表学术论文2篇.

E-mail：xindan625@126.com

顾纯祥(通信作者) 男，1976年出生于安徽霍山.现为信息工程大学副教授，研究生导师，主要研究方向为网络与信息安全,在国内外重要期刊和会议上发表相关学术论文30余篇，其中被SCI收录20余篇.

E-mail：gcxiang5209@alinyun.com

郑永辉男，1976年出生于江西乐平.现为信息工程大学讲师，主要研究方向为密码学、网络与信息安全,在国内外重要期刊和会议上发表相关学术论文10余篇.

E-mail：yonghui.zh@163.com

光焱男，1983年出生于河南新乡.现为信息工程大学讲师，主要研究方向为密码学、网络与信息安全,在国内外重要期刊和会议上发表相关学术论文10余篇.

E-mail：gyinarmy@126.com

康元基男，1992年出生于内蒙古牙克石.现为信息工程大学研究生，主要研究方向为密码学、网络与信息安全.

Identity-Based Fully Homomorphic Encryption from Ring Learning with Errors Problem

XIN Dan1，GU Chun-xiang1，ZHENG Yong-hui2，GUANG Yan1，KANG Yuan-ji1

(1.InformationEngineeringUniversity,Zhengzhou,Henan450002,China; 2.StateKeyLaboratoryofMathematicalEngineeringandAdvancedComputing,Wuxi,Jiangsu214125,China)

Fully homomorphic encryption provides a new idea on the solution of many problems,such as the whole life cycle of data privacy protection on cloud computing.Currently,the existing fully homomorphic encryption schemes share a common flaw of large size public keys.We construct an identity-based fully homomorphic encryption which compromises the merits of both kinds of encryption from ring learning with errors to work in arbitrary cyclotomic rings.To make user’s identity as the unique public key,our scheme has advantage in computational efficiency and key management.The security of our scheme strictly reduces to hardness of decision ring learning with problem solving in the random oracle model.

fully homomorphic encryption;identity-based;ring learning with errors

2015-04-09;

2015-06-29;责任编辑：梅志强

河南省科技创新杰出青年基金(No.134100510002);河南省基础与前沿技术研究(No.142300410002);数学工程与先进计算国家重点实验室开放基金资助

TN918.1

0372-2112 (2016)12-2887-07

��学报URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.12.011