pairing-inversion-attempt.ipynb

Kernel: SageMath 10.0

Break: Pairing Inversion Attempt

Module 07 | Breaking Weak Parameters

Try to recover discrete logs from pairing outputs and see why it's hard.

Why This Matters

Every pairing-based protocol. BLS signatures, identity-based encryption, SNARKs -- relies on the assumption that the pairing cannot be "inverted." Specifically:

• BLS signatures: if you could invert $e(\sigma, g_2) = e(H(m), pk)$ to recover $\sigma$, you could forge signatures.

• Boneh-Franklin IBE: if you could invert the pairing, you could recover private keys.

• SNARKs: pairing-based proof systems would be unsound.

The pairing "transfers" the discrete log problem from the curve to the target group $\mathbb{F}_{p^k}^*$. The security of pairing-based crypto depends on the DLP being hard in both the curve group and the target group. Let's see this transfer in action and understand why inversion is hard.

The Scenario

Given a pairing $e: G_1 \times G_2 \to G_T$ and a value $r = e(P, Q)$ in the target group, the pairing inversion problem asks:

Find $x$ such that $Q = xP$ (equivalently, recover the discrete log from pairing output).

The key observation is that $e(P, xP) = e(P, P)^x$. So if we know $e(P, P) = g_T$ and $e(P, xP) = g_T^x$, recovering $x$ reduces to solving the DLP in $G_T \subseteq \mathbb{F}_{p^k}^*$.

# === Step 1: Set up the pairing on a supersingular curve ===

p = 467  # prime, p ≡ 3 mod 4
E = EllipticCurve(GF(p), [1, 0])  # y^2 = x^3 + x, supersingular
card = E.cardinality()
n = 13  # prime-order subgroup
k = 2   # embedding degree
cofactor = card // n

# Extension field and extended curve
F2.<a> = GF(p^k)
E_ext = E.change_ring(F2)

# Find a generator P in G1 (n-torsion over base field)
while True:
    P = cofactor * E.random_point()
    if P != E(0) and n * P == E(0):
        break

P_ext = E_ext(P)

# Find a generator Q in G2 (n-torsion over extension, independent of P)
cofactor_ext = E_ext.cardinality() // n
while True:
    Q_gen = cofactor_ext * E_ext.random_point()
    if Q_gen != E_ext(0) and n * Q_gen == E_ext(0):
        if P_ext.weil_pairing(Q_gen, n) != 1:
            break

print(f"Curve: y^2 = x^3 + x over GF({p})")
print(f"Subgroup order: n = {n}")
print(f"Embedding degree: k = {k}")
print(f"Target group lives in: GF({p}^{k})* = GF({p^k})*")
print(f"\nP = {P}  (G1 generator)")
print(f"Q = {Q_gen}  (G2 generator)")

# Compute the base pairing value
g_T = P_ext.weil_pairing(Q_gen, n)
print(f"\ne(P, Q) = {g_T}")
print(f"Order of e(P,Q) in GF({p^k})*: {g_T.multiplicative_order()}")

Step 2: The Pairing Transfers the DLP

Suppose someone knows $P$ and $xP$ but not $x$. The pairing reveals:

$$e(P, xP) = e(P, P)^x$$

So the unknown scalar $x$ appears as an exponent in the target group. If we can solve the DLP in $G_T$, we recover $x$.

# === Step 2: Observe the DLP transfer ===

# Secret scalar
x_secret = 7

# Compute xP on the curve
xP = x_secret * P
xP_ext = E_ext(xP)

print(f"Secret: x = {x_secret}")
print(f"P  = {P}")
print(f"xP = {xP}")

# Compute pairings
e_P_Q = P_ext.weil_pairing(Q_gen, n)      # e(P, Q) = g_T
e_xP_Q = xP_ext.weil_pairing(Q_gen, n)    # e(xP, Q) = g_T^x

print(f"\ne(P, Q)  = {e_P_Q}")
print(f"e(xP, Q) = {e_xP_Q}")
print(f"e(P, Q)^x = {e_P_Q^x_secret}")
print(f"\ne(xP, Q) == e(P, Q)^x? {e_xP_Q == e_P_Q^x_secret}")
print(f"\nThe pairing has transferred the DLP from the curve to GF({p^k})*:")
print(f"  Curve DLP: given P and xP, find x")
print(f"  Target DLP: given g_T and g_T^x, find x")
print(f"  Both encode the SAME secret x = {x_secret}")

