4.4 Digital signatures

ECDSA

ECDSA stands for elliptic curve digital signature algorithm. It is used to verify that a message was signed by a certain user.

Consider a curve $E$ over a field $\mathbb F_q$ and a subgroup of a prime size $r$ with generator $G$ ($r$ should be large). All these parameters are public. Then a signer generates a private key $s \in \mathbb F_r$ and reveals a public key $K = [s]G$.

Assume a signer wants to sign a message $m$ with hash $H(m) \in \mathbb F_r$ (both $m$ and $H(m)$ is public). Then he chooses a random $k \in \mathbb F_r^*$, computes $R:=[k]G=(x_R,y_R)$ and a signature $s_g:=k^{-1}(H(m)+sx_R) \pmod r$. Then he publishes:

$$(R, s_g)$$

The verifier generates $H(m)$ and then computes $u_1=s_g^{-1}H(m)$ and $u_2=s_g^{-1}x_R$. Then computes $V=[u_1]G+[u_2]K$. The signature is valid if $V=R$.

Let's check that it's indeed the case:

$$V=[u_1]G+[u_2]K=[s_g^{-1}H(m)]G+[s_g^{-1}x_Rs]G =\\ [s_g^{-1}]([H(m)]G+[x_Rs]G)=[s_g^{-1}s_gk]G=[k]G=R$$

BLS 12-381

BLS 12-381 is named after Barreto-Lynn-Scott with 12 being the embedding degree of the elliptic curve and 381 is the number of bits that's needed to encode field size ($q$). It is a more advanced algorithm than ECDSA and allows having aggregated and threshold signatures.

Setup

This algorithm relies heavily on pairings, so let's describe the setup. First, it's based on a family of elliptic curves with the folowing attributes:

$$q(x):=\frac{1}{3}(x-1)^2(x^4-x^2+1)+x \\ r(x):=\Phi_{12}(x)=x^4-x^2+1 \\ t(x) = x+1$$

So we can pick some parameter $x$ and then find an elliptic curve with these attributes, namely $q$ - finite field size, $r$ - the size of the torsion subgroup, $t:=|E(\mathbb F_q)-q-1|$ - trace of the curve.

In a specific case of BLS 12-381 we take

$$x = -15132376222941642752 \\ q = 4002409555221667393417789825\\ 7359041565568828199390078853\\ 3205813612403165049083786444\\ 2687629129015664037894272559787 \\ r= 5243587517512619047944774050\\ 8185965837690552500527637822\\ 603658699938581184513\\ t=-15132376222941642751$$

Or in hexadecimal:

$$x = -0xd201000000010000 \\ q = 0x1a0111ea397fe69a4b1ba7b643\\ 4bacd764774b84f38512bf6730d2\\ a0f6b0f6241eabfffeb153ffffb9\\ feffffffffaaab \\ r=0x73eda753299d7d483339d808\\ 09a1d80553bda402fffe5bfeffff\\ ffff00000001 \\ t = -0xd20100000000ffff$$

In this case we have embedding degree is $12$ (we can check $r \mid q^{12} - 1$).

Then we define a field extension $\mathbb F_{q^{12}}$ in the following way:

$$\mathbb F_{q^2}:= \mathbb F_q(\alpha), i^2+1 = 0 \\ \mathbb F_{q^6}:= \mathbb F_{q^2}(\beta), \beta^3- i - 1 = 0 \\ \mathbb F_{q^{12}}:= \mathbb F_{q^6}(\gamma), \gamma^2-\beta = 0 \\$$

Next we define two curves: the prime curve and it's sextic twist:

$$y^2 = x^3+4 \\ y^2 = x^3+4(1+i) \\$$

Note they have both the same j-invariant ($j=0$) and hence isomorphic. Moreover $u=\gamma$ and $u^6 = 1+i \in \mathbb F_{q^2}$ so this is indeed a sextic twist.

Then we can define an Ate pairing:

$$\alpha_{\lambda}: E[r]_{\mathbb F_{q^k}} \times E_{\mathbb F_{q^k}}/[r]E_{\mathbb F_{q^k}} \to \mu_r$$

with $\lambda = q \pmod r$.

But we take the first torsion to be from $\mathbb F_q$ since $r \mid |E_{\mathbb F_q}|$ and the second from $\mathbb F_{q^2}$ of the twisted curve. We can do it since $d = 6$ and $k=12$ but the question is why do we have an $r$-torsion subgroup in a twist over $\mathbb F_{q^2}$? It can be derived that if $|E_{\mathbb F_q}|=q+1-t$ then $|E_{\mathbb F_{q^2}}|=q+1-t_2=q+1-(t^2-2q)$. But for twist we have $t'=-t$ so $t_2'=(-t_2)^2-2q=t_2$. So we have the same number of points in both curves over $\mathbb F_{q^2}$ but $r \mid |E_{\mathbb F_{q^2}}|$ since the r-torsion subgroup over $\mathbb F_q$ is still in $\mathbb F_{q^2}$. So we have r-torsion subgroup in a twist as well. To sum up out Ate pairing is defined in:

$$\alpha_{\lambda}: E[r]_{\mathbb F_{q}} \times E_{\mathbb F_{q^2}}/[r]E_{\mathbb F_{q^2}} \to \mu_r$$

So we limit ourselves to arithmetic in $\mathbb F_{q^2}$ only. But $\mu_r$ is in $\mathbb F_{q^{12}}$ so how come we're limited only to $\mathbb F_{q^2}$? The thing is we actually aren't. We're just doing all arithmetics in on elliptic curves in $\mathbb F_{q^2}$ but then we need to map it back to $\mathbb F_{q^{12}}$ via isomopshism and make a final expontiation in this field.

The following generators for two torsion groups are used:

