Elliptic Curve Pairings: Mathematical Foundations and BLS Signature Implementation

Introduction

Bilinear pairings on elliptic curves revolutionized modern cryptography by enabling novel protocols impossible with traditional discrete logarithm primitives. From identity-based encryption (Boneh-Franklin, 2001) to compact BLS signatures now securing Ethereum 2.0’s proof-of-stake consensus, pairings provide unique mathematical structure exploited across blockchain, zero-knowledge proofs, and post-quantum transitional cryptography.

This article provides rigorous treatment of pairing mathematics, efficient implementation techniques, and security considerations for pairing-based cryptographic systems.

Mathematical Foundations

Elliptic Curve Preliminaries

An elliptic curve E over finite field 𝔽_q is defined by the Weierstrass equation:

E: y² = x³ + ax + b (mod q)

where 4a³ + 27b² ≠ 0 (non-singular condition).

Group structure: Points on E(𝔽_q) form an abelian group under point addition with identity element 𝒪 (point at infinity).

Order: By Hasse’s theorem, the number of points satisfies:

|E(𝔽_q)| = q + 1 - t
where |t| ≤ 2√q

Torsion Points and Embedding Degree

Definition: For prime r dividing |E(𝔽_q)|, the r-torsion subgroup is:

E[r] = {P ∈ E(𝔽̄_q) : [r]P = 𝒪}

Embedding degree: The smallest integer k such that r | (q^k - 1). This determines the smallest extension field 𝔽_{q^k} containing E[r].

Security implication: The discrete logarithm problem (DLP) on E(𝔽_q) can be reduced to DLP in 𝔽_{q^k} via pairing. Security requires k large enough that 𝔽_{q^k} DLP is intractable.

Bilinear Pairings

A pairing is a bilinear map:

e: G₁ × G₂ → G_T

where G₁, G₂ are cyclic groups of prime order r on E, and G_T ⊆ 𝔽*_{q^k}.

Bilinearity: For all P, P’ ∈ G₁, Q, Q’ ∈ G₂, and a, b ∈ ℤ:

e([a]P, [b]Q) = e(P, Q)^{ab}
e(P + P', Q) = e(P, Q) · e(P', Q)
e(P, Q + Q') = e(P, Q) · e(P, Q')

Non-degeneracy: If e(P, Q) = 1 for all Q ∈ G₂, then P = 𝒪.

Pairing types:

1. Type-1 (symmetric): G₁ = G₂
2. Type-2 (asymmetric): G₁ ≠ G₂, efficient homomorphism φ: G₂ → G₁
3. Type-3 (asymmetric): G₁ ≠ G₂, no efficient homomorphism

Modern protocols prefer Type-3 for optimal performance.

Weil and Tate Pairings

Weil Pairing

Definition: For points P, Q ∈ E[r], let f_P, f_Q be functions with divisors:

div(f_P) = r(P) - r(𝒪)
div(f_Q) = r(Q) - r(𝒪)

The Weil pairing is:

e_r(P, Q) = (-1)^r · f_P(Q + S) / f_P(S) · f_Q(S) / f_Q(P + S)

for random S ∈ E(𝔽_{q^k}).

Properties:

• Bilinearity: e_r([a]P, [b]Q) = e_r(P, Q)^{ab}
• Alternating: e_r(P, P) = 1
• Non-degenerate: e_r(P, Q) is a primitive r-th root of unity

Tate Pairing

Definition: For P ∈ E[r] and Q ∈ E(𝔽_{q^k}):

t_r(P, Q) = f_P(Q)^{(q^k - 1)/r}

where f_P has divisor div(f_P) = r(P) - r(𝒪).

Advantages over Weil:

• ~2× faster (single Miller loop vs. two)
• No point subtraction required
• Preferred for implementations

Reduced Tate pairing (ate pairing): Further optimization using Frobenius endomorphism.

Miller’s Algorithm

The core computational primitive for pairings is Miller’s algorithm, computing rational functions f_P efficiently.

Algorithm Derivation

Given point P of order r, construct f_P via double-and-add:

f_P = ∏_{i=0}^{log₂(r)-1} l_{iP, iP} / v_{2iP}  if bit i of r is 0
                          · l_{T, P} / v_{T+P}    if bit i of r is 1

where:

• l_{A, B}: Line through A and B
• v_C: Vertical line through C

Python Implementation

