Fundamental Concepts Underlying Elliptic Curves (Level 2): Divisors and Pairings

Elliptic curve has a lot of nice structures attached to it. One of them is the idea of divisors. Using divisors, we can construct an example of a pairing, which is used for Pairing-Based cryptography. This is especially useful in the blockchain world to construct cryptographic primitives like threshold signatures. Here we only go over the basics of the theory of divisors and pairings, as we will be delaying the discussion of algebraic geometry, the field underlying the whole study of elliptic curves, to next time.

Prerequisites: Fundamental Concepts Underlying Elliptic Curves (Level 1): Projective Space)

Introduction

Zeros and Poles

In complex analysis, we study functions that are differentiable (in the complex sense) at almost all points. The study of the zeros (\(f(z)=0\)) and poles (\((1/f)(z)=0\)) is very important, because in complex analysis, the famous Cauchy’s integral theorem implies if \(f\) is holomorphic (does not have any poles), then for \(C\) enclosing a simply connected domain,\[\oint_Cf(z)d\,z=0,\] on the other hand, the residue theorem implies that the integral of \(f\) (that has poles) relates to the poles and its order.

Order of zeros

\[\DeclareMathOperator{\div}{div} \DeclareMathOperator{\Div}{Div} \DeclareMathOperator{\Pic}{Pic} \DeclareMathOperator{\Cl}{Cl} \DeclareMathOperator{\ord}{ord}\]

For polynomials, we know that \(f(x)=x\) and \(g(x)=x^2\) both have a zero at \(x=0\), but for \(g(x)\), the root is a “repeated root”. We say that for \(f(x)\), the order of zero (at \(x=0\)) is \(1\) while that of \(g(x)\) is \(2\).

On the other hand, \(h(x)=1/x\) and \(u(x)=1/x^2\) both have a pole at \(x=0\), but the order of pole of \(h\) is \(1\) while that of \(u\) is \(2\)¹.

In general, for a function \(f(z)\), the order of zero of a point \(z_0\) is \(m\), if \(f\) is analytic at \(z_0\), \(f^{(n)}(z_0)=0\) for \(n=0,1,\cdots,m-1\), and \(f^{(m)}(z_0)\neq 0\). The order of pole of a point \(z_0\) is \(m\), if for the function \(1/f\), the order of zero of \(z_0\) is \(m\).

For rational functions (where it can be written as a fraction, both numerator and denominator are polynomials), the order of zero of the whole function is the order of zeros of the numerator minus the order of zeros of the denominator. We say the order of zero of the zero polynomial is infinity.

We can denote the order of zero of a holomorphic (complex-differentiable) function \(f\) at the point \(p\) by \(ord_p(f)\). Then to extend the definition to meromorphic functions, if \(f=g/h\) where \(g\) and \(h\) are holomorphic , then \(\ord_p(f)=\ord_p(g)-\ord_p(h).\)

The order satisfies the following properties:

1. \(\ord_p(f)\in \mathbb{Z}\cup\{\infty\},\) and \(\ord_p(f)=\infty\iff f=0\)
2. \(\ord_p(fg)=\ord_p(f)+\ord_p(g)\) for any \(f\) and \(g\)
3. \(\ord_p(f+g)\leq \min\{\ord_p(f),\ord_p(g)\}\), equality holds if \(f\neq g\).

---

Divisor of Meromorphic Functions

The zeros and poles of a meromorphic functions can be captured in a simple object.

Divisor Group

Let \(\Div(\mathbb{C}^*)\) be the free abelian group generated by the points of \(\mathbb{C}^*\)². Elements of \(Div(\mathbb{C}^*)\) have the form \(\displaystyle\sum_{P\in\mathbb{C}^*} n_p (P)\), where the sum is finite.

These elements are called divisors. The group itself is called the divisor group of \(\mathbb{C}^*\).

If \(D\in \Div(\mathbb{C}^*)\), we can define the degree of a divisor as \(\displaystyle\deg D = \sum_{P\in\mathbb{C}^*} n_p\).

Divisor of Meromorphic Functions

For a meromophic function \(f(z)\), we can define the divisor of \(f\) as \[\div f=\sum_{P\in\mathbb{C}^*} \left(\ord_Pf\right)(P).\] Since \(f\) is meromorphic, the points \(P\) at which \(\ord_P f\neq 0\) is finite, so \(\div f\) is indeed a divisor. In fact, if \(f\in K(\mathbb{C}^*)^*\) (non-zero meromorphic function), then \(\deg\div f=0\).

