全同态加密的相关算法研究

发布时间：2017-08-04 10:41

  本文关键词：全同态加密的相关算法研究

  更多相关文章： 全同态加密 委托计算 密钥生成 批处理 盖尔圆定理 中国剩余定理

【摘要】：伴随网络技术研究和信息社会的发展,云计算、委托计算等新兴计算模式得到了广泛应用。在这些计算模式中,个人或企业(客户)将自有数据交付给数据处理服务供应商,由供应商完成客户所要求的数据处理任务。这些计算模式极大提升了客户对信息数据的处理能力,有效降低客户在信息基础设施上的投资。但是云计算、委托计算的应用也面临一个很重要的挑战,即如何在信息数据处理中确保客户数据的隐私。作为数据隐私保护的重要手段,传统加密体制因为受限于加密后得到的密文,无法进一步处理,使得传统加密体制无法应用到云计算、委托计算中。如何能够在云计算、委托计算等新兴计算模式中有效保护数据安全,已经成为一个迫切的现实需求。全同态加密是指经同态加密所得到的密文,在不经解密的前提下,任何一方都可以对密文进行处理,且满足密文紧致性要求。加密方案的同态性是指,对密文执行的计算任务等同于对相应明文执行相同的计算任务。这一特性使得全同态加密在云计算、委托计算等诸多领域有着良好的应用前景,越来越多的学者投入到其理论和应用的研究中。全同态加密方案的构造方法不断更新,陆续出现了多个优化方案,算法效率有了一定的提升。但是现有全同态加密方案多存在密钥生成算法复杂度过高,密钥规模过大,批处理方案受限于比特明文空间等问题,上述问题的存在使得全同态加密在实际应用上面临严峻挑战。如何构造更加高效、具备实用性的全同态加密方案,成为当前全同态加密研究的重点。本论文从密钥算法构造、提升算法效率、明文空间扩展等角度对全同态加密进行了深入研究,提出了快速密钥生成算法、高效整数同态加密方案和基于整数明文空间的批处理同态加密方案,并和相关的工作进行了比较。本论文主要包括以下几个贡献：1.密钥生成算法的改进。就目前来看,Gentry类型全同态加密方案,特别是其密钥生成算法的复杂度过高。在该类型的全同态加密方案中,早先的密钥生成算法的思想是：随机生成理想格的一个格基作为私钥,并要求所生成的格基满足预先定义的代数要求,为得到私钥需要多次执行密钥生成算法。现有的全同态加密算法的密钥生成算法因其过高的计算复杂度,距离实际应用尚有一定距离。针对这一问题,提出了一种新的构造思路：在密钥生成之前,预先确定方案同态电路的乘法深度,利用同态电路乘法深度和私钥格基特征值的数值关系确定特征值的取值范围。随后依据特征值的取值范围,利用盖尔圆定理生成私钥格基,并将得到的格基作为私钥,求取该格基的HNF作为方案的公钥。密钥生成算法不是预先随机生成格基,而是依据预先确定的电路深度来求取密钥,取代了以往方案中生成私钥格多采用随机生成然后再去验证的思路,有效提升了密钥生成算法效率。2.提升算法效率。基于整数的全同态加密方案,该类型方案所存在的问题在于其过大的公钥规模、密文规模,计算复杂度过高。基于整数环这一简单的代数结构,本文提出了一个高效同态加密方案。首先构造一个私钥同态加密方案。随后提出了一个密文清洗程序,该程序以新鲜密文作为输入,输出对同一明文加密的密文,该密文称为清洗密文。清洗密文所含噪声相比较新鲜密文的噪声更小,可支持对该密文做更多的同态计算,增加了方案的同态计算能力。在不影响安全性和计算效率的前提下,将私钥同态加密方案转换成一个公钥同态加密方案。和之前的相关工作相比,所构造方案的公钥规模、密文规模均得到了较大降低,有效提升了算法效率。所提方案为一个部分同态加密方案,从实际应用角度看,部分同态加密方案算法复杂度低,可以满足绝大多数应用场景。3.扩展明文空间,降低密文膨胀率。密文膨胀率过大也是当前全同态加密方案存在的一个问题,这使得密文在通过网络传输时占用大的带宽,限制了全同态加密方案的实际部署。针对这一问题,提出了一个基于整数的部分同态加密方案,通过引入中国剩余定理(CRT),该方案可支持对多整数明文的并行计算。提出了一个新的计算困难问题RAGCD,方案的安全性可规约至该计算困难问题。所提方案能够支持对整数明文的同态计算,使得方案的密文膨胀率有了较大改进,实用性更高。
【关键词】：全同态加密 委托计算 密钥生成 批处理 盖尔圆定理 中国剩余定理
【学位授予单位】：山东大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：TN918.4
【目录】：

