A polynomial-time key recovery attack of Facto-DSA

Simon Abelard; Ludovic Perret; Hao Shi

Paper 2026/1403

A polynomial-time key recovery attack of Facto-DSA

Simon Abelard

, Laboratoire de Recherche de l’EPITA (LRE), EPITA, France, Sorbonne Université, CNRS, LIP6, Paris, France

Ludovic Perret

, Laboratoire de Recherche de l’EPITA (LRE), EPITA, France, Sorbonne Université, CNRS, LIP6, Paris, France

Hao Shi, Laboratoire de Recherche de l’EPITA (LRE), EPITA, France, École Polytechnique, Institut Polytechnique de Paris, France

Abstract

This work introduces a polynomial-time attack on the signature scheme Facto-DSA. We provide an implementation that breaks all proposed parameter sets, including the largest, in under one minute on a standard laptop. These results question the suitability of multivariate polynomial factorization as a foundation for robust cryptographic schemes.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Preprint.
Keywords: Multivariate Cryptography Cryptanalysis
Contact author(s): simon abelard @ epita fr
ludovic perret @ epita fr
hao shi @ polytechnique edu
History: 2026-07-12: approved; 2026-07-09: received; See all versions
Short URL: https://ia.cr/2026/1403
License: CC BY

BibTeX

@misc{cryptoeprint:2026/1403,
      author = {Simon Abelard and Ludovic Perret and Hao Shi},
      title = {A polynomial-time key recovery attack of Facto-{DSA}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/1403},
      year = {2026},
      url = {https://eprint.iacr.org/2026/1403}
}