1 of 18

Threshold signatures,

multisignatures

& aggregate signatures

Intuition and definitions

1

Alin Tomescu

@alinush407

Aptos Labs

2 of 18

Normal signature schemes

Rivest, Shamir, Adleman '78

2

σ = Sign(m, sk)

Verify(σ, m, pk)

sk

message m

(e.g., Bitcoin TXN)

In a normal signature scheme, we have a signer who has a secret key (SK) with a corresponding public key (PK).

The signer can can digitally sign any message m using their SK, producing a signature σ.

A verifier who has the corresponding PK can verify the signature σ on m.

At a high-level, digital signatures allow a verifier to check that a signer has said "something": e.g., the signer "said" m.

They are used in consensus protocols, when replica i wants to send messages to all other replicas, who must be able to verify the message indeed came from replica i.

They are used in Bitcoin, where the blockchain must verify that a valid transaction indeed came from a user who had enough Bitcoin to pay someone else.

They are used in secure messaging too, where an app like WhatsApp must verify that the message it's about to display indeed came from the person on the other end of the conversation.

A big problem with digital signature schemes is that the SK often sits on one single device (e.g., a cellphone), which can be compromised by an attacker.

This is no good: e.g., in Bitcoin, if an attacker steals your SK, they can steal your money.

3 of 18

API for a normal signature scheme

KeyGen(1^k) → (sk, pk)

Generates a key-pair for a signer: a secret key and its corresponding public key

(k denotes a security parameter; e.g., k = 128 bits)

Sign(m, sk) → σ

Produces a signature σ on m

Verify(σ, m, pk) → 0/1

Verifies the signature σ on m under the public key pk of the signer

3

4 of 18

Threshold signature (TS) schemes

Desmedt '87

4

σ₁ = Sign(m, sk₁)

sk

sk₅

sk₄

sk₃

sk₂

sk₁

e.g., "3 out of 5" secret sharing

Signature share

σ₃= Sign(m, sk₃)

5 of 18

Threshold signature (TS) schemes

Desmedt '87

5

σ = Sign(m, sk)

σ₁ = Sign(m, sk₁)

σ₅

sk

e.g., "3 out of 5" secret sharing

σ₃

sk₅

sk₄

sk₃

sk₂

sk₁

Verify(σ, m, pk)

(t out of n) sharing ⇒ tolerate t-1 compromises

Assuming uncorrelated vulnerabilities/failures

σ = Aggr(σ₁, σ₃, σ₅, m)

Verifier need not be aware that the threshold signature came from signers 1, 3 and 5

To produce a signature on m that verifies under pk, the signers must now collaborate!

Each signer takes m, produces a signature share σ_i on m and sends it to an aggregator.

(These signatures shares can actually be verified by the aggregator against a corresponding verification key vk_i associated with sk_i, but we ignore this for now.)

Again, nobody knows sk, not even the aggregator!

Nonetheless, the aggregator can aggregate any t of these signature shares, into a final threshold signature σ that verifies under the original pk (as long as the chosen t signature shares are valid, which as explained above the aggregator can ensure).

This is kind of miraculous: even though no single signer knows sk, together, the signers were able to produce a final threshold signature that verifies under pk!

6 of 18

Threshold signature (TS) schemes

Desmedt '87

6

Verify(σ, m, pk)

σ = Sign(m, sk)

σ₁ = Sign(m, sk₁)

σ₅

sk

σ₃

sk₅

sk₄

sk₃

sk₂

sk₁

σ = Aggr(σ₁, σ₃, σ₅, m)

A naive aggregator cannot aggregate correctly if one of the signers is malicious. But a sophisticated aggregator who verifies each signature share can aggregate correctly!

7 of 18

API for a TS scheme

DistKeyGen(1^k, t, n) → ((sk_i, vk_i)_{i∈[1, n]}, pk)

Generates a key-pairs for all n signers, such that any subset of t out of n signers can collaborate to produce a threshold signature. (k denotes a security parameter; e.g., k = 128 bits)

SignShare(m, sk_i) → σ_i

Produces a signature share σ_i on m under signer i's secret key sk_i

VerifyShare(σ_i, m, vk_i) → 0/1

Verifies the signature share σ_i on m allegedly signed under signer i's secret key

Aggregate((i, σ_i)_{i∈[1, n]}) → σ

Aggregates the t signature shares into a succinct threshold signature σ.

Verify(σ, m, pk) → 0/1

Verifies the threshold signature σ on m under the PK pk of the group of n signers

7

Distributed key generation (DKG) protocols are non-trivial and deserve their own special treatment

8 of 18

Multisig signature (MS) schemes

8

Verify(σ, m, {pk₁, pk₃, pk₅})

σ = Aggr(σ₁, σ₃, σ₅, m)

σ₁ = Sign(m, sk₁)

sk₅

sk₄

sk₃

sk₂

sk₁

Verifier must be aware that the multisignature came from signers 1, 3 and 5

σ₅ = Sign(m, sk₅)

σ₃ = Sign(m, sk₃)

9 of 18

Multisig signature (MS) schemes

9

Verify(σ, m, {pk₁, pk₃, pk₅})

