基于格的代理密码的设计与分析

发布时间：2018-03-04 20:10

本文选题：格公钥密码　切入点：无证书公钥加密　出处：《西安电子科技大学》2014年博士论文　论文类型：学位论文

【摘要】：随着量子计算机的发展,研究者发现利用量子计算机可以在多项式时间内解决离散对数问题和大整数分解问题。那么基于这两个困难问题的密码体制在量子环境下将不再安全。因此,研究量子环境下安全的密码体制是非常有意义的。格公钥密码作为后量子密码的典型代表,具有良好的密码学性质。虽然格公钥密码在最近几年取得了突破性进展和很多重要成果,但总体来说还是处在研究初期,与基于离散对数和大整数分解问题的密码体制相比,还远远不够成熟,还有很多问题需要解决。该论文对格公钥密码进行了深入的研究与分析,主要取得如下结果：1、利用格上第一个基于身份的加密方案,构造了一个无证书加密方案,与基于离散对数问题和大整数分解问题的无证书加密方案相比,该方案的大部分计算都是矩阵向量乘法和内积运算,计算复杂度较低,并且在量子环境下是安全的。2、利用无陷门签名技术和小范数矩阵传递技术,基于格上的小整数解问题,构造了一个高效代理签名方案。方案中的小范数矩阵传递技术可以控制代理签名私钥的维数,使得代理签名私钥的维数小于原始签名私钥的维数。与基于盆景树原理和固定维数的格基委托技术构造的代理签名方案相比,大大降低了代理签名私钥和代理签名的尺寸。3、针对量子环境下基于大整数分解与离散对数困难问题的代理重签名的不安全性,提出一种能够抵抗量子攻击的代理重签名方案。借助Xagawa的代理重加密技术和格上的无陷门签名技术,构造了第一个基于格的代理重签名方案,并运用格上的小整数解问题的困难性对其进行了安全性证明。证明和效率分析结果表明,该方案具有双向性、多次使用性、密钥最优性以及透明性,与基于其它困难问题的代理重签名方案相比,具有渐近计算复杂度低的优点。最后,把该方案扩展为基于身份的代理重签名方案。4、利用原像抽样算法构造了格上第一个多次使用的单向代理重签名方案,部分解决了Libert等在CCS 2008上提出的公开问题。该方案基于格上的小整数解问题,其验证开销不会随着变换次数的增加而增大,并且签名尺寸随着变换次数的增加呈线性增长。5、利用原像抽样技术与固定维数的格基委派技术,基于格上的小整数解问题,构造了格上第一个基于身份的单向代理重签名方案。该方案具有单向性,多次使用性等性质。与其他具有相同性质的基于身份的代理重签名相比,具有验证开销小,渐近复杂度低等优点。6、利用原像抽样技术,构造了格上第一个多次使用的单向代理重加密方案。该方案的代理重加密密钥不需要双方私钥的交互就可以生成,从而可以抵抗合谋攻击,并且被证明在标准模型下是CPA安全的。同时扩展为基于身份的单向代理重加密方案。
[Abstract]:With the development of quantum computer, Researchers have found that quantum computers can solve discrete logarithm problems and large integer decomposition problems in polynomial time. The cryptosystem based on these two difficult problems will no longer be secure in quantum environment. It is very meaningful to study secure cryptosystem in quantum environment. Lattice public key cryptography is a typical representative of post-quantum cryptography. Although lattice public key cryptography has made a breakthrough and many important achievements in recent years, generally speaking, it is still in the early stage of study, compared with the cryptosystem based on discrete logarithm and large integer decomposition. It is still far from mature, there are still many problems to be solved. This paper deeply studies and analyzes the lattice public key cryptography, and obtains the following results: 1, using the first identity-based encryption scheme on the lattice. A certificate free encryption scheme is constructed. Compared with the certificate free encryption scheme based on discrete logarithm problem and large integer decomposition problem, most of the computations of the scheme are matrix vector multiplication and inner product operation, and the computational complexity is lower than that of the one based on discrete logarithm problem and large integer decomposition problem. And it is safe in quantum environment. By using the technique of no-trapdoor signature and small norm matrix transfer, the problem of small integer solution is based on the lattice. In this paper, an efficient proxy signature scheme is constructed, in which the dimension of the private key of proxy signature can be controlled by the small norm matrix transfer technique. The dimension of the proxy signature private key is smaller than that of the original signature private key. The size of private key and proxy signature of proxy signature is greatly reduced. The security of proxy resignature based on the problem of large integer decomposition and discrete logarithm in quantum environment is greatly reduced. A proxy resignature scheme, which can resist quantum attack, is proposed. The first lattice-based proxy resignature scheme is constructed by means of proxy reencryption technology of Xagawa and non-trapping door signature technology. The security of the scheme is proved by using the difficulty of solving the problem of small integers on lattices. The results of proof and efficiency analysis show that the scheme is bidirectional, multiple use, key optimality and transparency. Compared with the proxy resignature scheme based on other difficult problems, it has the advantage of low asymptotic computational complexity. Finally, The scheme is extended to an identity-based proxy resignature scheme. 4, and the first unidirectional proxy resignature scheme is constructed by using the original image sampling algorithm. This scheme is based on the small integer solution problem on lattice, and the verification overhead does not increase with the increase of the number of transformations. And the size of signature increases linearly with the increase of transformation times. 5. By using the original image sampling technique and the fixed dimension lattice-assignment technique, the small integer solution problem on the lattice is used to solve the problem. The first identity-based proxy resignature scheme on a lattice is constructed. The scheme has the properties of unidirectionality and multiple usage. Compared with other identity-based proxy resignature schemes with the same property, the scheme has less verification overhead. The asymptotic complexity is low. 6. By using the original image sampling technique, the first unidirectional proxy reencryption scheme is constructed on the lattice. The proxy reencryption key of the scheme can be generated without the interaction of the two private keys. It can resist collusion attack and is proved to be CPA secure under the standard model. It is also extended to an identity-based one-way proxy reencryption scheme.
【学位授予单位】：西安电子科技大学
【学位级别】：博士
【学位授予年份】：2014
【分类号】：TN918.4;O413

【参考文献】