07c-pairing-friendly-curves.ipynb

Kernel: SageMath 10.5

Notebook 07c: Pairing-Friendly Curves

Module 07. Bilinear Pairings

---

Motivating Question. Not every elliptic curve supports efficient pairings. For a random curve over a 256-bit prime, the embedding degree $k$ is astronomically large, making the pairing target field $\mathbb{F}_{p^k}$ computationally infeasible. How do we find curves where $k$ is small enough to compute with, yet large enough for security? This is the art of pairing-friendly curve construction.

---

Prerequisites. You should be comfortable with:

• The Weil pairing and its properties (Notebook 07b)

• Embedding degree $k$: smallest integer with $n \mid p^k - 1$ (07a, 07b)

• Extension fields $\mathbb{F}_{p^k}$ (Module 02/03)

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

1. Compute the embedding degree for a given curve and subgroup.

2. Understand why most curves are not pairing-friendly.

3. Know the key families of pairing-friendly curves (supersingular, MNT, BN, BLS).

4. Appreciate the security implications of the embedding degree.

1. The Embedding Degree

Bridge from Notebook 07b. In the previous notebooks, we saw that the pairing maps into $\mathbb{F}_{p^k}^*$ where $k$ is the embedding degree, the smallest positive integer such that the subgroup order $n$ divides $p^k - 1$.

The embedding degree determines:

• Efficiency: Arithmetic in $\mathbb{F}_{p^k}$ costs roughly $O(k^2)$ times as much as in $\mathbb{F}_p$. Smaller $k$ = faster pairing.

• Security: The DLP in $G_T \subset \mathbb{F}_{p^k}^*$ can be attacked by index-calculus methods. Larger $p^k$ = harder DLP in $G_T$.

We need $k$ in a "Goldilocks zone": small enough for efficiency, large enough for security.

def embedding_degree(p, n, max_k=1000):
    """
    Find the embedding degree k: smallest k >= 1 such that n | p^k - 1.
    Returns k, or -1 if not found within max_k.
    """
    Zn = Integers(n)
    pk = Zn(p)
    for k in range(1, max_k + 1):
        if pk == 1:
            return k
        pk = pk * Zn(p)
    return -1

# Our supersingular curve from 07a/07b
p = 59
E = EllipticCurve(GF(p), [1, 0])
card = E.cardinality()
print(f"Curve: y² = x³ + x over F_{p}")
print(f"|E| = {card}")
print(f"Factorization: {factor(card)}")

# Compute embedding degree for each prime factor
for n_factor, exp in factor(card):
    k = embedding_degree(p, n_factor)
    print(f"  n = {n_factor}: embedding degree k = {k}")
    print(f"    p^k - 1 = {p^k - 1}, divisible by {n_factor}? {(p^k - 1) % n_factor == 0}")

Checkpoint 1. For our supersingular curve $y^2 = x^3 + x$ over $\mathbb{F}_{59}$, the embedding degree is $k = 2$ for all prime-order subgroups. This is typical of supersingular curves, they always have small embedding degree ($k \leq 6$). This makes them natural candidates for pairing-based crypto.

2. Why Most Curves Are NOT Pairing-Friendly

For a "random" elliptic curve, the embedding degree is essentially $k \approx n$, which is $\approx 2^{256}$ for a 256-bit curve. Computing in $\mathbb{F}_{p^{2^{256}}}$ is utterly impossible.

Let's verify this empirically:

# Pick random curves and check their embedding degrees

print("Embedding degrees for random curves over F_p (p ≈ 2^16):")
print("Curve (a,b) |E| n (largest prime) k")
p_test = next_prime(2^16)
for _ in range(8):
    a_t = randint(0, p_test - 1)
    b_t = randint(0, p_test - 1)
    if (4 * a_t^3 + 27 * b_t^2) % p_test == 0:
        continue  # singular
    E_t = EllipticCurve(GF(p_test), [a_t, b_t])
    card_t = E_t.cardinality()
    # Largest prime factor
    n_t = max(f for f, e in factor(card_t))
    k_t = embedding_degree(p_test, n_t, max_k=500)
    k_str = str(k_t) if k_t > 0 else "> 500"
    print(f"({a_t}, {b_t}) {card_t} {n_t} {k_str}")

