Skip to content

Elliptic-Curve Cryptography

Further Reading

Elliptic curve (EC)

In cryptography, we use ECs over finite fields (i.e., \(\mathbb{F}_n\), which is unique for a given value of \(n\)). Often, we use a prime field \(\mathbb{F}_p\) where \(p\) is prime. An EC over \(\mathbb{F}_n\) is defined as a set of points \((x,y) \in \mathbb{F}_n^2\) satisfying some bivariate equation. The points form a group.

Type Field EC Examples
Weierstrass \(\mathbb{F}_p\) \(\{ (x,y): y^2 = x^3 + ax + b, 4a^3 + 27b^2 \neq 0\}\) All curves can be written in Weierstrass form
Koblitz \(\mathbb{F}_{2^p}\) \(\{ (x,y) : y^2 + xy = x^3 + ax^2 + 1, a \in \{0,1\}\}\) nistk163, nistk283, nistk571 (the number after k is the prime \(p\))
Binary \(\mathbb{F}_{2^m}\) \(\{ (x,y) : x^2 + xy = x^3 + x^2 + b \}\) nistb163, nistb283, nistb571
Edwards \(\{ (x,y) : x^2 + y^2 = 1 + dx^2y^2, d \in \{0,1\}\}\)
Montgomery \(\{ (x,y) : by^2 = x^3 + ax^2 + x, b(a^2-4) \neq 0 \}\) Curve25519

An EC may or may not be pairing-friendly. Pairing-friendly curves have all three of the common pairings (Weil, Ate, and Tate; see below).

  • Pairing-friendly curves: Baretto-Naehrig (e.g., BN254), Barreto-Lynn-Scott (e.g., BLS12-381, BLS12-377), Kachisa-Schaefer-Scott (KSS), Miyaji-Nakabayashi-Takano (MNT)
  • Pairing-free curves: secp256k1, NIST P-256, Curve25519

Resource

  • The parameters for many elliptic curves used in practice can be found here.

Pairing-Based Cryptography

(Bilinear) Pairing

In its most common form in cryptography, a bilinear pairing is a map \(e: G_1 \times G_2 \rightarrow G_T\), where \(G_1, G_2\) are additive cyclic groups of prime order \(q\) and \(G_T\) is a multiplicative cyclic group of order \(q\). The map \(e\) is required to have the following properties:

  • Bilinearity. For any \(a,b \in \mathbb{F}_q^*\) and \(P, P_1, P_2 \in G_1\) and \(Q, Q_1, Q_2 \in G_2\),
    • \(e(aP, Q) = e(P, aQ) = e(P,Q)^a\)1 and
    • \(e(P_1 + P_2, Q) = e(P_1, Q) \cdot e(P_2, Q)\) and \(e(P, Q_1 + Q_2) = e(P, Q_1) \cdot e(P, Q_2)\).
  • Non-degeneracy. \(e(P, Q) \neq 1\) where \(P, Q\) are generators of \(G_1, G_2\), respectively.
  • Computability. There is an efficient algorithm for computing \(e\).

(A bilinear map is only required to meet the first property.)

Examples: Weil pairing, Tate pairing, Ate pairing

Depending on the (sub)group (i.e., elliptic curve) used, a pairing falls into one of three types:

  • Type-12 (symmetric pairing): \(G_1 = G_2\). DDH is easy in \(G_1\) (and therefore \(G_2\)).
  • Type-23: \(G_1 \neq G_2\) but there exists an efficiently computable homomorphism \(\phi: G_2 \rightarrow G_1\). DDH is easy in \(G_2\) but thought to be hard in \(G_1\), referred to as the external Diffie-Hellman (XDH) assumption.
    Examples: Some pairings on BN curves
  • Type-3: \(G_1 \neq G_2\) and there is no efficiently computable homomorphism between \(G_1\) and \(G_2\). DDH is thought to be hard in both \(G_1\) and \(G_2\), referred to as the symmetric external Diffie-Hellman (SXDH) assumption.
    Examples: BLS curves, some pairings on BN curves

  1. Therefore \(e(aP, bQ) = e(P,Q)^{ab}\). ↩

  2. Type-1 pairings are generally less efficient to compute than asymmetric (type-2 and 3) pairings, so they are less commonly used. ↩

  3. Type-2 pairings have been found to be less functional, secure, and efficient than type-3, so they are hardly used anymore. ↩