Paper 2025/1953

Adaptively Secure Partially Non-Interactive Threshold Schnorr Signatures in the AGM

Yanbo Chen, University of Ottawa

Julian Loss, Ruhr University Bochum

Stefano Tessaro, University of Washington

Chenzhi Zhu, NTT Research

Abstract

Very recently, Crites et al. (CRYPTO 2025) gave a proof for the full adaptive security of FROST (Komlo and Goldberg, SAC 2020), the state-of-the-art two-round threshold Schnorr signature scheme, which is currently used in real-world applications and is covered by an RFC standard. Their security proof, however, relies on the computational hardness of a new search problem they call “low-dimensional vector representation” (LDVR). In fact, the authors show that hardness of LDVR is necessary for adaptive security of a large class of threshold Schnorr signatures to hold, including FROST and its two-round variants. Given that LDVR is a new assumption and its hardness has not been seriously scrutinized, it remains an open problem whether a two-round threshold Schnorr signature with full adaptive security can be constructed based on more well-established assumptions. In this paper, we resolve this open problem by presenting ms-FROST. Our scheme is partially non-interactive and supports any t - 1 < n adaptive corruptions, where n is the number of signers and t is the signing threshold. Its security relies on the algebraic one-more discrete logarithm (AOMDL) assumption, the algebraic group model (AGM), and the random oracle model (ROM). Further, it achieves the strongest security notion (TS-UF-4) in the security hierarchy of Bellare et al. (CRYPTO 2022). To justify our use of the algebraic group model, we show an impossibility result: We rule out any black-box algebraic security reduction in the ROM from AOMDL to the adaptive TS-UF-0 security of ms-FROST.

@misc{cryptoeprint:2025/1953,
      author = {Renas Bacho and Yanbo Chen and Julian Loss and Stefano Tessaro and Chenzhi Zhu},
      title = {Adaptively Secure Partially Non-Interactive Threshold Schnorr Signatures in the {AGM}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1953},
      year = {2025},
      url = {https://eprint.iacr.org/2025/1953}
}