Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
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 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 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 at 1:57
    
Nb: Paper has now been accepted for Eurocrypt14 [link] –  figlesquidge Feb 17 at 14:28
add comment

1 Answer 1

My understanding is that the attack only works against McEliece with algebraic geometry codes. The paper by Bernstein, Lange and Peters recommends parameters for McEliece with binary Goppa codes, so the attack does not apply against those parameters.

share|improve this answer
    
There is another paper by the authors that attack Wild Goppa codes over quadratic extension (q>2,m=2). –  QuadrExAtt yesterday
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.