def miller_algorithm(P, Q, r, E):
    """
    Compute f_r,P(Q) using Miller's algorithm

    Args:
        P: Point in G₁
        Q: Point in G₂
        r: Order (scalar)
        E: Elliptic curve

    Returns:
        f_r,P(Q) ∈ 𝔽_{q^k}
    """
    T = P
    f = E.base_field().one()

    # Binary expansion of r
    r_bits = bin(r)[2:]  # Remove '0b' prefix

    for i in range(1, len(r_bits)):
        # Line through T and T (tangent)
        l = line_function(T, T, Q, E)
        # Vertical through 2T
        v = vertical_function(2*T, Q, E)

        # Update f: f ← f² · (l / v)
        f = f**2 * l / v

        # Double T
        T = 2*T

        if r_bits[i] == '1':
            # Line through T and P
            l = line_function(T, P, Q, E)
            # Vertical through T + P
            v = vertical_function(T + P, Q, E)

            # Update f: f ← f · (l / v)
            f = f * l / v

            # Add P
            T = T + P

    return f

def line_function(P, Q, R, E):
    """
    Evaluate line through P and Q at point R

    Returns:
        l_{P,Q}(R)
    """
    if P == Q:
        # Tangent line: y - y_P = λ(x - x_P)
        # where λ = (3x_P² + a) / (2y_P)
        x_P, y_P = P.xy()
        a = E.a4()

        λ = (3 * x_P**2 + a) / (2 * y_P)
    else:
        # Secant line: λ = (y_Q - y_P) / (x_Q - x_P)
        x_P, y_P = P.xy()
        x_Q, y_Q = Q.xy()

        λ = (y_Q - y_P) / (x_Q - x_P)

    # Evaluate at R: l(R) = y_R - y_P - λ(x_R - x_P)
    x_R, y_R = R.xy()
    return y_R - y_P - λ * (x_R - x_P)

def vertical_function(P, R, E):
    """
    Evaluate vertical line through P at point R

    Returns:
        v_P(R) = x_R - x_P
    """
    x_P, _ = P.xy()
    x_R, _ = R.xy()
    return x_R - x_P

Complexity: O(log r) curve operations and field multiplications.

Optimizations

1. Sparse multiplication: Line evaluation produces sparse elements in 𝔽_{q^k}
2. Denominator elimination: For well-chosen curves, vertical lines can be omitted
3. Twisted curves: Map G₂ to E’(𝔽_{q^{k/d}}) for smaller field operations
4. Precomputation: Cache line parameters for fixed P

BLS12-381: Pairing-Friendly Curve Construction

Design Criteria

Barreto-Lynn-Scott (BLS) curves optimize pairing-friendly parameters:

BLS12-381 parameters:

• Field modulus (381 bits):

  q = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab

• Curve equation: E: y² = x³ + 4 over 𝔽_q

• Embedding degree: k = 12

• Subgroup order (255 bits):

  r = 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001

• Cofactor: h = 0x396c8c005555e1568c00aaab0000aaab

Security level: ~128-bit (comparable to AES-128)

Subgroup Construction

G₁: Prime-order subgroup of E(𝔽_q)

• Points: Compressed 48-byte representation
• Operations: Standard elliptic curve arithmetic in 𝔽_q

G₂: Prime-order subgroup of E’(𝔽_{q²}) (sextic twist)

• Twist curve: E’: y² = x³ + 4(1 + i)
• Points: Compressed 96-byte representation
• Operations: Arithmetic in 𝔽_{q²}

G_T: Subgroup of 𝔽*_{q^{12}}

• Elements: 576-byte representation (can be compressed)
• Operations: Multiplication in extension field

Twisted Curve Mathematics

Using sextic twist reduces G₂ operations to 𝔽_{q²} instead of 𝔽_{q^{12}}:

# Define 𝔽_{q²} = 𝔽_q[i] / (i² + 1)
F_q2 = GF(q^2, modulus=x^2 + 1, name='i')

# Twisted curve E' over 𝔽_{q²}
E_twist = EllipticCurve(F_q2, [0, 4*(1 + F_q2.gen())])

# Isomorphism ψ: E'(𝔽_{q²}) → E(𝔽_{q^{12}})
def twist_isomorphism(P):
    """
    Map point from twist curve to base curve
    """
    x, y = P.xy()
    # ψ(x, y) = (x · w², y · w³) where w ∈ 𝔽_{q^{12}}
    # (implementation details omitted for brevity)
    return E_base_12([x * w**2, y * w**3])

