07a-bilinear-maps-definition.ipynb

Kernel: SageMath 10.5

Notebook 07a: Bilinear Maps, Definition

Module 07. Bilinear Pairings

---

Motivating Question. With elliptic curve groups (Module 06), we can build key exchange (ECDH) and signatures (ECDSA). But some powerful protocols, BLS aggregate signatures, identity-based encryption, SNARKs, require something more: a way to "multiply" two group elements and get a meaningful result in a third group. This is exactly what a bilinear map (pairing) provides. What is this mysterious map, and why does bilinearity unlock so much?

---

Prerequisites. You should be comfortable with:

• Elliptic curve groups, scalar multiplication, and the ECDLP (Module 06)

• Group theory basics: identity, order, generators (Module 01)

• Finite fields $\mathbb{F}_p$ and extension fields $\mathbb{F}_{p^k}$ (Module 02/03)

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

1. State the formal definition of a bilinear map $e: G_1 \times G_2 \to G_T$.

2. Verify the bilinearity and non-degeneracy properties computationally.

3. Understand the three groups ($G_1, G_2, G_T$) and how they relate to elliptic curves.

4. See why bilinearity enables "checking multiplications in the exponent."

1. The Idea: A Map That "Multiplies" Discrete Logs

Bridge from Module 06. In Module 06, we worked with a single elliptic curve group $E(\mathbb{F}_p)$. Given points $P$ and $Q = aP$, there's no way to "multiply" two points to get $abP$ from $aP$ and $bP$ alone, that would break Diffie-Hellman! A bilinear pairing doesn't break DH, but it does something subtler: it maps pairs of points to elements of a different group where the discrete logs multiply.

Informal picture:

$$e(aP, bQ) = e(P, Q)^{ab}$$

The pairing $e$ takes two curve points and outputs an element of a multiplicative group (typically $\mathbb{F}_{p^k}^*$). The key magic: the "exponents" $a$ and $b$ end up multiplied in the output.

2. Formal Definition

Let $G_1, G_2$ be additive groups of prime order $n$ and $G_T$ a multiplicative group of the same order $n$. A bilinear map (pairing) is a function:

$$e: G_1 \times G_2 \to G_T$$

satisfying:

1. Bilinearity: For all $P, P' \in G_1$ and $Q, Q' \in G_2$:

   • $e(P + P', Q) = e(P, Q) \cdot e(P', Q)$ (linear in the first argument)

   • $e(P, Q + Q') = e(P, Q) \cdot e(P, Q')$ (linear in the second argument)

2. Non-degeneracy: If $P \neq \mathcal{O}$ and $Q \neq \mathcal{O}$, then $e(P, Q) \neq 1_{G_T}$.

3. Computability: There is an efficient algorithm to compute $e(P, Q)$.

From bilinearity, it follows immediately that: $$e(aP, bQ) = e(P, Q)^{ab}$$

This is the property that makes pairings cryptographically useful.

3. A Toy Example: Pairings in $\mathbb{Z}/n\mathbb{Z}$

Before using elliptic curves, let's build intuition with a simpler (and cryptographically useless, but illustrative) bilinear map.

Let $G_1 = G_2 = (\mathbb{Z}/n\mathbb{Z}, +)$ and $G_T = (\mathbb{Z}/n\mathbb{Z}, +)$. Define:

$$e(a, b) = a \cdot b \bmod n$$

This is bilinear: $e(a + a', b) = (a + a')b = ab + a'b = e(a, b) + e(a', b)$.

It's non-degenerate (for prime $n$): if $a \neq 0$ and $b \neq 0$, then $ab \neq 0 \bmod n$.

But it's useless for crypto because "computing discrete logs" in $(\mathbb{Z}/n\mathbb{Z}, +)$ is trivial (just division). The real power comes when $G_1, G_2$ are elliptic curve groups where DLP is hard.

# Toy bilinear map: e(a, b) = a*b mod n
n = 23  # prime
Zn = Integers(n)

def e_toy(a, b):
    """Toy bilinear map in Z/nZ."""
    return Zn(a) * Zn(b)

# Check bilinearity: e(a + a', b) == e(a, b) + e(a', b)
a, a_prime, b = Zn(7), Zn(13), Zn(5)
lhs = e_toy(a + a_prime, b)
rhs = e_toy(a, b) + e_toy(a_prime, b)
print(f"Bilinearity (left arg):  e({a}+{a_prime}, {b}) = {lhs}")
print(f"                         e({a},{b}) + e({a_prime},{b}) = {rhs}")
print(f"                         Equal? {lhs == rhs}")

