THE QUANTUM INTELLIGENCER

Full Private Key Recovery from One MQOM v2.1 Signature In Plain English: This research finds a serious flaw in a new type of digital signature system called MQOM v2.1, which was being considered for global cybersecurity standards. The system is supposed to keep secrets safe even from future quantum computers. But the researchers discovered that just one signed message is enough to uncover the entire secret key. With that key, an attacker can impersonate the signer and create fake but valid signatures. This means the system isn’t secure and shouldn’t be used, no matter how advanced it seems. Summary: The paper presents a full-key-recovery attack on MQOM v2.1, a post-quantum digital signature scheme that reached Round 3 of the NIST Post-Quantum Cryptography Standardization Project. The attack exploits deterministic relationships within the signature structure to recover the complete private key from just one valid signature. Specifically, the prefix of the witness value ($\delta$) and the sibling path in the Merkle tree reveal a public value $A$, allowing computation of $s = \delta \oplus A$. Substituting this into the hidden-leaf commitment equation yields $\mathsf{Enc}_K(\delta \oplus A) = T \oplus \mathsf{LinOrtho}(\delta)$, where all parameters except the secret key are known or derivable from the signature transcript. The authors solve this equation by evaluating it over AES/Rijndael circuits using retained internal states during a Gray-code traversal of the input space. They perform domain scans across multiple categories: Category I and V require $2^{142.34}$ and $2^{271.79}$ Boolean gates respectively, while Category III covers over half the domain at around $2^{206.8}$ gates—costs that fall below NIST's minimum security requirements. These theoretical analyses are backed by practical experiments on the reference implementation, where the exact byte-level witness and secret key are recovered in all tested categories. Critically, the attack enables creation of a fresh-message signature that passes verification, demonstrating real-world exploitability. Even modifications like salt-bound global-root expansion fail to eliminate the vulnerability because all values in the equation are fixed by the accepted signature transcript. This indicates a fundamental design flaw rather than an implementation oversight. As a result, MQOM v2.1 cannot provide the claimed security level and should not proceed in the NIST standardization process. Key Points: - A single valid signature from MQOM v2.1 is sufficient to recover the full private signing key. - The attack uses public values from the signature transcript and structural properties of the Merkle tree and hidden-leaf commitment. - By solving an equation involving AES/Rijndael circuits via Gray traversal, attackers can reconstruct the secret witness and key. - Computational costs for key recovery across various domains are below NIST’s minimum security benchmarks. - Practical tests successfully recovered keys and generated forged signatures accepted by the official verifier. - Salt-based countermeasures do not mitigate the attack, as all relevant values are fixed by the signature itself. - This breaks the core security promise of MQOM v2.1 and disqualifies it as a viable post-quantum signature candidate. Notable Quotes: - "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." - "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." Data Points: - Full key recovery achieved with $2^{142.335112}$ Boolean gates (Category I). - Category V scan requires $2^{271.794162}$ Boolean gates. - Category III covers $1/2 + 2^{-20}$ of the domain at $2^{206.774558}$ gates. - Another Category III run covers 58.000477% of the domain at $2^{206.988685}$ gates. - All attack costs are below NIST security benchmarks. - Successful byte-exact key recovery demonstrated on reference implementation. - Fresh-message forgery produced and verified as valid. - Attack works across Categories I, III, and V. Controversial Claims: - Claiming full key recovery from just one signature challenges the assumed security margin of MQOM v2.1, which was expected to withstand chosen-message attacks. - Asserting that domain-wide circuit evaluations stay below NIST security thresholds contradicts the scheme’s submission claims. - The assertion that salt-based defenses are ineffective suggests deeper flaws than previously thought possible in this class of schemes. Technical Terms: - MQOM v2.1: A post-quantum digital signature scheme based on multivariate quadratic equations and hash trees, submitted to NIST. - NIST Additional-Signature Process: A competition to standardize post-quantum cryptographic algorithms resistant to quantum attacks. - Full-Key Recovery: An attack that completely exposes the private key used for signing. - Hidden-Leaf Commitment: A cryptographic mechanism in hash-based signatures that hides the leaf node of a Merkle tree until revealed during signing. - Gray Traversal: A method of systematically exploring binary inputs in minimal-change order to optimize circuit evaluation. - Boolean Gates: Basic units of computational complexity measuring logic operations in circuit models. - Witness: A secret value used in zero-knowledge or structured proofs to satisfy a public relation. - FirstBits_λ(x): Function extracting the first λ bits of a bitstring x, used as a prefix in the attack. - LinOrtho(δ): A linear-orthogonal transformation applied to the witness prefix in the commitment equation. - Salt-Bound Global-Root Expansion: A proposed defense modifying public constants via randomness - shown ineffective here. —Ada H. Pemberley Dispatch from The Prepared E0