print(f"\nFor random curves, k is typically very large (≈ n).")
print(f"Pairing-friendly curves with small k are RARE and must be specially constructed.")

3. Families of Pairing-Friendly Curves

Since random curves don't work, cryptographers have identified specific families of curves with small, controlled embedding degrees:

Family	Embedding degree $k$	Typical use	Key feature
Supersingular	$k \leq 6$	Teaching, simple constructions	$
MNT	$k = 3, 4, 6$	Early pairing crypto	Found by CM method
Barreto-Naehrig (BN)	$k = 12$	SNARKs (Groth16), Ethereum	Parameterized by a single integer $u$
BLS (Barreto-Lynn-Scott)	$k = 12, 24, 48$	Ethereum 2.0 (BLS12-381)	Better security margin than BN

4. Supersingular Curves

We've been using supersingular curves ($|E| = p + 1$) throughout this module. They are the simplest pairing-friendly curves.

Key properties:

• Trace of Frobenius $t = 0$ (i.e., $|E(\mathbb{F}_p)| = p + 1$).

• Embedding degree $k \leq 6$ (for $j$-invariant $\neq 0, 1728$: $k = 2$).

• Easy to construct: $y^2 = x^3 + x$ over $\mathbb{F}_p$ with $p \equiv 3 \pmod 4$ is always supersingular.

Downside: The small embedding degree means $G_T$ lives in a relatively small extension field, which limits security. For 128-bit security, you need $p \approx 2^{512}$ (since $p^2 \approx 2^{1024}$ for the DLP in $\mathbb{F}_{p^2}$).

# Verify supersingularity for various primes p ≡ 3 mod 4
print("Supersingular curves y² = x³ + x over F_p (p ≡ 3 mod 4):")
print("p |E| p+1 SS? k")
for p_ss in [59, 467, 1019, 4099, 65539]:
    if not is_prime(p_ss):
        continue
    E_ss = EllipticCurve(GF(p_ss), [1, 0])
    card_ss = E_ss.cardinality()
    is_ss = (card_ss == p_ss + 1)
    # Find largest prime factor for embedding degree
    n_ss = max(f for f, e in factor(card_ss))
    k_ss = embedding_degree(p_ss, n_ss)
    print(f"{p_ss} {card_ss} {p_ss + 1} {'yes' if is_ss else 'no'} {k_ss}")

print(f"\nAll supersingular with k = 2. The pairing target is F_{{p^2}}.")

5. BN Curves (Barreto-Naehrig)

BN curves are a family of pairing-friendly curves with embedding degree $k = 12$. They are parameterized by a single integer $u$:

$$p(u) = 36u^4 + 36u^3 + 24u^2 + 6u + 1$$$$n(u) = 36u^4 + 36u^3 + 18u^2 + 6u + 1$$

The curve is $E: y^2 = x^3 + b$ over $\mathbb{F}_p$ for a suitable $b$.

Properties:

• $k = 12$ always.

• $p$ and $n$ are both prime (for suitable $u$).

• $n = p + 1 - t$ where $t = 6u^2 + 1$ (trace of Frobenius).

• Used in SNARKs (Groth16) and was the curve of choice for Ethereum's pairing precompile (alt_bn128).

# Construct a small BN curve
def bn_params(u):
    """Compute BN curve parameters from u."""
    p_val = 36*u^4 + 36*u^3 + 24*u^2 + 6*u + 1
    n_val = 36*u^4 + 36*u^3 + 18*u^2 + 6*u + 1
    t_val = 6*u^2 + 1
    return p_val, n_val, t_val

# Try small values of u to find a BN curve
print("BN curve parameters for small u:")
print("u p n p prime? n prime? k")
for u in range(1, 20):
    p_bn, n_bn, t_bn = bn_params(u)
    if p_bn < 2 or n_bn < 2:
        continue
    p_prime = is_prime(p_bn)
    n_prime = is_prime(n_bn)
    if p_prime and n_prime:
        k_bn = embedding_degree(p_bn, n_bn)
        print(f"{u} {p_bn} {n_bn} {str(p_prime)} {str(n_prime)} {k_bn}")

