Cubic multivariate cryptosystems based on big field constructions and their vulnerability to a min-rank attack
In this work we analyze the security of cubic cryptographic constructions with respect to rank weakness. We detail how to extend the big field idea from quadratic to cubic, and show that the same rank defect occurs. We extend the min-rank problem and propose an algorithm to solve it in this setting....
- Autores:
-
Escudero Ospina, Daniel Esteban
- Tipo de recurso:
- Fecha de publicación:
- 2019
- Institución:
- Universidad Nacional de Colombia
- Repositorio:
- Universidad Nacional de Colombia
- Idioma:
- spa
- OAI Identifier:
- oai:repositorio.unal.edu.co:unal/69559
- Acceso en línea:
- https://repositorio.unal.edu.co/handle/unal/69559
http://bdigital.unal.edu.co/71489/
- Palabra clave:
- 51 Matemáticas / Mathematics
Criptograffía de clave pública
Criptografía multivariada
public-key cryptography
multivariate cryptography
cubic polynomials
- Rights
- openAccess
- License
- Atribución-NoComercial 4.0 Internacional
Summary: | In this work we analyze the security of cubic cryptographic constructions with respect to rank weakness. We detail how to extend the big field idea from quadratic to cubic, and show that the same rank defect occurs. We extend the min-rank problem and propose an algorithm to solve it in this setting. We show that for fixed small rank, the complexity is even lower than for the quadratic case. However, the rank of a cubic polynomial in n variables can be larger than n, and in this case the algorithm is very inefficient. We show that the rank of the differential is not necessarily smaller, rendering this line of attack useless if the rank is large enough. Similarly, the algebraic attack is exponential in the rank, thus useless for high rank. |
---|