Field element to curve point mapping used by EIP 2537

For a BLS12-381 implemented by EIP-2537 a short Weierstrass curve equation y^2 = x^3 + A * x + B has a property that a product AB = 0, so to implement a mapping function two step algorithms is performed:

Below we describe generic algorithms for mapping and isogeny application, and later on give concrete parameters for the algorithms

Helper function to clear a cofactor

Later on we use a helper function to clear a cofactor of the curve point. It's implemented as

    clear_cofactor(P) := h_eff * P

where values of h_eff are given below in parameters sections

Simplified SWU for AB != 0

The function map_to_curve_simple_swu(u) implements a simplification of the Shallue-van de Woestijne-Ulas mapping described by Brier et al., which they call the "simplified SWU" map. Wahby and Boneh generalize and optimize this mapping.

Preconditions: A Weierstrass curve y^2 = g(x) x^3 + A * x + B where A != 0 and B != 0.

Constants:

Sign of y: Inputs u and -u give the same x-coordinate. Thus, we set sgn0(y) == sgn0(u).

Exceptions: The exceptional cases are values of u such that Z^2 * u^4 + Z * u^2 == 0. This includes u == 0, and may include other values depending on Z. Implementations must detect this case and set x1 = B / (Z * A), which guarantees that g(x1) is square by the condition on Z given above.

Operations:

1. tv1 = inv0(Z^2 * u^4 + Z * u^2)
2.  x1 = (-B / A) * (1 + tv1)
3.  If tv1 == 0, set x1 = B / (Z * A)
4. gx1 = x1^3 + A * x1 + B
5.  x2 = Z * u^2 * x1
6. gx2 = x2^3 + A * x2 + B
7.  If is_square(gx1), set x = x1 and y = sqrt(gx1)
8.  Else set x = x2 and y = sqrt(gx2)
9.  If sgn0(u) != sgn0(y), set y = -y
10. return (x, y)

Simplified SWU for AB == 0

Wahby and Boneh show how to adapt the simplified SWU mapping to Weierstrass curves having A == 0 or B == 0, which the mapping of simple SWU does not support.

This method requires finding another elliptic curve E' given by the equation

    y'^2 = g'(x') = x'^3 + A' * x' + B'

that is isogenous to E and has A' != 0 and B' != 0. This isogeny defines a map iso_map(x', y') given by a pair of rational functions. iso_map takes as input a point on E' and produces as output a point on E.

Once E' and iso_map are identified, this mapping works as follows: on input u, first apply the simplified SWU mapping to get a point on E', then apply the isogeny map to that point to get a point on E.

Note that iso_map is a group homomorphism, meaning that point addition commutes with iso_map. Thus, when using this mapping in the hash_to_curve construction of {{roadmap}}, one can effect a small optimization by first mapping u0 and u1 to E', adding the resulting points on E', and then applying iso_map to the sum. This gives the same result while requiring only one evaluation of iso_map.

Preconditions: An elliptic curve E' with A' != 0 and B' != 0 that is isogenous to the target curve E with isogeny map iso_map from E' to E.

So the full mapping algorithm looks as:

Sign of y: for this map, the sign is determined by map_to_curve_simple_swu. No further sign adjustments are necessary.

Exceptions: map_to_curve_simple_swu handles its exceptional cases. Exceptional cases of iso_map are inputs that cause the denominator of either rational function to evaluate to zero; such cases MUST return the identity point on E.

Full algorithm restated

1. (x', y') = map_to_curve_simple_swu(u)    # (x', y') is on E'
2.   (x, y) = iso_map(x', y')               # (x, y) is on E
3. (x, y) = clear_cofactor((x, y))          # clears cofactor for point (x, y) on E
4. return (x, y)

Parameters for EIP-2537

Fp-to-G1 mapping

The 11-isogeny map from (x', y') on E' to (x, y) on E is given by the following rational functions:

The constants used to compute x_num are as follows:

The constants used to compute x_den are as follows:

The constants used to compute y_num are as follows:

The constants used to compute y_den are as follows:

Fp2-to-G2 mapping

Symbol I means a non-residue used to make an extension field Fp2

The 3-isogeny map from (x', y') on E' to (x, y) on E is given by the following rational functions:

The constants used to compute x_num are as follows:

The constants used to compute x_den are as follows:

The constants used to compute y_num are as follows:

The constants used to compute y_den are as follows: