基于遍历矩阵的单向(陷门)函数的构造方案  

Scheme to Construct One-Way(Trapdoor) Functions Based on Ergodic Matrices

作　　者：孙永雄[1] 赵永哲[1] 杨永健[1] 李荣[1] 

机构地区：[1]吉林大学计算机科学与技术学院,长春130012

出　　处：《吉林大学学报（信息科学版）》2006年第5期555-560,共6页Journal of Jilin University（Information Science Edition）

摘　　要：针对基于特定非交换壹半群(m,.)中的困难问题,给出了单向(陷门)函数的一种新的构造方案,即已知A和B=xAy,而求x和y的难度;选取有限域Fq上的n×n矩阵,在Fq矩阵乘法下,以所构成的非交换壹半群作为研究对象,利用Fq上“遍历矩阵”的密码学特性,提出了基于Fq上遍历矩阵的实现方案,并对可能的攻击手段进行了分析。提出了“强壮矩阵”的概念,并对给定的两个遍历矩阵Q1和Q2,给出了关于Q1,Q2的强壮矩阵的判别标准和寻找算法;由〈Q1〉,〈Q2〉以及关于Q1,Q2的强壮矩阵,可以构造相应的单向(陷门)函数。We present a new implementation of the one-way （trapdoor） functions. It is based on the difficult problem in a specific monoid （ m, · ） which is noncommutative, namely the difficulty to deduce x and y by knowing A and B = xAy. So we focus on certain monoid which is formed by all the n x n matrices over finite field Fq under multiplication. By the cryptography characteristics of ＂ergodic matrix＂ based on the ergodic matrices over Fq and then analyze the possible attacks. over Fq, we scheme out a method Then we introduce the concept of ＂strong matrix＂ and provide distinguishing criterion and search algorithm of the strong matrix about two certain ergodic matrices Q1 and Q2- Using 〈Q1 〉, 〈 Q2 〉 and a strong matrix m about Q1 and Q2, we can construct a one-way （trapdoor） function.

关 键 词：遍历矩阵 强壮矩阵 有限域 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]