Using ECC for (Multi-)Signatures

[!NOTE] I am not a cryptographer, nor a mathematician. This article is the result of my own research and understanding of the subject. If you find any mistakes, please let me know!

The vast majority of what is written here is taken from various sources, which are listed at the end of this article. I highly recommend you to read them if you want to dive deeper into the subject.

Elliptic curves may not write your emails, but they can help prove you sent them. Our goal is to output a signature $(𝑟, 𝑠)$ for a given message $𝑚$ , so that the recipient can verify that the sender is authentic. The sender’s keys are $(𝑝, 𝑃)$ , with $𝑝$ the private key, and $𝑃$ the public one.

ECDSA Signatures

Let’s take a look at the Elliptic Curve Digital Signature Algorithm (ECDSA).

Compute the hash $ℎ = 𝐻 (𝑚)$ where $𝐻 (𝑥)$ is any cryptographic hash function (e.g. SHA-256).
Generate a random $𝑘$ number in in the current subgroup.
Calculate the associated random point on the curve $𝐾 = 𝑘 \cdot 𝐺$ , with $𝐺$ a generator, with $𝑥_{𝐾}$ the $𝑥$ -coordinate of this point.
Calculate the signature $𝑠 = 𝑘^{- 1} \cdot (ℎ + 𝑥_{𝐾} \cdot 𝑝)$ , where $𝑘^{- 1}$ is the modular inverse of $𝑘$ .

By sending $(𝑟, 𝑠)$ , you confirm you know:

The content of the message $𝑚$
The private key $𝑝$ associated to $𝑃 = 𝑝 \cdot 𝐺$

The verifier may follow this procedure to check if the message $𝑚$ that he received along with $(𝑟, 𝑠)$ is authentic:

Compute the hash $ℎ = 𝐻 (𝑚)$ with the same cryptographic hash function defined before.
Calculate the modular inverse of $𝑠$ : $𝑆 = 𝑠^{- 1}$
Recover the random point used in the signature process: $𝐾 = ℎ 𝑆 \cdot 𝐺 + 𝑟 𝑆 \cdot 𝑃$
Check whether $𝑥_{𝐾} = 𝑟$ , if so, then the message is authentic.

To prove this works, let’s start with the definition of the signature $𝑠$ :

\begin{aligned} 𝑠 = 𝑘^{- 1} \cdot (ℎ + 𝑥_{𝐾} \cdot 𝑝) \\ ⟺ & 𝑠 \cdot 𝑘 = ℎ + 𝑥_{𝐾} \cdot 𝑝 \\ ⟺ & \underset{(𝑎)}{\underset{⏟}{𝑠 \cdot 𝑘 = ℎ + 𝑟 \cdot 𝑝}} \end{aligned}

Incorporate $(𝑎)$ into $𝐾$ :

\begin{aligned} 𝐾 & = ℎ 𝑆 \cdot 𝐺 + 𝑟 𝑆 \cdot 𝑃 \\ = ℎ 𝑠^{- 1} \cdot 𝐺 + 𝑟 𝑠^{- 1} \cdot (𝑝 \cdot 𝐺) \\ = 𝑠^{- 1} (ℎ \cdot 𝐺 + 𝑟 \cdot (𝑝 \cdot 𝐺)) \\ = 𝑠^{- 1} \underset{(𝑎)}{\underset{⏟}{(ℎ + 𝑟 \cdot 𝑝)}} \cdot 𝐺 \\ = \underset{= 1}{\underset{⏟}{𝑠^{- 1} 𝑠}} \cdot 𝑘 \cdot 𝐺 \\ = 𝑘 \cdot 𝐺 \end{aligned}

Which is just our definition of $𝐾$ when generating the signature.

Cool Kids Public Key Recovery

Let’s suppose you are talking through a Tin can telephone with your friend and every byte you send matters. You don’t want to send the public key $𝑃$ along with the signature $(𝑟, 𝑠)$ because that’s just too much data. Instead, you can recover the public key from the signature and the message.

