Introducción a la Criptografía post-cuántica basada en teoría de códigos (2021)
La criptografía es la disciplina que estudia el arte de transformar un mensaje (llamado texto plano) en un mensaje no legible por un tercero (llamado texto cifrado) utilizando una clave secreta. Los protocolos de cifrado, descifrado y construcción de claves es lo que llamamos un criptosistema. Existen dos grandes familias: 1. Criptografía simétrica: conformada por los criptosistemas que utilizan una misma clave secreta para cifrar y descifrar mensajes. 2. Criptografía asimétrica o a clave pública: son aquellos en los que los procesos de cifrado y descifrado son llevados a cabo por dos claves, una pública para el proceso de cifrado y otra secreta para descifrado. La criptografía simétrica tiene dos principales problemas: las personas que van a comunicarse deben tener un primer encuentro para definir la clave secreta y por otro lado para cada pareja de personas que se quieran comunicar debe existir una clave secreta. Ambos problemas son resueltos por la criptografía a clave pública ya que en este caso no hay necesidad de ponerse de acuerdo con la clave y por otro lado una misma clave pública le permite a una persona recibir mensajes de muchas personas sin que estas tengan la posibilidad de descifrar el mensaje. Esto hace que la criptografía a clave pública sea la base del comercio electrónico. En 1978 se propuso el RSA, el cual fue el primer criptosistema a clave pública. Más de 40 años después los criptosistemas a clave pública que se utilizan dependen únicamente de dos problemas matemáticos: la factorización y el logaritmo discreto. Es decir que, si de alguna manera lográramos resolver estos problemas, toda la criptografía a clave pública quedaría expuesta e insegura. Sin embargo, en 1994, Peter Shor, publicó un algoritmo en el cual, de tener un computador cuántico suficientemente poderoso, podría resolver estos dos problemas. La carrera de varias empresas y centros de investigación por crear un computador cuántico ha sido bastante activa y ya se han creados algunos en los cuales se ha podido implementar el algoritmo de Shor y factorizar, por ejemplo, el número 15. Como respuesta a este nuevo escenario, en donde la computación cuántica pone en jaque a toda la criptografía a clave pública, se presenta la criptografía post-cuántica, la cual consiste en buscar criptosistemas que sean resistentes a ataques hechos en computadores convencionales y cuánticos. El instituto Nacional de estándares y Tecnología de Estados Unidos (llamado NIST por sus siglas en inglés, National Institute of Standards and Technology) preocupado por esta situación, y buscando promover la investigación en critpografía post-cuántica organizó un concurso público para buscar un criptosistema post-cuántico que se pueda convertir en el estándar. Existen diferentes familias que han inspirado algunas propuestas de criptosistemas post-cuánticos: la teoría de códigos, retículos funciones de Hash y álgebra multivariada que se vienen estudiando aproximadamente desde los años 2000 y recientemente se trabajan con isogeny en curvas elípticas. En este trabajo de grado nos concentramos en la criptografía post-cuántica basada en la teoría de códigos. En 1978, McEliece propuso un criptosistema que no tuvo mucha acogida dado su tamaño de la clave secreta, pero que resulta ser resistente a ataques post-cuánticos. En los últimos 20 años se han propuesto varias variantes del McEliece, que usan la misma idea de basarse en códigos correctores de errores, pero que usan protocolos diferentes para tratar de reducir el tamaño de la clave. Hasta el momento la mayoría han sido atacados, existen algunos vigentes, pero todavía la comunidad no tiene confianza en su seguridad ya que son muy recientes. En esta tesis se realizó un documento donde se introduce las bases matemáticas, la criptografía, la teoría de corrección de errores y la computación cuántica necesaria para poder entender la criptografía post-cuántica basada en teoría de códigos. Al final de la tesis introducimos los criptosistemas de McEliece y Niederreiter así como la versión del criptosistema de McEliece que llegó a la última etapa de la competencia de la NIST (todavía en curso).