矩阵分解在密码中应用研究  

A Survey on Applications of Matrix Decomposition in Cryptography

作　　者：张焕国[1,2] 刘金会[1,2] 贾建卫[1,2] 毛少武[1,2] 吴万青[1,2] 

机构地区：[1]武汉大学计算机学院,武汉430072 [2]空天信息安全与可信计算教育部重点实验室,武汉430072

出　　处：《密码学报》2014年第4期341-357,共17页Journal of Cryptologic Research

基　　金：国家自然科学基金资助项目(61303212;61170080;61202386);国家自然科学基金资助重点项目(61332019;U1135004);国家自然科学基金资助重大项目(91018008);国家重点基础研究发展规划项目(973计划)(2014CB340600);湖北省自然基金项目(2011CDB453)

摘　　要：矩阵在密码学中有着悠久的应用历史.有一些基于矩阵的密码是安全的,如McEliece密码、格密码等.但是也有一些基于矩阵的密码是不安全的,如某些背包密码等.由于矩阵运算效率高,所以基于矩阵的密码具有效率高的优点.基于矩阵的密码的另一个优点是具有抗量子计算攻击的潜力.随着量子计算技术的发展,量子计算机对现在广泛使用的一些公钥密码(如RSA、ECC、ElGamal等)构成了严重威胁.这是因为在量子计算环境下,基于交换代数结构上许多困难问题存在有效的量子算法.但是基于非交换代数结构上的困难问题目前还没有有效的量子算法.所以密码界普遍认为,非交换代数结构上的公钥密码具有抵抗量子计算攻击的潜力(如纠错码密码、格密码和多变量密码等).由于矩阵运算具有非交换属性,所以基于矩阵的密码具有抗量子计算攻击的潜力.基于矩阵的密码的安全性与矩阵分解的困难性密切相关.因此,为了设计构造安全的密码,特别是设计构造安全的抗量子计算密码,有必要研究矩阵分解问题及其计算复杂性.本文综合论述了矩阵分解的方法、矩阵分解的计算复杂性,以及矩阵分解在密码安全性分析中的应用等内容,并对矩阵分解研究中存在的难点问题以及未来可能的发展方向进行了展望.Many of the cryptographic applications based on matrix are historical. Some matrix-based cryptosystems are highly secure, such as McEliece public key cryptosystem and Lattice-based cryptosystem. While some others are not, such as some knapsack public-key cryptosystems. Because the matrix calculation is very efficient, this advantage makes it highly efficient in matrix-based cryptosystems. Another advantage of matrix-based cryptosystems is that it has the potential to resist known quantum algorithms attacks. Advances in quantum computers threaten to break the currently used public key cryptosystems on commutative algebraic structures such as RSA, ECC, and EIGamal. This is because of Shor's quantum algorithms for integer factoring and solving the DLP, the known public-key systems will be insecure when quantum computers become practical, while no quantum algorithms are found to solve certain mathematical problems on non-commutative algebraic structures. Most of experts believe that many public-key cryptosystems(such as Code-based cryptography, Lattice-based cryptography, MQ-based cryptography) on non-commutative algebraic structures used today have the potential to resist known quantum algorithms attacks. Multiplication of matrices have non-commutative attribute, so matrix-based cryptosystems have the potential to resist known quantum algorithms attacks. In order to construct a secure cryptosystem, especially design of a secure cryptography against the threat of quantum computing attacks, it is necessary to study matrix decomposition problems and computational complexity relating to the matrix decomposition. Taking into account the above scenarios, after introducing the methods and computational complexity relating to the matrix decomposition, design and cryptanalysis of matrix decomposition-based cryptosystems, are analyzed and reviewed in detail. At last, some challenges, together with the future directions of content-matrix decomposition-based cryptography are discussed.

关 键 词：密码学 抗量子计算密码 计算复杂性 矩阵分解 方程组求解 

分 类 号：TN918.1[电子电信—通信与信息系统] O151.21[电子电信—信息与通信工程]