Decodificación de códigos lineales utilizando conjuntos de información.

Abstract

La criptograf´ıa nace de la necesidad de establecer comunicaciones seguras. En la actualidad, est´a muy presente tanto en nuestra vida personal como institucional, ya que, al mismo tiempo que crece la libertad para comunicarnos, se multiplican los riesgos para la privacidad. Adem´as, la necesidad actual de utilizar y transferir datos electr´onicos hace que el uso de la criptograf´ıa no sea opcional. El principal problema es que la posible aparici´on del ordenador cu´antico tendr´ıa efectos devastadores en la criptograf´ıa que se utiliza actualmente. Por eso, estudiamos una posible soluci´on: el estudio de la criptograf´ıa basada en c´odigos, cuya seguridad se basa en la dificultad de decodificar c´odigos lineales. En este trabajo, estudiamos los algoritmos de decodificaci´on m´as eficientes conocidos, que son aquellos basados en conjuntos de informaci´on. En particular, trabajaremos los algoritmos de Prange (1962), Lee-Brickell (1988) y Stern (1989).

Cryptography arises from the needs to keep safe communications. In a world where the use of electronic data plays a larg part in both personal and institutional life, the proper archiving, retention and encryption is no longer optional. However, the construction of large quantum computers would have dramatically effects on the currently used cryptography. Therefore, we study a possible solution: Code-based Cryptography, whose security is based on the difficulty of decoding linear codes. In particular, we study the best known technique to decode random linear codes: information set decoding algorithms. We will study in this work the decoding algorithms of Prange (1962), Lee-Brickell (1988) and Stern (1989).