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 and is a constant defined in the Inverse Square Roots section.

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

  1. .

  2. .

  3. .

  4. .

  5. If a square root for exists, then the Jacobi quartic representation of the resulting point is . Else .

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.

  • TODOs: specify optimized version, need to match the choice of quadratic nonresidue with used in invsqrt.