基于格的高斯抽样和密钥交换

发布时间：2018-02-22 10:48

本文关键词： 格 LWE R-LWE 高斯抽样密钥交换　出处：《西安电子科技大学》2014年硕士论文　论文类型：学位论文

【摘要】：伴随着数字信息化的快速发展,人类即将进入量子信息时代,基于格的公钥密码作为后量子密码(即抵抗量子计算攻击的密码)的典型代表,在密码学领域占据重要地位。基于格的公钥密码具有清晰的安全性证明(即良好的归约特性)以及丰富多彩的服务功能等优点。近年来基于格的各种密码体制得到飞速发展。然而,格公钥密码的安全性和效率还严重受制于格上陷门的质量,即陷门基的尺寸和陷门基上高斯抽样的标准偏差。Micciancio和Peikert两位学者在2012年提出了一种基于格的陷门生成方案(简称MP12陷门),该方案简洁而紧凑,生成陷门的速度快,且生成陷门的质量达到了拟最优的程度；同时他们也给出了该陷门上的高斯抽样算法,该算法在保证安全性的同时,很大程度上提高了执行效率。但是在模数不为2的幂次时,该算法执行效率仍然不高,使得运行时间长,占用空间大。针对这个问题,本文基于MP12陷门提出了一个改进的高斯抽样算法,该算法主要利用非球形的基本高斯抽样来对原始算法进行改进,明显地减少了模数不为2的幂次时的计算量。此外,当陷门矩阵选取自典型分布时,改进的高斯抽样的标准差几乎总是略小于MP12陷门的标准差。与此同时,基于格的密钥交换协议在近些年也得到了很大的发展。尽管相关的研究还比较少,不够深入,但还是有很多密码学者对此进行了研究。2012年,丁津泰等人提出了一个基于LWE问题的可证明安全的密钥交换协议,该协议简洁且效率高,却不具备认证功能,不能抵抗主动攻击。因此,本文提出了该协议的一种可认证形式,利用广义压缩背包问题的哈希函数对需要发送的消息进行一次杂凑,从而达到认证的效果。
[Abstract]:With the rapid development of digital information, mankind is about to enter the era of quantum information. The lattice-based public key cryptography is a typical representative of post-quantum cryptography (that is, to resist the attack of quantum computing). Lattice-based public key cryptography has the advantages of clear security proof (that is, good reduction property) and rich and colorful service functions. In recent years, various lattice-based cryptosystems have been obtained. To rapid development. However, The security and efficiency of latticed public key cryptography are also severely restricted by the quality of the lattice trap. In 2012, two scholars, Micciancio and Peikert, proposed a grid-based trapping door generation scheme (MP12 trapping door for short), which is simple and compact. At the same time, they also give the Gao Si sampling algorithm on the trapping door, which not only guarantees the security, but also improves the execution efficiency to a great extent. But when the modulus is not equal to the power of 2, The efficiency of the algorithm is still not high, which makes the operation time long and the space large. In order to solve this problem, an improved Gao Si sampling algorithm based on MP12 trapdoor is proposed in this paper. The algorithm mainly uses the non-spherical basic Gao Si sampling to improve the original algorithm, which obviously reduces the computational complexity when the modulus is not equal to 2. In addition, when the trapdoor matrix is selected from the typical distribution, The standard deviation of improved Gao Si sampling is almost always slightly smaller than that of MP12 trapping. At the same time, the lattice-based key exchange protocol has been greatly developed in recent years. In 2012, Ding Jintai and others put forward a provable secure key exchange protocol based on LWE problem. The protocol is simple and efficient, but it does not have authentication function. Therefore, an authenticated form of the protocol is proposed, in which the hash function of the generalized compressed knapsack problem is used to hash the messages to be sent, so as to achieve the authentication effect.
【学位授予单位】：西安电子科技大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TN918.4

【相似文献】