Re: [CFRG] Closure (was Re: Small subgroup question for draft-irtf-cfrg-hash-to-curve)

[Mike Hamburg <[e-mail]>]

> On Apr 13, 2021, at 5:50 AM, Hao, Feng <Feng.Hao=[e-mail]> wrote:
> 
> Therefore, precluding low-order points from map-to-curve by design is still a relevant research question. Can it be possibly done? If so, can it be done efficiently? I am curious to learn.

I suggested a way to do this earlier in the thread, which works for typical Edwards curves like Ed25519 and Ed448: just precompute the least (lexicographically or whatever) point Q such that map_to_curve(anything) + Q doesn’t hit any low-order points, and call that function map_to_large_order_point_on_curve or whatever.  Then clear the cofactor if you want, to get to the large-prime-order subgroup.  The point Q is easy to compute if the small subgroup is small enough (e.g. at most 24 elements), because SWU and Elligator are easy to invert.  For Ristretto and Decaf, I believe the byte serializations of these points are

000000000000000000000000000000000000000000000000000000000000097e

and

0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002

respectively.  You could alternatively make Q the least possible multiple of G, which would be (if I’m calculating correctly) 16*G or 47*G, respectively.  The least positive and least negative values are the same, because Q is in image of Elligator iff -Q is; this also means that you can’t take Q to be map_to_curve(the least possible input).

If you want a uniform map to the large-prime-order subgroup, you can scalarmul by (1 + (second input % (p-1))).  That’s expensive, but in many cases you’re going to scalarmul the output of map-to-curve anyway, so you can just combine the two scalars.

Obviously this calculation is slightly more annoying than a single map_to_curve, but it’s entirely feasible.

Cheers,
— Mike