International Association
for Cryptologic Research

The adaptive security of threshold signatures considers an adversary that adaptively corrupts users to learn their secret key shares and states. Crites, Komlo, and Maller (Crypto 2023) proposed Sparkle, the first adaptively secure threshold signature scheme in the pairing-free discrete-log setting, but it requires the algebraic group model (AGM) and is based on an interactive assumption. Bacho, Loss, Tessaro, Wagner, and Zhu (Eurocrypt 2024) proposed Twinkle, whose adaptive security can be proved based on the standard DDH assumption without the AGM. We propose Dazzle and Dazzle-T, adaptively secure threshold signature schemes based on DDH without the AGM, the same assumption and model as Twinkle. Our schemes improve upon Twinkle in signature size, round complexity, and/or security tightness. In particular, Dazzle and Dazzle-T both have signatures that are shorter than Twinkle by one group element. Regarding the round complexity and tightness, Twinkle is three-round and non-tight. Dazzle is two-round and has the same security loss as Twinkle. Dazzle-T is three-round and fully tight. We achieve our improvements by optimizing the underlying single-party signature scheme and showing that the single-party scheme can be transformed to a threshold scheme by a simpler transformation than that of Twinkle.

A multi-signature scheme allows multiple signers to jointly sign a common message. In recent years, two lattice-based two-round multi-signature schemes based on Dilithium-G were proposed: DOTT by Damg{\aa}rd, Orlandi, Takahashi, and Tibouchi (PKC'21) and Musig-L by Boschini, Takahashi, and Tibouchi (CRYPTO'22). In this work, we propose a new lattice-based two-round multi-signature scheme called DualMS. Compared to DOTT, DualMS is likely to significantly reduce signature size, since it replaces an opening to a homomorphic trapdoor commitment with a Dilithium-G response in the signature. Compared to Musig-L, concrete parameters show that DualMS has smaller public keys, signatures, and lower communication, while the first round cannot be preprocessed offline as in Musig-L. The main reason behind such improvements is a trapdoor-free ``dual signing simulation'' of our scheme. Signature simulation of DualMS is virtually the same as the normal signing procedure and does not use lattice trapdoors like DOTT and Musig-L.