Pairings

A bilinear pairing is an efficiently computable, non-degenerate map $e:{\mathbb{G}}_1\times {\mathbb{G}}_2\to {\mathbb{G}}_T$ between cyclic groups of prime order $l$, satisfying $e(aP,bQ)=e(P,Q{)}^{ab}$ for all $P\in {\mathbb{G}}_1$, $Q\in {\mathbb{G}}_2$, $a,b\in \mathbb{Z}$. In practice, pairings arise from the Weil pairing or Tate pairing on an elliptic curve $E({\mathbb{F}}_q)$, where the groups ${\mathbb{G}}_1,{\mathbb{G}}_2\subset E({\mathbb{F}}_{q^k})$ are $l$-torsion subgroups and $k$ is the embedding degree.

Types

Galbraith, Paterson, and Smart GPS06 classify pairings into three types based on the availability of efficiently computable group homomorphisms. No type simultaneously achieves all four properties:

Property	Type 1	Type 2	Type 3
Efficient hash to ${\mathbb{G}}_2$	✓	✗	✓
Short ${\mathbb{G}}_1$ representations	✗	✓	✓
Efficiently computable $\varphi :{\mathbb{G}}_2\to {\mathbb{G}}_1$	✓	✓	✗
Poly-time parameter generation	✗	✓	✓

Type 1 (${\mathbb{G}}_1={\mathbb{G}}_2$, symmetric). Implemented on supersingular curves. Hashing to ${\mathbb{G}}_2={\mathbb{G}}_1$ is trivial, and the identity serves as a computable homomorphism. The embedding degree $k$ is small and fixed for known supersingular constructions, so the security level is bounded and polynomial-time parameter generation for arbitrary $\lambda$ is infeasible. Elements of ${\mathbb{G}}_1$ cannot be made shorter than elements of ${\mathbb{G}}_2$.

Type 2 (${\mathbb{G}}_1\ne {\mathbb{G}}_2$, with $\varphi :{\mathbb{G}}_2\to {\mathbb{G}}_1$ efficiently computable). Implemented on ordinary curves; the trace map serves as $\varphi$. Supports short ${\mathbb{G}}_1$ representations and polynomial-time parameter generation. No efficient hash to ${\mathbb{G}}_2$ is known, because ${\mathbb{G}}_2$ is an eigenspace of the Frobenius endomorphism.

Type 3 (${\mathbb{G}}_1\ne {\mathbb{G}}_2$, no efficiently computable homomorphism in either direction). Implemented on ordinary curves with ${\mathbb{G}}_2$ the trace-zero subgroup. Supports efficient hash to ${\mathbb{G}}_2$, short ${\mathbb{G}}_1$ representations, and polynomial-time parameter generation. No efficiently computable $\varphi :{\mathbb{G}}_2\to {\mathbb{G}}_1$ (or ${\mathbb{G}}_1\to {\mathbb{G}}_2$) exists, as far as is known.

Efficiency

Pairing-based systems scale like RSA rather than ECC. Achieving $\kappa$ bits of security requires ${\mathbb{G}}_T\subset {\mathbb{F}}_{q^k}^{\ast }$ to be of RSA-modulus size, so any operation involving pairing outputs is bounded by arithmetic in that large extension field. At 256-bit security, this corresponds to a roughly 15 000-bit field — GPS06.

Type 3 is the only type offering acceptable efficiency and parameter flexibility at high security levels. The trade-off is the absence of a ${\mathbb{G}}_2\to {\mathbb{G}}_1$ homomorphism: security proofs for several published pairing-based schemes assume such a map, and those proofs do not carry through when the scheme is instantiated with Type 3 pairings — GPS06.

Standard instantiations

Citations for specific curve families (BN curves, BLS12-381, MNT curves) should be added here with appropriate references.