Paper 2026/629

Towards Formal Security Proofs of MQOM

Abstract

Recent MPC-in-the-Head (MPCitH) signatures increasingly rely on aggressive GGM-tree optimizations to reduce signature size and cost, culminating in _secret-key-root correlated_ GGM tree as used in MQOM (NIST PQC Standardization for Additional Signature Round-2, 2024). While this technique yields substantial compression, it introduces a dependency loop in the proof. The transcript we would like to randomize for simulation is generated by expanding a GGM tree from a root that is part of the secret key, so this randomization must be justified via a reduction to the hardness of recovering the secret key. However, the hiding of the secret key relies on masking randomness that is a part of the transcript derived from the same GGM tree. As a result, justifying the randomization requires hiding, while proving hiding requires the randomization, and standard MPCitH proof templates do not apply directly. We propose and analyze two variants of MQOM and provide the EUF-CMA security proofs. The first variant makes a minor change to salts and replaces blockcipher-based hash functions in the GGM trees with random functions; we then prove its EUF-CMA security in the (quantum) random oracle model under partial-domain one-wayness or slightly stronger one-wayness assumptions. The second variant also makes a minor change to salts and adjusts security parameters to admit a proof under standard one-wayness in the ideal-cipher and random-oracle models. The proof exploits the H-coefficient technique with one-wayness, which might be of independent interest.