Paper 2026/078

Breaking the Myth of MPCitH Inefficiency: Optimizing MQOM for Embedded Platforms

Thibauld Feneuil, CryptoExperts (France)

Abstract

Signature schemes based on the MPC-in-the-Head (MPCitH) paradigm play an important role in enabling cryptosystems founded on a wide diversity of hardness assumptions. While the design of such schemes is currently stabilizing, providing efficient implementations on embedded devices remains a critical challenge, as MPCitH frameworks are known to manipulate large data structures and to rely heavily on symmetric primitives. In this work, we present a highly optimized implementation of the NIST candidate MQOM (version 2) targeting embedded microcontrollers. Our implementation significantly outperforms existing MPCitH implementations on such platforms, both in terms of memory footprint and execution time. In particular, for the L1 parameter set, we can achieve an SRAM usage below 10 KB, including the key and signature buffers, while preserving practical signing and verification performance (on the order of a few hundred megacycles). We further explore time-memory trade-offs, achieving execution times below 100 Mc for certain variants at the cost of an additional 5-10 KB of memory. We also provide the first memory-friendly implementation of the one-tree technique, which is used to reduce signature sizes in several MPCitH-based schemes. This enables a comparative analysis of the implementation costs of correlated trees (used in MQOM) versus the one-tree technique (used in other candidates). We then demonstrate how streaming and precomputation techniques can further mitigate the impact of the running time and the signature size. For instance, these approaches enable overlapping computation with data reception, for example by starting computations before all inputs are available, thereby reducing overall latency.

Note: [2026-04-24 update] The DMA mode for hardware has been added, the tree traversal in BLC has been improved to provide better trade-offs between memory and timings, and the comparison with prior work has been refined. Overall timings have been improved, with the most significant gains observed for the "Memory" and "Hardware" profiles.

@misc{cryptoeprint:2026/078,
      author = {Ryad Benadjila and Thibauld Feneuil},
      title = {Breaking the Myth of {MPCitH} Inefficiency: Optimizing {MQOM} for Embedded Platforms},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/078},
      year = {2026},
      url = {https://eprint.iacr.org/2026/078}
}