A DIGITAL SIGNATURE SCHEME BASED ON MAXIMUM RANK DISTANCE CODES

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.