基于格的数字签名和认证协议研究

发布时间：2018-01-12 19:34

本文关键词：基于格的数字签名和认证协议研究　出处：《复旦大学》2014年硕士论文　论文类型：学位论文

更多相关文章： 数字签名 认证 量子计算机 格 离散对数

【摘要】：数字签名和认证是公钥密码学在日常生活中的两个非常重要的应用。自数字签名和认证的概念被提出以来,基本上所有的数字签名和认证方案的安全性都是基于大整数分解问题和离散对数问题。Shor在1994年提出了在量子计算机下能够解决这两个难解性问题的算法,从而引起了密码学界对于量子计算机下密码学的关注和研究。因此,除了大整数分解问题和离散对数问题,必须要提出其他的复杂性假设,并以此来设计密码学方案,使得最终的方案不仅在现在的计算机上能够保证安全性,而且能够抵抗量子计算机下的攻击。基于格的密码学因其最差情况难解的强可证明安全性、计算高效和丰富的难解性假设等优点成为了近几年后量子密码学的研究热点。目前已经有很多基于格的数字签名和认证方案被提出,但是多数方案都无法在效率和安全性上都做到与现有的基于大整数分解和离散对数的方案相近,这会大大限制基于格的密码学的实际应用。本文通过分析国际国内对基于格的签名和认证方案的最新研究进展,首先提出一个在随机预言机模型下基于格的可证明安全数字签名方案,该方案的公私钥长度和计算复杂度都接近线性时间(O(nlogn)),并且能够在随机预言机模型下证明其安全性,其安全性依赖于Ring-SIS问题的难解性,而且该签名方案满足强不可锻造性。更重要的是,与其他基于格的签名方案相比,该方案具有很高的效率,并且签名算法不会出现签名失败的情况,从而保证了运行一次签名算法即可产生一个合法的签名。然后,本文提出了一个具有完美完备性的基于格的可证明安全认证方案,该方案采用Schnorr认证协议的结构来执行认证流程。新协议使用SIS问题作为安全假设,并使用理想格(Ideal Lattice)将方案的空间复杂度由mn log p降到mlogp,将时间复杂度从O(mn)降到O(mlogn)。
[Abstract]:Digital signature and authentication are two very important applications of public key cryptography in daily life. Since the concept of digital signature and authentication was proposed. The security of almost all digital signature and authentication schemes is based on the large integer decomposition problem and discrete logarithm problem. In 1994, Shor proposed that these two difficult problems can be solved by quantum computer. The algorithm. Therefore, in addition to the large integer decomposition problem and discrete logarithm problem, we must put forward other complexity assumptions. And to design a cryptographic scheme, so that the final solution not only in the current computer to ensure security. And it can resist the attack under the quantum computer. The lattice-based cryptography has strong provable security because of its worst case. Computational efficiency and rich insoluble assumptions have become the focus of quantum cryptography research in recent years. At present, many lattice-based digital signature and authentication schemes have been proposed. However, most schemes can not achieve the same efficiency and security as the existing schemes based on large integer decomposition and discrete logarithm. This will greatly limit the practical application of lattice-based cryptography. This paper analyzes the latest research progress of the lattice-based signature and authentication schemes at home and abroad. Firstly, a lattice-based provable secure digital signature scheme based on random prophecy model is proposed. The length and computational complexity of the public and private keys are close to linear time. And it can prove its security under the random oracle model, its security depends on the Ring-SIS problem, and the signature scheme satisfies the strong inforging property. More importantly, the security of the signature scheme is very important. Compared with other lattice-based signature schemes, this scheme has a high efficiency, and the signature algorithm will not have the situation of signature failure. In order to ensure that the one-time signature algorithm can produce a legal signature. Then, this paper proposes a lattice-based provable security authentication scheme with perfect completeness. The scheme adopts the structure of Schnorr authentication protocol to implement the authentication process. The new protocol uses SIS problem as a security assumption. The space complexity of the scheme is reduced from mn logp to mlogp, and the time complexity is reduced from logp to Oomlognan using ideal ideal Lattice.
【学位授予单位】：复旦大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TN918.91

【相似文献】