Cryptology ePrint Archive: Report 2018/110

Rank Analysis of Cubic Multivariate Cryptosystems

John Baena and Daniel Cabarcas and Daniel Escudero and 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.

Category / Keywords: public-key cryptography / multivariate cryptography, cubic polynomials, tensor rank, min-rank

Original Publication (in the same form): PQCrypto 2018

Date: received 29 Jan 2018

Contact author: dcabarc at unal edu co

Available format(s): PDF | BibTeX Citation

Version: 20180130:212305 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]