Principal Divisors

Let \(K(\mathbb{C}^*)\) be the field of meromorphic functions on \(\mathbb{C}^*\). Then the divisor function \(\div\cdot: K(\mathbb{C}^*)^*\to \Div(\mathbb{C}^*)\) is a homomorphism of groups. Divisors of the form \(\div f\) is known as principal divisors.

We say two divisors are linearly equivalent, denoted \(D\sim D'\), if \(D-D' = \div f\) for some meromorphic \(f\). This give rise to the quotient group of \(\Div(\mathbb{C}^*)\) by the principal divisors, as the Picard group (or the divisor class group) of \(\mathbb{C}^*\), denoted as \(\Pic(\mathbb{C}^*)\) or \(\Cl(\mathbb{C}^*)\).

Example

Let’s work through an example of computing the divisor of the function \(f(z) = z^2 + 1\). Obviously we have a pole of order \(1\) at \(z=i\) and \(-i\). However, since we are considering the domain of \(\mathbb{C}^*\), we also need to consider the point at infinity. In this case we say we have a pole at infinity if \(f(\frac 1z)\) has a zero at \(z=0\), and a pole at infinity if \(f(\frac 1z)\) has a pole at \(z=0\).

Here we have \(f(\frac 1z) = \frac{1}{z^2}+1\), which has a pole of order \(2\) at \(z=0\). So in the divisor of \(f\) is \[\div f = (i)+(-i)-2(\infty)\]

Of course, since \(f\) is meromorphic, we already know that \(\deg \div f = 0\), so after computing the zeros and poles of points in \(\mathbb{C}\), we can already conclude that \(\ord_\infty f = -2\).

---

Divisors of Elliptic Curves

Now we turn our attention back to elliptic curves. The theory of divisors are almost the same as the case of \(\mathbb{C}^*\) (with the details omitted for now), except in the case of the Riemann shpere, we are considering meromorphic functions. In the case of elliptic curves, the function we consider rational functions, which we shall discuss next time, but for now, just think of them as “locally” a ratio of polynomials.

Elliptic Curve and its Picard Group

Using the definition as above, and let \(E\) be an elliptic curve,

Theorem : For each degree-0 divisor \(D\in \Div(E)\), there exists a point \(P\in E\) such that \(D\sim(P)-(\mathcal{O})\).

This gives an isomorphism of groups between \(E\), and the degree-0 part of the Picard group \(\Pic^0(E)\) (where the group operation is taken from \(\Div(E)\)).

Corollary : Let \(E\) be an elliptic curve and \(\displaystyle D=\sum_{P\in E}n_P(P)\in\Div(E)\) be a divisor. Then \(D\) is a principal divisor if and only if\[\sum_{P\in E}n_P=0\qquad\text{and}\qquad\sum_{P\in E} [n_P]P = \mathcal{O} \]

Where the second summation is using the group law of elliptic curves.

---

Pairing-based Cryptography

To see how divisors relate to cryptography, we first turn our attention back to cryptoghraphy.

Let \(G_1,G_2,G_T\) be three cyclic groups all of order \(q\), where \(q\) is a prime number. By convention we write the first two group additively, and the third multiplicatively. Then a pairing is a map \(e:G_1\times G_2\to G_T\) such that

1. (Bilinearity 1) For every \(U,V\in G_1\) and \(W\in G_2\), \(e(U+V,W)=e(U,W)e(V,W)\).
2. (Bilinearity 2) For every \(U\in G_1\) and \(V, W\in G_2\), \(e(U,V+W)=e(U,V)e(U,W)\).
3. (Non-degeneracy) For every \(P\in G_1\) that is not the identity, there exists \(Q\in G_2\) such that \(e(P,Q)\neq 1\). Similarly for \(Q\in G_2\).

Example (Determinant): For every free \(R\)-module \(M\), the determinant map \(\det: M\times M\) is a non-degenrate bilinear map.

Let \(R=\mathbb{Z}/m\mathbb{Z}\) where \(m\) is an integer larger than 1, and consider the free \(R-\)Module \(R\times R\), the determinant is a pairing. Choosing a basis \(\{u, v\}\), we have \[\det(au+bv, cu+dv)=ad-bc \] where we note that the value is independent of the choice of basis.

