Departamento de Computación

La criptografía de clave pública es utilizada día a día a la hora de compartir cualquier tipo de información utilizando canales inseguros. A la fecha, en la práctica algunos de los esquemas más utilizados son RSA, ElGamal y los basados en curvas elípticas, los cuales siguen siendo resistentes a ataques utilizando nuestro cómputo actual. Sin embargo, en una computadora cuántica esta criptografía ya estaría rota gracias al algoritmo de Shor para resolver el problema de factorización y el del logaritmo discreto en tiempo polinomial. Por esta razón es que se han estado estudiando otros esquemas criptográficos que sean capaces de reemplazar los esquemas utilizados hoy en día siendo resistentes a ataques empleados desde una computadora cuántica.

Una de esas alternativas es la criptografía sobre varias variables que ha sido de gran interés en los últimos años, debido a que resolver sistemas de polinomios de grado dos con más de dos variables ha sido demostrado ser un problema NP-difícil, por lo que dicho paradigma criptográfico cae entre los esquemas de criptografía post-cuántica. Uno de los problemas de esta criptografía es que las claves tiendan a ser muy grandes, las claves públicas siendo sistemas de ecuaciones de grado dos en varias variables y las claves privadas parejas de transformaciones afines en espacios vectoriales sobre un campo infinito. Presentamos una plataforma de experimentación llamada MQCrypto que incorpora las implementaciones de un total de diez esquemas de criptografía sobre varias variables, en MQCrypto es posible generar instancias de claves de cada uno de los esquemas y utilizarlas para realizar procesos de firma y verificación. De igual manera se propone una manera de representar y codificar tanto las claves públicas y las privadas con la que se logra una significante reducción en su tamaño comparándola con la representación usual de las mismas instancias.

Abstract

Public key cryptography is used in day to day communication when transferring data through insecure channels. Nowadays, some of the most used cryptographic schemes in practice are RSA, ElGamal and based on elliptic curve, being resistant to attacks with our actual computing resources. However, when quantum computing becomes a reality, these schemeswould turn to be insecure, as Shor published in 1994 a quantum algorithm capable of solving the factorization and discrete logarithm problem in polynomial time. Hence, some cryptographic schemes capable of supporting attacks from a quantum computer have been widely studied. One of those cryptographic schemes is Multivariate Cryptography, whose security relies in solving a system of multivariate polynomials over a nite eld.

Multivariate cryptography has been of great interest in recent years, due to the fact that solving systems of quadratic