Distinguisher-Based Attacks on Public-Key Cryptosystems Using Reed-Solomon Codes

International audienceThe purpose of this paper is to demonstrate that a distinguisher of Reed-Solomon codes based on the square code construction leads to the cryptanalysis of several cryptosystems relying on them. These schemes are respectively (i) a homomorphic encryption scheme proposed by Bogdanov and Lee; (ii) a variation of the McEliece cryptosystem proposed by Baldi et al. which firstly uses Reed-Solomon codes instead of Goppa codes and secondly, adds a rank 1 matrix to the permutation matrix; (iii) Wieschebrink's variant of the McEliece cryptosystem which consists in concatenating a few random columns to a generator matrix of a secretly chosen generalized Reed-Solomon code