基于LWE的全同态密码及其应用研究

发布时间：2020-04-22 11:55

【摘要】：全同态加密(Fully Homomorphic Encryption,FHE)支持在不知道密钥的前提下对密文进行任意的盲操作,且运算结果的解密值恰好等于对应的明文运算结果,真正从根本上解决了将数据及操作委托给第三方时的保密问题,使人们既可以充分利用云计算强大的计算/存储能力为用户提供海量密文处理服务,又可以自己管理保证数据安全的密钥,实现了数据在不可信环境下的安全计算(服务)。同时,FHE方案大多是以格上困难问题作为基础,而格密码是抗量子密码的重要组成部分,从而FHE也是后量子密码的组成之一。因此,FHE密码逐渐成为欧美国家在密码领域争夺的“战略制高点”,能够在大数据与云计算等新型服务模式下发挥重要作用。近年来FHE的研究不断取得进步,尤其是基于错误学习问题(Learing with Errors,LWE)的FHE方案,由于其简单、安全且便于高效实现,成为FHE方案设计的主流。但是其方案效率距离实用仍有很大差距,主要原因在于同态密文运算时,尤其是同态乘法运算,噪声增长过快。为了保证密文在运算足够次数后仍能正确解密,不得不以牺牲方案参数尺寸,或引入用来约减噪声的大量额外计算为代价。因此,降低基于LWE的FHE方案密文运算的噪声膨胀速度,或设计高效的噪声约减技术具有重要的意义,这也是本文的主要研究工作。此外,为了进一步促进FHE走向实用,解决后量子时代云计算环境下大数据的隐私保护和资源共享的矛盾,针对现有同态隐私信息检索(Private Information Retrieval,PIR)协议模型构造单一的问题,本文又对同态PIR协议模型进行了研究。主要成果和创新点如下:1.提出了一种低噪声膨胀的多元基重线性化技术。重线性化技术是构建基于LWE的FHE方案的关键技术,其解决了密文向量的维数膨胀问题,但是同时也带来了较大的噪声扩张代价,影响FHE方案的效率。本文首先给出了重线性化技术噪声约减效果与选择的分解基之间的具体关系,在此基础上,利用时空转换技术,提出了一种低噪声膨胀的多元基重线性化技术,并给出了相应的衍生技术—多元基密钥转换技术。并且选择的分解基越大,噪声约减效果越好。2.设计了一个参数规模较小的LWE上密文为向量的层次型FHE(LFHE)方案。基于低噪声膨胀的多元基重线性化技术,结合双重LWE参数规模约减技术,构造了一个参数规模较小的LWE上密文为向量的LFHE方案,同时对该方案同态运算的噪声增长情况进行了详细分析,并给出了具体的安全参数。通过分析对比,该方案是目前LWE上参数规模最小的LFHE方案。3.提出了一个新的噪声约减方法:明文倍增法。使用该方法可显著降低LWE上FHE方案的密文乘法噪声膨胀速度,并且该方法具有通用性,不需要使用模数转换等噪声约减技术,即可构造出更加有效的基于LWE的LFHE方案。4.给出了几类密文为矩阵的LWE上低同态乘法噪声膨胀的LFHE方案。基于明文倍增法,结合双重LWE参数规模约减技术与亚高斯随机变量分布,分别在标准LWE与环LWE上设计了一个密文为矩阵的低同态乘法噪声膨胀的LFHE方案,将单次密文乘法噪声膨胀因子由poly(n)降到(48)(1),即密文同态乘法与加法运算噪声膨胀速度几乎相同。此外,基于明文倍增法与时空转换技术,又提出了一个支持多比特明文矩阵加密的低同态乘法噪声膨胀的GSW13类扩展SIMD加密方案,可以有效地降低GSW13类方案的明密文规模膨胀率,提高GSW13类方案的实用性。5.优化了Halevi与Shoup在2015年欧密会上提出的快速自举技术的参数。Halevi与Shoup构造的快速自举技术对密文的取值范围有所限制,同时要求密文模数必须为2的方幂。本文对Halevi与Shoup快速自举技术的上述两个重要参数进行了研究。通过引入“承载度”的概念,利用回溯分析拓展了Halevi与Shoup快速自举技术支持的密文取值范围,同时又将其密文模数由必须为2的方幂推广至更一般的情形。此外,我们还对Halevi与Shoup自举算法的效率进行了优化。6.设计了一种基于混合FHE的快速PIR协议模型。现有的基于FHE的PIR协议模型通常需要用到大量的数据索引加密与连乘运算。加密与连乘的次数与检索数据库的规模呈正相关。在不影响协议安全的前提下,巧妙地利用赋值法替代了大量的同态加密运算,同时先用乘法单同态加密(MHE)方案对检索中的大规模连乘运算进行处理,接着利用高效的部分FHE(Somewhat FHE,SWHE)方案,处理剩下的简单运算。基于这种混合FHE的检索模式,可以大大提升同态PIR协议模型的效率,尤其是对大规模隐私数据库。7.设计了一种基于FHE的高比特逐位递归查询的快速PIR协议模型。利用高比特逐位递归查询的方法,基于FHE方案,设计了一种高效的小规模数据库PIR协议模型。并且,在牺牲适量通信代价的情况下,该模型的检索效率会得到进一步的提升,为基于FHE的PIR协议设计提供了一种新的思路与方法。
【图文】：

