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.

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).

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

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.)

The types of pairings are:

  • Type-1 (symmetric pairing): \(G_1 = G_2\). DDH is easy in \(G_1\) (and therefore \(G_2\)).
  • Type-2: \(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.
  • 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: Weil pairing, Tate pairing, Ate pairing

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