Elligator

The Decaf paper explains how to formulate a map from field elements to points suitable for hashing to group elements. Rather than mapping directly to the Edwards or Montgomery model, Decaf suggests using Elligator 2 to the Jacobi quartic \(\mathcal J\), then applying an isogeny to obtain a point on whichever curve is used for implementing group operations. This allows implementations using different curves internally to have compatible Elligator maps.

This method also applies to Ristretto, with a suitable change of variables.

Elligator for Decaf

The Decaf paper constructs the Elligator map as follows, using the Decaf parameters \(a_1, d_1\). First, fix a parameter \(n \in \mathbb F \) which is nonsquare. Then, on input \(r_0 \in \mathbb F\), compute \( r \gets n r_0^2 \). Since \( n \) is nonsquare, \(r\) is nonsquare unless \(r_0 = 0\), in which case \(r = 0\).

The output of the Elligator map is either \[ (s,t) = \left( + \sqrt{ \frac{ (r+1)(a_1 - 2d_1) }{ (d_1 r + a_1 - d_1) (d_1 r - a_1 r - d_1) } } , \frac{ -(r-1)(a_1 - 2d_1)^2 }{ (d_1 r + a_1 - d_1) (d_1 r - a_1 r - d_1) } - 1 \right) \] or \[ (s,t) = \left( - \sqrt{ \frac{ r(r+1)(a_1 - 2d_1) }{ (d_1 r + a_1 - d_1) (d_1 r - a_1 r - d_1) } } , \frac{ r(r-1)(a_1 - 2d_1)^2 }{ (d_1 r + a_1 - d_1) (d_1 r - a_1 r - d_1) } - 1 \right) \] depending on which square root exists, preferring the second case when \(r = 0\) and both are square.

Changing variables to Ristretto parameters

We can rewrite this in terms of the Ristretto parameters \(a_2, d_2\) using the identities \(a_1 = -a_2\), \(d_1 = a_2d_2 / (a_2 - d_2)\). The denominator is \[ \begin{aligned} D &= (d_1 r + a_1 - d_1) (d_1 r - a_1 r - d_1) \\ &= \left( \frac {a_2 d_2}{ a_2 - d_2} r - a_2 - \frac {a_2 d_2}{ a_2 - d_2} \right) \left( \frac {a_2 d_2}{ a_2 - d_2} r + a_2r - \frac {a_2 d_2}{ a_2 - d_2} \right) \\ &= \frac { \left( a_2 d_2 r - a_2(a_2 - d_2) - a_2 d_2 \right) \left( a_2 d_2 r + a_2(a_2 -d_2) r - a_2 d_2 \right) } {(a_2 - d_2)^2} \\ &= \frac { \left( a_2 d_2 r - 1 \right) \left( r - a_2 d_2 \right) } {(a_2 - d_2)^2} . \\ \end{aligned} \] Since \(a_2^2 = 1\), this is \[ \begin{aligned} D &= \frac { a_2^2 \left( a_2 d_2 r - 1 \right) \left( r - a_2 d_2 \right) } {(a_2 - d_2)^2} \\ &= \frac { \left( a_2^2 d_2 r - a_2 \right) \left( a_2 r - a_2^2 d_2 \right) } {(a_2 - d_2)^2} \\ &= \frac { \left( d_2 r - a_2 \right) \left( a_2 r - d_2 \right) } {(a_2 - d_2)^2} , \\ \end{aligned} \] so that \[ 1/D = \frac {(a_2 - d_2)^2} { \left( d_2 r - a_2 \right) \left( a_2 r - d_2 \right) } . \] The numerators of the terms in the Elligator map are \[ \begin{aligned} (r+1)(a_1 - 2d_1) &\qquad & -(r+1)(a_1 - 2d_1)^2 \\ r(r+1)(a_1 - 2d_1) & \qquad & r(r+1)(a_1 - 2d_1)^2; \\ \end{aligned} \] since \[ a_1 - 2d_1 = - a_2 \left( \frac{a_2 + d_2}{a_2 - d_2} \right)^2, \] these become \[ \begin{aligned} -a_2 (r+1) \left( \frac{a_2 + d_2}{a_2 - d_2} \right) &\qquad & +a_2 (r-1) \left( \frac{a_2 + d_2}{a_2 - d_2} \right)^2 \\ -a_2 r (r+1) \left( \frac{a_2 + d_2}{a_2 - d_2} \right) & \qquad & -a_2 r (r-1) \left( \frac{a_2 + d_2}{a_2 - d_2} \right)^2. \\ \end{aligned} \] Multiplying the numerators by the denominator \(1/D\) gives \[ \begin{aligned} \frac { -a_2 (r+1) (a_2 + d_2)(a_2 - d_2) }{ (d_2 r - a_2)(a_2r-d_2) } &\qquad & \frac { +a_2 (r-1) (a_2 + d_2)^2 }{ (d_2 r - a_2)(a_2r-d_2) } \\ \frac { -a_2 r (r+1) (a_2 + d_2)(a_2 - d_2) }{ (d_2 r - a_2)(a_2r-d_2) } & \qquad & \frac { -a_2 r (r-1) (a_2 + d_2)^2 }{ (d_2 r - a_2)(a_2r-d_2) } \\ \end{aligned} \]

Elligator for Ristretto

The Elligator map, written in terms of the Ristretto parameters, is therefore given by \[ (s,t) = \left( + \sqrt{ \frac{ a_2(r+1)(a_2 + d_2)(d_2 - a_2) }{ (d_2 r - a_2)(a_2 r - d_2) } } , \frac{ +a_2(r-1)(a_2 + d_2)^2 }{ (d_2 r - a_2)(a_2 r - d_2) } - 1 \right) \] or \[ (s,t) = \left( - \sqrt{ \frac{ a_2r(r+1)(a_2 + d_2)(d_2 - a_2) }{ (d_2 r - a_2)(a_2 r - d_2) } } , \frac{ -a_2r(r-1)(a_2 + d_2)^2 }{ (d_2 r - a_2)(a_2 r - d_2) } - 1 \right) \] depending on which square root exists, preferring the second when \(r = 0\) and both are square.