Eciency and security of ZHFE

Abstract

In this thesis we describe the hidden structure in the key generation process for the multivariate public key cryptosystem ZHFE. Based on such structure, we propose a new method for the mentioned process. We compare the time and memory required between our new method and the original key generation process. We also analyze the security of ZHFE with respect to the MinRank Attack. We show that with high probability there exist a linear combination of Frobenious power of the core polynomials F and ~ F of low rank. Furthermore, we show that such linear combination can be extracted from the public key.

Resumen: En esta tesis describimos la estructura oculta en el proceso de generación de llave para el criptosistema de llave pública multivariada ZHFE. Basados en tal estructura, proponemos un nuevo método para tal proceso. Comparamos los tiempos y memoria requerida entre nuestro nuevo método y el método original de generación. También analizamos la seguridad de ZHFE respecto al Ataque del MinRank. Demostramos que con alta probabilidad existe de una combinanción lineal de las potencias de Frobenious de los polinomios centrales F y ~ F de rango pequeño. Más aún, demostramos que tal combinación puede ser extraída de la llave pública.