Departamento de Computación

Criptosistemas asimétricos de clave pública, tales como RSA o ElGamal/ECC, podrán convertirse en esquemas inseguros cuando el cómputo cuántico sea una realidad. En 1994, Peter Shor publicó un algoritmo cuántico capaz de resolver los problemas antes mencionados en tiempo polinomial. Hay afortunadamente, otros criptosistemas que se supone son problemas intratables y resisten el ataque del algoritmo de Shor. A estos criptosistemas se les conoce como criptosistemas post-cuánticos. Uno de estos criptosistemas es el conocido como de ecuaciones cuadráticas de varias variables. Los criptosistemas de clave pública de ecuaciones en varias variables, se basan en la dificultad de resolver un sistema de ecuaciones no lineales en un campo ´nito. Por ventajas de cálculo computacional, se emplean sistemas de ecuaciones cuadráticas y al problema de resolver estos sistemas cuadráticos, se le conoce como el problema de varias variables cuadrático. En este trabajo, un conjunto de polinomios cuadráticos formará la clave pública y encontrar la solución a este conjunto de polinomios, para que se cumpla con una cierta imagen deseada, es el problema intratable en el que se basan los protocolos de autenticación y cifrado planteados. La autenticación de conocimiento nulo perfecto que proponemos, se basa en la autenticación reto/respuesta, pero es innovadora en el sentido que el verificador no adquiere ningún conocimiento nuevo cuando el probador responde al reto. Por la forma en que se construye este algoritmo de autenticación, el verificador realiza una pregunta al probador, de algo que de antemano ya conoce como respuesta y por lo tanto, el probador no revela ninguna información secreta, sólo ratifica lo que el verificador ya sabe. Por otra parte, presentamos también un algoritmo de cifrado, usando esta misma infraestructura. En este caso, Beto que quiere enviar un mensaje cifrado a Alicia, pide a ´esta que encuentre los valores de las variables de los polinomios, que generan una imagen deseada de la clave pública. Cuando Alicia tiene esta solución, Beto envía a Alicia un nuevo polinomio que representa el cifrado de un bit del texto plano. Alicia que conoce la solución a los polinomios de la clave pública, podrá sustituir los valores que calculo, en el polinomio enviado, para encontrar así el bit cifrado por Beto. Presentamos los fundamentos teóricos de las dos propuestas anteriores y los resultados obtenidos de las implementaciones de los algoritmos para dichas propuestas. Se incluye además la forma en que se representan los polinomios públicos y el detalle de las estructuras que forman la clave privada. Estos resultados, junto con la teoría correspondiente, muestran que nuestra propuesta es factible de implementarse desde ahora, preparándonos al cómputo cuántico, cada día más cercano.

Abstract

Public key asymmetric cryptosystems, such as RSA or ElGamal/ECC, could turn into insecure schemes when quantum computing becomes a reality. In 1994, Peter Shor published a quantum algorithm capable to resolve the above problems in polynomial time. Fortunately, there are others cryptosystems, that supposedly resist Shor's algorithm. These are known, as post-quantum cryptosystems and one of them is the multivariate quadratic equations system. Multivariate equations public key cryptosystems are based on the difficulty to resolve a non-linear system of equations in a finite field. Because of computational power, quadratic equations are used and the problem to resolve these quadratic systems, is known as the multivariate quadratic problem. In the present work, the set of quadratic polynomials will be the public key and finding the values of the variables in order to satisfy a defined image, is the intractable problem that the authentication and encryption protocols presented here, are based on. The perfect zero knowledge authentication protocol, presented in this thesis, is the well known challenge/response method, however it is innovative in the sense that the verifier does not acquire any new knowledge when the prober respond the challenge. The way this authentication algorithm is built, only allows the verifier, to receive information of something that beforehand, he already knows, therefore the prober does not disclose any secret information, he only confirms what the verifier already knows. On the other hand, we also present an encryption algorithm, using this same infrastructure. In this case, Bob who wants to send an encrypted message to Alice, ask her to find the values of the variables in the set of public polynomials in order that those polynomials comply with a certain image. When Alice finds the values of those variables, Bob sends to Alice a new polynomial, that when evaluated in the values found by Alice will reveal the encrypted bit. We present in this thesis, the theoretical fundamentals of the two proposals mentioned above as well as the obtained results of the implemented algorithms. Public polynomials representation and details of the private key is also included. These results, along with the corresponding theory, shows that our proposals are feasible to implement now, preparing ourselves to the quantum computing era, each day closer.