论文部分内容阅读
随着计算能力的提升，尤其是量子计算的发展，传统的密码方案遭受着越来越多的挑战。为了应对这些潜在的安全威胁，人们迫切希望找到一些更加安全（如抗量子攻击）的新型密码方案。格密码因其高效、可证明安全和支持同态加密的特性，获得了越来越多的关注。其中，如何通过格密码获取与传统密码方案相同或类似安全需求的格密码方案是一个重要的研究方向，比如基于格的公钥密码方案和基于格的代理重加密方案等。
本文以格密码和格困难问题的研究为基础，以构造基于格的公钥密码方案为条件，以构造基于格的代理重加密方案为目的，得到了一系列与格密码有关的研究成果。主要研究成果如下：
1.分析研究了常见的格困难问题的复杂度情况，为构造相应的基于格困难问题的格密码方案提供了安全保障。根据类型不同，这些困难问题分为最坏情况下的格困难问题和平均情况下的格困难问题。其中，最坏情况下的困难问题主要包括最短向量问题(SVP)、最近向量问题(CVP)以及它们的一些变形，如最短独立向量问题(SIVP)等；平均情况下的困难问题主要包括小整数解问题(SIS)和错误学习问题(LWE)。通过分析和总结最坏情况下的格困难问题的复杂度成果，得到了SVP，CVP和SIVP在不同参数和不同范数下的依据参数大小排序的复杂度表格；通过分析和总结格困难问题之间的归约情况，得到了SIS和LWE按参数大小排序的归约表格。最后，根据相应的归约结果，得到了不同困难问题之间的归约关系图。
2.通过格在同态运算方面的特性，构造了支持云端同态加和同态乘运算的基于错误学习问题(LWE)的单层同态云计算方案sLHCC。此方案可以在不泄露操作需求（密文）的情况下，执行远程操作和控制。与其它同态加密方案相比，单层同态云计算方案的公钥尺寸从O(n2log q)降低到了O(n log q)，显著减小了密文尺寸和云端的存储需求。
3.针对格密码在多比特加密效率低下的问题，构造了高效的多比特公钥密码方案。与传统密码方案相比，现有的格密码方案在执行多比特加密时需要更大的计算开销和存储开销。为了提高效率，本文以正交格为基础，构造了一系列高效的多比特公钥密码方案(PKE)。在不需要通用的多比特加密改良情况下，方案实现了多比特（向量）级别的加密。与其他公钥密码方案相比，当明文尺寸较大时，新方案拥有更高的效率。此外，当明文为单比特时，相应的多比特公钥密码方案还可以通过进一步优化，从而提高执行效率。
4.代理重加密(PRE)可以在用户不泄露自身私钥的情况下，授权合法用户解密自身可以解密的合法密文。然而迄今为止，鲜有基于格的代理重加密方案出现。为了探讨方案稀有的原因，本文分析了常用的平均情况下的格困难问题(SIS和LWE)构造代理重加密方案的可行性。分析结果表明，通过单一问题直接构造代理重加密方案是不可行的。
5.抗合谋攻击的代理重加密方案具有重要的研究价值。因为在实际应用中，所使用的代理通常是第三方的，是并不可信的。然而，通过研究已有的抗合谋的基于格的代理重加密方案，本文发现已有的两个抗合谋的代理重加密方案在构造上都有错误。本文指出了造成方案出现错误的共同原因并构造了一个新的抗合谋的基于格的代理重加密方案。新的方案修正了以上两个方案中出现的问题，并且还最大限度的保留了这两个方案中有用的性质，如抗合谋攻击、选择明文安全(CPA)和单向重加密等。从方案的正确性来说，本方案是第一个抗合谋的基于格的代理重加密方案。
本文以格密码和格困难问题的研究为基础，以构造基于格的公钥密码方案为条件，以构造基于格的代理重加密方案为目的，得到了一系列与格密码有关的研究成果。主要研究成果如下：
1.分析研究了常见的格困难问题的复杂度情况，为构造相应的基于格困难问题的格密码方案提供了安全保障。根据类型不同，这些困难问题分为最坏情况下的格困难问题和平均情况下的格困难问题。其中，最坏情况下的困难问题主要包括最短向量问题(SVP)、最近向量问题(CVP)以及它们的一些变形，如最短独立向量问题(SIVP)等；平均情况下的困难问题主要包括小整数解问题(SIS)和错误学习问题(LWE)。通过分析和总结最坏情况下的格困难问题的复杂度成果，得到了SVP，CVP和SIVP在不同参数和不同范数下的依据参数大小排序的复杂度表格；通过分析和总结格困难问题之间的归约情况，得到了SIS和LWE按参数大小排序的归约表格。最后，根据相应的归约结果，得到了不同困难问题之间的归约关系图。
2.通过格在同态运算方面的特性，构造了支持云端同态加和同态乘运算的基于错误学习问题(LWE)的单层同态云计算方案sLHCC。此方案可以在不泄露操作需求（密文）的情况下，执行远程操作和控制。与其它同态加密方案相比，单层同态云计算方案的公钥尺寸从O(n2log q)降低到了O(n log q)，显著减小了密文尺寸和云端的存储需求。
3.针对格密码在多比特加密效率低下的问题，构造了高效的多比特公钥密码方案。与传统密码方案相比，现有的格密码方案在执行多比特加密时需要更大的计算开销和存储开销。为了提高效率，本文以正交格为基础，构造了一系列高效的多比特公钥密码方案(PKE)。在不需要通用的多比特加密改良情况下，方案实现了多比特（向量）级别的加密。与其他公钥密码方案相比，当明文尺寸较大时，新方案拥有更高的效率。此外，当明文为单比特时，相应的多比特公钥密码方案还可以通过进一步优化，从而提高执行效率。
4.代理重加密(PRE)可以在用户不泄露自身私钥的情况下，授权合法用户解密自身可以解密的合法密文。然而迄今为止，鲜有基于格的代理重加密方案出现。为了探讨方案稀有的原因，本文分析了常用的平均情况下的格困难问题(SIS和LWE)构造代理重加密方案的可行性。分析结果表明，通过单一问题直接构造代理重加密方案是不可行的。
5.抗合谋攻击的代理重加密方案具有重要的研究价值。因为在实际应用中，所使用的代理通常是第三方的，是并不可信的。然而，通过研究已有的抗合谋的基于格的代理重加密方案，本文发现已有的两个抗合谋的代理重加密方案在构造上都有错误。本文指出了造成方案出现错误的共同原因并构造了一个新的抗合谋的基于格的代理重加密方案。新的方案修正了以上两个方案中出现的问题，并且还最大限度的保留了这两个方案中有用的性质，如抗合谋攻击、选择明文安全(CPA)和单向重加密等。从方案的正确性来说，本方案是第一个抗合谋的基于格的代理重加密方案。