Criptografía post-cuántica: Análisis de McEliece y una nueva versión con MPC

Abstract

La seguridad empleada en prácticamente todas comunicaciones realizadas actualmente utiliza una criptografía de clave pública o híbrida mediante el uso de sistemas criptográficos como el RSA, Gamal o de curva elíptica entre otros. Dichos sistemas aunque son actualmente seguros, en cuanto seamos capaces de construir un ordenador cuántico, se conoce un algoritmo que permite romperlos en tiempo polinómico. Por ello, actualmente se están estudiando distintos criptosistemas que sean resistentes a ataques realizados por un ordenador cuántico. El presente documento se centra en el criptosistema de McEliece, el cual es uno de los criptosistemas resistente frente a estos ataques. En adicción se muestran los códigos Reed-Solomon, Goppa y de producto de matrices, que se pueden emplear, entre otros, para construir el criptosistema. Después vemos un posible ataque contra el criptosistema construido a partir de un código Reed-Solomon. También, mostramos el método empleado por Gaborit para intentar eliminar la principal desventaja del criptosistema de McEliece preservando la seguridad, el gran tamaño de las claves. Por último se muestra un método innovador que nos permite reducir notablemente el tamaño de las claves del criptosistema mediante el empleo de códigos de producto de matrices.

The security used in almost all communications currently performed a public key cryptography or hybrid through the use of cryptographic systems such as RSA, Gamal or elliptical curve among others. These systems although they are currently safe, as soon as we are able to build a quantum computer, it is known an algorithm that can break them in polynomial time. For this reason, different cryptosystems that are resistant to attacks carried out by a quantum computer are currently being studied. This paper focuses on the McEliece cryptosystem, which is one of the cryptosystems resistant to these attacks. In addition, Reed-Solomon, Goppa and matrix product codes are shown, which can be used to build the cryptosystem. Afterwards, a possible attack against the cryptosystem built from a Reed-Solomon code is shown. Also, it is shown the method used by Gaborit to try to eliminate the main disadvantage of the McEliece cryptosystem while preserving security,the large size of the keys. Finally, it shows an innovative method that allows us to significantly reduce the size of the cryptosystem keys by using matrix product codes.