Cryptanalysis of the Sidelnikov cryptosystem

We present a structural attack against the Sidelnikov cryptosystem. The attack creats a private key from a give public key. Its running time is subexponential and it is effective if the parameters of the Reed-Muller code allow for efficient sampling of minimum weight codewords. For example, the length 2048, 3rd order Reed-Muller code takes roughly an hour to break on a stock PC using the presented metho.