On the Adaptive Security of Key-Unique Threshold Signatures

In this work, we investigate the security assumptions required to prove the adaptive security of threshold signatures. Adaptive security is a strong notion of security that allows an adversary to corrupt parties at any point during the execution of the protocol, and is of practical interest due to recent standardization efforts for threshold schemes. Towards this end, we give two different impossibility results.

We begin by formalizing the notion of a key-unique threshold signature scheme, where public keys have a unique correspondence to secret keys and there is an efficient algorithm for checking that public keys are well-formed. Key-uniqueness occurs in many threshold schemes that are compatible with standard, single-party signatures used in practice, such as BLS, ECDSA, and Schnorr signatures.

Our first impossibility result demonstrates that it is impossible to prove the adaptive security of any key-unique threshold signature scheme under any non-interactive computational or decisional assumption for a broad class of reductions, in the range ⌊t/ℓ⌋ < t_c ≤ t, where t+1 is the threshold out of n parties, t_c is the number of corrupted parties (polynomially related with the security parameter), and ℓ is a constant. Such assumptions include, but are not limited to, the discrete logarithm (DL), recently introduced circular DL (CDL), computational Diffie-Hellman (CDH), decisional DH (DDH), and q-Strong DH (q-SDH) assumptions.

Our second impossibility result applies specifically to key-unique threshold Schnorr signatures, currently an active area of research. We demonstrate that, even under the interactive computational assumptions one-more DL (OMDL), algebraic OMDL (AOMDL) and algebraic one-more CDH (AOMCDH), it is impossible to prove adaptive security for ⌊t/2⌋ < t_c ≤ t in the ROM for a natural class of rewinding reductions.

Taken together, our results underscore the difficulty of achieving adaptive security for key-unique threshold signatures, but at the same time, they open a new line of research, by indicating assumptions and properties to aim for when constructing adaptively secure threshold schemes, or informing new attacks.