Publicación:

CÓDIGOS REED-SOLOMON TORCIDOS PARA CRIPTOGRAFÍA POSCUÁNTICA

Resumen

La teoría de códigos correctores de errores y la criptografía comparten una misma raíz: la necesidad de transmitir y proteger información de manera confiable incluso en presencia de perturbaciones o adversarios. Desde su aparición a mediados del siglo XX, los códigos Reed-Solomon se consolidaron como una de las familias más poderosas dentro de este campo, gracias a su estructura algebraica sobre cuerpos finitos y a su capacidad de alcanzar la cota de Singleton, condición que los convierte en códigos MDS. En este trabajo se estudia una generalización reciente de dicha familia: los códigos Reed-Solomon torcidos, introducidos por Beelen, Puchinger y Rosenkilde en 2017. La construcción incorpora ℓ términos de torsión, parametrizados por vectores t, h y η sobre el cuerpo base Fq, que modifican la estructura clásica de Vandermonde sin sacrificar, en principio, la distancia mínima óptima. Se presenta de forma detallada la definición de estos códigos, sus matrices generadoras y las condiciones algebraicas precisas bajo las cuales conservan la propiedad MDS, incluyendo dos construcciones explícitas de conjuntos Fq0 -libres de suma-producto. La parte central del trabajo aborda el problema de la decodificación. Se analiza el algoritmo de fuerza bruta, que explora las q ℓ combinaciones posibles de los coeficientes de torsión, aplica un decodificador Reed-Solomon clásico en cada iteración y emplea una verificación de consistencia para descartar soluciones espurias. Se prueba formalmente la corrección y unicidad del algoritmo bajo la hipótesis MDS. Finalmente, se explora la aplicación de estos códigos al criptosistema McEliece. Se describe la construcción del esquema McEliece-TRS, su proceso de cifrado y descifrado, y se discuten las consideraciones de seguridad que lo distinguen de la versión original basada en códigos de Goppa, en particular la mayor dificultad estructural que presenta frente al ataque de Sidelnikov-Shestakov. El análisis se complementa con implementaciones en SageMath que permiten comparar la eficiencia computacional entre el esquema clásico y las variantes torcidas con ℓ = 1 y ℓ = 2 torsiónes, poniendo de manifiesto el costo exponencial en ℓ y las ventajas que ofrece la flexibilidad estructural adicional de esta familia.