Welcome to the resource topic for 2025/952
Title:
A Provably Secure W-OTS$^+$ based on MQ Problem
Authors: Zijun Zhuang, Yingjie Zhang, Jintai Ding
Abstract:In 2022, Antonov showed that SHA-256 does not satisfy some secure property that SPHINCS$^+ needs, and a fogery attack based on this observation reduces the concrete classical security by approximately 40 bits of security. This illustrates a more general concern: the provable security of some hash-based signature schemes can be compromised when implemented with certain real-world hash functions, and motivates the need to design new functions with rigorous, provable security guarantees. Besides, it has been shown that from W-OTS to W-OTS^+, the security requirement for the hash function's collision resistance can be relaxed to second-preimage resistance (SPR), which means that it is possible to use some functions with SPR property to instantiate the underlying function family \mathcal{F}_n$ in W-OTS$^+, and obtain a provably secure W-OTS^+. In this paper, we use multivariate quadratic functions (MQ functions) to instantiate \mathcal{F}_n$ in W-OTS$^+, which yields the first provably secure W-OTS^+. To prove its security, we need to derive the SPR property of MQ functions. The key is to show the \mathbf{NP}-hardness of finding second preimages. Furthermore, we prove the multi-function, multi-target one-wayness (MM-OW) and the multi-function, multi-target second-preimage resistance (MM-SPR) of MQ functions, which implies the provable security of MQ-based W-OTS^+$ in the multi-user setting, on the condition that the number of users is O(n^{1-\epsilon}) for some \epsilon\in (0,1), where n is the security parameter.
ePrint: https://eprint.iacr.org/2025/952
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .