An Attack on High Rate McEliece Cryptosystems Using Generalized Reed Solomon Codes with Weight 2 Mask

Due to the insecurity of McEliece cryptosystems instantiated with Generalized Reed-Solomon codes, there have been several proposals of McEliece type systems that replace the permutation matrix by a matrix M with larger row and column weight. In many of them, the secret key is still a GRS code. There have been successful attacks on some of those schemes with row and column weight between 1 and 1 + R, where R is the rate of the code. The case of weight two and larger has been left open in these works. Subsequently, several authors proposed schemes with weight exactly two and with even higher weight. We provide distinguishers for the public codes appearing in these cryptosystems in the high rate regime. In addition, we give a framework to turn a good enough distinguisher into a key-recovery attack. In the case where the matrix M has row and column weight 2, we can successfully attack the scheme in the high rate regime using a cube code distinguisher.