Facto-DSA

The hidden zero subspace is found by Gröbner bases, not by guessing

Practical · Tested at small scale · Cause: construction

Property: key recovery

Cost against claim: Facto-DSA-128 key recovery ≈2⁵² against 2¹²⁸

The public map vanishes on the n-dimensional subspace K2 = ker(L2). Recovering a vector of it is priced by the specification as a random search over qⁿ possibilities, but restricting the public map to a random (n+1)-dimensional subspace gives a system with a guaranteed solution, which a Gröbner-basis computation solves at degree n+1.

Evidence

Solving degree n+1 observed for n up to 7, and reproduced independently for n = 4, 5 and 6. The full-size costs are extrapolated with the linear-algebra exponent ω = 2.81.

Cause in the specification, traced to the specification text.

Limits

Full-size costs are extrapolated, not computed.

Credit

First public report: Kris Kwiatkowski (PKC forum, also ngcc.dev sign-10-1, 2026-09-22). Found independently by PQC-X.

A polynomial-time key recovery on an earlier, quadratic version of Facto-DSA was published by Abelard, Perret and Shi (ePrint 2026/1403, July 2026); whether it applies to the submitted cubic version is not established.

The digest space is too small at levels 128 and 512

Minor break · Argued · Cause: parameter size

Property: existential unforgeability

Cost against claim: digest collision 2¹⁰⁴ against 2¹²⁸

Verification depends on the message only through a digest of m elements of GF(q): 208, 512 and 992 bits for the three levels. A birthday collision on that digest transfers a signature from one message to another.

Evidence

Cause in the specification, traced to the specification text.

Limits

Generic; fixed by lengthening the digest.

Credit

Found by PQC-X.