• 摘要10-13
• Abstract13-16
• 符号说明16-17
• 缩略语简表17-19
• 第一章 绪论19-35
• 1.1 全同态加密的研究背景19-20
• 1.1.1 云计算的信息安全19-20
• 1.1.2 全同态加密的研究意义20
• 1.2 研究历史和现状20-31
• 1.2.1 全同态加密方案的构造23-29
• 1.2.2 针对全同态加密方案的攻击算法研究29-30
• 1.2.3 全同态加密的应用研究30-31
• 1.3 本文的主要内容31-32
• 1.4 章节安排32-35
• 第二章 基础知识35-67
• 2.1 算法复杂度和计算困难问题35-40
• 2.1.1 算法复杂度35-36
• 2.1.2 计算困难问题36-40
• 2.2 可证安全性40-42
• 2.3 全同态加密方案的定义和可证安全性42-51
• 2.3.1 全同态加密方案的定义42-46
• 2.3.2 全同态加密方案的可证安全性46-51
• 2.4 SBF方法51-65
• 2.4.1 部分同态加密方案51-62
• 2.4.2 自举同态加密方案62-65
• 2.4.3 全同态加密方案65
• 2.5 本章小结65-67
• 第三章 Gentry类型全同态加密方案的密钥快速生成算法67-85
• 3.1 理想格68-69
• 3.2 Gentry类型全同态加密方案的密钥生成算法研究69-73
• 3.2.1 随机生成法69-71
• 3.2.2 预先确定法71-73
• 3.2.3 当前存在的问题73
• 3.3 盖尔圆定理73-74
• 3.3.1 数值关系73-74
• 3.3.2 盖尔圆的应用74
• 3.4 基于盖尔圆定理的密钥生成算法74-84
• 3.4.1 密钥生成算法的相关定义75-76
• 3.4.2 算法设计76-78
• 3.4.3 形式化分析78-81
• 3.4.4 仿真结果81-84
• 3.5 本章小结84-85
• 第四章 基于整数的单比特全同态加密算法研究85-103
• 4.1 基于整数的全同态加密方案概述85-88
• 4.1.1 DGHV方案分析85-86
• 4.1.2 CMNT方案分析86
• 4.1.3 Gu方案分析86
• 4.1.4 CNT12方案分析86-87
• 4.1.5 CLT14方案分析87
• 4.1.6 存在问题87-88
• 4.2 方案所用计算困难问题88-90
• 4.2.1 LDN问题的复杂度88
• 4.2.2 LDN和LWE88-90
• 4.3 高效的整数同态加密方案90-101
• 4.3.1 私钥同态加密方案91-94
• 4.3.2 密文清洗94-96
• 4.3.3 将私钥方案转化成公钥方案96-101
• 4.4 总结101-103
• 第五章 整数批处理全同态加密方案研究103-123
• 5.1 批处理研究综述103-105
• 5.1.1 CLT13方案104
• 5.1.2 KLYC13方案104-105
• 5.1.3 NK14方案105
• 5.1.4 存在的问题105
• 5.2 结合CRT的同态加密方案105-120
• 5.2.1 中国剩余定理106-107
• 5.2.2 方案描述107-109
• 5.2.3 方案分析109-117
• 5.2.4 本方案和其他方案的比较117-118
• 5.2.5 仿真结果118-120
• 5.3 参数选择120-121
• 5.3.1 暴力攻击120-121
• 5.3.2 针对GCD的攻击121
• 5.4 结语121-123
• 第六章 总结与展望123-127
• 6.1 工作总结123-124
• 6.2 展望124-127
• 参考文献127-137
• 致谢137-138
• 攻读学位期间发表的学术论文138-139
• 附件139-160

【参考文献】

中国期刊全文数据库 前1条

1 光焱;祝跃飞;顾纯祥;郑永辉;汤全有;;一种针对全同态加密体制的密钥恢复攻击[J];电子与信息学报;2013年12期

中国博士学位论文全文数据库 前1条

1 柴震川;门限密码方案安全性和应用研究[D];上海交通大学;2007年

，

本文编号：619137