Paper 2018/110

Rank Analysis of Cubic Multivariate Cryptosystems

John Baena, Daniel Cabarcas, Daniel Escudero, Karan Khathuria, and Javier Verbel

Abstract

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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. PQCrypto 2018
Keywords
multivariate cryptographycubic polynomialstensor rankmin-rank
Contact author(s)
dcabarc @ unal edu co
History
2018-01-30: received
Short URL
https://ia.cr/2018/110
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/110,
      author = {John Baena and Daniel Cabarcas and Daniel Escudero and Karan Khathuria and Javier Verbel},
      title = {Rank Analysis of Cubic Multivariate Cryptosystems},
      howpublished = {Cryptology ePrint Archive, Paper 2018/110},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/110}},
      url = {https://eprint.iacr.org/2018/110}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.