Skew Reed-Solomon codes to the ReSkew: a new broken code-based cryptosystem

Abstract

We give our motivation to propose ReSkew, a new McEliece-like cryptosystem based on generalized skew Reed-Solomon (GSRS) codes. While many earlier proposals based on generalized Reed-Solomon (GRS) and Gabidulin codes were broken by structural attacks, the non-commutativity of the underlying skew-polynomial ring seems to prohibit the known techniques and their adaptations to the skew setting for suitable parameter choices. Since GSRS codes have a higher error-correction capability than Goppa codes, the same security level as Classic McEliece can be achieved with smaller code parameters and thus reduce the public-key size by a factor 3 compared to Classic McEliece for each security level. Since we found efficient attacks on the system prior to the talk, we focus on presenting them.