高度互联、全面开放等优点，但是也带来了隐私泄露等严峻的安全问题[2-4]，如图1.1所示。数据加密存储是一种有效的数据信息隐私保护手段，但是经典的对称或非对称密码体制不支持对密文进行复杂运算，用户在调用数据并对其进行处理时，需要先下载所有数据并解密，这势必给用户端带来较大的通信和计算开销，无法体现出“云”的优点[5]。图1.1 云计算与隐私泄露全同态加密（Fully Homomorphic Encryption, FHE）的思想源于“隐私同态”，首次由Rivest等人提出[6]。FHE指的是操作者可在不解密的情况下对密态数据进行各种运算，其结果在解密后与对明文进行相应运算的结果是一样的，如图1.2所示。FHE不仅能够对密文进行任意的盲操作，而且还允许对计算/操作行为本身进行加密。

战略支援部队信息工程大学博士学位论文第 2 页图1.2 全同态加密框架FHE真正从根本上解决了将数据及操作委托给第三方时的保密问题，使人们既可以充分利用云计算强大的计算/存储能力为用户提供海量密文处理服务，又可以自己管理保证数据安全的密钥，实现了数据在不可信环境下安全计算（服务）[7,8]。同时，FHE方案大多以格困难问题作为基础，而格密码是抗量子密码的重要组成部分，从而FHE也是后量子密码（Post-Quantum Cryptography, PQC）[9]的组成之一。因此，FHE密码逐渐成为欧美国家在密码领域争夺的“战略制高点”，能够在大数据与云计算等新型服务模式下发挥重要作用[10-12]。在与大数据、云计算相关的众多服务中
【学位授予单位】：战略支援部队信息工程大学
【学位级别】：博士
【学位授予年份】：2018
【分类号】：TN918

【相似文献】

相关期刊论文 前10条

1 黄仕杰;洪璇;;基于同态实现多候选人的电子投票方案[J];计算机应用与软件;2017年03期

2 高升;;域同态的扩张的个数[J];大学数学;2015年04期

3 吴琦;;浅谈同态加密技术及其在物联网中的应用[J];通讯世界;2015年21期

4 刘艮;蒋天发;;同态加密技术及其在物联网中的应用研究[J];信息网络安全;2011年05期

5 丁龙云;顾沛;;群上亚同态的一个结构性定理及其应用[J];南开大学学报(自然科学版);2009年03期

6 敖忠平;蔡述平;宋海燕;;半模的Z-同态与正合列[J];新疆师范大学学报(自然科学版);2007年04期

