Search papers, labs, and topics across Lattice.
This paper investigates the security vulnerabilities of McEliece cryptosystems that utilize Generalized Reed-Solomon codes, specifically focusing on those with a row and column weight of two. The authors develop distinguishers for public codes in these high-rate cryptosystems and establish a framework to convert these distinguishers into key-recovery attacks. Their findings reveal that the proposed scheme with weight two can be effectively compromised, highlighting significant weaknesses in the current cryptographic implementations.
High-rate McEliece cryptosystems with weight two can be broken using a novel cube code distinguisher, exposing critical vulnerabilities in their security.
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.