$$G_1 := \lang P \rang_G,G_2 := \lang Q \rang_G \\ P = (x_P,y_P), Q = (x_Q, y_Q) \\ x_P=0x04 \\ y_P= 0x0a989badd40d6212b33cff\\ c3f3763e9bc760f988c9926b\\ 26da9dd85e928483446346b8\\ ed00e1de5d5ea93e354abe706c \\ x_Q=0x02 \\ y_Q=0x013a59858b6809fca4\\ d9a3b6539246a70051a3c888\\ 99964a42bc9a69cf9acdd9dd\\ 387cfa9086b894185b9a46a4\\ 02be73 + \\ 0x02d27e0ec3356299a346a0\\ 9ad7dc4ef68a483c3aed53f9\\ 139d2f929a3eecebf72082e5\\ e58c6da24ee32e03040c406d4f\cdot i$$

Hashing

To implement a digital signature we first need to find a way to hash a message into a point of the group $G_2$. We use the following algorithm:

1. Make a hash $h$ into a number mod $q$
2. Check if there's a point $S$ in $E'(\mathbb F_{q^2})$ with real part of $x$-coordinate being $h$ and imaginary part being $0$.
3. If there is then $G:=[|E'(\mathbb F_{q^2})|/r]S$ is the point in $E[r]$ and we can use the anti-trace map to map it to $G_2$ and that is our hash
4. If not: add 1 to message and goto 1.

note

This is a basic hashing algorithm that involve some trial-and-error check and thus doesn't have explicit guarantees on the time of the hashing (though in practice it works fine - 20 iterations in the worst random message in 1 000 000 messages).

Currently more advanced algorithms like SWU (The simplified Shallue–van de Woestijne–Ulas map of Brier) are used.

Single signature

We take private key to be any number

$$s:0 \le s \le r-1$$

Then public key

$$K:=[s]P$$

Then we take a hash of the message $m$ to be $H(m)$. Then the signature of the message is

$$S = [s]H(m)$$

Now we can easily verify this signature. It's valid iff:

$$\alpha_{\lambda}(P, S)=\alpha_{\lambda}(K, H(m))$$

Note that we can always do this check as all the arguments in the pairing are public. But in order to make this signature $S$ correct, the signer needs to know private key $s$. Why does this check work?

$$\alpha_{\lambda}(P, S) = \alpha_{\lambda}(P, [s]H(m))=\alpha_{\lambda}(P,H(m))^s= \\ \alpha_{\lambda}([s]P,H(m))=\alpha_{\lambda}(K,H(m))$$

Aggregated signatures

If we want the same message to be signed by $n$ parties we don't need to check pairing equations $n$ times. We can actually do it once. If we have keys $K_i=[s_i]P$ and signatures $S_i=[s_i]H(m)$ then we can calculate that combined key $K=\sum K_i$ and combined signature $S=\sum S_i$. Then

$$\alpha_{\lambda}(P, S)=\alpha_{\lambda}(P, \sum S_i)=\alpha_{\lambda}(P, \sum [s_i]H(m))= \\ \alpha_{\lambda}(\sum [s_i]P, H(m))=\alpha_{\lambda}(K, H(m))$$

Threshold signatures

Now we want to verify that message is signed by $k$ out of $n$ parties. To do that we generate a private key $s$ and then use a technique called Shamir Secret Sharing.

First, we take $n$ values of $x_i \in \mathbb F_r$ (this could be arbitrary like $1, 2, \ldots, n$ or some roots of unity). Then we assume that $a_0=s$ take $k-1$ random values $a_i \in \mathbb F_r (i=1,2,\ldots, k-1)$ and calculate a polynomial $f(x)=a_0 + a_1x + \ldots + a_{k-1}x^{k-1}$.

Next we calculate $n$ points $(x_i, s_i:=f(x_i))$ and give $s_i$ to each signing party. Each $(x_i, s_i:=f(x_i))$ is a private key. $K:=[s]P$ is public key that we make available to verifiers. Note that having $k$ private keys $(x_i, s_i)$ we can recover the private key $s$ using Lagrange interpolation:

$$s=a_0=f(0)=\sum_{j=0}^{k-1}s_j\prod_{i=0, i \ne j}^{k-1}\frac{x_i}{x_i-x_j}$$

This is how Shamir Secret Sharing works. In essence we take $n \ge k$ points of a polynomial of degree $k-1$. Knowing $k$ points we can reconstruct this polynomial and thus find $a_0$ which is our private key. At the same time having less than $k$ points is not enough to infer anything.

Now we use this technique for threshold signatures. Assume we have $k$ out of $n$ signatures:

$$(x_i,S_i:=[s_i]H(m))$$

Then the verifier has the following data:

$$m, H(m), K \\ (x_{i_1}, S_{i_1}), \ldots, (x_{i_k}, S_{i_k}) \\$$

The verification procedure then:

$$\alpha_{\lambda}(K, H(m))=\alpha_{\lambda}([s]P, H(m))=\alpha_{\lambda}(P, [s]H(m))= \\ \alpha_{\lambda}(P, [\sum_{j=0}^{k-1}s_j\prod_{i=0, i \ne j}^{k-1}\frac{x_i}{x_i-x_j}]H(m))= \\ \alpha_{\lambda}(P, [\sum_{j=0}^{k-1}b_js_j]H(m))= \\ \alpha_{\lambda}(P, \sum_{j=0}^{k-1}[b_j]S_j)$$

So all the verifier needs to check is:

$$\alpha_{\lambda}(K, H(m))=\alpha_{\lambda}(P, \sum_{j=0}^{k-1}[\prod_{i=0, i \ne j}^{k-1}\frac{x_i}{x_i-x_j}]S_j)$$

then we have correct $k$ out of $n$ signatures.