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, and are the curve parameters. is a constant and isqrt(x) is a function, both defined in the Inverse Square Roots section.

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

  1. .

  2. .

  3. .

  4. isqrt where is a boolean indicating whether or not a square root exists for the provided input.

  5. If a square root for does not exist, then and . Else, and is unchanged.

  6. .

  7. .

  8. If ( and is true) or ( and is false) then .

The Jacobi quartic representation of the resulting point is given by . The resulting point can be converted from its Jacobi quartic representation to affine Edwards coordinates via:

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