# Build and test a concrete BN curve
u_bn = 1
p_bn, n_bn, t_bn = bn_params(u_bn)
print(f"BN curve with u = {u_bn}:")
print(f"  p = {p_bn}")
print(f"  n = {n_bn} (group order = prime)")
print(f"  t = {t_bn} (trace of Frobenius)")
print(f"  p + 1 - t = {p_bn + 1 - t_bn} (should equal n = {n_bn})")

# The BN curve equation is y^2 = x^3 + b. Find a suitable b.
F_bn = GF(p_bn)
for b_val in range(1, p_bn):
    E_bn = EllipticCurve(F_bn, [0, b_val])
    if E_bn.cardinality() == n_bn:
        print(f"  Curve: y² = x³ + {b_val} over F_{p_bn}")
        print(f"  |E| = {E_bn.cardinality()} (matches n!)")
        break

# Verify embedding degree
k_check = embedding_degree(p_bn, n_bn)
print(f"  Embedding degree: k = {k_check} (should be 12 for BN)")

Misconception alert. "BN curves always have $|E| = n$ (prime order)." Yes, this is by design. The BN family is constructed so that $n$ is prime, meaning there's no cofactor ($h = 1$). This simplifies the protocol (no cofactor clearing needed) and ensures every non-identity point is a generator.

6. BLS Curves (Barreto-Lynn-Scott)

After advances in the Number Field Sieve (NFS) for extension fields, BN curves at 128-bit security required larger parameters. The BLS family provides a better security margin.

The most famous: BLS12-381, used in Ethereum 2.0, Zcash, and many other systems.

Parameter	BLS12-381
Embedding degree	$k = 12$
Field size ($p$)	381 bits
Subgroup order ($n$)	255 bits
Security level	$\approx 128$ bits
$G_T$ field size	$381 \times 12 = 4572$ bits

# BLS12-381 parameters (the actual curve used in Ethereum 2.0)
# These are large numbers, so we just display them.

u_bls = -0xd201000000010000  # the BLS12-381 parameter

# BLS12 parameterization:
# p = (u - 1)^2 * (u^4 - u^2 + 1) / 3 + u
# n = u^4 - u^2 + 1

p_bls = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
n_bls = 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001

print("BLS12-381 (Ethereum 2.0 / Zcash curve):")
print(f"  p has {Integer(p_bls).nbits()} bits")
print(f"  n has {Integer(n_bls).nbits()} bits")
print(f"  p is prime? {is_prime(p_bls)}")
print(f"  n is prime? {is_prime(n_bls)}")
print(f"  Embedding degree: k = 12")
print(f"  GT field: F_{{p^12}} has {Integer(p_bls).nbits() * 12} bits")
print(f"  Security level: ~128 bits")

# Verify embedding degree
Zn_bls = Integers(n_bls)
pk = Zn_bls(p_bls)
for test_k in [1, 2, 3, 4, 6, 12]:
    if Zn_bls(p_bls)^test_k == 1:
        print(f"\n  Smallest k with n | p^k - 1: k = {test_k}")
        break

7. Security: Balancing the Two DLPs

A pairing-based system has two discrete log problems:

1. ECDLP in $G_1$ (or $G_2$): best attack is Pollard's rho, $O(\sqrt{n})$ operations.

2. DLP in $G_T \subset \mathbb{F}_{p^k}^*$: best attack is the Number Field Sieve, roughly $L_{p^k}[1/3, c]$.

The security level is the minimum of these two. We want them to be roughly balanced:

| Security level | $\sqrt{n}$ needs | $|\mathbb{F}_{p^k}|$ needs | |----------------|-----------------|---------------------------| | 128-bit | $n \approx 2^{256}$ | $p^k \approx 2^{3072}$ or more | | 192-bit | $n \approx 2^{384}$ | $p^k \approx 2^{7680}$ | | 256-bit | $n \approx 2^{512}$ | $p^k \approx 2^{15360}$ |