# Check bilinearity: e(a, b + b') == e(a, b) + e(a, b')
b_prime = Zn(17)
lhs2 = e_toy(a, b + b_prime)
rhs2 = e_toy(a, b) + e_toy(a, b_prime)
print(f"\nBilinearity (right arg): e({a}, {b}+{b_prime}) = {lhs2}")
print(f"                         e({a},{b}) + e({a},{b_prime}) = {rhs2}")
print(f"                         Equal? {lhs2 == rhs2}")

# The key consequence: e(c*a, d*b) = c*d * e(a, b)
c, d_ = Zn(3), Zn(11)
print(f"\nKey property: e({c}·{a}, {d_}·{b}) = {e_toy(c*a, d_*b)}")
print(f"              {c}·{d_}·e({a},{b}) = {c * d_ * e_toy(a, b)}")
print(f"              Equal? {e_toy(c*a, d_*b) == c * d_ * e_toy(a, b)}")

Checkpoint 1. The bilinearity property means the pairing is "linear in each argument separately." This is the same concept as a bilinear form in linear algebra. The cryptographic consequence: if you know $e(P, Q)$, then $e(aP, bQ) = e(P, Q)^{ab}$, the scalars "pass through" to become exponents in $G_T$.

4. Pairings on Elliptic Curves: The Weil Pairing

The real cryptographic pairing is defined on elliptic curve groups. SageMath provides the Weil pairing built in.

Setup:

• An elliptic curve $E$ over $\mathbb{F}_p$

• An integer $n$ (typically the order of the subgroup) with $n | |E(\mathbb{F}_p)|$

• The $n$-torsion subgroup $E[n] = \{P \in E(\overline{\mathbb{F}_p}) : nP = \mathcal{O}\}$

• Two linearly independent points $P, Q \in E[n]$ (often $Q$ lives in an extension field $\mathbb{F}_{p^k}$)

The Weil pairing maps: $$e_n: E[n] \times E[n] \to \mu_n \subset \mathbb{F}_{p^k}^*$$

where $\mu_n$ is the group of $n$-th roots of unity and $k$ is the embedding degree (the smallest $k$ such that $n | p^k - 1$).

# Set up a pairing-friendly curve
# We use a small supersingular curve for a clean teaching example.
# E: y^2 = x^3 + x over F_p with p = 59 (supersingular: #E = p+1 = 60)

p = 59
E = EllipticCurve(GF(p), [1, 0])
card = E.cardinality()
print(f"Curve: y² = x³ + x over F_{p}")
print(f"|E(F_p)| = {card}")
print(f"p + 1 = {p + 1} (supersingular: trace t = 0)")

# Factor the group order to find a nice subgroup order n
print(f"\nFactorization of |E|: {factor(card)}")

# Pick n (a prime factor of |E|)
# For a supersingular curve y^2 = x^3 + x, embedding degree k = 2
n = 5  # 5 divides 60
k = 2  # embedding degree: 5 | p^2 - 1 = 3480
print(f"\nChosen subgroup order: n = {n}")
print(f"Embedding degree: k = {k}")
print(f"n divides p^k - 1 = {p^k - 1}? {(p^k - 1) % n == 0}")
print(f"n divides p - 1 = {p - 1}? {(p - 1) % n == 0}  (if yes, k=1; if no, need extension)")

# Find a point of order n in E(F_p)
cofactor = card // n
while True:
    P_candidate = E.random_point()
    P = cofactor * P_candidate
    if P != E(0) and n * P == E(0):
        break

print(f"P = {P}")
print(f"Order of P: {P.order()}")
assert P.order() == n

# For the Weil pairing, we need a SECOND linearly independent point of order n.
# On a supersingular curve, we can find Q in the extension field F_{p^k} = F_{p^2}.
F_pk = GF(p^k, 'a')
E_ext = E.change_ring(F_pk)

# Lift P to the extended curve
P_ext = E_ext(P)

# Find Q in E(F_{p^2}) \ E(F_p) of order n
card_ext = E_ext.cardinality()
cofactor_ext = card_ext // n
print(f"\n|E(F_{{p^2}})| = {card_ext}")

while True:
    Q_candidate = E_ext.random_point()
    Q = cofactor_ext * Q_candidate
    if Q != E_ext(0) and n * Q == E_ext(0):
        # Check Q is not in the F_p subgroup (linearly independent from P)
        if Q.weil_pairing(P_ext, n) != 1:
            break

print(f"Q = {Q}")
print(f"Order of Q: {Q.order()}")
print(f"Q lives in F_{{p^2}} (extension field)")

