Bilinear Pairings

In the previous part we explored Fields, Torsion Points, and Endomorphism. Now we are gonna take our understanding of the topic further and dig into more constructions revolving around the Elliptic Curves, namely:

Divisors
Overview of Principal divisor, Picard groups
Introduction to Genus

Understanding Divisors: A Key Concept in Algebraic Geometry

A divisor is a mathematical construct that helps us study functions and points on algebraic curves, such as elliptic curves. In simple terms, a divisor is a formal sum of points on a curve, where each point is assigned an integer coefficient.

Formal Definition

A divisor DD on an algebraic curve CC is a formal sum of points:

$$D = \sum_{P\in C}n_p. P$$

where:

P are the points on the curve C,
$n_P$ are integers (can be positive, negative, or zero) also called multiplicity.. The multiplicity of a point in a divisor quantifies how much that point contributes to the divisor.
- $n_p> 0$ => point P contributes as a zero of a function
- $n_p <0$ => point P contributes as a pole of a function
- $n_p = 0$ => point P does not contribute to the divisor.
Only finitely many are nonzero.

For example, D=3P−2Q+R is a divisor, where P, Q, and R are points on the curve.

The set of all divisors on $E$ is denoted by $Div_{\overline{F_q}}(E)$ and forms a group, where addition of divisors is natural, and the identity is the divisor with all $n_p = 0$, the zero divisor $0 \in Div_{\overline{F_q}}(E)$

Degree of a Divisor

The degree of a divisor D is the sum of its coefficients:

$$D = \sum_{P\in C}n_p$$

For $D=3P−2Q+R, deg(D)=3−2+1=2$.

Divisors of degree 0 are particularly important in pairing-based cryptography because they often correspond to the group elements used in cryptographic operations.

Support of a Divisor

The support of a divisor D:

$$supp(D) = { P \in E(\overline{F_q})}$$

Associating divisors with a function

Writing divisors as a function f on E is a convenient way to write down the intersection points ( and their multiplicities) of f and E.

$$(f) = \sum_{P \in E(\overline{F_q})}ord_P(f)(P)$$

where $ord_P(f) $ counts the multiplicity of f at P.

In pairing-based cryptography, divisors help define certain mathematical structures on elliptic curves:

Principal Divisors and Pairings: Bilinear pairings, such as the Weil pairing and Tate pairing, rely on divisors to define their operation.
Divisors and Group Elements: The points on elliptic curves can be seen as specific types of divisors, and their manipulation through pairings is crucial for cryptographic protocols.

Types of Divisors

Effective Divisor: All coefficients $n_p >= 0$. For instance, $D = P + 2Q$.
Principal Divisor: A divisor associated with a rational function f on the curve.
- Zeros of f contribute positively.
- Poles of f contribute negatively.

eg. If f has a zero of order 2 at P and a pole of order 1 at Q, its divisor is $D = 2P - Q$.

If a divisor D is equal to the divisor of a function, i.e. $D = (f)$ then D is the principal divisor.

A principal divisor always has degree of 0.

$$Prin(E) \subset Div^0(E) \subset Div(E)$$

Understanding Divisor Equivalence and Picard Groups

We will use an example to understand the divisor equivalence.

Consider the elliptic curve $E/F_{61}: y^2 = x^3 + 8x + 1$. We have four points: $P = (57, 24), Q=(25,37), R=(17,32), S = (42,35)$.

Two divisors on E:

$D_1 = (P) + (Q) + (R)$
$D_2 = 4(O) - (S) $ where O is point at infinity

Proving Equivalence: The divisors $D_1$ and $D_2$ are equivalent because there exists a rational function $f(x,y)$ on $E$ with the divisor: $(f) = (P) + (Q) + (R) + (S) - 4(O)$

Here, $f(x,y)$ is the function $y = 33 x^2 + 10 x + 24$ which intersects $E $ at $P,Q,R,S$, each with the multiplicity of 1. This implies f has a pole of order 4 at $O$. Substituting in the equivalence relation: $D_1 = D_2 + (f)$ we see $D_1\sim D_1$showing that $D_1 $ and $D_2$ lie in the same divisor class.

An alternate perspective: If finding $f$ explicitly seems challenging, we can consider the difference $D_1 - D_2= (P) + (Q) + (R) + (S) - 4(O)$. The divisor has degree zero, satisfying the condition for membership in the group of degree-zero divisors, $Div^0(E)$. Using the addition law on elliptic curve, we compute: $P+Q+R+S-[4]O = 0$ indicating that $D_1- D_2$ belongs to the set of principal divisors, $Prin(E).$ Thus $D_1 - D_2 = (f) $ for some function f, reaffirming $D_1 \sim D_2$.

Picard Group ( Divisor Class group ):

The example introduces the Picard group of E. It is defined as:

$$Pic^0(E) = Div^0(E) / Prin(E)$$