Given $𝑥_{𝐾}$ , there are typically two candidate points $𝐾_{𝑖}^{'}$ that fit. And since we know that $𝐾 = ℎ 𝑆 \cdot 𝐺 + 𝑟 𝑆 \cdot 𝑃$ , which we just verified works, it can be rearranged to isolate the public key $𝑃$ :

\begin{aligned} 𝐾_{𝑖}^{'} & = ℎ 𝑆 \cdot 𝐺 + 𝑟 𝑆 \cdot 𝑃_{𝑖} \\ ⟺ 𝑃_{𝑖} & = 𝑠^{- 1} (𝑟 𝐾_{𝑖}^{'} - ℎ 𝐺) \end{aligned}

To choose which one is the correct one, we need to verify the signature with each $𝑃_{𝑖}$ :

\begin{matrix} 𝐾_{𝑖} = ℎ 𝑆 \cdot 𝐺 + 𝑟 𝑆 \cdot 𝑃_{𝑖} = (𝑥_{𝐾}, 𝑦_{𝐾}) \\ 𝑥_{𝐾} \overset{?}{=} 𝑟 \end{matrix}

This ambiguity is often removed by adding a single bit $𝑏 \in {0, 1}$ into the signature message: $(𝑟, 𝑠, 𝑏)$

Schnorr Signatures

Schnorr signatures are a bit like ECDSA, but faster and simpler. We are going to use the same keys $(𝑝, 𝑃)$ as before, with $𝑝$ the private key and $𝑃$ the public one. We’ll first see the procedure and then discuss the mathematical proof of why this works.

Sample a random nonce $𝑟 \leftarrow ℤ_{𝑛}$

What the hell is

$ℤ_{𝑛}$ ?

The set $ℤ_{𝑛}$ is a cyclic group of integers, isomorphic to the quotient group $ℤ / 𝑛 ℤ$ . It is basically just the set of integers modulo $𝑛$ .

ℤ_{𝑛} = {0, 1, 2, \dots, 𝑛 - 1}

In our case, $𝑛$ is the order (how many points are in) of the subgroup generated by $𝐺$ . If the curve’s cofactor $ℎ$ is 1, then $𝑛$ is the order of the curve. If $ℎ$ is not 1, the order is $\frac{𝑛}{ℎ} = ord (𝐺)$

Multiply it by the generator: $𝑅 = 𝑟 𝐺$
We can now compute the challenge $𝑒 = 𝐻 (𝑅 ‖ 𝑃 ‖ 𝑚)$
And the signature: $𝑠 = 𝑟 + 𝑒 𝑝$

The final signature is $(𝑅, 𝑠)$ .

Once the signature has been emitted, verifying it is as easy as checking:

𝑠 \cdot 𝐺 = 𝑅 + 𝑒 𝑃

To know $𝑒$ , the verifier needs to know the message $𝑚$ , the public key $𝑃$ . In some cases, you might not need to include the public key into the challenge and simply hash $𝑒 = 𝐻 (𝑅 ‖ 𝑚)$ .

Why it Works

There isn’t really a proof needed for the verifying step as it’s just factoring out $𝐺$ , but here you are:

\begin{aligned} 𝑠 \cdot 𝐺 = 𝑅 + 𝑒 𝑃 \\ ⟺ & 𝑠 \cdot 𝐺 = \underset{𝑅}{\underset{⏟}{𝑟 𝐺}} + ℎ \underset{𝑃}{\underset{⏟}{𝑝 𝐺}} \\ ⟺ & 𝑠 \cdot 𝐺 = (𝑟 + 𝑒 𝑝) \cdot 𝐺 \end{aligned}

One trickier part is to explain why we are adding a random nonce $𝑟$ to both the signature and the challenge. This value has to be sampled randomly and must not be reused. If it is, the private key can be recovered. Let’s first take the case where no $𝑟$ is used:

\begin{aligned} 𝑠 = 𝑒 𝑝 \\ ⟺ & 𝑝 = 𝑠^{- 1} 𝑒 \end{aligned}

Recovering the private key is as simple as multiplying the challenge $𝑒$ by the modular inverse of $𝑠$ . Not good.

Now, let’s take the case where $𝑟$ is reused, with two messages $𝑚_{1}$ and $𝑚_{2}$ , along with their respective signatures $(𝑅, 𝑠_{1})$ and $(𝑅, 𝑠_{2})$ :

