This article is cited in 1 paper

Mathematical Methods of Cryptography

The failure of McEliece PKC based on Reed–Muller codes

I. V. Chizhov, M. A. Borodin

M. V. Lomonosov Moscow State University

Abstract: This paper describes new algorithm for breaking McEliece cryptosystem, being built on Reed–Muller binary code $RM(r, m)$.The algorithm calculates the private key from the public key using O$(n^d+n^4\log_2n)$ bit operations, where $n=2^m, d=(r,m-1).$ In case of limited $d$, the attack has a polynomial complexity. Practical results of implementation show that McEliece cryptosystems, based on the Reed–Muller binary code of length $n=65526$ bits, can be broken in less than 7 hours on a personal computer.

Keywords: McEliece cryptosystem, Reed–Muller code, polynomial attack.

UDC: 056.55