基于最大秩距离码的数字签名方案

A DIGITAL SIGNATURE SCHEME BASED ON MAXIMUM RANK DISTANCE CODES

1990年王新梅基于纠错码构造了一种数字签名方案—— Xin- Mei方案 ,1992年该方案被 Alabbadi和Wicker提出的选择明文攻击方法攻破 ,该攻击方法的工作因子仅为 O(n3 ) ,n为 Xin- Mei方案中使用的码的长度 .Gabidulin于 1985年提出了最大秩距离码的理论 ,由于秩距离码的特点 ,利用秩距离码构造密码系统 ,可用比较小的参数获得比较大的工作因子 .在此对 Xin- Mei数字签名方案进行改进 ,基于最大秩距离码提出一新的数字签名方案 ,用穷搜索方法、选择明文攻击方法以及通用伪造攻击方法对该方案的安全性进行了分析 ,指出在这些攻击方法下 ,该数字签名方案是安全的 .

A digital signature scheme based on error-correcting codes, named Xin-Mei scheme, was suggested by Wang Xin-Mei in 1990. The scheme can be totally broken by a chosen-plaintext attack method suggested by Alabbadi and Wicker in 1992 with complexity O(n 3) , where n is the length of the code used in Xin-Mei scheme. The theory of maximum rank distance codes was introduced by Gabidulin in 1985. Because of the characteristics of rank distance codes, if cryptosystems are constructed based on rank distance codes, relative large work-factor can be obtained by using relative small parameters. By modifying the Xin-Mei digital signature scheme, a new digital signature scheme based on maximum rank distance codes is presented in this paper. Security of the scheme proposed is analyzed by using the exhaustive search attack method and the chosen-plaintext attack method suggested by Alabbadi and Wicker. Besides, security of the scheme is also analyzed using universal forgeries attack method. It is shown that the digital signature scheme based on maximum rank distance codes is computationally secure on these attacks.