7 顾沛;丁龙云;;群上亚同态的一个必要条件及由此引出的一些性质[J];南开大学学报(自然科学版);2006年02期

8 王树忠;几个数域上的重要同态[J];渤海大学学报(自然科学版);2005年02期

9 胡月宏,杨晓梅,刘亚军;李群上的亚同态[J];新疆师范大学学报(自然科学版);2005年03期

10 刘宏伟;对群上亚同态的几点注记[J];华中师范大学学报(自然科学版);2004年04期

相关会议论文 前8条

1 张诚一;;模糊集的同构与同态[A];第二届不确定系统年会论文集[C];2004年

2 朱建栋;徐秋亮;唐朝霞;;同态密钥更新[A];2007北京地区高校研究生学术交流会通信与信息技术会议论文集（上册）[C];2008年

3 毕恺;夏英华;;Fuzzy群的同态映射[A];模糊集理论与应用——98年中国模糊数学与模糊系统委员会第九届年会论文选集[C];1998年

4 吴旭东;;云计算数据安全研究[A];第26次全国计算机安全学术交流会论文集[C];2011年

5 姚谛;胡慧俐;朱培栋;;基于加同态加密机制的互联网路由异常检测[A];全国网络与信息安全技术研讨会论文集（上册）[C];2007年

6 王晓玲;;环的Fuzzy弱理想与Fuzzy近理想[A];模糊集理论与应用——98年中国模糊数学与模糊系统委员会第九届年会论文选集[C];1998年

7 韦立宏;赵立军;;L-Fuzzy子环上的L-Fuzzy理想的L-Fuzzy同态[A];中国系统工程学会模糊数学与模糊系统委员会第十一届年会论文选集[C];2002年

8 李彦平;徐心和;;代数同态理论在离散事件动态系统分析中的应用[A];1992年中国控制与决策学术年会论文集[C];1992年

相关博士学位论文 前10条

1 宋巍涛;基于LWE的全同态密码及其应用研究[D];战略支援部队信息工程大学;2018年

2 蒋林智;（全）同态加密及其在云计算中的应用研究[D];电子科技大学;2018年

3 陈智罡;基于格的全同态加密研究与设计[D];南京航空航天大学;2015年

4 陈良;基于同态加密的移动代码安全技术研究[D];华南理工大学;2009年

5 冯超;全同态加密的相关算法研究[D];山东大学;2015年

6 陈虎;几类同态加密方案的研究[D];西安电子科技大学;2016年

7 郝彦彬;基于属性集信息粒的信息系统结构及同态研究[D];西北工业大学;2016年

8 尹春勇;基于密态的安全数据库应用研究[D];贵州大学;2008年

9 巩林明;新型公钥加密方案及应用研究[D];陕西师范大学;2016年

10 周强;无线传感器网络安全数据融合技术研究[D];南京邮电大学;2014年

相关硕士学位论文 前10条

1 曹静坤;基于证书的线性同态签名方案及其在云存储中的应用[D];南京师范大学;2018年

2 杜嵘;基于无证书线性同态签名的云存储完整性验证系统的设计与实现[D];南京师范大学;2018年

3 王巨卿;基于加法同态和差值直方图的加密域可逆信息隐藏算法[D];天津师范大学;2018年

4 梁家豪;基于同态加密或分段Logistic映射的安全生物特征认证技术[D];杭州电子科技大学;2018年

5 李焕云;关于S-系的覆盖及S-系的分解系[D];西北师范大学;2017年

6 王永恒;基于全同态加密技术的电子投票系统的设计与实现[D];中国科学院大学(中国科学院重庆绿色智能技术研究院);2017年

7 王晓萌;G×K_n的量子色素及量子可乘图[D];兰州大学;2018年

8 魏文燕;Paillier同态密码在隐私保护中的应用研究[D];河南理工大学;2017年

9 吴卓伟;云环境下整数上的全同态加密算法研究[D];广西大学;2018年

10 杨乐;基于同态公钥加密系统的数字水印算法研究[D];暨南大学;2018年

，

本文编号：2636487