New candidates for multivariate trapdoor functions and new multivariate public key encryption schemes

Abstract

Abstract: In this thesis we present a new method for building pairs of HFE1 polynomials of high degree, in such a way that the map constructed with this pair is easy to invert. The inversion is accomplished using a low degree polynomial of Hamming weight three, which is derived from a special reduction via Hamming weight three polynomials produced by these two HFE polynomials. This allows us to build new candidates for multivariate trapdoor functions in which we use the pair of HFE polynomials to fabricate the core map. Using this new multivariate trapdoor function we derive an encryption scheme in a similar way as the HFE scheme is created. We show that this encryption scheme is relatively efficient and that it resists the attacks that have threatened the security of HFE. Finally, we propose parameters for a practical implementation of our cryptosystem.

Resumen: En esta tesis presentamos un nuevo método para construir parejas de polinomios HFE2 de grado alto, de tal manera que la función construida con esta pareja es fácil de invertir. La inversión se lleva a cabo utilizando un polinomio de grado bajo y de peso de Hamming tres, el cual se deriva por medio de una reducción especial, a través de polinomios de peso de Hamming tres producidos a partir de estos dos polinomios HFE. Esto nos permite construir nuevas candidatas para funciones de puerta trasera multivariadas, en las cuales utilizamos la pareja de polinomios HFE para construir la función central. Utilizando esta nueva función de puerta trasera multivariada derivamos un esquema de cifrado de una manera similar a como se construye el esquema HFE. Demostramos que este esquema de cifrado es relativamente eficiente y que resiste los ataques que han amenazado la seguridad de HFE. Finalmente, proponemos parámetros para una aplicación práctica de nuestro criptosistema.