TitlePublic key cryptosystems based on algebraic geometry codes
Professor/a organitzador/aMaria Bras-Amorós
InstitutionTechnische Universiteit Eindhoven
Date 10-11-2014 12:00
SummaryThis is a report on the McEliece public key cryptosystem based on algebraic geometry codes. In [3, 4] it is explained how a representation (Y, Q, F ) is retrieved efficiently from a generator matrix of the algebraic geometry code CL (X , P, E) for a given curve X , an n-tuple P of points on the curve and a divisor E. This result is not sufficient to obtain a polynomial attack on the public key cryptosystem based on these codes. In  a polynomial time attack is given using the idea of an error correcting pair . It runs in O(n4 ) elementary operations in Fq , where n denotes the code length. Compared to previous attacks, it allows to recover a decoding algorithm for the public key even for codes from high genus curves.
Recently the attack was extended to subcodes of algebraic geometry codes . The problem for subfield subcodes of algebraic geometry codes is still open. Joint work with Alain Couvreur, Irene Márquez-Corbella, Edgar Martínez-Moro
and Diego Ruano. See [1, 3, 4].
 A. Couvreur and I. Marquez–Corbella and R. Pellikaan, “A polynomial time attack against algebraic geometry code based public key cryptosystems”, ISIT 2014, pp. 1446, 2014.
 A. Couvreur and I. Marquez–Corbella and R. Pellikaan, “Cryptanalysis of public-key cryptosystems that use subcodes of algebraic geometry codes”, 4ICMCTA, 2014.
 Márquez-Corbella, I. and Martínez-Moro, E. and Pellikaan, R. “On the unique representation of very strong algebraic geometry codes”, Designs, Codes and Cryptography 70, pp. 215-230, 2014.
 Márquez-Corbella, I. and E. Martínez-Moro and R. Pellikaan and D. Ruano, “Computational aspects of retrieving a representation of an algebraic geometry code”, Journ. Symb. Comput. 64, pp. 67–87, 2014.
 Pellikaan, R., “On decoding by error location and dependent sets of error positions”, Discrete Math. 106–107, pp. 369–381, 1992.