elliptic curve pairing

Work in Progress

Summary

Secure elliptic curves need a large prime-order subgroup and a large embedding degree. Pairings can move ECDLP into a finite field, so they are either an attack surface or a deliberate protocol feature.

Concept

For coprime to the characteristic, the algebraic-closure torsion satisfies

Consequently is cyclic or a product of two cyclic groups. Point counting is polynomial-time via Schoof’s algorithm; random curves have orders distributed near and can be searched for prime order.

A nondegenerate bilinear pairing has the form

with

If , then

reducing ECDLP to DLOG in . The embedding degree is the least such that .

Curve selection therefore checks:

  1. A large prime group order or prime-order subgroup.
  2. No small embedding degree.
  3. Group order not equal to .
  4. Safe formulas, input validation, and twist security.

Application

  • NIST P-256 uses a sparse prime and for efficient arithmetic.
  • Curve25519 uses , Montgomery-form x-only arithmetic, cofactor , and a secure twist; scalar clamping keeps operations in the intended subgroup.
  • secp256k1 uses and is deployed by Bitcoin.

Invalid-point attacks exploit implementations that scalar-multiply a point on another curve. Validate points or use a design, such as Curve25519’s x-only ladder, that safely handles the twist. See pairing based cryptography for constructive uses.