论文部分内容阅读
随着量子计算理论的快速发展,很多传统密码体制的安全性受到了严重挑战.而格密码作为可以抵抗量子攻击的公钥密码体制受到人们越来越多的关注.很多格密码体制的设计及格密码分析都依赖于格的具体结构.在格上引入额外的结构会使得格在密码学中有着更为广泛的应用. 理想格就是一类有着额外的理想结构的格.理想格既是取定环的一个理想,又在特定的嵌入下同构于多维实数空间中的格.因为有着比起普通格而言更为丰富的结构和可以更为快速实现的元素间的加法运算和乘法运算,理想格在现代密码学的很多研究领域有着越来越多的应用. 本文主要关注理想格在密码学中应用的两个重要方向:一个是考虑环上的LWE(R-LWE)的计算困难性问题.R-LWE是格上一般情况下的计算困难问题LWE在理想格上的自然推广.由于理想格中的乘法运算比起一般格中的内积运算更容易在计算机中实现,因此,基于R-LWE的密码体制将会更为有效.但基于R-LWE的密码体制的安全性的基础是证明R-LWE的计算困难性.我们给出了从理想格上的已知计算困难问题(如GapSVP)到R-LWE的经典归约,从而说明R-LWE是计算困难的. 本文另一个关注的方向是利用理想格来构造密码学上的多线性映射的候选者以及这些候选者在具体密码协议构造上的应用.利用密码学上的多线性映射,我们可以构造很多密码体制.但是如何构造变元个数大于2的密码学上的多线性映射至今仍是一个未获得圆满解决的问题.受到Gentry利用理想格来构造全同态加密体制的启发,Garg,Gentry和Halevi给出了基于理想格的第一个密码学上的多线性映射的候选者-GGH分次编码体制.虽然GGH体制还不是严格意义上的密码学上的多线性映射,但其在密码学中已经有了非常广泛的应用.很多需要在密码学上的多线性映射假设成立前提下方能构造的密码体制,都可以利用GGH体制来具体实现. 本文的主要研究成果包含: 1.给出了理想格上计算困难问题到R-LWE的一个经典归约.在具体的归约过程中,我们首先深入讨论应用非常广泛的一类理想格的几何结构和这类理想格在椭球形离散高斯分布下的性质.然后结合已有的理想格上的计算困难问题到R-LWE的量子归约和不同版本R-LWE之间归约的已知结论,给出特定参数下理想格上的GapSVP到R-LWE的经典归约.我们的归约更为完整地刻画了R-LWE的困难性,从而使得基于R-LWE的密码体制有了更为坚实的安全基础. 2.利用GGH体制,给出了最优认证数据结构的第一个可以实现的构造,为远程数据存储和访问提供了一个更为有效和安全的方式.在具体构造过程中,我们先来简要介绍最优认证数据结构的相关概念,然后利用GGH体制在一定的假设下给出最优认证数据结构的具体构造.最后,我们证明新的数据结构的最优性,正确性;并利用基于GGH体制的困难假设,证明新体制的安全性. 3.利用GGH体制的一个变体,给出了唯一签名体制的一个新构造.比起已有的唯一签名体制的构造,我们的构造基于完全不同的困难假设.在构造过程中,我们先简要回顾唯一签名体制的形式定义,然后给出GGH体制的一个变体,并利用这个变体来给出唯一签名体制的一个新构造.最后,我们证明新唯一签名体制的正确性及体制在新的困难假设下的安全性.