¿Qué familia de códigos es adecuada para la criptografía basada en códigos?

Abstract

Este trabajo comienza explicando la diferencia entre Teor´ıa de c´odigos y Criptograf´ıa, y de c´omo siendo dos ´areas tan diferentes se pueden fusionar ambas en Criptograf´ıa basada en C´odigos (CBC), una propuesta interesante para resistir ataques con un ordenador cu´antico (Criptograf´ıa post-cu´antica). Estos esquemas requieren de familias de c´odigos con algoritmos eficientes de decodificaci´on y que tengan la propiedad de que sean indistinguibles de un c´odigo lineal aleatorio. En este trabajo vamos a centrarnos en estudiar las familias de c´odigos de evaluaci´on de polinomios. El trabajo contin´ua con el Cap´ıtulo 1, una introducci´on a la Teor´ıa de c´odigos; en particular conceptos de c´odigos lineales, c´ıclicos y restricci´on de c´odigos lineales a otros subcuerpos. Luego, en el Cap´ıtulo 2 nos centramos en algunas familias de c´odigos de evaluaci´on de polinomios. Introducimos estas familias y estudiamos algunas de sus propiedades fundamentales; en particular, los c´odigos Reed-Solomon y sus generalizaciones, para los que explicamos un algoritmo de decodificaci´on eficiente, y los c´odigos Reed-Muller, que son c´odigos de evaluaci´on en varias variables. Finalmente, en el Cap´ıtulo 3, trabajamos con la restricci´on de las familias antes nombradas a subcuerpos m´as peque˜nos, como los c´odigos Goppa, que pueden ser estudiados como la restricci´on de un c´odigo Reed-Solomon generalizado. Adem´as, en este ´ultimo cap´ıtulo explicamos porqu´e siguen siendo interesantes estos ´ultimos c´odigos en criptograf´ıa.

This work begins by explaining the difference between Coding Theory and Cryptography, and even being two different areas how they can be merged into Code-based Cryptography (CBC), an interesting proposal to resist attacks from a quantum computer (Post-quantum cryptography). These schemes require a family of codes with an efficient decoding algorithm and which have the property that they are indistinguishable from a random linear code. In this work we will focus on studying the families of polynomial codes. The work continues with Chapter 1, an introduction to Coding theory; in particular concepts of linear codes, cyclic codes and subfield-subcodes. Then, in Chapter 2, we focus on some families of polynomial codes. We introduce these families and we study some of their fundamental properties; in particular, Reed-Solomon codes and their generalizations, for which we explain an efficient decoding algorithm, as well as Reed-Muller codes, which are polynomial codes in several variables. Finally, in Chapter 3, we work with the subfield-subcodes of some of the previously named families, such as Goppa codes, which can be studied as the subfield-subcode of a generalized Reed-Solomon code. Furthermore, in this last chapter we explain why these last codes are still interesting in cryptography.