σ = Aggr(σ₁, σ₃, σ₅, m)

σ₁ = Sign(m, sk₁)

sk₅

sk₄

sk₃

sk₂

sk₁

σ' = Aggr(σ₃, σ₅, m)

Verifier must be aware that the multisignature came from signers 1, 3 and 5

Verify(σ', m, {pk₃, pk₅})

…or that the multisignature came from signers 3 and 5

σ₅ = Sign(m, sk₅)

σ₃ = Sign(m, sk₃)

10 of 18

Multisig signature (MS) schemes

10

Verify(σ, m, { pk₁, pk₃, pk₅})

σ = Aggr(σ₁, σ₃, σ₅, m)

σ₁ = Sign(m, sk₁)

σ₅

sk₅

sk₄

sk₃

sk₂

sk₁

As in a TS, if one signer is malicious, naive aggregation will not produce a valid multisignature.

σ₃ = Sign(m, sk₃)

11 of 18

API for an MS scheme

KeyGen(1^k) → (sk, pk)

Generates a key-pair for a signer. (k denotes a security parameter; e.g., k = 128 bits)

SignShare(m, sk_i) → σ_i

Produces a signature share σ_i on m under signer i's secret key sk_i

VerifyShare(σ_i, m, pk_i) → 0/1

Verifies the signature share σ_i on m was produced by the signer with public key pk_i

Aggregate(m, (σ_i, pk_i)_{i∈[1, n]}) → σ

Aggregates n signature shares, each on the same message m, into a succinct multisignature σ.

Verify(σ, m, (pk_i)_{i∈[1, n]}) → 0/1

Verifies the multisignature σ on m was produced by the n signers with the specified public keys

11

12 of 18

Aggregate signature (AS) schemes

12

Verify(σ, (m_i, pk_i)_i∈{1,3,5})

σ = Aggr((σ_i, m_i, pk_i)_i∈{1,3,5})

σ₁ = Sign(m₁, sk₁)

σ₅ = Sign(m₅, sk₅)

sk₅

sk₄

sk₃

sk₂

sk₁

Verifier must be aware that the aggr. signature came from signers 1, 3 and 5 and that the signed messages are m₁, m₃ and m₅.

σ₃ = Sign(m₃, sk₃)

13 of 18

Aggregate signature (AS) schemes

13

Verify(σ, (m_i, pk_i)_i∈{1,3,5})

σ = Aggr((σ_i, m_i, pk_i)_i∈{1,3,5})

σ₁ = Sign(m₁, sk₁)

σ₅ = Sign(m₅, sk₅)

sk₅

sk₄

sk₃

sk₂

sk₁

σ' = Aggr((σ_i, m_i, pk_i)_i∈{3,5})

Verifier must be aware that the aggr. signature came from signers 1, 3 and 5 and that the signed messages are m₁, m₃ and m₅.

Verify(σ', (m_i, pk_i)_i∈{3,5})

…or that the aggr. signature came from signers 3 and 5 on messages m₃ and m₅.

σ₃ = Sign(m₃, sk₃)

14 of 18

API for an AS scheme

KeyGen(1^k) → (sk, pk)

Generates a key-pair for a signer. (k denotes a security parameter; e.g., k = 128 bits)

SignShare(m, sk_i) → σ_i

Produces a signature share σ_i on m under signer i's secret key sk_i

VerifyShare(σ_i, m, pk_i) → 0/1

Verifies the signature share σ_i on m was produced by the signer with public key pk_i

Aggregate((σ_i, m_i, pk_i)_{i∈[1, n]}) → σ

Aggregates n signature shares, each on a different message m_i, into a succinct aggregate signature σ.

Verify(σ, (m_i, pk_i)_{i∈[1, n]}) → 0/1

Verifies the aggregate signature σ on messages m₁, m₂,…, m_n ensuring that each signer i with public key pk_i signed message m_i

14

15 of 18

When to use a TS, MS or an AS scheme?

TS:

MS:

AS:

Much slower aggregation than MS
Rigid t-out-of-n threshold

Possible to update it to t'-out-of-n' but complex cryptography & interaction involved

Final threshold signature always verifies against unique public key pk, independent of the signers who produced it:

i.e., threshold signatures are constant-sized

Much faster aggregation than TS
Flexible t-out-of-n threshold

Easy to add a new signer (or to remove a signer)
Verifier enforces any verification threshold t by plugging in the expected public keys in the Verify() API

Final multisignature only verifies against the individual public keys of the signers who produced it:

i.e., multisignatures must include the signer IDs and are not constant-sized

Just like MS, except signers can sign different messages
Slightly slower verification of final aggr. signature than MS

15

16 of 18

Appendix

16

17 of 18

Threshold signatures... but why?

A key decentralized crypto primitive!

Cryptocurrency wallets
Consensus protocols
Random beacons
Voting

Needs large t and n!

...and more are likely to come!

17

18 of 18

References

[Bold03] Threshold Signatures, Multisignatures and Blind Signatures Based on the Gap-Diffie-Hellman-Group Signature Scheme; by Boldyreva, Alexandra; in PKC 2003

18