Expand description
Follows approach of SvdW06 to construct a “near injection” from a field into an elliptic curve defined over that field. WB19 is also a useful reference that details several constructions which are more appropriate in other contexts.
Fix an elliptic curve E given by y^2 = x^3 + ax + b over a field “F” Let f(x) = x^3 + ax + b.
Define the variety V to be (x1, x2, x3, x4) : f(x1) f(x2) f(x3) = x4^2.
By a not-too-hard we have a map V -> E. Thus, a map of type F -> V yields a
map of type F -> E by composing.
Our goal is to construct such a map of type F -> V. The paper SvdW06 constructs
a family of such maps, defined by a collection of values which we’ll term params.
OCaml implementation https://github.com/o1-labs/snarky/blob/2e9013159ad0d1df0af681735b89518befc4be11/group_map/group_map.ml#L4 SvdW06: Shallue and van de Woestijne, “Construction of rational points on elliptic curves over finite fields.” Proc. ANTS 2006. https://works.bepress.com/andrew_shallue/1/download/ WB19: Riad S. Wahby and Dan Boneh, Fast and simple constant-time hashing to the BLS12-381 elliptic curve. https://eprint.iacr.org/2019/403
Structs
Traits
Functions
- returns the y-coordinate if x is a valid point on the curve, otherwise None TODO: what about sign?