Enhancing the Security of the GPT Cryptosystem Against Attacks

The concept of Public key cryptosystems based on error correcting codes wasinvented by McEliece in 1978. In 1991 Gabidulin, Paramonov and Tretjakov proposed a newversion of the McEliece cryptosystem (GPT) based on maximum rank distance codes insteadof hamming distance codes. Respective structural attacks against dierent variants of theGPT cryptosystem were proposed by Gibson and lately by Overbeck. The Overbeck attackbreaks all variants of the GPT cryptosystem and are turned out to be either polynomial orexponential depending on parameters of the cryptosystem. Furthermore, In 2013, Gaboritet al. have presented a decoding attack against the parameters of the simple variant ofthe GPT cryptosystem which were demonstrated to combat the GPT cryptosystem againstOverbeck's attack.In this paper, we introduce two new secure approaches against both the structural (Over-beck's attack) and decoding (brute force) attacks. The rst one is called Distortion MatrixApproach (DMA), and the second is called Advanced Approach for Reducible Rank Codes(ARC). The DMA based on proper choice of a distortion matrix X, while, the ARC basedon a proper choice of a scramble matrix P. Furthermore, we evaluate the simple variant ofGPT cryptosystem against Gaborit et al. attack and demonstrate a new set of parameterswhich are secure against all known attacks. Our results show the proposed approaches com-bat the structural and decoding attacks with a large reduction in the key size in comparisonto the original McEliece cryptosystem.