2013/07/24 by Alain Couvreur, Couvreur, Alain, Philippe Gaborit +6 · 5 citations
Computer Science · Engineering · #Coding theory and cryptography #graph theory and CDMA systems #Quantum Computing Algorithms and Architecture
paper · pdf · doi:10.48550/arxiv.1307.6458
Because of their interesting algebraic properties, several authors promote\nthe use of generalized Reed-Solomon codes in cryptography. Niederreiter was the\nfirst to suggest an instantiation of his cryptosystem with them but Sidelnikov\nand Shestakov showed that this choice is insecure. Wieschebrink proposed a\nvariant of the McEliece cryptosystem which consists in concatenating a few\nrandom columns to a generator matrix of a secretly chosen generalized\nReed-Solomon code. More recently, new schemes appeared which are the\nhomomorphic encryption scheme proposed by Bogdanov and Lee, and a variation of\nthe McEliece cryptosystem proposed by Baldi et \al. which hides the\ngeneralized Reed-Solomon code by means of matrices of very low rank.\n In this work, we show how to mount key-recovery attacks against these\npublic-key encryption schemes. We use the concept of distinguisher which aims\nat detecting a behavior different from the one that one would expect from a\nrandom code. All the distinguishers we have built are based on the notion of\ncomponent-wise product of codes. It results in a powerful tool that is able to\nrecover the secret structure of codes when they are derived from generalized\nReed-Solomon codes. Lastly, we give an alternative to Sidelnikov and Shestakov\nattack by building a filtration which enables to completely recover the support\nand the non-zero scalars defining the secret generalized Reed-Solomon code.\n