Cryptology ePrint Archive: Report 2014/064

A Polynomial Time Attack against Algebraic Geometry Code Based Public Key Cryptosystems

Alain Couvreur and Irene Márquez-Corbella and Ruud Pellikaan

Abstract: 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.

Category / Keywords: public-key cryptography / Algebraic Geometry codes

Date: received 28 Jan 2014

Contact author: irene marquez-corbella at inria fr

Available format(s): PDF | BibTeX Citation

Version: 20140128:181238 (All versions of this report)

Short URL: ia.cr/2014/064

Discussion forum: Show discussion | Start new discussion