# Security analysis for different curve families
print("Security analysis: matching ECDLP and DLP levels")
print(f"Curve family k |p| bits |n| bits "
      f"{'|p^k| bits'} {'ECDLP sec'} {'GT sec (approx)'}")

# Supersingular with k=2
print(f"Supersingular 2 512 512 "
      f"{'1024'} {'256'} {'~80 (weak!)'}")

# BN128 (the old Ethereum curve)
print(f"BN254 (alt_bn128) 12 254 254 "
      f"{'3048'} {'127'} {'~100 (post-NFS)'}")

# BLS12-381
print(f"BLS12-381 12 381 255 "
      f"{'4572'} {'128'} {'~128'}")

# BLS12-461 (higher security)
print(f"BLS12-461 12 461 308 "
      f"{'5532'} {'154'} {'~140'}")

print(f"\nNote: BN254's GT security dropped due to advances in NFS for extension fields.")
print(f"BLS12-381 was designed with a safety margin against such advances.")

Checkpoint 2. The takeaway: embedding degree $k$ determines the tradeoff.

• Too small ($k = 1, 2$): DLP in $G_T$ is easy → insecure (this is the MOV attack).

• Too large ($k \approx n$): Can't compute in $\mathbb{F}_{p^k}$ → pairing is useless.

• Just right ($k = 12$ for BN/BLS at 128-bit security): Efficient and secure.

The MOV (Menezes-Okamoto-Vanstone) attack uses the pairing itself to reduce the ECDLP to a DLP in $\mathbb{F}_{p^k}^*$. This is why non-pairing curves must avoid having small embedding degree.

8. The MOV Attack: When Pairings Work Against You

If a curve has a small embedding degree but you're trying to use it for non-pairing crypto (like ECDH), the pairing becomes an attack:

1. Attacker wants to solve ECDLP: given $P, Q = kP$, find $k$.

2. Compute $e(P, R)$ and $e(Q, R) = e(kP, R) = e(P, R)^k$ for some auxiliary point $R$.

3. Now solve the DLP $g^k = h$ in $\mathbb{F}_{p^k}^*$, where $g = e(P, R)$ and $h = e(Q, R)$.

4. If $k$ is small enough, index calculus solves this quickly.

This is why secp256k1 and P-256 have enormous embedding degrees, they must be immune to MOV.

# Demonstrate the MOV attack on our small supersingular curve
# E: y² = x³ + x over F_59, k = 2

p = 59
E = EllipticCurve(GF(p), [1, 0])
n = 5
k = 2

# Set up the extension and find points
F2 = GF(p^k, 'a')
E2 = E.change_ring(F2)

cof = E.cardinality() // n
while True:
    P = cof * E.random_point()
    if P != E(0) and n * P == E(0):
        break

P2 = E2(P)

# ECDLP instance: Q = secret * P
secret = 3
Q = secret * P
Q2 = E2(Q)

print(f"ECDLP: Given P = {P}, Q = {Q}, find k with Q = kP.")
print(f"(Secret: k = {secret})")

# Find an independent point R for MOV
cof_ext = E2.cardinality() // n
while True:
    R = cof_ext * E2.random_point()
    if R != E2(0) and n * R == E2(0):
        if R.weil_pairing(P2, n) != 1:
            break

# MOV reduction
g = P2.weil_pairing(R, n)  # e(P, R)
h = Q2.weil_pairing(R, n)  # e(Q, R) = e(kP, R) = e(P, R)^k

print(f"\nMOV attack:")
print(f"  g = e(P, R) = {g}")
print(f"  h = e(Q, R) = {h}")
print(f"  Now solve g^k = h in F_{{p^{k}}}^* ...")

# Solve DLP in GT (trivial for small groups)
for k_guess in range(n):
    if g^k_guess == h:
        print(f"  Found: k = {k_guess}")
        print(f"  Correct? {k_guess == secret}")
        break

print(f"\n⚠ The ECDLP was reduced to a DLP in F_{{p^2}}^*, which can be easier!")

Crypto foreshadowing. Pairing-friendly curves are the foundation of:

