Criptografía basada en códigos correctores: alternativa a los clásicos criptosistemas de clave pública
Résumé
Criptografía basada en códigos correctores: alternativa a los clásicos criptosistemas de clave pública Irene Márquez-Corbella 1 En un mundo en que la utilización de datos electrónicos es imprescindible tanto en la vida personal como en la institucional, el uso de la criptografía ya no es opcional: es imperativo. Sin embargo, se está convirtiendo en una tarea ardua encontrar primitivas criptográficas eficientes que sobrevivan a ataques crip-toanalíticos. Por ejemplo, la seguridad de casi todos los criptosistemas de clave pública-aquellos que no requieren un intercambio inicial de secretos-se basa hoy en día sólo en dos problemas: la factorización y el logarítmo discreto. Por lo tanto, avances en estos problemas o la construcción de ordenadores cuánticos cambiarán de forma drástica el panorama actual. La criptografía basada en códigos correctores junto con la criptografía basada en retículos (en inglés: lattice based cryptography), la criptografía multivariable o la criptografía basada en funciones hash son las principales técnicas de las que disponemos para resistir a ataques por ordenador cuántico. McEliece en 1978 [3] propone el primer criptosistema basado en la teoría de códigos correctores, definiendo uno de los sistemas de cifrado más eficientes que existen y que, además, resiste (hasta el momento) cualquier tipo de criptoanálisis. El principio de estos criptosistemas se basa en la siguiente función " trapdoor one-way " : es fácil y rápido codificar mensajes utilizando transformaciones lineales; pero el problema general de decodificación se ha demostrado que es un problema NP-completo para la métrica de Hamming. La " puerta trampa " consiste en que existen ciertas familias de códigos que poseen algoritmos específicos eficientes de decodificación. En su artículo original, McEliece propone utilizar códigos Goppa binarios, y esta opción sigue siendo segura. Pero otras familias de códigos han sido propuestas en un intento de reducir el tamaño de las claves, por ejemplo (y esta lista está lejos de ser exhaustiva): los códigos Reed-Solomon Generalizados [6], los códigos Reed-Muller binarios [8] o los códigos geométricos [2]. Todas estas propuestas han sido atacadas en tiempo polinomial o sub-exponencial [7, 4, 1]. La principal desventaja de estos criptosistemas es el gran tamaño de sus claves. Sin embargo, se han realizado grandes avances en este área (reduciendo la longitud de la clave pero manteniendo el mismo nivel de seguridad). Los nuevos resultados admiten claves muy compactas [5] (alrededor de 5000 bits para alcanzar 80 bits de seguridad), lo que permite comparar estos criptosistemas con el clásico criptosistema RSA. En esta charla presentaremos con detalle el estado de la criptografía basada en códigos correctores y los progresos que ha hecho la comunidad con el fin de estar preparada para el proceso de estandarización.