Search papers, labs, and topics across Lattice.
This paper presents a full-key-recovery attack on the MQOM v2.1 signature scheme, demonstrating that the complete signing key can be extracted from a single accepted signature, allowing for the signing of new messages. The authors utilize a combination of tree parity and hidden-leaf commitments to derive the secret key, achieving this with computational costs that remain below NIST security benchmarks. The attack's effectiveness is validated through reduced-domain runs that successfully recover the signing key and produce fresh-message forgeries accepted by the reference verifier.
Extracting a complete signing key from just one accepted signature reveals critical vulnerabilities in the MQOM v2.1 signature scheme.
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 $\delta=\operatorname{FirstBits}_{\lambda}(x)$ is the prefix of the witness $x$, the sibling path determines a public value $A$ such that tree parity gives $s=\delta\oplus A$. Substitution into the hidden-leaf commitment yields $$\mathsf{Enc}_K(\delta\oplus A)=T\oplus\mathsf{LinOrtho}(\delta)$$ 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.