# Compute the Weil pairing!
w = P_ext.weil_pairing(Q, n)
print(f"Weil pairing: e(P, Q) = {w}")
print(f"e(P, Q) lives in F_{{p^k}}^* = F_{{p^2}}^*")
print(f"Order of e(P, Q): {w.multiplicative_order()}")
print(f"Is it a {n}-th root of unity? {w^n == 1}")
print(f"Is it non-trivial (≠ 1)? {w != 1}")

Misconception alert. "The pairing output is a point on an elliptic curve." No, the output $e(P, Q) \in G_T$ is an element of a multiplicative group, typically a subgroup of $\mathbb{F}_{p^k}^*$. The inputs are curve points; the output is a field element.

5. Verifying Bilinearity

The defining property: $e(aP, bQ) = e(P, Q)^{ab}$.

Let's test this exhaustively for our small groups.

# Test: e(aP, bQ) = e(P, Q)^(ab)
w = P_ext.weil_pairing(Q, n)

print("Testing e(aP, bQ) = e(P, Q)^(ab) for all a, b in {0,...,n-1}:")
all_pass = True
for a in range(n):
    for b in range(n):
        lhs = (a * P_ext).weil_pairing(b * Q, n)
        rhs = w^(a * b)
        if lhs != rhs:
            print(f"  FAIL at a={a}, b={b}: {lhs} ≠ {rhs}")
            all_pass = False

print(f"All {n}×{n} = {n^2} pairs passed? {all_pass}")

# Test bilinearity in each argument separately

# Left-linearity: e(P1 + P2, Q) = e(P1, Q) · e(P2, Q)
a1, a2 = 2, 3
P1 = a1 * P_ext
P2 = a2 * P_ext

lhs = (P1 + P2).weil_pairing(Q, n)
rhs = P1.weil_pairing(Q, n) * P2.weil_pairing(Q, n)
print(f"Left-linearity:")
print(f"  e({a1}P + {a2}P, Q) = {lhs}")
print(f"  e({a1}P, Q)·e({a2}P, Q) = {rhs}")
print(f"  Equal? {lhs == rhs}")

# Right-linearity: e(P, Q1 + Q2) = e(P, Q1) · e(P, Q2)
b1, b2 = 1, 4
Q1 = b1 * Q
Q2 = b2 * Q

lhs2 = P_ext.weil_pairing(Q1 + Q2, n)
rhs2 = P_ext.weil_pairing(Q1, n) * P_ext.weil_pairing(Q2, n)
print(f"\nRight-linearity:")
print(f"  e(P, {b1}Q + {b2}Q) = {lhs2}")
print(f"  e(P, {b1}Q)·e(P, {b2}Q) = {rhs2}")
print(f"  Equal? {lhs2 == rhs2}")

Checkpoint 2. Bilinearity has a powerful consequence: $e(aP, bQ) = e(P, Q)^{ab}$. This means we can "check multiplication in the exponent" without knowing $a$ or $b$ individually. Given $A = aP$, $B = bQ$, and a claimed product $C = cP$, we can check whether $c = ab$ by testing:

$$e(A, B) = e(P, Q)^{ab} \stackrel{?}{=} e(cP, Q) = e(C, Q)$$

This is the core trick behind BLS signatures and SNARKs.

6. Non-Degeneracy

A pairing is non-degenerate if there exist $P \in G_1, Q \in G_2$ with $e(P, Q) \neq 1$.

Equivalently: for every non-identity $P \in G_1$, there exists some $Q \in G_2$ such that $e(P, Q) \neq 1$ (and vice versa).

If the pairing were degenerate ($e(P, Q) = 1$ for all $P, Q$), it would be useless, it couldn't distinguish anything.

# Check non-degeneracy: e(P, Q) ≠ 1 for generators P, Q
print(f"e(P, Q) = {w}")
print(f"e(P, Q) ≠ 1? {w != 1}")

# The pairing of any non-identity point with Q gives a non-identity in GT
print(f"\nPairing values for all multiples of P:")
for a in range(n):
    val = (a * P_ext).weil_pairing(Q, n)
    is_id = "(identity)" if val == 1 else ""
    print(f"  e({a}P, Q) = {val}  {is_id}")

print(f"\nOnly e(0·P, Q) = e(O, Q) = 1. All others are non-trivial.")
print(f"This is non-degeneracy: the pairing 'sees' the discrete log.")

7. The Three Groups

In pairing-based cryptography, we always work with three groups:

