Elligator: Hiding cryptographic key exchange as random noise

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 v2 = u3 + Au2 + Bu. We want to map a representative r to a point (uv) that satisfies this equation.

Merely trying u = r does not work, because r3 + Ar2 + Br 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 u1 and u2 coordinates, such that the ratio v12 / v22 is not a square. This will guarantee that either u1 or u2 will be on the curve, and the other will not. We then just need to select the right one.

We start by using the ratio v12 / v22 as a stepping stone. Instead of trying to map r to some u1 and u2 directly we map it to a single non-square number that we decide 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: Zr2 = v12 / v22.

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:

A second constraint that works (and is new in Elligator 2) is deciding that (u12 + Au1 + B) = (u22 + Au2 + B). Simplifying this gives us eq2: u1 + u2 = −A.

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

That's the gist of it. For every representative r, either u1 or u2 will work. We just need to test which is the right one, compute the corresponding 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 = (uv) from the representative r:

Let's walk through it:

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 r2. 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/Zr will merely flip u1 and u2. The correct 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 (uv) is on the curve, so is (u, −v). Thus, we can select the sign of v depending on whether u1 or u2 was chosen. This let us map r and 1/Zr to opposite points instead of the same one: if r maps to (uv), 1/Zr 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 v12 and v22 in terms of r and Z. This is a little tedious, but we ultimately get to:

The only difference between v12 and v22 is the little Zr2 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 u1 or u2 is the correct mapping 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.