International Association
for Cryptologic Research

Algebraic cryptanalysis is an important and versatile tool in the evaluation of the security of various cryptosystems especially in multivariate cryptography. Its effectiveness can be determined by analyzing the Polynomial System Solving problem (PoSSo). However, the polynomial systems arising from cryptanalytic algebraic models often exhibit structure that is crucial for the solving complexity and is often not well understood.

In this paper we turn our focus to multi-homogeneous systems that very often arise in algebraic models. Despite their overwhelming presence, both the theory and the practical solving methods are not complete. Our work fills this gap. We develop a theory for multi-homogeneous systems that extends the one for regular and semi-regular sequences. We define "border-regular" systems and provide exact statements about the rank of a specific submatrix of the Macaulay that we associate to these systems. We then use our theoretical results to define Multi-homogeneous XL - an algorithm that extends XL to the multi-homogeneous case. We further provide fully optimized implementation of Multi-homogeneous XL that uses sparse linear algebra and can handle a vast parameter range of multi-homogeneous systems. To the best of our knowledge this is the first implementation of its kind, and we make it publicly available.