# === Step 3: Brute-force DLP in the target group (small example) ===

# In our toy example, n = 13, so brute force is trivial
print(f"Target group order: {n}")
print(f"Brute-forcing DLP in GF({p^k})*...")
print()

g_T_base = e_P_Q   # generator of the cyclic subgroup in G_T
g_T_target = e_xP_Q  # the value we want to take the log of

x_recovered = None
for candidate in range(n):
    if g_T_base^candidate == g_T_target:
        x_recovered = candidate
        print(f"  Trying x = {candidate}: g_T^{candidate} = {g_T_base^candidate}  <-- MATCH!")
        break
    else:
        print(f"  Trying x = {candidate}: g_T^{candidate} = {g_T_base^candidate}")

print(f"\nRecovered x = {x_recovered}")
print(f"Actual x    = {x_secret}")
print(f"Correct? {x_recovered == x_secret}")
print(f"\nWith n = {n}, brute force took at most {n} steps. Easy!")

Step 4: Why This Gets Hard

Our toy example had $n = 13$. Brute force was trivial. But for cryptographic parameters:

• BLS12-381 uses $n \approx 2^{255}$ and $k = 12$, so the target group lives in $\mathbb{F}_{p^{12}}^*$ with $p \approx 2^{381}$.

• The DLP in $\mathbb{F}_{p^{12}}^*$ is subject to index calculus attacks, but for properly chosen parameters, the best known attacks are still exponential.

• The embedding degree $k$ is chosen so that the DLP in $\mathbb{F}_{p^k}^*$ is at least as hard as the ECDLP on the curve (128-bit security for BLS12-381).

Let's see the brute force become infeasible as we increase the prime.

# === Step 4: Scaling up, brute force becomes infeasible ===


# Try increasingly large primes with supersingular curves
test_primes = [47, 467, 4999, 49999]


for p_test in test_primes:
    if not is_prime(p_test) or p_test % 4 != 3:
        # Find nearest suitable prime
        while not is_prime(p_test) or p_test % 4 != 3:
            p_test += 1
    
    E_test = EllipticCurve(GF(p_test), [1, 0])
    card_test = E_test.cardinality()
    
    # Find a prime factor of the curve order
    factors_test = [q for q, e in factor(card_test) if q > 10]
    if not factors_test:
        continue
    n_test = factors_test[-1]  # largest prime factor
    cof_test = card_test // n_test
    
    # Set up curve point
    F2_test.<b> = GF(p_test^2)
    E_ext_test = E_test.change_ring(F2_test)
    
    # Find generator
    tries = 0
    found = False
    while tries < 100:
        P_test = cof_test * E_test.random_point()
        if P_test != E_test(0) and n_test * P_test == E_test(0):
            found = True
            break
        tries += 1
    
    if not found:
        continue
    
    P_test_ext = E_ext_test(P_test)
    
    # Find G2 generator
    cof_ext_test = E_ext_test.cardinality() // n_test
    tries = 0
    found = False
    while tries < 100:
        Q_test = cof_ext_test * E_ext_test.random_point()
        if Q_test != E_ext_test(0) and n_test * Q_test == E_ext_test(0):
            if P_test_ext.weil_pairing(Q_test, n_test) != 1:
                found = True
                break
        tries += 1
    
    if not found:
        continue
    
    # DLP instance
    x_test = randint(1, n_test - 1)
    g_T_test = P_test_ext.weil_pairing(Q_test, n_test)
    target_test = g_T_test^x_test
    
    # Brute force with timeout
    t0 = walltime()
    recovered = False
    for c in range(min(n_test, 50000)):
        if g_T_test^c == target_test:
            recovered = True
            break
    elapsed = walltime() - t0
    
    status = "Yes" if recovered else f"No (>{min(n_test,50000)} steps)"

print()
print("As n grows, brute-force DLP in the target group becomes infeasible.")
print("For BLS12-381: n ~ 2^255, target group in GF(p^12)* with p ~ 2^381.")
print("Best known attack: ~2^128 operations (index calculus is sub-exponential")
print("in GF(p^k)*, but k=12 and p are chosen to maintain 128-bit security).")