Group	Type	Typical realization	Operation
$G_1$	Additive	$E(\mathbb{F}_p)$ or subgroup thereof	Point addition
$G_2$	Additive	$E(\mathbb{F}_{p^k})$ or a twist	Point addition
$G_T$	Multiplicative	$\mu_n \subset \mathbb{F}_{p^k}^*$ ($n$-th roots of unity)	Multiplication

All three have the same prime order $n$. The pairing maps $G_1 \times G_2 \to G_T$.

Important variants:

• Type 1 (symmetric): $G_1 = G_2$. The Weil pairing on supersingular curves.

• Type 3 (asymmetric): $G_1 \neq G_2$, no efficient map from $G_2$ to $G_1$. Used in practice (BN, BLS curves).

For this module, we primarily use Type 1 pairings for simplicity.

# Summary of our three groups
print("The three groups in our pairing setup:")
print(f"\n  G1: subgroup of E(F_{p}) generated by P = {P}")
print(f"      Order: {P.order()}")
print(f"      Operation: point addition")

print(f"\n  G2: subgroup of E(F_{{p^{k}}}) generated by Q = {Q}")
print(f"      Order: {Q.order()}")
print(f"      Operation: point addition")

print(f"\n  GT: {n}-th roots of unity in F_{{p^{k}}}^*")
print(f"      Generator: e(P,Q) = {w}")
print(f"      Order: {w.multiplicative_order()}")
print(f"      Operation: multiplication")

# List all elements of GT
print(f"\n  Elements of GT:")
for i in range(n):
    print(f"    w^{i} = {w^i}")

8. Why Bilinearity Is Useful: The DDH Shortcut

Consider the Decisional Diffie-Hellman (DDH) problem: given $P, aP, bP, cP$, decide whether $c = ab \bmod n$.

In a group without a pairing, DDH is believed to be hard.

In a group with a pairing, DDH is easy! Just check: $$e(aP, bP) \stackrel{?}{=} e(cP, P)$$

If $c = ab$, both sides equal $e(P, P)^{ab}$. If $c \neq ab$, they differ (with overwhelming probability).

This means pairing groups are weaker for some assumptions (DDH) but enable new protocols.

# DDH test using the pairing
# For symmetric pairings (Type 1), we can use the same group for both inputs.

# Pick random a, b
a = randint(1, n - 1)
b = randint(1, n - 1)
c_real = (a * b) % n
c_fake = randint(1, n - 1)

aP = a * P_ext
bQ = b * Q

# DDH challenge: is c = ab?
print(f"a = {a}, b = {b}, ab mod n = {c_real}")
print(f"Fake c = {c_fake}")

# Test with real c
test_real = aP.weil_pairing(bQ, n) == (c_real * P_ext).weil_pairing(Q, n)
print(f"\ne(aP, bQ) == e({c_real}·P, Q)? {test_real}  ← c = ab (real)")

# Test with fake c
test_fake = aP.weil_pairing(bQ, n) == (c_fake * P_ext).weil_pairing(Q, n)
print(f"e(aP, bQ) == e({c_fake}·P, Q)? {test_fake}  ← c ≠ ab (fake)")

print(f"\nThe pairing lets us decide DDH instantly!")

Crypto foreshadowing. This DDH-solving trick is a double-edged sword:

• Bad news: Protocols that rely on DDH being hard (like ElGamal in the curve group) are broken if a pairing exists.

• Good news: The ability to "check multiplications" enables BLS signatures (Notebook 07d), identity-based encryption (07e), and zero-knowledge proofs (Module 10).

The art of pairing-based cryptography is exploiting bilinearity for new functionality while basing security on assumptions that remain hard (like CDH or the Bilinear Diffie-Hellman assumption).

9. Properties Summary

Let's collect all the useful identities that follow from bilinearity:

Property	Formula
Bilinearity (left)	$e(P_1 + P_2, Q) = e(P_1, Q) \cdot e(P_2, Q)$
Bilinearity (right)	$e(P, Q_1 + Q_2) = e(P, Q_1) \cdot e(P, Q_2)$
Scalar extraction	$e(aP, bQ) = e(P, Q)^{ab}$
Identity	$e(\mathcal{O}, Q) = e(P, \mathcal{O}) = 1$
Inverse	$e(-P, Q) = e(P, Q)^{-1} = e(P, -Q)$
Alternating (Weil)	$e(P, P) = 1$ (for the Weil pairing when $G_1 = G_2$)

# Verify all properties

# Identity
print("Identity:")
print(f"  e(O, Q) = {E_ext(0).weil_pairing(Q, n)} (should be 1)")
print(f"  e(P, O) = {P_ext.weil_pairing(E_ext(0), n)} (should be 1)")