BLS Signature Scheme

Construction

BLS (Boneh-Lynn-Shacham) signatures exploit pairing bilinearity for compact, aggregatable signatures.

Setup:

• Public parameters: (G₁, G₂, G_T, e, P, H)
  • P: Generator of G₁
  • H: Hash function H: {0,1}* → G₁

Key generation:

def keygen():
    """
    Generate BLS keypair

    Returns:
        (sk, pk): Secret key sk ∈ ℤ_r, public key pk ∈ G₂
    """
    # Secret key: random scalar
    sk = random_scalar(r)

    # Public key: pk = [sk]P₂ where P₂ is generator of G₂
    pk = sk * P2

    return (sk, pk)

Signing:

def sign(sk, message):
    """
    Sign message

    Args:
        sk: Secret key
        message: Message bytes

    Returns:
        σ ∈ G₁: Signature
    """
    # Hash message to curve point
    H_m = hash_to_curve_G1(message)

    # Signature: σ = [sk]H(m)
    σ = sk * H_m

    return σ

Verification:

def verify(pk, message, σ):
    """
    Verify BLS signature

    Args:
        pk: Public key (G₂ element)
        message: Message bytes
        σ: Signature (G₁ element)

    Returns:
        bool: True if signature valid
    """
    # Hash message to curve
    H_m = hash_to_curve_G1(message)

    # Check pairing equation: e(σ, P₂) = e(H(m), pk)
    # Equivalently: e(σ, P₂) · e(H(m), -pk) = 1
    lhs = pairing(σ, P2)
    rhs = pairing(H_m, pk)

    return lhs == rhs

Correctness:

e(σ, P₂) = e([sk]H(m), P₂)
         = e(H(m), P₂)^{sk}      (bilinearity)
         = e(H(m), [sk]P₂)       (bilinearity)
         = e(H(m), pk)           (by definition)

Signature Aggregation

Multiple signatures on different messages can be aggregated:

def aggregate_signatures(signatures):
    """
    Aggregate multiple signatures

    Args:
        signatures: List of σ_i ∈ G₁

    Returns:
        σ_agg: Aggregated signature
    """
    # Simply sum the signatures
    σ_agg = sum(signatures)
    return σ_agg

def verify_aggregate(public_keys, messages, σ_agg):
    """
    Verify aggregated signature

    Args:
        public_keys: List of pk_i ∈ G₂
        messages: List of messages m_i
        σ_agg: Aggregated signature

    Returns:
        bool: True if valid
    """
    # Check: e(σ_agg, P₂) = ∏ᵢ e(H(mᵢ), pkᵢ)

    # Left side
    lhs = pairing(σ_agg, P2)

    # Right side: product of pairings
    rhs = G_T.one()
    for pk, m in zip(public_keys, messages):
        H_m = hash_to_curve_G1(m)
        rhs *= pairing(H_m, pk)

    return lhs == rhs

Advantage: n signatures → 1 signature (48 bytes instead of 48n bytes)

Application: Ethereum 2.0 uses BLS aggregation for validator attestations, reducing bandwidth by >95%.

Hash-to-Curve

Secure BLS signatures require deterministic, uniform hashing to G₁:

def hash_to_curve_G1(message):
    """
    Hash message to elliptic curve point (RFC 9380)

    Args:
        message: Arbitrary bytes

    Returns:
        Point in G₁
    """
    # Domain separation tag
    DST = b"BLS_SIG_BLS12381G1_XMD:SHA-256_SSWU_RO_"

    # Expand message to field elements
    u = hash_to_field(message, count=2, DST=DST)

    # Map to curve using Simplified SWU
    Q0 = map_to_curve_SSWU(u[0])
    Q1 = map_to_curve_SSWU(u[1])

    # Sum and clear cofactor
    P = clear_cofactor(Q0 + Q1)

    return P

def map_to_curve_SSWU(u):
    """
    Simplified Shallue-van de Woestijne-Ulas (SSWU) mapping

    Maps field element to curve point
    """
    # Constants for BLS12-381
    A = 0x144698a3b8e9433d693a02c96d4982b0ea985383ee66a8d8e8981aefd881ac98936f8da0e0f97f5cf428082d584c1d
    B = 0x12e2908d11688030018b12e8753eee3b2016c1f0f24f4070a0b9c14fcef35ef55a23215a316ceaa5d1cc48e98e172be0

    # SSWU algorithm (simplified):
    # 1. tv1 ← u²
    # 2. tv3 ← Z · tv1
    # ... (complete algorithm per RFC 9380)

    # Returns point on E(𝔽_q)
    return (x, y)

