# Is the Couvreur et al. polynomial time attack on McEliece practical?

There's a new e-print out on arXiv titled "A Polynomial Time Attack against Algebraic Geometry Code Based Public Key Cryptosystems" by Alain Couvreur, Irene Márquez-Corbella and Ruud Pellikaan:

"We give a polynomial time attack on the McEliece public key cryptosystem based on algebraic geometry codes. Roughly speaking, this attacks runs in $O(n^4)$ operations in $\mathbb F_q$, where $n$ denotes the code length. Compared to previous attacks, allows to recover a decoding algorithm for the public key even for codes from high genus curves."

Is this a practical attack against currently used implementations of the McEliece cryptosystem, with security parameters such as those recommended by Bernstein, Lange and Peters (2008)?

If the answer is yes, then how much do we need to increase the security parameters $n, k, t$ to be safe? Or do we need to switch another code / curve entirely?

• Hi, fractal, and welcome to Cryptography Stack Exchange! I've edited your question to add some detail and make it a better fit to our site. Please don't hesitate to correct any mistakes or omissions I may have introduced while doing so. – Ilmari Karonen Jan 30 '14 at 11:25
• @figlesquidge original means Binary Goppa codes we already use from 1978 on McEliece cryptosystem. there are a few implementation available and looks like FlexiProvider is the best one. The attack effect these implementations? for mceliece parameters last recommendation says to achieve 128bit security we need ${n,k,t}$ to be as ${2960,2288,56}$ with 57 error added from sender(?). is that still ok? – fractal Jan 30 '14 at 15:36
• The target of the attack is a wide class of algebraic geometry codes, while the binary Goppa code is a subcode of them. It seems hard to apply the attack to the subcode case. – xagawa Feb 2 '14 at 1:57
• Nb: Paper has now been accepted for Eurocrypt14 [link] – figlesquidge Feb 17 '14 at 14:28