X24 Down: Cryptanalysis of Hankel-based Multivariate Signatures

Alexandre Camelin; Thai Hung Le; Brice Minaud; Phong Q. Nguyen; Florian Tousnakhoff

Paper 2026/803

X24 Down: Cryptanalysis of Hankel-based Multivariate Signatures

Alexandre Camelin, École normale supérieure, PSL University, CNRS, Inria, France

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.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Preprint.
Keywords: Algebraic cryptanalysis Signature MinRank Exterior Algebra Multivariate cryptography Code-based Cryptanalysis
Contact author(s): Alexandre Camelin @ ens psl eu
thai le @ telecom-paris fr
Brice Minaud @ inria fr
Phong Nguyen @ inria fr
Florian Tousnakhoff @ ens psl eu
History: 2026-04-27: approved; 2026-04-23: received; See all versions
Short URL: https://ia.cr/2026/803
License: CC BY

BibTeX

@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}
}