• BLS signatures (next notebook): sign = hash to curve + scalar mul; verify = one pairing check.

• Groth16 SNARKs (Module 10): trusted setup on a pairing curve; verification = 3 pairings.

• KZG commitments (Module 10): polynomial commitment scheme using a single pairing check.

The choice of curve (BN254 vs BLS12-381) affects both performance and security of these systems.

9. Exercises

Exercise 1 (Worked): Computing Embedding Degree

Problem. For the curve $E: y^2 = x^3 + x$ over $\mathbb{F}_{1019}$, find $|E|$, its largest prime factor $n$, and the embedding degree $k$.

Solution:

# Exercise 1: Worked solution
p_ex = 1019
E_ex = EllipticCurve(GF(p_ex), [1, 0])
card_ex = E_ex.cardinality()
print(f"E: y² = x³ + x over F_{p_ex}")
print(f"|E| = {card_ex}")
print(f"p + 1 = {p_ex + 1} (supersingular? {card_ex == p_ex + 1})")
print(f"Factorization: {factor(card_ex)}")

n_ex = max(f for f, e in factor(card_ex))
print(f"\nLargest prime factor: n = {n_ex}")

k_ex = embedding_degree(p_ex, n_ex)
print(f"Embedding degree: k = {k_ex}")
print(f"Verify: n | p^k - 1 = {p_ex^k_ex - 1}? {(p_ex^k_ex - 1) % n_ex == 0}")

Exercise 2 (Guided): BN Curve Construction

Problem. Find the smallest $u > 0$ such that BN parameters $p(u)$ and $n(u)$ are both prime. Construct the curve $y^2 = x^3 + b$ and verify that $|E| = n$ and the embedding degree is 12.

Fill in the TODOs:

# Exercise 2: fill in the TODOs

# TODO 1: Find smallest u with p(u) and n(u) both prime
# for u_test in range(1, 100):
#     p_test, n_test, t_test = bn_params(u_test)
#     if is_prime(p_test) and is_prime(n_test):
#         print(f"Found u = {u_test}, p = {p_test}, n = {n_test}")
#         break

# TODO 2: Find b such that |E(F_p)| = n for y^2 = x^3 + b
# for b_test in range(1, p_test):
#     E_test = EllipticCurve(GF(p_test), [0, b_test])
#     if E_test.cardinality() == n_test:
#         print(f"Curve: y^2 = x^3 + {b_test}")
#         break

# TODO 3: Verify embedding degree is 12
# k_test = embedding_degree(p_test, n_test)
# print(f"Embedding degree: {k_test}")

Exercise 3 (Independent): MOV on a Larger Curve

Problem.

1. Use the supersingular curve $y^2 = x^3 + x$ over $\mathbb{F}_{467}$ (embedding degree $k = 2$).

2. Choose a prime-order subgroup. Create an ECDLP instance $Q = sP$ with a random secret $s$.

3. Implement the MOV attack: use the Weil pairing to reduce to a DLP in $\mathbb{F}_{467^2}^*$.

4. Solve the DLP in $G_T$ using SageMath's discrete_log function.

5. Verify you recovered the correct secret.

# Exercise 3: write your solution here

Summary

Concept	Key Fact
Embedding degree	Smallest $k$ with $n \mid p^k - 1$; determines $G_T = \mu_n \subset \mathbb{F}_{p^k}^*$
Random curves	Have $k \approx n$ (huge) → pairing is infeasible
Supersingular	Always have $k \leq 6$; simplest pairing-friendly curves
BN curves	$k = 12$, parameterized by $u$; used in SNARKs
BLS curves	$k = 12$; BLS12-381 is the standard for 128-bit security
MOV attack	Pairing reduces ECDLP to DLP in $\mathbb{F}_{p^k}^*$, small $k$ is dangerous for non-pairing curves
Security balance	Must balance ECDLP security ($\sqrt{n}$) with $G_T$ DLP security ($L_{p^k}$)

Now that we know which curves to use, we're ready to build real protocols. Next: BLS signatures, arguably the most elegant signature scheme.

---

Next: 07d: BLS Signatures