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.

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.