The Elligator Map and Inverse Map

Elligator specifies two kinds of maps, the “map” (or “direct map” for clarity) and the “inverse map”.

The map is a function that takes a number r from an elliptic curve’s finite field (which we call a “field element”), and produces a point P = (u, v) on that elliptic curve. Note that the map is not quite injective: r and −r map to the same point. Numbers that are neither equal nor opposite do map to different points though.

The inverse map is a function that takes as input an elliptic curve point P and outputs a field element r. We also call that number the “representative” because it represents a point on the curve. Note that only about half of the curve can be mapped back.

For any given point P that can be mapped, applying the inverse map then the direct map will yield the original point P.

For any representative r in the curve’s finite field, applying the direct map then the inverse map will yield either the original representative r or its opposite −r.

Applicability

Elligator does not work on all elliptic curves, and will not properly hide points on all curves where it does work. The following conditions must hold:

• The finite field the curve is based on must have an odd characteristic. That is, it cannot be a binary field. In practice most curves use large prime fields, which are all odd. While extension fields and binary fields can sometimes be faster, prime fields have a more compelling security story.

• The curve is expressible in the form v² = u³ + Au² + Bu, such that AB(A² − 4B) ≠ 0. Note that this includes all Montgomery curves of the form v² = u³ + Au² + u (except v² = u³ + u), including Curve25519 and Curve448. In practice, almost any curve with an odd field and a point of order two can be written in this form.

• Additionally, for Elligator to properly hide points on the curve as random noise, The characteristic of its field must be very close to a power of two. This is because we are ultimately transmitting bit strings over the network, whose range is always a power of two. In practice, only Mersenne primes (2^k − 1), pseudo-Mersenne primes (2^k − c), and some Solinas primes (2^k − 2^l … − 1 where k − l ideally exceeds 128) are adequate.

Overall, those conditions cover a wide range of curves, including the very popular Curve25519 and Curve448. One notable exception are short Weierstraß curves that have a prime order and therefore lack a point of order two; an example of a curve with a prime order is NIST P-256.

Instantiation Parameters

An Elligator instantiation works over a specific curve, and has a couple parameters of its own. Before actually defining the maps, we need to fix those parameters.

• The finite field GF(q) over which the curve operates. Note that q is always the power of a prime. That is, q = p^m, for some prime p and some strictly positive integer m. Most of the time though, we will be using a prime field, where q = p. Recall that p = 2 is not possible because the field must have an odd characteristic.

  Examples of finite fields include GF(2²⁵⁵ − 19), used by Curve25519, and GF(2⁴⁴⁸ − 2²²⁴ − 1), used by Curve448.

• The elliptic curve, defined by the equation v² = u³ + Au² + Bu.

  Examples of elliptic curves include Curve25519 (A = 486662, B = 1) and Curve448 (A = 156326, B = 1).

• The non-square Z in GF(q). It can be any number in GF(q) that has no square root. That is, there is no number n in GF(q) such that n² = Z.

  We generally chose Z to minimise computations down the line, like small numbers, or numbers tailored to speed up specific implementations. With GF(2²⁵⁵ − 19), those would be 2 and √−1 respectively. With GF(2⁴⁴⁸ − 2²²⁴ − 1), −1 is best in all cases.

• The set of non-negative field elements. A square s in GF(q) always has two square roots: √s and −√s. We need a way to determine which is the positive one for the direct and inverse maps to be deterministic.

  For prime fields GF(p) where p ≡ 3 (mod 4), we can pick √s = s^(p+1)/4, which is the unique square root that is also a square (the principal square root).

  For other fields, we chose the set of non-negative field elements somewhat arbitrarily. Common choices are the set {0, 1, … (q−1)/2} or the set of even numbers.

The direct map

First, we need to define the legendre() function; it computes the Legendre symbol of a field element f:

• legendre(f) = 0 if f is zero.
• legendre(f) = 1 if f is a non-zero square.
• legendre(f) = −1 if f is not a square.

This can be constructed using the square root checking functions needed to find the chosen non-square Z above. In a prime fields GF(p), it can be defined as: legendre(f) = f^{(p − 1) / 2}.

The map itself takes any non-zero field element r (the representative), and outputs a point P = (u, v) on the curve as follows:

• w = −A / (1 + Z r²)
• e = legendre(w³ + A w² + B w)
• u = e w − (1 − e) (A / 2)
• v = −e √(u³ + A u² + B u)
• P = (u, v)

Zero is a special case, which maps to the point (0, 0).

The inverse map

Unlike the direct map, the inverse map does not work for all points on the curve. It only holds for points P = (u, v) such that:

• u ≠ −A;
• −Zu(u + A) is a square;
• if v = 0, then u = 0 as well.

Assuming those conditions hold, the representative r of P = (u, v) is computed as follows:

• r = √(−u / (Z (u + A))) if v is non-negative,
• r = √(−(u + A) / (Z u)) if v is strictly negative.

Note: if P = (0, 0) then r = √(−0 / (Z (0 + A))) = 0.