Schnorr Signature Aggregation

Open Table of contents

What it is
How it works
Why it works
Rogue-Key Attack
References

What it is

Schnorr’s Signature Protocol can be used in a setup so that the secret key is shared among a group of users such that a valid signature can only be produced if those users collaborate.

The secret key is split-up and shared in a way so that it’s never reconstructed in one central place. This way an attacker would need to compromise all involved parties to produce a valid signature.

How it works

As a prerequisite, it’s useful to have a basic understanding of Schnorr Signatures before continuing.

We’ll be working with an Elliptic Curve $E$ that is of order $q$ and has a generator $G$ . All calculations are done $\bmod\ q$ if not stated otherwise.

In our example Alice and Bob collaborate to produce a valid signature over a message $m$ which Carol will validate.

Note: In this writeup, every parameter Alice generates uses the subscript $_1$ , whereas all the parameters Bob generates use the subscript $_2$ .

The first step is for Alice and Bob to generate their private- and public keys.

x_1 \overset{{\scriptscriptstyle\$}}{\leftarrow} \mathbb{Z}_q

X_1 = x_1G

x_2 \overset{{\scriptscriptstyle\$}}{\leftarrow} \mathbb{Z}_q

X_2 = x_2G

Alice and Bob then share the public values $X_1$ and $X_2$ with each other.

Once received, both compute the shared public key $X$ as $X = X_1 + X_2$ .

Next up, Alice and Bob generate the random secret nonce value as well as its public derivative:

r_1 \overset{{\scriptscriptstyle\$}}{\leftarrow} \mathbb{Z}_q

R_1 = r_1G

r_2 \overset{{\scriptscriptstyle\$}}{\leftarrow} \mathbb{Z}_q

R_2 = r_2G

Alice and Bob also share the public values $R_1$ and $R_2$ with each other.

Once they’ve received those values, they can compute the shared $R$ as $R = R_1 + R_2$ .

As a next step, Alice and Bob compute $c$ as the hash value of the concatenation of $X$ , $R$ and $m$ :

c = H(X \mathbin\Vert R \mathbin\Vert m)

The $e$ values can be computed by Alice and Bob independently as:

e_1 = r_1 + cx_1

e_2 = r_2 + cx_2

The signature is $R = R_1 + R_2$ and $e = e_1 + e_2$ which Carol can validate by checking if $eG \overset{?}{=} R + cX$ as it’s done in a regular Schnorr Signature.

This works because:

\begin{aligned} eG &= R + cX \\ (r + cx)G &= rG + cxG \\ (r + cx)G &= (r + cx)G \end{aligned}

Schnorr Signature Aggregation

Why it works

Carol, the verifier uses the regular Schnorr Signature verification method $eG \overset{?}{=} R + cX$ to check the signature for its validity.

Given the linearity of the mathematical operations involved in the Schnorr Signature protocol (mostly addition and multiplication is used) we can calculate $R$ and $e$ as the addition of their respective shared values.

Expanding the signature validation equation from above with the knowledge that $R = R_1 + R_2$ and $e = e_1 + e_2$ we get:

\begin{aligned} eG &= R + cX \\ (e_1 + e_2)G &= R_1 + R_2 + cX \\ (r_1 + cx_1 + r_2 + cx_2)G &= r_1G + r_2G + c(x_1G + x_2G) \\ (r_1 + r_2 + cx_1 + cx_2)G &= (r_1 + r_2 + cx_1 + cx_2)G \\ (r + c(x_1 + x_2))G &= (r + c(x_1 + x_2))G \\ (r + cx)G &= (r + cx)G \end{aligned}

Rogue-Key Attack

It’s important to note that the aforementioned key aggregation scheme isn’t secure under adversarial conditions (when the co-signers can’t trust each other).

The reason being that the last co-signer can wait until all the other co-signers shared their public keys to then compute a “fake” public key that subtracts the other co-signers public keys. This ultimately gives the last co-signer full control over the signature creation.

To show how this would work, let’s take a look at our example where Alice and Bob both create a signature collaboratively. Assuming that Alice shared here public key $X_1 = x_1G$ first, Bob can now generate his public key as $X_2 = x_2G$ but share a “fake” public key with Alice that subtracts her public key from his:

X_2' = X_2 - X_1

The shared public key $X$ that’s both derived by Alice and Bob is therefore Bob’s public key:

\begin{aligned} X &= X_1 + X_2' \\ &= X_1 + (X_2 - X_1) \\ &= X_2 \end{aligned}

Given this, Bob can now sign without Alice while Carol, the validator would assume that the signature was generated collaboratively.

Fortunately there’s a simple solution to this problem called “Knowledge of Secret Key” (KOSK). All parties participating in the protocol need to not only share their public key but also a signature over that public key to ensure that they also know the private key that was used to derive the public key.

This mitigation works as the adversary computing and sharing the “fake” public key has no way to figure out what its private key would be.

References

The following resources have been invaluable for me to learn the concepts discussed in this article.

You should definitely give them a read if you want to dive deeper into the topic.