New Paper: On Adaptive Security of Key-Unique Threshold Signatures

I am happy to say that I've recently published the paper "On the Adaptive Security of Key-Unique Threshold Signatures," in collaboration with my (fantastic) co-authors Elizabeth Crites and Mary Maller. We worked on this paper for quite a while to get it right, so I'm very happy to see it out in the open.

As a reminder, adaptive security is a stronger notion of theoretical security over static security. Static security models a security experiment with the adversary picking corrupted parties all at once, at the beginning of the experiment, before it is allowed to interact with honest participants in the protocol. Adaptive security allows the adversary to adaptively corrupt participants throughout its interaction in the protocol. Hence, adaptive security models real-world attacks more closely. It is always possible to prove adaptive security by what we call "complexity leveraging" and static security- where static challenger guesses the corrupted parties up front, then runs the adaptive adversary, and aborts if the adversary corrupts a participant that it did not guess. However, this "complexity leveraging+static" approach incurs tightness loss in the proof, and hence it is desirable to write proofs of adaptive security with improved tightness.

The question that motivated this work began with our prior paper "Fully Adaptive Schnorr Threshold Signatures." In that paper, we defined Sparkle, a three-round threshold Schnorr signature scheme, and we gave three different proofs of security. We first proved that Sparkle was statically secure under the discrete logarithm (DL) problem in the ROM. We then gave an adaptive proof of security for up to t/2 corruptions under the algebraic one-more discrete logarithm problem (AOMDL) in the ROM. We finally proved full adaptive security (up to t-1 corruptions) under AOMDL, in the ROM and in the algebraic group model (AGM).

The goal of our new paper "On the Adaptive Security of Key-Unique Threshold Signatures" was in essence to understand why we needed three different proofs of security for Sparkle to establish these results, and whether it was possible to do any better. Did we need such a strong model as the AGM to prove full adaptive security? Or was it possible that our proof techniques could be improved?

In short, we found that no, we really couldn't do any better. I'll refer to the paper for technical details as to why. But what is really interesting is that our results hold not only for Sparkle, but for other schemes in the literature that have public keys of the same form, such as FROST, and even threshold BLS. We refer to such schemes as "key-unique" threshold signatures.

What is the takeaway? Firstly, I don't think our results mean that we need to drop everything and migrate to schemes that are not key unique, so that we can achieve full adaptive security under weaker security assumptions. I primarily see our results as an interesting data point about adaptive security itself. Because there are no existing practical attacks that can break a scheme with an adaptive adversary but not with a static adversary, my (current) opinion is that adaptive security remains an interesting theoretical notion.

However, I do think we need more cryptanalysis into the real possibility that a practical separation might exist between adaptive and static security. If a practical attack is discovered, this discovery would be a very compelling argument to switch to schemes with proven adaptive security. While ideally we would choose schemes with weaker security assumptions, we must balance the need for real-world considerations (performance, ease of implementation) with theoretical considerations (strength of security assumptions).

Overall, I enjoyed writing this paper- this was my first time establishing an impossibility result via a metareduction. I learned a lot, which is the best part of doing research (along with working with amazingly talented people)!

Please let us know what you think of the paper, and any comments/questions! We hope it is useful.