Full-Key Recovery and Forgery from One MQOM v2.1 Signature
2026-08-10 • Cryptography and Security
Cryptography and Security
AI summaryⓘ
The authors demonstrate a way to fully recover the secret signing key of MQOM v2.1, a digital signature candidate, from just one valid signature. They use mathematical properties of the signature’s components and the underlying encryption to reconstruct the secret key, allowing them to forge new valid signatures. Their attack was tested on different security categories and consistently succeeded at costs below NIST’s security goals. The work shows that despite public constants changing, the method to break the key from one signature remains effective.
MQOM v2.1NIST signature competitionfull-key-recovery attackdigital signatureAES/Rijndael circuitsBoolean circuitsGray code traversaltree parityideal cipher modelpublic-key validation
Authors
José Luis Delgado
Abstract
We give a full-key-recovery attack on MQOM v2.1, a Round-3 candidate in the NIST additional-signature process, that recovers the complete signing key from one accepted signature and uses it to sign a fresh message. If $δ=\operatorname{FirstBits}_λ(x)$ is the prefix of the witness $x$, the sibling path determines a public value $A$ such that tree parity gives $s=δ\oplus A$. Substitution into the hidden-leaf commitment yields $$\mathsf{Enc}_K(δ\oplus A)=T\oplus\mathsf{LinOrtho}(δ)$$ with public values $K$ and $T$. The correction in the same signature expands a solution into a complete witness, while the public MQ relation identifies those yielding valid signing keys; serializing such a witness gives the secret key, enabling a fresh-message signature accepted by the reference verifier. We evaluate this equation over the specified AES/Rijndael circuits using retained circuit state along a Gray traversal. Complete-domain scans for Categories I and V cost $2^{142.335112}$ and $2^{271.794162}$ Boolean gates. Category-III scans cover $1/2+2^{-20}$ and $0.580004770183$ of the domain at costs of $2^{206.774558}$ and $2^{206.988685}$ gates. All four totals are below the NIST security benchmarks. Reduced-domain runs against the reference implementation recover the byte-exact witness and key in all three categories and produce a fresh-message forgery accepted by the reference verifier. Independently generated source-syntax circuits evaluate the fixed ciphers over the stated domains and translated L3 prefixes, while an exact ideal-cipher factorial-moment bound controls additional equation preimages passed to public-key validation. Every value in the equation is fixed by the accepted transcript, so salt-bound global-root expansion changes its public constants without removing the one-signature recovery channel.