Full-Key Recovery and Forgery from One MQOM v2.1 Signature

• URL: http://arxiv.org/abs/2608.09699v2
• Date: Thu, 13 Aug 2026 14:15:00 GMT
• Title: Full-Key Recovery and Forgery from One MQOM v2.1 Signature
• Abstract summary: We give a full-key-recovery attack on MQOM v2.1, a Round-3 candidate in the NIST additional-signature process.<n>We recover the complete signing key from one accepted signature and use it to sign a fresh message.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  We study tradeoff between solution quality and stability when elements arrive over time.<n>Our algorithm has a future implementation for rational oracle$ with $O(varepsilon-1)$ recourse and separate the existence of universal-price certificates from their efficient algorithms.
  arXiv  Detail & Related papers  (2026-09-09T10:13:43Z)
• A Public-Key-Dependent Adversarial-Deletion Ceiling for Fixed-Alphabet Multi-Bit Pseudorandom Codes [2.1485350418225244]
  A pseudorandom code (PRC) is a keyed error-correcting code whose codewords are computationally indistinguishable from uniform strings.<n>We study publickey PRCs over fixed alphabets against adversarial deletions.
  arXiv  Detail & Related papers  (2026-08-31T21:31:03Z)
• Memorization Is Not Extraction: Tight Differential-Privacy Bounds and Audit Blind Spots [9.539275654775706]
  Memorization in large language models is measured through a zoo of definitions whose formal relations are unknown.<n>We show that differential privacy (DP) is treated as a proxy against all of them at once.
  arXiv  Detail & Related papers  (2026-08-27T23:28:08Z)
• Security Analysis for SCONE Logic Locking [8.289792786302579]
  SCONE [DAC'25] expands a logic locking interface with additional encoded inputs from the original primary inputs.<n>We show that both realizations are vulnerable, but for different reasons.<n>We propose a lightweight non-linear mitigation and show that it does not exhibit the vulnerabilities identified in this paper.
  arXiv  Detail & Related papers  (2026-07-03T12:57:29Z)
• Isolating LLM Alignment from Regex: Zero Coverage and Metric-Dependent Divergence Under Adversarial Mutation [51.56484100374058]
  Previous work found no measurable coverage gain from adding a live Gemini backend behind an active filter.<n>We introduce $L_5$-no-regex -- identical to $L_4$-real (Gemini-2.5-flash, token-budget cap, rate limit, output scrub) but with the nine-pattern filter disabled.<n>We evaluate it against adversarial probes across three sub-languages.
  arXiv  Detail & Related papers  (2026-06-12T18:54:24Z)
• Imbuing Large Language Models with Bidirectional Logic for Robust Chain Repair [44.80087038178069]
  We introduce Teleological Reasoning Infilling (TRI), a training framework that endows decoder-only transformers with a native emphgoal-conditioned bridging capability.<n>At inference, TRI operates as a surgical repair module within a dual-system loop.<n>Experiments on three benchmarks demonstrate that TRI achieves state-of-the-art performance across all tasks, while reducing per-problem token expenditure by 31.2%.
  arXiv  Detail & Related papers  (2026-06-03T15:58:48Z)
• The Security Budget of Code-LLM Prompt Hardening: Provable Limits Under Pass-Only Acceptance [0.0]
  We operationalize the floor as the emphTri-Audit Protocol, a two-axis reporting protocol that separates a prompt-side deductive registry attribute from a model-side empirical corollary.<n>A constrained best-of-family search over deterministic and guarded learned filters on CodeLlama-7B, Qwen2.5-Coder-7B/1.5B and DeepSeek-Coder-6.7B at $n=164$ yields the emphCross-Model Tri-Audit Invariance: of twenty-eight pass-preserving rows, twelve-changed-of-record learned-can
  arXiv  Detail & Related papers  (2026-06-02T08:22:14Z)
• Copy-as-Decode: Grammar-Constrained Parallel Prefill for LLM Editing [2.6382975801439836]
  LLMs edit text and code by autoregressively regenerating the full output, even when most tokens appear verbatim in the input.<n>We study Copy-as-Decode, a decoding-layer mechanism that recasts edit generation as structured decoding over a two-primitive grammar.
  arXiv  Detail & Related papers  (2026-04-20T12:29:53Z)
• Rényi exponent landscape of multipartite entanglement in free-fermion systems [51.56484100374058]
  We show that the Rényi tripartite information $I_3() exhibits a qualitatively $exclusion-dependent scaling at small Fermi momentum.<n>A direct consequence is a replica obstruction: $I_m(n)/I_m(1) sim zm-1 to 0$ for all integer $n geq 2$, so the leading von Neumann signal cannot be reconstructed from integer Rényi data.
  arXiv  Detail & Related papers  (2026-03-09T22:27:00Z)
• Burau representation, Squier's form, and non-Abelian anyons [53.92822954974537]
  We introduce a frequency-tunable, two-dimensional non-Abelian control of operation order constructed from the Burau representation of the braid group $B_3$.<n>The sign change of $Delta(omega)$ across the Squier positivity window reveals alternating constructive and destructive interference of causal orders.<n> Numerical simulations confirm both enhancement and suppression regimes, establishing a minimal $B_3$ braid control.
  arXiv  Detail & Related papers  (2025-10-21T00:25:21Z)
• A Symmetric-Key Cryptosystem Based on the Burnside Ring of a Compact Lie Group [0.0]
  We propose a symmetric-key cryptosystem whose linear action takes place instead in the Burnside ring $A(G)$ of a compact Lie group $G$.<n>Messages of arbitrary finite length are encoded as finitely supported elements of $A(G)$ and encrypted via the Burnside product with $k$.<n>We show that any finite set of observations constrains the action only on a finite-rank submodule $W_Lsubset A(O(2))$, and we show information-theoretic non-identifiability of the key from such data.
  arXiv  Detail & Related papers  (2025-10-13T01:57:22Z)
• Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under $(L_0, L_1)$-Smoothness [74.18546828528298]
  We show that SignSGD with Majority Voting can robustly work on the whole range of complexity with $kappakappakappakappa-1right, kappakappakappa-1right, kappakappakappa-1right, kappakappakappa-1right, kappakappakappa-1right, kappakappakappa-1right, kappakappakappa-1right, kappa
  arXiv  Detail & Related papers  (2025-02-11T19:54:11Z)
• Extending Asynchronous Byzantine Agreement with Crusader Agreement [23.27199615640474]
  We present a new reduction from multivalued BA to binary BA.<n>As our reduction uses multivalued CA, we also design two new information-theoretic CA protocols for $ell$-bit inputs.
  arXiv  Detail & Related papers  (2025-02-04T13:44:41Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  We study multiclass PAC learning with bandit feedback, where inputs are classified into one of $K$ possible labels and feedback is limited to whether or not the predicted labels are correct. Our main contribution is in designing a novel learning algorithm for the agnostic $(varepsilon,delta)$PAC version of the problem.
  arXiv  Detail & Related papers  (2024-06-18T08:54:04Z)
• WR-ONE2SET: Towards Well-Calibrated Keyphrase Generation [57.11538133231843]
  Keyphrase generation aims to automatically generate short phrases summarizing an input document. The recently emerged ONE2SET paradigm generates keyphrases as a set and has achieved competitive performance. We propose WR-ONE2SET which extends ONE2SET with an adaptive instance-level cost Weighting strategy and a target Re-assignment mechanism.
  arXiv  Detail & Related papers  (2022-11-13T09:56:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.