基于矩阵环上求根问题的数字签名算法

基于矩阵环上求根问题的数字签名算法 Digital Signature Scheme Based on the Root Extraction Problem on Matrix Ring 巨春飞 JU Chunfei1 1 first-author 王保仓 WANG Baocang2 2 陈志罡 CHEN Zhigang3 3 西京学院工程技术系 西京学院工程技术系 Department of Engineering Technology,Xijing University Department of Engineering Technology,Xijing University 西安电子科技大学计算机网络与信息安全教育部重点实验室 西安电子科技大学计算机网络与信息安全教育部重点实验室 Key Laboratory of Computer Networks and Information Security of Ministry of Education,Xidian University Key Laboratory of Computer Networks and Information Security of Ministry of Education,Xidian University 浙江万里学院计算机与信息学院 浙江万里学院计算机与信息学院 College of Computer Science and Information Technology,Zhejiang Wanli University College of Computer Science and Information Technology,Zhejiang Wanli University 考虑定义在模数N的剩余类环上的矩阵所构成的矩阵环上的求根问题的困难性,本文设计了一个数字签名算法,证明了攻击者能够成功伪造一个签名当且仅当攻击者能够求解矩阵环上的求根问题.对矩阵环上的求根问题的困难性进行了分析,在一种特殊情况下,证明了矩阵环上的求根问题与整数分解问题是等价的.分析表明,该数字签名算法是一个高效安全的签名算法. The computational intractability of the root extraction problem on the matrix ring constructed from the residue ring modulo N is investigated,and a digital signature scheme is proposed.It is proven that the attacker can forge a signature if and only if he can solve the root extraction problem defined over matrix ring.The computational intractability of the root extraction problem over the matrix ring is analyzed,and it is proven that the root digital extraction problem is equivalent to the integer factorization problem in a special case.Analysis shows that the proposed signature scheme is efficient and secure. 数字签名 求根问题 矩阵环 整数分解 digital signature scheme root extraction problem matrix ring integer factorization 10.14188/j.1671-8836.2010.02.008 TN918.1 国家自然科学基金资助项目（60803149）;浙江省自然科学基金资助项目（Y1091085） 2010-02-01 2021-04-01 2 56