论文部分内容阅读
全同态加密能够对密文进行任意计算,这一特殊性质使得全同态加密具有重要的理论意义与实践应用价值。自1978年全同态加密提出后一直是密码学界的一个开放难题,直到2009年Gentry设计出第一个全同态加密方案。尽管近年来全同态加密的研究不断取得进步,但是依然面临以下一些问题:第一,全同态加密的候选方案很少;第二,全同态加密的效率不高,离实践应用有距离;第三,全同态加密使用的安全性。格密码学可以抵抗量子计算,成为当前密码学界的研究热点。此外LWE问题和环LWE问题上的密码方案计算简单,而且其安全性可以归约到格上困难问题,使得LWE问题和环LWE问题上的密码学成为格密码学研究的一个重要主题。以下简称LWE问题和环LWE问题为(环)LWE问题。本博士论文开展(环)LWE问题上的全同态加密研究与设计。一方面从理论上,提出一些更加有效的全同态加密方案以及优化方法;另一方面从实践角度,提出分析计算全同态加密具体安全参数的方法,并且给出每个方案的具体安全参数。保证了研究的系统性与全面性。所做工作如下:1.开展全同态加密方案具体安全参数分析方法的研究。主要研究方法与结果如下:(1)提出一个(环)LWE问题上全同态加密方案具体安全参数的方法。该方法基于区分攻击,引入了敌手优势,能够真实的反映应用场景的安全需求。根据不同的安全等级以及敌手优势,使用区分攻击确定最小维数n与模q之间的关系。再根据全同态加密方案的噪音增长与电路深度L以及模q之间的关系,计算出电路深度L、模q与维数n的具体尺寸,从而获得公钥、私钥和密文的具体尺寸。并且使用该方法对目前(环)LWE问题上全同态加密方案进行了具体安全参数分析,并且进行了详细比较。这也是首次给出这些方案的具体安全参数,为全同态加密的实践奠定了基础。(2)提出一个噪音依赖分析的全同态加密方案分类的方法。通过对目前(环)LWE问题上全同态加密方案的噪音增长进行详细分析,给出紧致的噪音界,从而获得噪音增长的主要依赖项。根据该主要依赖项对目前全同态加密方案进行了分类。分类的目的是为进一步优化方案提供指南。2.开展设计全同态加密方案的研究。主要研究如何去除全同态加密设计过程中的密钥交换(key switching)过程,设计更加有效的全同态加密方案。主要研究方法与结果如下:(1)提出一个新的设计方法:提升维数法。使用该方法可以去除密钥交换过程,从而提高全同态加密方案的效率。该方法分为两个步骤。第一步,通过添加一些密文辅助项,将密文从向量提升到矩阵,得到一个密文是矩阵并且具有同态性的加密方案。但是由于噪音过大导致该方案无法进行密文计算。第二步,为了使用位扩展技术约减密文中的噪音,再次使用提升维数法添加密文辅助项,得到一个无需密钥交换的全同态加密方案。提升维数法比Gentry等人在2013年美密会上提出的特征值和特征向量的方法(GSW13方案)更加有效。此外,提升维数法是一个通用框架,可以设计(环)LWE问题上所有无需密钥交换的全同态加密方案。因此提升维数法具有重要的理论意义。(2)基于提升维数法设计一个NTRU型无需密钥交换的全同态加密方案。由于NTRU方案中的密文是一个多项式,只需使用提升维数法的第二步,即将密文从多项式提升到向量,就能获得一个无需密钥交换的全同态加密方案。此外,计算分析了该方案的具体安全参数,该方案是目前(环)LWE上全同态加密方案中参数尺寸最小的全同态加密方案。(3)基于提升维数法设计一个环LWE上无需密钥交换的全同态加密方案。使用上述提升维数法将密文从向量提升到矩阵,即可获得一个环LWE上无需密钥交换的全同态加密方案。该方案的安全性归约到理想格上的困难问题。此外,计算分析了该方案的具体安全参数,该方案的参数尺寸优于环LWE上同类方案GSW13方案以及Bra12方案的参数尺寸。(4)基于提升维数法设计一个LWE上无需密钥交换的全同态加密方案。设计方法与环上方案相同。但是该方案的安全性归约到格上的困难问题。该方案的参数尺寸优于LWE上同类方案GSW13方案以及Bra12方案的参数尺寸。3.开展基于Binary-LWE问题设计全同态加密方案以及优化全同态加密方案的研究。研究成果如下:(1)基于Binary-LWE问题设计一个短公钥的全同态加密方案。根据Linder和Peikert在2010年提出的LWE上的公钥加密方案,基于Binary-LWE问题约减密钥长度,从而约减密文计算的噪音,设计了一个短公钥的全同态加密方案。该方案的公钥是目前LWE上全同态加密方案中公钥最短的。(2)研究使用Binary-LWE问题对噪音依赖于密钥的全同态加密方案,进行噪音控制与优化。并且以LWE上Bra12全同态加密方案为实例,进行了改进与提高。