Effective structural attack on McEliece-Sidelnikov public-key cryptosystem

Resumen

The authors propose an algorithm for recovering the secret key of the M?Eliece?Sidelnikov cryptosystem in general case: with u ? N copies of the Reed?Muller codes. Recovering the secret key of the McEliece?Sidelnikov cryptosystem is reduced to u problems of recovering the secret key of the McEliece cryptosystem  based on the Reed?Muller codes. It is proved in the paper that the proposed attack is polynomial. A set of keys for which the algorithm is applicable is described. The set is called the set of weak keys. The authors believe that the most of the keys are weak and show that it should be assumed that the ratio of the weak keys in the cryptosystem?s key space is close to one. Methods for calculating the number of the weak keys are described and computational experiments confirming it have  been performed.