Security: RFC 9380 specifies “hash_to_curve” to prevent related-message attacks and ensure indifferentiability from random oracle.

Security Analysis

Computational Assumptions

BLS security relies on:

1. Computational Co-Diffie-Hellman (Co-CDH): Given (P, [a]P, [b]Q) ∈ G₁ × G₁ × G₂, compute [ab]P ∈ G₁.

2. Decisional Bilinear Diffie-Hellman (DBDH): Distinguish (P, [a]P, [b]P, [c]P, e(P, P)^{abc}) from (P, [a]P, [b]P, [c]P, e(P, P)^z) for random z.

BLS signature security:

• Existential unforgeability under Co-CDH in random oracle model
• Aggregation security requires distinct messages (prevented by message augmentation)

Rogue Public Key Attack

Threat: Attacker chooses pk* = [s]P₂ - ∑ pkᵢ to forge aggregate signature.

Mitigation:

1. Proof of possession: Require signature on pk before accepting
2. Message augmentation: Hash pk with message: σ = [sk]H(pk || m)
3. Distinct messages: Prevent aggregating signatures on same message

Pairing Inversions and Small Subgroup Attacks

Vulnerability: If point has small-order component, pairing may leak information.

Defense:

• Subgroup checks: Verify [r]P = 𝒪 for all inputs
• Cofactor multiplication: Multiply by cofactor h to clear small components

def is_in_G1(P):
    """
    Verify point is in prime-order subgroup G₁
    """
    # Check 1: Point on curve
    if not E.is_on_curve(P):
        return False

    # Check 2: Prime order
    if r * P != E.point_at_infinity():
        return False

    return True

Pairing-Based Cryptographic Protocols

Identity-Based Encryption (IBE)

Boneh-Franklin IBE eliminates public key certificates by deriving public keys from identities.

Setup:

def ibe_setup():
    """
    Generate IBE system parameters

    Returns:
        (params, msk): Public params and master secret key
    """
    # Master secret key
    msk = random_scalar(r)

    # Public parameters
    P_pub = msk * P2  # Master public key
    params = (P, P_pub, H1, H2)  # H1: {0,1}* → G₁, H2: G_T → {0,1}^n

    return (params, msk)

Key extraction:

def ibe_extract(params, msk, identity):
    """
    Extract private key for identity

    Args:
        identity: Email, domain, etc.

    Returns:
        sk_id ∈ G₁
    """
    # Hash identity to curve
    Q_id = H1(identity)

    # Private key: sk_id = [msk]Q_id
    sk_id = msk * Q_id

    return sk_id

Encryption:

def ibe_encrypt(params, identity, message):
    """
    Encrypt message for identity
    """
    P, P_pub, H1, H2 = params

    # Hash identity
    Q_id = H1(identity)

    # Random scalar
    σ = random_scalar(r)

    # Compute pairing: g_id = e(Q_id, P_pub)
    g_id = pairing(Q_id, P_pub)

    # Ciphertext
    C1 = σ * P
    C2 = message ⊕ H2(g_id^σ)

    return (C1, C2)

Decryption:

def ibe_decrypt(params, sk_id, ciphertext):
    """
    Decrypt ciphertext with identity private key
    """
    C1, C2 = ciphertext

    # Compute e(sk_id, C1) = e([msk]Q_id, [σ]P)
    #                       = e(Q_id, P)^{msk·σ}
    #                       = e(Q_id, [msk]P)^σ
    #                       = e(Q_id, P_pub)^σ
    #                       = g_id^σ
    shared_secret = pairing(sk_id, C1)

    # Decrypt
    message = C2 ⊕ H2(shared_secret)

    return message

Short Randomizable Signatures

BLS enables efficient blind signatures and threshold signatures:

Threshold BLS (t-of-n):

def threshold_keygen(t, n):
    """
    Generate threshold BLS keys

    Args:
        t: Threshold
        n: Total participants

    Returns:
        shares: Key shares for each participant
    """
    # Master secret polynomial: s(x) = s₀ + s₁x + ... + s_{t-1}x^{t-1}
    coeffs = [random_scalar(r) for _ in range(t)]
    s_0 = coeffs[0]  # Master secret key

    # Evaluate polynomial at participant indices
    shares = []
    for i in range(1, n+1):
        share = sum(coeffs[j] * (i**j) for j in range(t)) % r
        shares.append((i, share))

    # Master public key
    pk = s_0 * P2

    return (shares, pk)

