Geodesic
The failure of McEliece PKC based on Reed–Muller codes
Prikladnaya Diskretnaya Matematika. Supplement, no. 6 (2013), pp. 48-49 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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. 
@article{PDMA_2013_6_a23,
     author = {I. V. Chizhov and M. A. Borodin},
     title = {The failure of {McEliece} {PKC} based on {Reed{\textendash}Muller} codes},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {48--49},
     year = {2013},
     number = {6},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2013_6_a23/}
}
TY  - JOUR
AU  - I. V. Chizhov
AU  - M. A. Borodin
TI  - The failure of McEliece PKC based on Reed–Muller codes
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2013
SP  - 48
EP  - 49
IS  - 6
UR  - http://geodesic.mathdoc.fr/item/PDMA_2013_6_a23/
LA  - ru
ID  - PDMA_2013_6_a23
ER  - 
%0 Journal Article
%A I. V. Chizhov
%A M. A. Borodin
%T The failure of McEliece PKC based on Reed–Muller codes
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2013
%P 48-49
%N 6
%U http://geodesic.mathdoc.fr/item/PDMA_2013_6_a23/
%G ru
%F PDMA_2013_6_a23
I. V. Chizhov; M. A. Borodin. The failure of McEliece PKC based on Reed–Muller codes. Prikladnaya Diskretnaya Matematika. Supplement, no. 6 (2013), pp. 48-49. http://geodesic.mathdoc.fr/item/PDMA_2013_6_a23/

[1] Mak-Vilyams F. Dzh., Sloen N. Dzh., Teoriya kodov, ispravlyayuschikh oshibki, Svyaz, M., 1979

[2] Sidelnikov V. M., “Otkrytoe shifrovanie na osnove dvoichnykh kodov Rida–Mallera”, Diskretnaya matematika, 6:2 (1994), 3–20

[3] Minder L., Shokrollahi A., “Cryptanalysis of the Sidelnikov cryptosystem”, LNCS, 4515, 2007, 347–360 | MR | Zbl