# How Elligator 2 was Designed

At a first glance, Elligator 2 looks like black magic. To unravel its mysteries, it helps to look into how it was conceived. Turns out, as is often the case with such elegant designs, the core ideas are actually fairly simple.

## The problem

We want to map arbitrary numbers to elliptic curve points.
We should do so in constant time,
and the mapping needs to be uniform,
or close enough to uniform.
The curves we're interested in have the form
`v`^{2} = `u`^{3} + `A``u`^{2} + `B``u`.
We want to map a representative `r` to a point
(`u`, `v`) that satisfies this equation.

Merely trying `u` = `r` does not work,
because
`r`^{3} + `A``r`^{2} + `B``r`
will not always have a square root.
In fact, this problem is the whole *point* of Elligator:
random numbers will fail this condition half the time,
while `u` coordinates never do.
This statistical difference is what allows attackers to distinguish
them.

We could also try `r`, `r`+1, `r`+2 etc.
until we find one that does work,
but this is neither constant time nor uniform.

## The solution

The idea that ended up working was the following:
instead of trying to map `r` to a single `u`
coordinate,
we map it to *two* `u _{1}` and

`u`coordinates, such that the ratio

_{2}`v`

_{1}^{2}/

`v`

_{2}^{2}is not a square. This will guarantee that either

`u`or

_{1}`u`will be on the curve, and the other will not. We then just need to select the right one.

_{2}We start by using the ratio
`v _{1}`

^{2}/

`v`

_{2}^{2}as a stepping stone. Instead of trying to map

`r`to some

`u`and

_{1}`u`directly we map it to a single non-square number that we decide

_{2}*is*the ratio. The easiest way to do this is to square

`r`then multiply it by an arbitrary non-square constant

`Z`. This leads to

**eq1:**

`Z`

`r`

^{2}=

`v`

_{1}^{2}/

`v`

_{2}^{2}.

We need to map to *two* numbers however,
and so far we only have *one* constraint.
We need a second one to get rid of the degree of freedom we have left.
Recall what our ratio is made of:

`v`_{1}^{2}=`u`_{1}^{3}+`A``u`_{1}^{2}+`B``u`=_{1}`u`(_{1}`u`_{1}^{2}+`A``u`+_{1}`B`)`v`_{2}^{2}=`u`_{2}^{3}+`A``u`_{2}^{2}+`B``u`=_{2}`u`(_{2}`u`_{2}^{2}+`A``u`+_{2}`B`)

A second constraint that works (and is new in Elligator 2) is
deciding that
(`u _{1}`

^{2}+

`A`

`u`+

_{1}`B`) = (

`u`

_{2}^{2}+

`A`

`u`+

_{2}`B`). Simplifying this gives us

**eq2:**

`u`+

_{1}`u`= −

_{2}`A`.

Finally, we can solve **eq1** and **eq2** together to get our mapping:

`u`= −_{1}`A`/ (1 +`Z``r`^{2})`u`= −_{2}`A``Z``r`^{2}/ (1 +`Z``r`^{2})

That's the gist of it.
For every representative `r`,
either `u _{1}`
or

`u`will work. We just need to test which is the right one, compute the corresponding

_{2}`v`coordinate if we need it, done.

## Constant time implementation

The official Elligator 2 map is a bit more refined than the
above.
Recall that we compute the point
`P` = (`u`, `v`) from the
representative `r`:

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

Let's walk through it:

We can readily see that

`w`=`u`._{1}The value of

`e`tells us whether`v`_{1}^{2}is really a square:- When
`e`= 1 then it is and`w`=`u`was the right choice._{1} - When
`e`= −1 then it is not and we must switch to`u`instead._{2}

- When
The

`u`=`e``w`− (1 −`e`) (`A`/ 2) equation is a bit harder to follow:- When
`e`= 1 then`u`reduces to`w`=`u`._{1} - When
`e`= −1 then`u`reduces to −`w`−`A`=`u`._{2}*(We can verify that −*`u`−_{1}`A`=`u`)_{2}

- When
The

`v`coordinate is computed by simply solving the curve equation. Note that at this point, the square root is guaranteed to work. Note the use of`e`to flip the select of the square root, depending on whether we ended up choosing`u`or_{1}`u`. This is needed to prevent_{2}`r`and 1/`Z``r`from mapping to the same point.

## Uniformity of the mapping

Full uniformity would mean having have each representative to map to a different curve point. This is not quite possible, because the order of a curve does not match the cardinality of its field, let alone a power of two. This forces mappings like Elligator 2 to accept some imperfections.

The first imperfection comes from the map being a function of
`r`^{2}.
This eliminates the sign of `r`,
such that both `r` and −`r` map to the same
point.
In practice this means Elligator 2 will cover only about *half* of
the curve.
The other half remains unmapped,
which is why the reverse map sometimes fail.

In many cases we can live with that.
If the reverse map doesn't work we can just generate another point and
retry,
and many protocols that map inputs to curve points can survive the loss
of half the curve.
In some cases however we do need a truly uniform map that covers the
whole curve.
One way to do so is to select *two* random numbers
(or derive two independent hashes),
map each to its curve point,
then add those two points together.
This covers the whole curve with no detectable bias.

The second imperfection comes from the cardinality of the field
GF(`q`) not being a power of 2.
When `q` is sufficiently close to a power of 2
(as is the case for Curve25519 and Curve448),
the bias is undetectable and we can ignore the issue.
When it is too far,
we need to select a number from a much bigger power of 2 before reducing
it
(with modular reduction)
into a field element.

A *potential* third imperfection to watch out for is how `r`
and 1/`Z``r` will merely *flip*
`u _{1}` and

`u`. The correct

_{2}`u`coordinate will end up being the same in both cases, so if we derive

`v`naively we'll end up with

*four*representatives mapping to the same point instead of just two. Thankfully we have an easy counter: whenever (

`u`,

`v`) is on the curve, so is (

`u`, −

`v`). Thus, we can select the sign of

`v`depending on whether

`u`or

_{1}`u`was chosen. This let us map

_{2}`r`and 1/

`Z`

`r`to

*opposite*points instead of the same one: if

`r`maps to (

`u`,

`v`), 1/

`Z`

`r`will map to (

`u`, −

`v`).

## Optimising the map

The astute reader may have noted that the above requires two
exponentiations (the `legendre`

symbol and the square root),
while our optimised formulas only require a *single*
exponentiation to compute both `u` and `v`.

To understand how this is even possible,
we must express `v _{1}`

^{2}and

`v`

_{2}^{2}in terms of

`r`and

`Z`. This is a little tedious, but we ultimately get to:

`v`_{1}^{2}=`A`(`A`^{2}`Z``r`^{2}−`B`(1 +`Z``r`^{2})^{2}) / (1 +`Z``r`^{2})^{3}`v`_{2}^{2}=`v`_{1}^{2}`Z``r`^{2}

The only difference between `v _{1}`

^{2}and

`v`

_{2}^{2}is the little

`Z`

`r`

^{2}factor. We can exploit this when we compute our square root: In practice, exponentiation based square root routines

*always*give a meaningful result, even if their operand is not square. A clever choice of

`Z`(typically −1 or √−1) can let us attempt the square root, and if it "fails" we just multiply the result by

`r`.

That way we can know which of `u _{1}` or

`u`is the correct mapping

_{2}*and*compute

`v`in a single exponentiation. And if for some reason we made a less clever choice (such as

`Z`= 2) we can still perform this optimisation. We just need an additional multiplication by the right constant to compensate.