Efficient ZHFE Key Generation

In this paper we present a new algorithm to construct the keys of the multivariate public key encryption scheme ZHFE. Constructing ZHFE’s trapdoor involves finding a low degree polynomial of q-Hamming-weight-three, as an aid to invert a pair of q-Hamming-weight-two polynomials of high degree and high rank. This is done by solving a large sparse linear system of equations. We unveil the combinatorial structure of the system in order to reveal the hidden structure of the matrix associated with it. When the system’s variables and equations are organized accordingly, an almost block diagonal shape emerges. We then exploit this shape to solve the system much faster than when ZHFE was first proposed. The paper presents the theoretical details explaining the structure of the matrix. We also present experimental data that confirms the notable improvement of the key generation complexity, which makes ZHFE more suitable for practical implementations. Keywords Multivariate public key cryptography Encryption schemes ZHFE Block diagonal matrix

• Autores: Baena Giraldo, John Bayron; Cabarcas Jaramillo, Daniel; Porras Barrera, Jaiberth; Verbel Herrera, Javier Alfonso
• Tipo de recurso: Article of investigation
• Fecha de publicación: 2016
• Institución: Tecnológico de Antioquia
• Repositorio: Repositorio Tdea
• Idioma: eng
• OAI Identifier: oai:dspace.tdea.edu.co:tdea/4202
• Acceso en línea: https://dspace.tdea.edu.co/handle/tdea/4202
• Palabra clave: Multivariate public key cryptography; Criptografía de clave pública multivariante; Encryption schemes; Esquemas de cifrado; ZHFE; Block diagonal matrix; Matriz diagonal de bloques; Algoritmo; Algorithm; Algorithme
• Rights: closedAccess
• License: http://purl.org/coar/access_right/c_14cb