Problem: Efficient weighted threshold signatures

We want to construct a signature scheme that allow a quorum to sign. Each participant has a weight $w_i$, and we want a signature to be accepted if the sum of weights of the signing participants is at least some threshold $w$.

---

Notes:

• There is good progress in eprint.iacr.org/2023/1609.pdf by Garg, Goel, and Wang, but this paper uses FRI. Can we do better?
• The “cheap” approach is just to use regular threshold signatures, where each participant signs $w_i$ times.
• If we have a big hammer like a SNARK, this is easy:
  • Everybody generates a signature, and then the aggregator generates a proof that it saw valid signatures from (say) five people, and the sum of their weights is greater than the threshold.
  • The witness would be the signatures from the individual participants and the weights of the participants.
• Is there a simple algebraic scheme?
  • Maybe there’s a way to generalize BLS signatures: https://en.wikipedia.org/wiki/BLS_digital_signature