The Insight: Pairing Inversion is at Least as Hard as DLP in $G_T$

The chain of reasoning:

1. Pairing transfers DLP: $e(P, xP) = e(P, P)^x$ means the curve DLP maps to a target DLP.

2. Pairing inversion requires target DLP: to recover $x$ from $e(P, xP)$, you must solve the DLP $\log_{g_T}(g_T^x)$ in $G_T \subseteq \mathbb{F}_{p^k}^*$.

3. Security parameter choice: the embedding degree $k$ is chosen so that the DLP in $\mathbb{F}_{p^k}^*$ matches the ECDLP difficulty on the curve.

If $k$ is too small (e.g., $k = 1$), the target group DLP might be easier than the curve DLP, weakening security. This is why embedding degree matters: it's the bridge between curve security and target group security.

# === Embedding degree and security balance ===

# For our toy curve: p = 467, k = 2
# Curve DLP: group of order n = 13 (trivial for any method)
# Target DLP: in GF(467^2)* which has order 467^2 - 1 = 218088

print("Security balance for our toy curve:")
print(f"  Curve group order: {n}")
print(f"  Target group order: {p^k - 1} = {factor(p^k - 1)}")
print(f"  The n-torsion subgroup in GF(p^k)*: order {n}")
print()

# For real curves:
print("For BLS12-381 (real parameters):")
print("  Curve: 255-bit subgroup order -> ~128-bit ECDLP security")
print("  Target: GF(p^12)* with p ~ 381 bits -> ~128-bit index calculus security")
print("  Balanced! Both provide 128-bit security.")
print()
print("If embedding degree were k=1:")
print("  Target: GF(p)* with p ~ 381 bits -> only ~50-bit security!")
print("  The pairing would LEAK information by moving the DLP to an easier group.")
print("  This is why supersingular curves over GF(p) with k=2 need larger p.")

Exercises

1. SageMath's discrete_log: Use discrete_log(g_T^x, g_T) in the target group for our toy example. Verify it gives the correct $x$. Then try it with progressively larger primes and observe the time growth.

2. MOV attack connection: The MOV (Menezes-Okamoto-Vanstone) attack uses pairings to reduce the ECDLP to a DLP in $\mathbb{F}_{p^k}^*$. For our supersingular curve with $k = 2$, this is exactly what we did above. Explain why MOV is only useful when $k$ is small relative to the curve security level.

3. Why not $k = 1$? If $n | (p - 1)$ (embedding degree 1), the Weil pairing maps directly into $\mathbb{F}_p^*$. Explain why this makes pairing-based crypto insecure (hint: index calculus in $\mathbb{F}_p^*$ for 256-bit $p$).

# === Exercise 1 starter: use SageMath's discrete_log ===

# In our toy target group, discrete_log should work instantly
x_via_dlog = discrete_log(e_xP_Q, e_P_Q)
print(f"discrete_log in target group: x = {x_via_dlog}")
print(f"Actual x: {x_secret}")
print(f"Match: {x_via_dlog == x_secret}")

# The pairing effectively 'leaked' the discrete log to a group
# where we could compute it. For cryptographic sizes, this
# computation would be infeasible.

Summary

Concept	Detail
DLP transfer	$e(P, xP) = e(P, P)^x$ moves the discrete log from the curve to $G_T$
Pairing inversion	Recovering $x$ from $e(P, xP)$ requires DLP in $\mathbb{F}_{p^k}^*$
Small examples	Brute force works for $n = 13$; infeasible for $n \approx 2^{255}$
Embedding degree	$k$ balances curve security and target group security
MOV attack	Uses this transfer offensively: reduce ECDLP to DLP in $\mathbb{F}_{p^k}^*$

Key takeaway: the pairing is a one-way bridge. It moves algebraic relationships from the curve to the target group (which protocols exploit for verification), but inverting this bridge, recovering curve discrete logs from target group elements, is as hard as the DLP in $\mathbb{F}_{p^k}^*$. Properly chosen parameters make this infeasible.

---

Back to Module 07: Bilinear Pairings