# 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 = (uv) 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 v2 = u3 + Au2 + Bu, such that AB(A2 − 4B) ≠ 0. Note that this includes all Montgomery curves of the form v2 = u3 + Au2 + u (except v2 = u3 + 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 (2k − 1), pseudo-Mersenne primes (2k − c), and some Solinas primes (2k − 2l … − 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 = pm, 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(2255 − 19), used by Curve25519, and GF(2448 − 2224 − 1), used by Curve448.

• The elliptic curve, defined by the equation v2 = u3 + Au2 + 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 n2 = Z.

We generally chose Z to minimise computations down the line, like small numbers, or numbers tailored to speed up specific implementations. With GF(2255 − 19), those would be 2 and √−1 respectively. With GF(2448 − 2224 − 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 = (uv) on the curve as follows:

• w = −A / (1 + Z r2)
• e = `legendre`(w3 + A w2 + B w)
• u = e w − (1 − e) (A / 2)
• v = −e √(u3 + A u2 + B u)
• P = (uv)

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 = (uv) 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 = (uv) 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.