{\begin{cases} 𝑠_{1} = 𝑟 + 𝑒_{1} 𝑝 ⟺ 𝑟 = (𝑠_{1} - 𝑒_{1} 𝑝) (𝑎) \\ 𝑠_{2} = 𝑟 + 𝑒_{2} 𝑝 ⟺ 𝑟 = (𝑠_{2} - 𝑒_{2} 𝑝) (𝑏) \end{cases}

Combining $(𝑎)$ and $(𝑏)$ :

\begin{aligned} 𝑟 = (𝑠_{1} - 𝑒_{1} 𝑝) = (𝑠_{2} - 𝑒_{2} 𝑝) \\ ⟺ & 𝑒_{1} 𝑝 - 𝑒_{2} 𝑝 = 𝑠_{1} - 𝑠_{2} \\ ⟺ & 𝑝 \cdot (𝑒_{1} - 𝑒_{2}) = 𝑠_{1} - 𝑠_{2} \\ ⟺ & 𝑝 = \frac{𝑠_{1} - 𝑠_{2}}{𝑒_{1} - 𝑒_{2}} \end{aligned}

You may see $𝑟$ as an additional unknown variable that is used to prevent the linear equation system from being solved, because for $𝑛$ messages, you have $𝑛$ equations and $𝑛 + 1$ unknowns, which is unsolvable in our case.

Aggregating Signatures

Schnorr signatures have the nice property that they can be aggregated, this means that a group of people can sign a message $𝑚$ together and the signature can be verified as if it was signed by a single person. Let’s consider our signing group $𝑆 = {𝑎, 𝑏, 𝑐}$ for Alice, Bob and Charlie respectively.

\begin{aligned} Alice & Bob & Charlie \\ 𝑅_{𝑎} = 𝑟_{𝑎} \cdot 𝐺 & 𝑅_{𝑏} = 𝑟_{𝑏} \cdot 𝐺 & 𝑅_{𝑐} = 𝑟_{𝑐} \cdot 𝐺 \end{aligned}

The aggregated nonce is simply the sum of all nonces:

\begin{aligned} 𝑅 & = \sum_{𝑖 \in 𝑆} 𝑅_{𝑖} \\ = 𝑅_{𝑎} + 𝑅_{𝑏} + 𝑅_{𝑐} \\ = (𝑟_{𝑎} + 𝑟_{𝑏} + 𝑟_{𝑐}) \cdot 𝐺 \end{aligned}

Likewise for the public key:

\begin{aligned} 𝑃 & = \sum_{𝑖 \in 𝑆} 𝑃_{𝑖} \\ = 𝑃_{𝑎} + 𝑃_{𝑏} + 𝑃_{𝑐} \\ = (𝑝_{𝑎} + 𝑝_{𝑏} + 𝑝_{𝑐}) \cdot 𝐺 \end{aligned}

Each of them computes the challenge $𝑒$ along with the final signature $𝑠_{𝑖}$ with the parameters just agreed upon:

\begin{matrix} 𝑒 = 𝐻 (𝑅 ‖ 𝑃 ‖ 𝑚) \\ 𝑠_{𝑖} = 𝑒 𝑝_{𝑖} + 𝑟_{𝑖} \end{matrix}

Everyone now sends their $𝑠_{𝑖}$ to the group.

And aggregate again:

𝑠 = \sum_{𝑖 \in 𝑆} 𝑠_{𝑖}

Because we are just adding signatures parts together, we can group the nonces and the private keys in our final signature:

\begin{aligned} 𝑠 & = \sum_{𝑖 \in 𝑆} 𝑠_{𝑖} \\ = \sum_{𝑖 \in 𝑆} (𝑒 𝑝_{𝑖} + 𝑟_{𝑖}) \\ = 𝑒 𝑝_{𝑎} + 𝑟_{𝑎} + 𝑒 𝑝_{𝑏} + 𝑟_{𝑏} + 𝑒 𝑝_{𝑐} + 𝑟_{𝑐} \\ = \underset{Nonces}{\underset{⏟}{𝑟_{𝑎} + 𝑟_{𝑏} + 𝑟_{𝑐}}} + 𝑒 \underset{Private Keys}{\underset{⏟}{(𝑝_{𝑎} + 𝑝_{𝑏} + 𝑝_{𝑐})}} \\ = \sum_{𝑖 \in 𝑆} 𝑟_{𝑖} + 𝑒 \cdot \sum_{𝑖 \in 𝑆} 𝑝_{𝑖} \end{aligned}

In the verifying step, multiplying each side by $𝐺$ :

\begin{aligned} 𝑠 𝐺 & = \sum_{𝑖 \in 𝑆} 𝑟_{𝑖} \cdot 𝐺 + 𝑒 \cdot \sum_{𝑖 \in 𝑆} 𝑝_{𝑖} \cdot 𝐺 \\ = \sum_{𝑖 \in 𝑆} 𝑅_{𝑖} + 𝑒 \cdot \sum_{𝑖 \in 𝑆} 𝑃_{𝑖} \\ = 𝑅 + 𝑒 𝑃 \end{aligned}

But wait!

At no point in this procedure, we ever check if the nonces or the public keys provided are honest. What if Charlie provided a malicious key $𝑃_{𝑐}^{*}$ in the sharing step ? Because everyone doesn’t send their public key at the exact same time, Carol could wait for everyone to send theirs, and compute:

𝑃_{𝑐}^{*} = 𝑃_{𝑐} - 𝑃_{𝑎} - 𝑃_{𝑏}

The aggregated key will look like:

\begin{aligned} 𝑃 & = \sum_{𝑖 \in 𝑆} 𝑃_{𝑖} \\ = 𝑃_{𝑎} + 𝑃_{𝑏} + 𝑃_{𝑐}^{*} \\ = 𝑃_{𝑎} + 𝑃_{𝑏} + (𝑃_{𝑐} - 𝑃_{𝑎} - 𝑃_{𝑏}) \\ = 𝑃_{𝑐} \end{aligned}

Carol just wiped everyone else from the signing key, and is now in full control of the signature. How can we prevent that ?

Multi-Signatures, don’t trust, verify

The most common way to prevent this is to force everyone to provide a proof that their public key is honest. This is done by providing a Proof of Knowledge for the private key, proving that they know the private key associated to the public key they provided.

Let’s take the case of a prover Patricia and a verifier Victor. Patricia wants to prove that she knows the private key $𝑝$ associated to the public key $𝑃 = 𝑝 \cdot 𝐺$ . The proof is done in four steps:

Patricia samples $𝑟 \leftarrow ℤ_{𝑛}$ at random and sends $𝑅 = 𝑟 \cdot 𝐺$ to Victor.
Victor sends a challenge $𝑐 \leftarrow ℤ_{𝑛}$ to Patricia.
Patricia computes $𝑧 = 𝑟 + 𝑐 𝑝$ and sends it to Victor.
Victor verifies that $𝑧 \cdot 𝐺 = 𝑅 + 𝑐 𝑃$ .

This works because:

\begin{aligned} 𝑧 & = 𝑟 + 𝑐 𝑝 \\ 𝑧 \cdot 𝐺 & = (𝑟 + 𝑐 𝑝) \cdot 𝐺 \\ = 𝑟 \cdot 𝐺 + 𝑐 𝑝 \cdot 𝐺 \\ = 𝑅 + 𝑐 𝑃 \end{aligned}

But what if Patricia doesn’t know the associated private key but still wants to prove that her key is honest ? Remember commitment schemes ? We can use them here. In our case, every participant will commit to their public key before disclosing it. Think of it as putting your public key in a box, sealing it and waiting for everyone to do the same before opening it. Let’s get back to our group $𝑆 = {𝑎, 𝑏, 𝑐}$ :

Each participant $𝑖$ hashes their public key $𝑃_{𝑖}$ and sends $𝐻 (𝑃_{𝑖})$ to everyone.
Once everyone has sent their hash, they disclose their public key $𝑃_{𝑖}$ .
Everyone verifies that the hash they received matches the public key.
The signing process continues as usual.

This way, everyone can be sure that the public keys are honest and that no one is trying to pull a fast one.

There’s more!

Random nonces are also aggregated, and at no point we are verifying that they are authentic. The exploit method is a bit trickier, I recommend you to read this article by conduition on the subject if you want to know the details.

References and Suggested readings

Practical Cryptography for Developers - Digital Signatures
Svetlin Nakov
cryptobook.nakov.com
A Dive Into the Math Behind Bitcoin Schnorr Signatures
conduition.io
Wagner’s Birthday Attack - How to Break InsecureMuSig
conduition.io
How to Prove Schnorr Assuming Schnorr: Security of Multi- and Threshold Signatures
Elizabeth Crites, Chelsea Komlo, and Mary Maller
eprint.iacr.org