07b-weil-pairing-intuition.ipynb

Kernel: SageMath 10.5

Notebook 07b: Weil Pairing Intuition

Module 07. Bilinear Pairings

---

Motivating Question. In Notebook 07a we defined bilinear maps abstractly and used SageMath's weil_pairing() as a black box. But where does this map actually come from? The answer involves divisors, formal sums of points on curves, and rational functions. Understanding divisors gives geometric meaning to the pairing and explains why bilinearity holds. We won't prove everything rigorously, but we'll build enough intuition to see the pairing as a natural construction, not magic.

---

Prerequisites. You should be comfortable with:

• The definition and properties of bilinear maps (Notebook 07a)

• Elliptic curve point addition and the group law (Module 06)

• Polynomial evaluation and roots (Module 02)

Learning objectives. By the end of this notebook you will be able to:

1. Understand divisors as formal sums of points and compute their degree and sum.

2. Relate rational functions on curves to their divisors (zeros and poles).

3. Sketch how the Weil pairing is constructed from rational functions.

4. Understand Miller's algorithm at a high level.

5. Compute the Weil and Tate pairings in SageMath and compare them.

1. Divisors: Formal Sums of Points

Bridge from Module 06. In Module 06 we thought of points on $E$ as group elements. Now we need a new perspective: treating points as places where functions have zeros and poles. The language for this is divisors.

A divisor on an elliptic curve $E$ is a formal sum of points:

$$D = \sum_{P \in E} n_P \cdot (P)$$

where $n_P \in \mathbb{Z}$ and only finitely many $n_P \neq 0$. Think of it as a "bookkeeping device" that records a list of points with integer multiplicities.

Two key quantities:

• Degree: $\deg(D) = \sum_P n_P$ (sum of all multiplicities)

• Sum: $\text{sum}(D) = \sum_P n_P \cdot P$ (add the points using the group law, weighted by multiplicity)

# Set up our curve (same as 07a)
p = 59
E = EllipticCurve(GF(p), [1, 0])
O = E(0)  # point at infinity

# A divisor is just a dictionary: point → multiplicity
# Example: D = (P) + (Q) - 2(O)
P1 = E(1, 24)
P2 = E(4, 14)

# We represent divisors as lists of (multiplicity, point) pairs
D = [(1, P1), (1, P2), (-2, O)]

def div_degree(D):
    return sum(n for n, _ in D)

def div_sum(D):
    result = E(0)
    for n, P in D:
        result = result + n * P
    return result

print(f"Divisor D = (P1) + (P2) - 2(O)")
print(f"  where P1 = {P1}, P2 = {P2}, O = point at infinity")
print(f"  deg(D) = 1 + 1 + (-2) = {div_degree(D)}")
print(f"  sum(D) = P1 + P2 - 2·O = {div_sum(D)}")