# Inverse
print(f"\nInverse:")
e_PQ = P_ext.weil_pairing(Q, n)
e_negP_Q = (-P_ext).weil_pairing(Q, n)
print(f"  e(P, Q) = {e_PQ}")
print(f"  e(-P, Q) = {e_negP_Q}")
print(f"  e(P,Q) · e(-P,Q) = {e_PQ * e_negP_Q} (should be 1)")

# Alternating (Weil pairing: e(P, P) = 1 when same group)
# Note: for linearly dependent points, the Weil pairing gives 1
e_PP = P_ext.weil_pairing(P_ext, n)
print(f"\nAlternating (Weil):")
print(f"  e(P, P) = {e_PP} (should be 1 for Weil pairing)")

10. Exercises

Exercise 1 (Worked): Verifying Scalar Extraction

Problem. Using our curve and pairing, verify that $e(3P, 4Q) = e(P, Q)^{12}$.

Solution:

# Exercise 1: Worked solution
e_PQ = P_ext.weil_pairing(Q, n)

lhs = (3 * P_ext).weil_pairing(4 * Q, n)
rhs = e_PQ^(3 * 4)

print(f"e(P, Q) = {e_PQ}")
print(f"e(3P, 4Q) = {lhs}")
print(f"e(P, Q)^12 = {rhs}")
print(f"Equal? {lhs == rhs}")

# Also verify the intermediate steps:
print(f"\nStep by step:")
print(f"  e(3P, Q) = e(P, Q)^3 = {e_PQ^3}")
print(f"  Check: {(3 * P_ext).weil_pairing(Q, n) == e_PQ^3}")
print(f"  e(P, 4Q) = e(P, Q)^4 = {e_PQ^4}")
print(f"  Check: {P_ext.weil_pairing(4 * Q, n) == e_PQ^4}")

Exercise 2 (Guided): DDH Solver

Problem. Write a function ddh_test(P, Q, aP, bQ, cP, n) that uses the Weil pairing to decide whether $c = ab \bmod n$. Test it with both real and fake tuples.

Fill in the TODOs:

# Exercise 2: fill in the TODOs

def ddh_test(P, Q, aP, bQ, cP, n):
    """
    Decide whether c == a*b mod n using the pairing.
    Returns True if the DDH tuple is real, False if fake.
    """
    # TODO: compute e(aP, bQ) and e(cP, Q)
    # TODO: return whether they are equal
    pass

# Test with real tuple
# a_test, b_test = randint(1, n-1), randint(1, n-1)
# c_test = (a_test * b_test) % n
# result = ddh_test(P_ext, Q, a_test * P_ext, b_test * Q, c_test * P_ext, n)
# print(f"Real DDH tuple: {result} (should be True)")

# Test with fake tuple
# c_fake = randint(1, n-1)
# result_fake = ddh_test(P_ext, Q, a_test * P_ext, b_test * Q, c_fake * P_ext, n)
# print(f"Fake DDH tuple: {result_fake} (should be False, unless c_fake == ab)")

Exercise 3 (Independent): Pairing on a Larger Curve

Problem.

1. Construct the supersingular curve $E: y^2 = x^3 + x$ over $\mathbb{F}_p$ with $p = 467$ (verify $p \equiv 3 \pmod 4$).

2. Verify that $|E(\mathbb{F}_p)| = p + 1 = 468$.

3. Pick a prime $n$ dividing 468. Determine the embedding degree $k$.

4. Find generators $P \in E(\mathbb{F}_p)$ and $Q \in E(\mathbb{F}_{p^k})$ of order $n$.

5. Compute $e(P, Q)$ and verify bilinearity for 5 random pairs $(a, b)$.

# Exercise 3: write your solution here

Summary

Concept	Key Fact
Bilinear map	$e: G_1 \times G_2 \to G_T$ with $e(aP, bQ) = e(P, Q)^{ab}$
Three groups	$G_1, G_2$ (additive, curve points), $G_T$ (multiplicative, field elements)
Non-degeneracy	For generators $P, Q$: $e(P, Q) \neq 1$
Weil pairing	SageMath's built-in pairing on $n$-torsion points
DDH shortcut	Pairings make the DDH problem easy: check $e(aP, bQ) = e(cP, Q)$
Embedding degree	Smallest $k$ with $n \mid p^k - 1$; determines which extension field $G_T$ lives in

We now have the abstract machinery. In the next notebook, we'll develop geometric intuition for why the Weil pairing works, using divisors on curves.

---

Next: 07b: Weil Pairing Intuition