cstef
/posts/multi-sig
TOP

Using ECC for (Multi-)Signatures

Math-powered methods for proving message authenticity, sounds great, doesn't it?

04/12/2024 Β· 10 min read Β· sapling πŸͺ΄

cryptography maths
Info

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 (r, s)(r, s) for a given message mm, so that the recipient can verify that the sender is authentic. The sender’s keys are (p, P)(p, P), with pp the private key, and PP the public one.

ECDSA Signatures

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

  1. Compute the hash h = H(m)h = H(m) where H(x)H(x) is any cryptographic hash function (e.g. SHA-256).
  2. Generate a random kk number in in the current subgroup.
  3. Calculate the associated random point on the curve K = k dot GK = k dot G, with GG a generator, with x_Kx_K the xx-coordinate of this point.
  4. Calculate the signature s = k^(-1) dot (h + x_K dot p)s = k^(-1) dot (h + x_K dot p), where k^(-1)k^(-1) is the modular inverse of kk.

By sending (r, s)(r, s), you confirm you know:

The verifier may follow this procedure to check if the message mm that he received along with (r,s)(r,s) is authentic:

  1. Compute the hash h = H(m)h = H(m) with the same cryptographic hash function defined before.
  2. Calculate the modular inverse of ss: S = s^(-1)S = s^(-1)
  3. Recover the random point used in the signature process: K = h S dot G + r S dot PK = h S dot G + r S dot P
  4. Check whether x_K = rx_K = r, if so, then the message is authentic.

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

& s = k^(-1) dot (h + x_K dot p) \ <==>& s dot & s = k^(-1) dot (h + x_K dot p) \ <==>& s dot

Incorporate (a)(a) into KK:

K &= h S dot G + r S dot P \ &= h s^(-1) dot G +K &= h S dot G + r S dot P \ &= h s^(-1) dot G +

Which is just our definition of KK 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 PP along with the signature (r, s)(r, s) because that’s just too much data. Instead, you can recover the public key from the signature and the message.

Given x_Kx_K, there are typically two candidate points K'_iK'_i that fit. And since we know that K = h S dot G + r S dot PK = h S dot G + r S dot P, which we just verified works, it can be rearranged to isolate the public key PP:

K'_i &= h S dot G + r S dot P_i \ <==> P_i &= K'_i &= h S dot G + r S dot P_i \ <==> P_i &=

To choose which one is the correct one, we need to verify the signature with each P_iP_i:

K_i = h S dot G + r S dot P_i = (x_K, y_K) \ x_K =K_i = h S dot G + r S dot P_i = (x_K, y_K) \ x_K =

This ambiguity is often removed by adding a single bit b in {0,1}b in {0,1} into the signature message: (r, s, b)(r, s, b)

Schnorr Signatures

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

  1. Sample a random nonce r <- ZZ_nr <- ZZ_n
What the hell is ZZ_nZZ_n?

The set ZZ_nZZ_n is a cyclic group of integers, isomorphic to the quotient group ZZ slash n ZZZZ slash n ZZ. It is basically just the set of integers modulo nn.

ZZ_n = {0, 1, 2, ..., n-1}ZZ_n = {0, 1, 2, ..., n-1}

In our case, nn is the order (how many points are in) of the subgroup generated by GG. If the curve’s cofactor hh is 1, then nn is the order of the curve. If hh is not 1, the order is n/h = "ord"(G)n/h = "ord"(G)

  1. Multiply it by the generator: R = r GR = r G
  2. We can now compute the challenge e = H(R || P || m)e = H(R || P || m)
  3. And the signature: s = r + e ps = r + e p

The final signature is (R, s)(R, s).

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

s dot G = R + e Ps dot G = R + e P

To know ee, the verifier needs to know the message mm, the public key PP. In some cases, you might not need to include the public key into the challenge and simply hash e = H(R || m)e = H(R || m).

Why it Works

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

& s dot G = R + e P \ <==>& s dot G = underbra & s dot G = R + e P \ <==>& s dot G = underbra

One trickier part is to explain why we are adding a random nonce rr 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 rr is used:

& s = e p \ <==>& p = s^(-1) e & s = e p \ <==>& p = s^(-1) e

Recovering the private key is as simple as multiplying the challenge ee by the modular inverse of ss. Not good.

Now, let’s take the case where rr is reused, with two messages m_1m_1 and m_2m_2, along with their respective signatures (R, s_1)(R, s_1) and (R, s_2)(R, s_2):

cases( space s_1 = r + e_1 p <==> r = (s_1 - ecases( space s_1 = r + e_1 p <==> r = (s_1 - e

Combining (a)(a) and (b)(b):

& r = (s_1 - e_1 p) = (s_2 - e_2 p) \ <==>& e_ & r = (s_1 - e_1 p) = (s_2 - e_2 p) \ <==>& e_

You may see rr as an additional unknown variable that is used to prevent the linear equation system from being solved, because for nn messages, you have nn equations and n+1n+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 mm together and the signature can be verified as if it was signed by a single person. Let’s consider our signing group S = {a,b,c}S = {a,b,c} for Alice, Bob and Charlie respectively.

&underline("Alice") &&underline("Bob") &&underline&underline("Alice") &&underline("Bob") &&underline

The aggregated nonce is simply the sum of all nonces:

R &= sum_(i in S) R_i \ &= R_a + R_b + R_c \ &R &= sum_(i in S) R_i \ &= R_a + R_b + R_c \ &

Likewise for the public key:

P &= sum_(i in S) P_i \ &= P_a + P_b + P_c \ &P &= sum_(i in S) P_i \ &= P_a + P_b + P_c \ &

Each of them computes the challenge ee along with the final signature s_is_i with the parameters just agreed upon:

e = H(R || P || m) \ s_i = e p_i + r_ie = H(R || P || m) \ s_i = e p_i + r_i

Aggregate again:

s = sum_(i in S) s_is = sum_(i in S) s_i

The final signature that can be sent to others is (R, s)(R, s).

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

s &= sum_(i in S) s_i \ &= sum_(i in S) (e p_i +s &= sum_(i in S) s_i \ &= sum_(i in S) (e p_i +

In the verifying step, multiplying each side by GG:

s G &= sum_(i in S) r_i dot G + e dot sum_(i in S)s G &= sum_(i in S) r_i dot G + e dot sum_(i in S)

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 P^*_cP^*_c 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:

P^*_c = P_c - P_a - P_b \P^*_c = P_c - P_a - P_b \

The aggregated key will look like:

P &= sum_(i in S) P_i \ &= P_a + P_b + P^*_c \ P &= sum_(i in S) P_i \ &= P_a + P_b + P^*_c \

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 pp associated to the public key P = p dot GP = p dot G. The proof is done in four steps:

  1. Patricia samples r <- ZZ_nr <- ZZ_n at random and sends R = r dot GR = r dot G to Victor.
  2. Victor sends a challenge c <- ZZ_nc <- ZZ_n to Patricia.
  3. Patricia computes z = r + c pz = r + c p and sends it to Victor.
  4. Victor verifies that z dot G = R + c Pz dot G = R + c P.

This works because:

z &= r + c p \ z dot G &= (r + c p) dot G \ z &= r + c p \ z dot G &= (r + c p) dot G \

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 S = {a,b,c}S = {a,b,c}:

  1. Each participant ii hashes their public key P_iP_i and sends H(P_i)H(P_i) to everyone.
  2. Once everyone has sent their hash, they disclose their public key P_iP_i.
  3. Everyone verifies that the hash they received matches the public key.
  4. 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 / Suggested readings