Paper 2026/803

X24 Down: Cryptanalysis of Hankel-based Multivariate Signatures

Thai Hung Le, École normale supérieure, PSL University, CNRS, Inria, France, LTCI, Telecom Paris, Institut Polytechnique de Paris, France

Brice Minaud, École normale supérieure, PSL University, CNRS, Inria, France

Phong Q. Nguyen, École normale supérieure, PSL University, CNRS, Inria, France

Florian Tousnakhoff, École normale supérieure, PSL University, CNRS, Inria, France

Abstract

The X24 multivariate signature scheme was introduced by Di Muzio, Feussner, and Semaev at PQCrypto 2026. It offers remarkably short signatures, together with a new design approach for multivariate signatures that departs from the typical UOV and HFE frameworks. In this work, we present an efficient cryptanalysis of X24. Our attack recovers the secret key from the public key in time $O(q \cdot \mathsf{poly}(n))$, where $n$ is the number of field elements in the signature, and $q$ is the order of the finite field. An implementation of the attack recovers the secret key in a few minutes on the full X24 parameters. The attack makes essential use of the exterior algebra, and shows a different way of using that algebra for multivariate cryptanalysis, compared to the wedge attack introduced by Ran at Eurocrypt 2026. Another notable feature of the attack is that it eventually reduces the cryptanalysis of X24 to the cryptanalysis of a McEliece variant using Generalized Reed-Solomon codes, drawing an unexpected connection between multivariate and code-based cryptanalysis.

@misc{cryptoeprint:2026/803,
      author = {Alexandre Camelin and Thai Hung Le and Brice Minaud and Phong Q. Nguyen and Florian Tousnakhoff},
      title = {X24 Down: Cryptanalysis of Hankel-based Multivariate Signatures},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/803},
      year = {2026},
      url = {https://eprint.iacr.org/2026/803}
}