Checkpoint 1. A divisor with $\deg(D) = 0$ and $\text{sum}(D) = \mathcal{O}$ is called principal. An important theorem (Abel's theorem for elliptic curves) states: a divisor is the divisor of a rational function if and only if it is principal. This connects the algebra of divisors to the geometry of functions on curves.

2. Rational Functions and Their Divisors

A rational function on $E$ is a ratio of polynomials $f = g/h$, where we consider points on the curve.

For example, the line through $P$ and $Q$ (used in point addition) is a rational function $\ell_{P,Q}(x, y) = y - \lambda x - \nu$. Its divisor records where it meets the curve:

$$\text{div}(\ell_{P,Q}) = (P) + (Q) + (-(P+Q)) - 3(\mathcal{O})$$

The line meets the curve at three points ($P$, $Q$, and the third intersection which becomes $-(P+Q)$), and has a pole of order 3 at $\mathcal{O}$.

Notice: $\deg = 1 + 1 + 1 - 3 = 0$ and $\text{sum} = P + Q + (-(P+Q)) = \mathcal{O}$. So this divisor is principal.

# The line through P and Q meets the curve at 3 points (Bézout)
P = E(1, 24)
Q = E(4, 14)
R = P + Q  # group law result
neg_R = -R  # the actual third intersection point (before reflection)

print(f"P = {P}")
print(f"Q = {Q}")
print(f"P + Q = R = {R}")
print(f"Third intersection = -(P+Q) = {neg_R}")

# Divisor of the line ℓ_{P,Q}
D_line = [(1, P), (1, Q), (1, neg_R), (-3, O)]
print(f"\nDiv(ℓ_PQ) = (P) + (Q) + (-(P+Q)) - 3(O)")
print(f"  deg = {div_degree(D_line)} (should be 0)")
print(f"  sum = {div_sum(D_line)} (should be O)")

# Similarly: the vertical line through R
# x = x_R has divisor (R) + (-R) - 2(O)
D_vert = [(1, R), (1, -R), (-2, O)]
print(f"\nDiv(x - x_R) = (R) + (-R) - 2(O)")
print(f"  deg = {div_degree(D_vert)} (should be 0)")
print(f"  sum = {div_sum(D_vert)} (should be O)")

3. The Weil Pairing Construction (Sketch)

Here's the key idea behind the Weil pairing, simplified:

Given: Two points $P, Q$ of order $n$ on $E$ (linearly independent in $E[n]$).

Step 1. Find a rational function $f_P$ whose divisor is: $$\text{div}(f_P) = n(P) - n(\mathcal{O})$$ Such a function exists because $nP = \mathcal{O}$, so this divisor has degree 0 and sum $\mathcal{O}$.

Step 2. Similarly find $f_Q$ with $\text{div}(f_Q) = n(Q) - n(\mathcal{O})$.

Step 3. The Weil pairing is: $$e_n(P, Q) = \frac{f_P(D_Q)}{f_Q(D_P)}$$

where $D_P, D_Q$ are auxiliary divisors equivalent to $(P) - (\mathcal{O})$ and $(Q) - (\mathcal{O})$ (with support disjoint from $f$'s zeros/poles).

The bilinearity comes from how divisors add: $\text{div}(f \cdot g) = \text{div}(f) + \text{div}(g)$.

Misconception alert. "You need to understand every detail of the Weil pairing construction to use it." Not true, for using pairings in protocols (BLS, IBE, SNARKs), you only need to know the bilinearity property. The construction matters for (a) trusting that the pairing exists, (b) understanding Miller's algorithm, and (c) advanced cryptanalysis. We aim for intuition, not a full proof.

4. Miller's Algorithm: Computing the Pairing

The function $f_P$ with $\text{div}(f_P) = n(P) - n(\mathcal{O})$ can be built iteratively using Miller's algorithm. The idea is analogous to double-and-add for scalar multiplication:

1. Start with $f_1$ (trivial function).

2. For each bit of $n$, update $f$ using the line functions from the group law.

3. After processing all bits, $f = f_P$.

The key identity: if $\text{div}(f_i) = i(P) - ([i]P) - (i-1)(\mathcal{O})$, then we can compute $f_{i+j}$ from $f_i, f_j$ and the line through $[i]P$ and $[j]P$.

Miller's algorithm runs in $O(\log n)$ steps, making pairing computation efficient.

# Miller's algorithm is what SageMath uses internally.
# Let's see it in action by computing the Weil pairing step by step.

# Set up our pairing-friendly curve
p = 59
E = EllipticCurve(GF(p), [1, 0])
n = 5  # subgroup order
k = 2  # embedding degree

F_pk = GF(p^k, 'a')
E_ext = E.change_ring(F_pk)

# Find generators P in E(F_p) and Q in E(F_{p^2})
cofactor = E.cardinality() // n
while True:
    P = cofactor * E.random_point()
    if P != E(0) and n * P == E(0):
        break

P_ext = E_ext(P)
cofactor_ext = E_ext.cardinality() // n
while True:
    Q = cofactor_ext * E_ext.random_point()
    if Q != E_ext(0) and n * Q == E_ext(0):
        if Q.weil_pairing(P_ext, n) != 1:
            break

# Compute Weil pairing
w = P_ext.weil_pairing(Q, n)
print(f"P = {P} (in E(F_{p}))")
print(f"Q = {Q} (in E(F_{{p^2}}))")
print(f"Weil pairing e(P, Q) = {w}")
print(f"Order of e(P, Q) = {w.multiplicative_order()}")

# The multiples of P trace out the n-torsion subgroup in G1
print("Multiples of P:")
for i in range(n + 1):
    iP = i * P
    label = " = O" if iP == E(0) else ""
    print(f"  {i}·P = {iP}{label}")

# The pairing maps each multiple to a power of w
print(f"\nPairing values (each multiple of P paired with Q):")
for i in range(n):
    val = (i * P_ext).weil_pairing(Q, n)
    # Find which power of w this is
    for j in range(n):
        if w^j == val:
            print(f"  e({i}P, Q) = w^{j} = {val}")
            break

Checkpoint 2. Miller's algorithm computes the pairing in $O(\log n)$ field operations, similar to double-and-add. Each step involves evaluating a line function at a point. This makes pairings practical: on a 256-bit curve, the pairing takes a few milliseconds, more expensive than a scalar multiplication, but still efficient.

5. The Tate Pairing

The Weil pairing is the classical construction, but in practice the Tate pairing (and its variants: ate, optimal ate) is more commonly used because it's faster.

The key difference:

• Weil pairing: Evaluate $f_P$ at $Q$ and $f_Q$ at $P$, then divide → two Miller loops.

• Tate pairing: Only evaluate $f_P$ at $Q$, then raise to a power ("final exponentiation") → one Miller loop.

$$\hat{e}(P, Q) = f_P(Q)^{(p^k - 1)/n}$$

SageMath provides tate_pairing() as well.

# Compute the Tate pairing
# SageMath's tate_pairing(Q, n, k) computes the Tate pairing with final exponentiation
t = P_ext.tate_pairing(Q, n, k)

print(f"Weil pairing: e_W(P, Q) = {w}")
print(f"Tate pairing: e_T(P, Q) = {t}")
print(f"\nBoth are {n}-th roots of unity:")
print(f"  e_W^{n} = {w^n}")
print(f"  e_T^{n} = {t^n}")

# The Tate and Weil pairings are related but not necessarily equal.
# They are both non-degenerate and bilinear.
# Check bilinearity of Tate:
a, b = 2, 3
lhs_t = (a * P_ext).tate_pairing(b * Q, n, k)
rhs_t = t^(a * b)
print(f"\nTate bilinearity: e_T({a}P, {b}Q) = {lhs_t}")
print(f"                  e_T(P,Q)^{a*b} = {rhs_t}")
print(f"                  Equal? {lhs_t == rhs_t}")

6. Comparing Weil and Tate Pairings

Property	Weil Pairing	Tate Pairing
Miller loops	2	1
Final exponentiation	No	Yes ($f^{(p^k-1)/n}$)
Alternating?	Yes: $e_W(P, P) = 1$	No
Speed	Slower	Faster (in practice)
Output	Primitive $n$-th root of unity	$n$-th root of unity

In production systems (BLS signatures, SNARKs), the optimal ate pairing is used, a variant of Tate that minimizes the Miller loop length.

# Demonstrate the alternating property of the Weil pairing
# e_W(P, P) = 1 (always, for Weil)
# e_T(P, P) might not be 1

print("Alternating property (Weil):")
e_PP_weil = P_ext.weil_pairing(P_ext, n)
print(f"  e_W(P, P) = {e_PP_weil} (always 1 for Weil)")

# This is why we need linearly independent points for a non-degenerate Weil pairing.
# P and Q must be from 'different' subgroups of E[n].

# For two DIFFERENT points of order n:
print(f"\nWeil pairing of independent points:")
print(f"  e_W(P, Q) = {w} ≠ 1 ✓")
print(f"  e_W(Q, P) = {Q.weil_pairing(P_ext, n)}")
print(f"  e_W(P, Q) · e_W(Q, P) = {w * Q.weil_pairing(P_ext, n)} (should be 1: anti-symmetry)")

Checkpoint 3. The Weil pairing is alternating: $e_W(P, Q) = e_W(Q, P)^{-1}$, and $e_W(P, P) = 1$. This means we can't get a non-trivial pairing from a single point, we need two linearly independent $n$-torsion points. This is why pairings require either:

• A supersingular curve (where $E[n]$ naturally has independent points from $\mathbb{F}_p$ and $\mathbb{F}_{p^k}$), or

• A twist (an isomorphic curve that provides a second independent subgroup).

7. A Larger Example

Let's work with a slightly larger curve to see pairings in a more realistic setting.

# Larger supersingular curve
p2 = 467  # prime, p ≡ 3 mod 4
E2 = EllipticCurve(GF(p2), [1, 0])
card2 = E2.cardinality()
print(f"Curve: y² = x³ + x over F_{p2}")
print(f"|E| = {card2} = p + 1 = {p2 + 1}")
print(f"Factorization: {factor(card2)}")

# Use n = 13 (prime factor of 468)
n2 = 13
k2 = 2
print(f"\nn = {n2}, embedding degree k = {k2}")

# Set up in extension field
F2 = GF(p2^k2, 'b')
E2_ext = E2.change_ring(F2)

cof2 = card2 // n2
while True:
    P2 = cof2 * E2.random_point()
    if P2 != E2(0) and n2 * P2 == E2(0):
        break

P2_ext = E2_ext(P2)
cof2_ext = E2_ext.cardinality() // n2
while True:
    Q2 = cof2_ext * E2_ext.random_point()
    if Q2 != E2_ext(0) and n2 * Q2 == E2_ext(0):
        if Q2.weil_pairing(P2_ext, n2) != 1:
            break

w2 = P2_ext.weil_pairing(Q2, n2)
print(f"P = {P2}")
print(f"Q = {Q2}")
print(f"e(P, Q) = {w2}")
print(f"Order of e(P, Q) = {w2.multiplicative_order()}")

# Verify bilinearity on the larger curve

print(f"Exhaustive bilinearity test for n = {n2}:")
start = walltime()
failures = 0
for a in range(n2):
    for b in range(n2):
        lhs = (a * P2_ext).weil_pairing(b * Q2, n2)
        rhs = w2^(a * b)
        if lhs != rhs:
            failures += 1

elapsed = (walltime() - start) * 1000
print(f"  Tested {n2^2} pairs in {elapsed:.0f} ms")
print(f"  Failures: {failures}")
print(f"  All passed? {failures == 0}")

8. Pairings as Isomorphisms

An important fact: for fixed $Q$, the map $P \mapsto e(P, Q)$ is a group homomorphism from $G_1$ to $G_T$. If $Q$ is a generator of $G_2$ and the pairing is non-degenerate, this map is an isomorphism.

This means the pairing gives a "dictionary" between the additive group $G_1$ (curve points) and the multiplicative group $G_T$ (field elements).

# Show the pairing as an isomorphism G1 → GT
print(f"The map P ↦ e(P, Q) sends G1 to GT:")
print("G1 (additive) → GT (multiplicative)")
for i in range(n):
    point = i * P_ext
    pairing_val = point.weil_pairing(Q, n)
    # Find the discrete log in GT
    for j in range(n):
        if w^j == pairing_val:
            pt_str = f"{i}·P" if i > 0 else "O"
            print(f"{pt_str} → w^{j} = {str(pairing_val)}")
            break

print(f"\nThis is a group isomorphism: addition in G1 ↔ multiplication in GT")

Crypto foreshadowing. This isomorphism is exactly what makes BLS signatures work (Notebook 07d). Signing is done in $G_1$ (efficient point arithmetic), but verification uses the pairing to "translate" the check into $G_T$ (where we can compare products). The Tate pairing variant is preferred in practice because it requires only one Miller loop.

9. Exercises

Exercise 1 (Worked): Principal Divisors

Problem. For $E: y^2 = x^3 + x$ over $\mathbb{F}_{59}$, let $P = (1, 24)$ and $Q = (4, 14)$. Compute $R = P + Q$. Write the divisor of the line through $P$ and $Q$, and verify it is principal.

Solution:

# Exercise 1: Worked solution
E_ex = EllipticCurve(GF(59), [1, 0])
P_ex = E_ex(1, 24)
Q_ex = E_ex(4, 14)
R_ex = P_ex + Q_ex
neg_R_ex = -R_ex

print(f"P = {P_ex}")
print(f"Q = {Q_ex}")
print(f"R = P + Q = {R_ex}")
print(f"-R = {neg_R_ex}")

# The line through P and Q has divisor: (P) + (Q) + (-R) - 3(O)
D_ex = [(1, P_ex), (1, Q_ex), (1, neg_R_ex), (-3, E_ex(0))]
deg = div_degree(D_ex)
s = div_sum(D_ex)

print(f"\nDiv(ℓ_PQ) = (P) + (Q) + (-R) - 3(O)")
print(f"  deg = {deg} {'✓' if deg == 0 else '✗'}")
print(f"  sum = {s} {'✓ (= O)' if s == E_ex(0) else '✗'}")
print(f"  Principal? {deg == 0 and s == E_ex(0)}")

Exercise 2 (Guided): Weil vs Tate

Problem. Using the curve $E: y^2 = x^3 + x$ over $\mathbb{F}_{59}$ with $n = 5$:

1. Compute the Weil pairing $e_W(P, Q)$ and the Tate pairing $e_T(P, Q)$.

2. Verify that both are $n$-th roots of unity.

3. Check bilinearity for both with $a = 3, b = 4$.

Fill in the TODOs:

# Exercise 2: fill in the TODOs
# (Use P_ext, Q, n, k from earlier in this notebook)

# TODO 1: Compute both pairings
# e_weil = P_ext.weil_pairing(Q, n)
# e_tate = P_ext.tate_pairing(Q, n, k)

# TODO 2: Verify both are n-th roots of unity
# print(f"e_W^n = {e_weil^n} (should be 1)")
# print(f"e_T^n = {e_tate^n} (should be 1)")

# TODO 3: Check bilinearity with a=3, b=4
# lhs_w = (3 * P_ext).weil_pairing(4 * Q, n)
# rhs_w = e_weil^(3*4)
# print(f"Weil: e(3P, 4Q) == e(P,Q)^12? {lhs_w == rhs_w}")
# ... same for Tate

Exercise 3 (Independent): Anti-Symmetry Exploration

Problem.

1. Compute $e_W(P, Q)$ and $e_W(Q, P)$ and verify that their product is 1 (anti-symmetry).

2. Show that if you swap the arguments of the Tate pairing, $e_T(P, Q) \neq e_T(Q, P)^{-1}$ in general. Why?

3. Using the Weil pairing on the larger curve ($p = 467, n = 13$), verify anti-symmetry for all $n^2$ pairs of multiples of $P$ and $Q$.

# Exercise 3: write your solution here

Summary

Concept	Key Fact
Divisor	Formal sum $D = \sum n_P (P)$; has degree $\sum n_P$ and sum $\sum n_P \cdot P$
Principal divisor	$\deg(D) = 0$ and $\text{sum}(D) = \mathcal{O}$; = divisor of a rational function
Weil pairing	Built from rational functions $f_P, f_Q$ evaluated at auxiliary divisors
Miller's algorithm	Computes $f_P$ iteratively in $O(\log n)$, like double-and-add
Tate pairing	One Miller loop + final exponentiation; faster in practice
Alternating (Weil)	$e_W(P, P) = 1$, $e_W(P, Q) = e_W(Q, P)^{-1}$
Isomorphism	For fixed $Q$: $P \mapsto e(P, Q)$ is a group isomorphism $G_1 \to G_T$

We now understand where pairings come from. The next question: which curves have efficient pairings?

---

Next: 07c: Pairing-Friendly Curves