In simpler terms, the Picard group is the collection of all degree-zero divisors, grouped by their equivalence under principal divisors.

Imagine you’re organizing a grand party, and you’re assigning tasks to your friends. Some of these tasks are simple, like “buy decorations” or “set up the music system,” while others are combinations of simpler tasks, like “prepare the venue” (which involves cleaning, arranging chairs, and decorating).

Now, here’s the catch: you don’t care how the tasks are grouped or assigned, as long as everything gets done. Whether one person handles “cleaning” and another does “decorating,” or one friend takes care of “preparing the venue” as a whole, it’s all the same to you as long as the end result is a successful party.

The Picard group works a bit like this. It’s a system for organizing and simplifying the roles (or relationships) of "tasks" (called divisors) on an elliptic curve. Here's how it works:

The Party Roles as Divisors

Tasks (Divisors): On the curve, each point represents a “task.” Some tasks are simple (like single points), while others are combinations of tasks (like sums of points).
Simplified Groups (Equivalence Classes): If two sets of tasks result in the same outcome (e.g., the venue looks ready), the Picard group treats them as equivalent. In math terms, these are called divisor classes.
Irrelevant Details (Principal Divisors): Just like you might ignore the specific order in which chairs are arranged if the venue still looks perfect, the Picard group ignores certain kinds of "irrelevant" details (principal divisors). These don’t affect the overall result and are treated as if they were invisible.

Let’s understand Principal divisor a bit using another analogy:

Imagine you have a see-saw, and you place weights (points on the curve) at different positions. The goal is to balance the see-saw so it doesn’t tip over.

Now, think of the function f as a special tool you can use to shift the weights around. This tool doesn’t change the total weight or the balance of the see-saw—it only redistributes the weights in a way that maintains equilibrium. Once the see-saw is balanced, the exact arrangement of weights doesn’t matter anymore; what matters is that the see-saw stays level.

In the mathematical world:

The divisor of f (written as $(f)$) records where f "puts" weights (its zeros and poles).
This divisor is called principal because it comes directly from f, which guarantees it maintains balance (degree zero).

When we’re working in the Picard group, we only care about whether the "see-saw" is balanced (the overall divisor class), not the specific arrangement of weights. This is why (f) doesn’t change anything important—it’s invisible in this sense.

Evaluating a Function at a Divisor

Evaluating a function $f \in F_q(E)$ at a divisor $D= \sum_{P \in E} n_p(P)$ has a natural definition, provided the divisors $(f)$ and $D$ have disjoint supports:

$$f(D) = \prod_{P \in E}f(P)^{n_p}$$

An Introduction to Genus

For any curve C, there is a unique minimal integer g, called the genus of C, such that any divisor $D \in Pic^0(C)$ is equivalent to a divisor $D^{'}$ with $Deg(\epsilon(D^{'}) <= g $ where $~ \epsilon(D^{'}) $ is the effective divisor. Elliptic curves $E$ are curves of genus = 1, meaning that every $D \in Pic^0(E)$ can be written as $(P_1) - (Q_1)$.

Imagine you’re designing different types of paper-folding crafts. The genus of a surface tells you how many “holes” or “handles” it has. For example:

A plain sheet of paper has no holes—it’s simple and flat. This is like a curve with genus 0.
If you take a piece of paper and make a single hole or a tunnel in the middle, you’ve added one hole. This is like a curve with genus 1.
If you were to fold or tear the paper to create multiple tunnels or holes, the number of holes increases, and the surface becomes more complex, which corresponds to a higher genus.

Now, let’s relate genus to divisors.

Think of a divisor as a way of distributing certain “marks” or “labels” across the surface of your folded paper (your curve). A divisor could represent things like:
- Marks where the paper is bent (points where a function is zero), or
- Marks where the paper is torn (poles where a function has an infinite value).

For any curve, the genus g tells us how complex these divisors can be. Specifically:

The genus gives us an upper bound on how complicated the divisor can be while still remaining "balanced" or simple enough to manage.
No matter how complicated a divisor looks, we can always find a simpler equivalent divisor with at most g total complexity. Essentially, the genus limits how much complexity or imbalance can exist in the system.

Elliptic curves are simple in terms of their genus, with $g=1$ This means every divisor on an elliptic curve can be simplified to just the difference between two points.

Elliptic curves are of genus 1 because they have just enough complexity to be interesting (like a simple fold or tunnel in paper), but not too complex to make the math difficult to handle.

This concludes Part 2 of our series, where we've explored the Picard group, divisors, principal divisors, genus, and their interconnections. In the next part, we’ll dive into "Pairing Groups" and build on everything we've discussed so far, leading us to a deeper understanding of bilinear relationships.

In the next part, we will dig into "Pairing Groups" and connect everything we discussed so far to create a bilinear relationships. Stay tuned!

For more updates, insights, and discussions, connect with me on Twitter: @privacy_prophet.

References

Parings for beginners

Bilinear Pairings: Deep Dive Part 2