Paper 2025/952

Trapdoor-Free Multivariate One-Time Signatures in the Standard Model

Abstract

Constructing a multivariate signature scheme that is both trapdoor-free and provably secure in the standard model has been a long-standing challenge. In this paper, we present MQ-based W-OTS$^+$, the first multivariate one-time signature scheme to achieve these properties, and prove its \emph{existential unforgeability under chosen-message attack} via reductions to the \emph{MQ one-wayness (MQOW) assumption}. Our analysis focuses on the three properties that the MQ function family must satisfy within the W-OTS$^+$ framework: \emph{one-wayness} (OW), \emph{second-preimage resistance} (SPR), and \emph{undetectability} (UD). For SPR, we give a tight reduction from SPR to its OW. For UD, we provide a tighter reduction from UD to its OW, reducing the security loss from the previous bound of $O(\epsilon^{-4})$ to $O(\epsilon^{-2})$ over arbitrary finite fields. MQ-based W-OTS$^+$ consolidates the three assumptions required by W-OTS$^+$ (OW, SPR, and UD) into one standard multivariate assumption (MQOW). This shows that we can leverage some desirable properties of the MQ function family to construct a multivariate one-time signature in the standard model, instead of relying on trapdoors or zero-knowledge proofs.