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

摘要

Because of their interesting algebraic properties, several authors promotethe use of generalized Reed-Solomon codes in cryptography. Niederreiter was thefirst to suggest an instantiation of his cryptosystem with them but Sidelnikovand Shestakov showed that this choice is insecure. Wieschebrink proposed avariant of the McEliece cryptosystem which consists in concatenating a fewrandom columns to a generator matrix of a secretly chosen generalizedReed-Solomon code. More recently, new schemes appeared which are thehomomorphic encryption scheme proposed by Bogdanov and Lee, and a variation ofthe McEliece cryptosystem proposed by Baldi et \textit{al.} which hides thegeneralized Reed-Solomon code by means of matrices of very low rank. In this work, we show how to mount key-recovery attacks against thesepublic-key encryption schemes. We use the concept of distinguisher which aimsat detecting a behavior different from the one that one would expect from arandom code. All the distinguishers we have built are based on the notion ofcomponent-wise product of codes. It results in a powerful tool that is able torecover the secret structure of codes when they are derived from generalizedReed-Solomon codes. Lastly, we give an alternative to Sidelnikov and Shestakovattack by building a filtration which enables to completely recover the supportand the non-zero scalars defining the secret generalized Reed-Solomon code.