11
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$
    – Ilmari Karonen
    Jan 30 '14 at 11:25
  • $\begingroup$ @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? $\endgroup$
    – fractal
    Jan 30 '14 at 15:36
  • $\begingroup$ 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. $\endgroup$
    – xagawa
    Feb 2 '14 at 1:57
  • $\begingroup$ Nb: Paper has now been accepted for Eurocrypt14 [link] $\endgroup$
    – Cryptographeur
    Feb 17 '14 at 14:28
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ There is another paper by the authors that attack Wild Goppa codes over quadratic extension (q>2,m=2). $\endgroup$
    – QuadrExAtt
    Jul 22 '14 at 15:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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