Paper 2025/952

A Provably Secure, MQ-Based W-OTS$^{+}$

Abstract

Hash-based signature (HBS) schemes provide a conservative foundation for post-quantum security, yet their formal proofs often rely on abstract hash properties that are difficult to verify in black-box heuristics. Recent research on SPHINCS$^{+}$ has highlighted a significant gap in this regard: when concrete instantiations fail to strictly satisfy the idealized properties required by the proofs, the security of the scheme may be compromised. Such discrepancies motivate a shift toward instantiations anchored in structured algebraic problems, where the specific security properties required by HBS frameworks can be formally derived from well-studied computational hardness assumptions. In this work, we present the first comprehensive instantiation of the W-OTS$^{+}$ scheme based on multivariate quadratic (MQ) functions. We establish the \emph{existential unforgeability under chosen message attack} (EU-CMA) of the scheme by providing a complete security reduction to the standard \emph{MQ assumption} and the \emph{one-wayness} of the MQ function family. Our analysis aligns with the rigorous standard-model requirements of the W-OTS$^{+}$ framework: specifically, we prove that \emph{second-preimage resistance} (SPR) inherits established average-case hardness while possessing worst-case $\mathbf{NP}$-hardness, providing a complexity-theoretic guarantee that persists independently of specific algorithmic refinements. Furthermore, we bridge a critical gap in standard-model proofs by grounding the \emph{undetectability} (UD) of the MQ family in its one-wayness, ensuring that the function's output distribution is theoretically indistinguishable from uniform. This construction provides a theoretically grounded alternative for HBS that prioritizes provable robustness derived from the inherent algebraic structure and well-studied hardness assumptions of the MQ problem.