# 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`^{2}=`u`^{3}+`A``u`^{2}+`B``u`, such that`A``B`(`A`^{2}− 4`B`) ≠ 0. Note that this includes all Montgomery curves of the form`v`^{2}=`u`^{3}+`A``u`^{2}+`u`(except`v`^{2}=`u`^{3}+`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

^{255}− 19), used by Curve25519, and GF(2^{448}− 2^{224}− 1), used by Curve448.The

**elliptic curve**, defined by the equation`v`^{2}=`u`^{3}+`A``u`^{2}+`B``u`.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`^{2}=`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^{255}− 19), those would be 2 and √−1 respectively. With GF(2^{448}− 2^{224}− 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`^{2})`e`=`legendre`

(`w`^{3}+`A``w`^{2}+`B``w`)`u`=`e``w`− (1 −`e`) (`A`/ 2)`v`= −`e`√(`u`^{3}+`A``u`^{2}+`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;- −
`Z``u`(`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.