Group Hash

Elligator can be applied to map a field element to a curve point. The map can be applied once to derive a curve point suitable for use with computational Diffie-Hellman (CDH) challenges, and twice to derive a curve point indistinguishable from random.

In the following section, $a$ and $d$ are the curve parameters as described here. $\zeta$ is a constant and sqrt_ratio_zeta(v_1,v_2) is a function, both defined in the Inverse Square Roots section.

The Elligator map is applied as follows to a field element $r_0$:

1. $r\leftarrow \zeta r_0^2$.

2. $u_1\leftarrow (dr-d+a)(dr-ar-d)$.

3. $n_1\leftarrow (r+1)(a-2d)$.

4. $m,x=$ sqrt_ratio_zeta$(1,u_1{n}_1)$ where $m$ is a boolean indicating whether or not a square root exists for the provided input.

5. If a square root for $u_1{n}_1$ does not exist, then $q=-1$ and $x=r_{0}x$. Else, $q=1$ and $x$ is unchanged.

6. $s\leftarrow x{n}_1$.

7. $t\leftarrow -qxs(r-1)(a-2d{)}^2-1$.

8. If ($s<0$ and $m$ is true) or ($s>0$ and $m$ is false) then $s=-s$.

The Jacobi quartic representation of the resulting point is given by $(s,t)$. The resulting point can be converted from its Jacobi quartic representation to extended projective coordinates via:

$E\leftarrow 2s$

$F\leftarrow 1+a{s}^2$

$G\leftarrow 1-a{s}^2$

$H\leftarrow t$

$X\leftarrow EH$

$Y\leftarrow FG$

$Z\leftarrow FH$

$T\leftarrow EG$

For single-width hash-to-group (encode_to_curve), we apply the above map once. For double-width (hash_to_curve) we apply the map to two field elements and add the resulting curve points.