论文部分内容阅读
格密码由于其具有抗量子性、最坏情况困难性、功能多样性和实现高效性被国内外密码学研究者广泛关注。基于格的密码假设不仅可以用来构造经典的公钥密码学组件如公钥加密、数字签名和密钥交换协议,还可以用来构造特殊功能的密码学组件如全同态加密等。本文选取了格密码中困难问题归约、全同态加密自举算法设计、多密钥全同态加密算法设计等问题进行了深入研究,分析了现有解决方案的不足之处并提出了具体的改进策略,取得了以下成果。 计算ring-LWR问题的困难性及其应用研究:本文提出了计算ring-LWR问题的概念,并且给出了ring-LWE到计算ring-LWR假设的归约,在此基础上提出了更加高效的公钥加密方案。ring-LWE的最坏情况困难性要求噪音产生于取整高斯分布并且标准差大小为O(√n)。然而从取整高斯分布采样是十分费时的。同时噪音标准差较大会导致模数较大,从而导致密文和公钥的尺寸较大。因此,提出了一个新的假设即计算ring-LWR假设,并且给出了ring-LWE到计算ring-LWR假设的归约。同时给出了基于ring-LWR假设的公钥加密方案。相比于基于ring-LWE的公钥加密方案,我们的方案不仅不需要从高斯分布中采样,而且公钥和密文的尺寸更小。 加密环元素的全同态加密方案自举算法研究:本文给出了加密环元素的全同态加密在多项式噪音积累下的自举算法。具体来说,基于ring-LWE假设的BGV方案为目前效率最高的全同态加密方案之一,因为其一个密文可以加密一个环元素并且支持基于中国剩余定理的密文批量技术。然而目前的BGV方案并不能在多项式噪音积累条件下自举。此外,观察到GSW全同态加密方案可以在多项式噪音积累下自举,这意味着可以选取更小的维数达到相同的安全等级。但是其一个密文只能加密单一比特。于是提出了一种新的BGV方案自举技术,使得其可以在多项式积累下自举。为了达到70比特安全性,方案密文的维数不超过212,而著名的HElib中至少需要214到216。因而我们的技术可以使密文的大小可以明显减小。 多密钥全同态加密算法研究:本文提出了首个标准假设下支持批量密文操作的多密钥全同态加密,具有更优的明密文比和更高效的密文扩展算法。目前标准假设下的多密钥全同态加密都是从GSW方案出发,因而单个密文只能加密单一比特。同时目前标准假设下的多密钥全同态家加密方案不支持批量密文操作,而且在进行同态密文计算之前需要对每个密文进行密钥扩展。其密钥扩展步骤的计算复杂度与参与计算密文的复杂度直接相关。本文提出了一种基于BGV方案构造的多密钥全同态加密。我们的方案一个密文可以加密一个环元素并且支持基于中国剩余定理的密文批量技术。同时,我们的方案密钥扩展步骤的计算代价与密文个数无关,只与安全参数和参与方个数相关。因此当密文个数较多时,本方案在效率方面优势明显。