We also note that the definition of pairing implies for every \(P\in G_1, Q\in G_2\) and \(a,b\in \mathbb{Z}\), we have \(e(aP,bQ)={e(P,Q)}^{ab}\).

Example : Let \(G_1=G_2=F_5\) (under addition), and \(G_T=\langle 5\rangle =\{1,3,4,5,9\}\in F_{11}^\times\) (under multiplication). Then the map \(e:G_1\times G_2\to G_T\), \(e(x,y)=3^{xy}\pmod{11}\) is a pairing.

Check to see that \(e(u+v, w)=3^{(u+v)w}= 3^{uw}3^{vw}=e(u,w)e(v,w)\). The case for \(G_2\) is the same. To see non-degeneracy, in this case we just need to enumerate all possibilities.

Exercise: Let \(G_1,G_2,G_T\) as above, \(u\in G_1, v\in G_2\) and \(a\in \mathbb{Z}_{>0}\). Show that \(e(au, v) = e(u,av)\).

BLS digital signature

One application of pairings in cryptography is to create digital signatures. Let \(G, G_T\) be cyclic groups of prime order \(q\), and \(e: G\times G\to G_T\) be a pairing. Additionally we also assume a hash function \(H\) that outputs an element in \(G\). Pick a generator \(g\) for \(G\).

To generate the key, we pick a random integer \(x\) with \(0<x<q\), the private key is \(x\), and the public key is \(g^x\).

To sign a message \(m\), we first compute the hash of it \(H(m)\), then the signature is \(H(m)^x\).

To verify a message \(s\) and the public key \(pk\), we simply verify that \(e(s,g) = e(H(m),pk)\).

The correctness of the signature is due to the fact that \(e(s,g) = e(H(m)^x, g) = e(H(m), g^x) = e(H(m), pk))\).

One nice property of BLS is that the signature is very small: it consists of only a single group element (of roughly the same size as \(q\))!

Computational Diffie-Hellman

The security of BLS relies on the fact that (roughly) the discrete logarithm problem of the underlying group \(G\) is hard. More specifically, we assume that the computational Diffie-Hellman (CDH) problem is intractable.

Definition (CDH): Let \(\langle g\rangle\) be a finite cyclic group of prime order \(p\). Let \(a,b\in \mathbb{Z}_p^*\), and given \((g, g^a, g^b)\), the computational Diffie-Hellman problem asks the value of \(g^{ab}\).

---

Weil Pairing

Now we try to construct a pairing with elliptic curves. Let \(E\) be an elliptic curve over \(K\), \(m\) an integer larger than 2, which is relatively prime to \(char(K)\).

Proposition-Definition (\(m-\)torsion point): The group of \(m-\)torsion points \(E[m]=\{P\in E: [m]P=\mathcal{O}\}\) are the points \(P\in E\) such that \([m]P=0\). It is the kernel of the function \([m]: E\to E\) defined by \(P\mapsto [m]P\).

We have that \(E[m] \cong \mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/m\mathbb{Z}\).

Let \(P, Q\in E[m]\), and choose a rational function \(F\) such that the divisor is \[\div F = \sum_{0\leq k<m} (P+[k]Q) - ([k]Q) \]. This is possible because \(\displaystyle \sum_{0\leq k<m} P+[k]Q - [k]Q = [m]P= \mathcal{O}\) (since \(P\) is a \(m-\)torsion point), and by applying the corollary above the divisor is principal.

Let \(G(X) = F(X+Q)\), then the divisor of \(G\) is the same, so \(F(X+Q)/F(X)\) is constant, and is a \(m-\)th root of unity. Then define the Weil pairing as \(e_m(P,Q) = \frac{F(X+Q)}{F(X)}\). This is a mapping from \(E[m]\times E[m]\to \mu_m\), where \(\mu_m\) contains the \(m-\)th roots of unity \(\mu_m=\{x\in K: x^m=1\}\).

Example

Here we use an example of the curve BLS 12-381, which is defined by \(y^2=x^3+4\pmod{q}\) where \(q\) is as defined below. The code snippet below shows a weil pairing with \(m=11\).

References

Silverman, J. H. (2009). The arithmetic of elliptic curves (Vol. 106, pp. xx+-513). New York: Springer.

1. We also say the order of zeros of \(h\) is \(-1\). ↩

2. The same as \(\mathbb{P}^1(\mathbb{C})\), the complex plane plus the point at infinity. \(\mathbb{C}^*\) is also known as the Riemann sphere. ↩