A study of cryptographic systems based on Rank metric codes

Abstract

The ubiquity, dependability, and extensiveness of internet access has seen a migration of local services to cloud services where the advantages of scalability can be efficiently exploited. In doing so, the exposure of sensitive data to eavesdropping is a principal concern. Asymmetric cryptosystems attempt to solve this problem by basing access on the knowledge of a solution to mathematically difficult problems. Shor demonstrated that on a quantum computer, cryptosystems based on the difficulty of factoring integers or solving discrete logarithms were efficiently solvable. As the most ubiquitous asymmetric cryptosystems in modern use are based on these problems, new cryptosystems had to be considered for post-quantum cryptography. In 1978, McEliece proposed a cryptosystem based on the difficulty of decoding random linear codes but the key sizes were too large for practical consideration. These systems, though, do appear to resist Shor’s algorithm and other quantum attacks. More recently, Gabidulin proposed using codes in the rank metric to design secure cryptosystems because they could be designed with smaller parameters. In this direction, many proposals for cryptosystems based on rank metric codes were designed. Overbeck managed to cryptanalyze many of these systems, but there remain several which resist all known structural attacks.
In this work, we investigate the use of rank metric codes for cryptographic purposes. Firstly, we investigate the construction of MRD codes and propose some new constructions based on combinatorial methods. We then generalize Overbeck’s attack and show how our generalized attack can be used to cryptanalyze some of the cryptosystems which were designed to resist the attack of Overbeck. Our attack is based on a new approach of exploiting the structure of low weight elements in the code. Our approach also allows us to extend a result of Gaborit to obtain a polynomial time decoding algorithm for codes with certain parameters. Lastly, we consider the use of codes in the subspace metric– which are based on rank metric codes–in order to create an alternative instance of Juels’ and Sudan’s fuzzy vault primitive.