The failure of McEliece PKC based on Reed-Muller codes.
Ivan Vladimirovich Chizhov, Бородин Михаил Алексеевич · 2013
This paper describes new algorithm for breaking McEliece cryptosystem, built on Reed-Muller binary code RM(r, m), which receives the private key from the public key. The algorithm has complexity O(n d +n 4 log2n) bit operations, where n = 2 m, d = GCD(r, m−1). In the case of GCD(r, m − 1) limitation, attack has polynomial complexity. Practical results of implementation show that McEliece cryptosystems, based on the code with length n = 65536 bits, can be broken in less than 7 hours on a personal computer. 1