1
$\begingroup$

The motivation for key aggregation multisig and threshold schemes (e.g. MuSig(2), FROST etc) in Bitcoin is obvious. Signatures are a large part of every transaction, all the nodes on the network are attempting to verify every signature and signatures in many cases have to be stored as part of the blockchain data structure for the rest of Bitcoin's existence. Hence reducing verification time and reducing the size/number of signatures is critically important.

But Bellare and Neven as early as 2006 and I'm assuming much earlier were working on aggregated multisignatures.

What was the motivation? Were any use cases or organizations attempting to verify multisignatures so frequently that size (bytes)/storage and verification time were relevant concerns pre Bitcoin (2008)? Or is this just a case of academia exploring new research fields many years before they might be used and without a need to justify how these schemes might be used in the "real world"?

$\endgroup$

1 Answer 1

1
$\begingroup$

Yes, Virginia/Virgil there was a world before bitcoin:

There has long been real-world reasons for desiring batch verification, protecting privacy in a group, etc.

Here is part of a 2008 publication available here giving some of the earlier background in this general area.

The concept of digital multisignature is very similar to the concept of group-oriented threshold signature. The group oriented cryptography was first introduced by Desmedt (1987). By applying the concept of group-oriented cryptography, threshold signature schemes can be developed. Several threshold signature schemes and their modifications have been developed (Chang and Lee, 1993; Chaum and Heyst, 1991; Desmedt and Frankel, 1989; Desmedt and Frankel, 1991; Laih and Harn, 1991). In a threshold signature scheme, a group signature is generated by a number of participating members, which is larger than or equal to a predefined threshold value. For instance, in a $(t, n)$ threshold signature scheme, any $t$ or more than $t$ members can represent the group to generate a group signature. Later, the verifier can use the group’s public key to validate the group signature. The special case of the threshold signature called the $(1, n)$ group signature was proposed by Chaum and Heyst (1991). In a $(1, n)$ group signature, a group signature could be generated by an employee i.e. a group member) of a large company, and be verified by any outside verifier as a normal digital signature, but not be able to identify the particular employee who signed it. However, even all other group members (and the manager) collude, they cannot forge a signature for a non-participating group member.

$\endgroup$
1
  • $\begingroup$ Thanks for the link, I hadn't seen this paper. $\endgroup$ Jul 25, 2022 at 13:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.