def threshold_sign(share, message):
    """
    Generate signature share
    """
    i, sk_i = share
    H_m = hash_to_curve_G1(message)
    σ_i = sk_i * H_m
    return (i, σ_i)

def threshold_combine(sig_shares, t):
    """
    Combine t signature shares into full signature
    """
    # Lagrange interpolation at x=0
    indices, sigs = zip(*sig_shares[:t])

    σ = G1.identity()
    for j in range(t):
        # Lagrange coefficient
        λ_j = 1
        for m in range(t):
            if m != j:
                λ_j *= indices[m] / (indices[m] - indices[j])

        σ += int(λ_j) * sigs[j]

    return σ

Implementation Considerations

Constant-Time Operations

Prevent timing attacks in pairing computations:

def constant_time_pairing(P, Q):
    """
    Constant-time Miller algorithm

    - No secret-dependent branches
    - Uniform memory access patterns
    - Constant-time field arithmetic
    """
    # Ensure all code paths take same time
    # regardless of secret values
    # ... (implementation uses dummy operations)

Performance Optimization

Benchmark (BLS12-381 on Intel i7-10710U):

Operation	Time	Notes
G₁ scalar mult	50 μs	Variable-base
G₂ scalar mult	180 μs	Variable-base
Pairing (single)	1.2 ms	Full Miller + final exp
Pairing (batch 10)	8.5 ms	Amortized 0.85 ms each
Signature verify	1.7 ms	2 pairings
Aggregate verify (10 sigs)	11 ms	Multi-pairing optimization

Optimizations:

1. Multi-pairing: Compute ∏ e(Pᵢ, Qᵢ) faster than individual pairings
2. Precomputation: Cache Miller loop values for fixed points
3. Batch verification: Use randomized checks for multiple signatures
4. Assembly: Hand-optimize field arithmetic (10×+ speedup)

Comparison with Other Signature Schemes

Scheme	Signature Size	Verification	Aggregation	Security Basis
BLS	48 bytes	2 pairings	Yes (linear)	Co-CDH
ECDSA	64 bytes	1 scalar mult	No	ECDLP
EdDSA	64 bytes	1 double-base mult	Partial	ECDLP
RSA-2048	256 bytes	Fast (e=65537)	No	Factoring
Schnorr	64 bytes	1 double-base mult	Yes (interactive)	ECDLP

BLS advantages:

• Smallest signatures
• Non-interactive aggregation
• Deterministic (no nonce vulnerabilities)

BLS disadvantages:

• Slower verification (~10× ECDSA)
• Larger public keys (96 bytes vs. 33 for ECDSA)
• Requires pairing-friendly curves

Conclusion

Elliptic curve pairings provide powerful cryptographic primitives enabling protocols impossible with traditional discrete logarithm systems. BLS signatures, leveraging bilinear pairings on BLS12-381, achieve unmatched compactness and aggregation properties critical for blockchain scalability (Ethereum 2.0) and distributed systems.

Understanding pairing mathematics—from Weil/Tate definitions through Miller’s algorithm to secure hash-to-curve—is essential for implementing pairing-based cryptography securely and efficiently. As post-quantum migration continues, pairings remain relevant for hybrid constructions and transitional protocols.

References

1. Boneh, D., Lynn, B., & Shacham, H. (2001). “Short signatures from the Weil pairing.” ASIACRYPT 2001.
2. Boneh, D., & Franklin, M. (2001). “Identity-based encryption from the Weil pairing.” CRYPTO 2001.
3. Barreto, P., & Naehrig, M. (2006). “Pairing-friendly elliptic curves of prime order.” SAC 2005.
4. Bowe, S. (2017). “BLS12-381: New zk-SNARK Elliptic Curve Construction.” Zcash blog.
5. Miller, V. (1986). “The Weil pairing, and its efficient calculation.” Journal of Cryptology.
6. Faz-Hernández, A., et al. (2023). “Hashing to Elliptic Curves.” RFC 9380.
7. Silverman, J. (2009). “The Arithmetic of Elliptic Curves.” Springer GTM 106.
8. Galbraith, S., Paterson, K., & Smart, N. (2008). “Pairings for cryptographers.” Discrete Applied Mathematics.