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

["Hao, Feng" <[e-mail]>]

Hi Armando,

Thanks for the good questions.

I think for all practical purposes, clear-cofactor is good enough, and should be safe to use.

There is a theoretical probability of failure, but that’s really negligible. If you treat the mapping function as a random oracle, then the probability is 1/q where q is the size for the prime order group. Of course, a random oracle is just a theoretical abstraction. In the real construction, depending on what encoding/mapping methods are used, the function only covers a fraction of points on the curve. Hence, you may end up with an upper bound probability h/q where h is the size of the small subgroup. Still even with h considered in the worst case and for the curve settings considered in the draft, the probability remains really negligible and there is nothing to worry about in practice.

On the other hand, is it still worthwhile to consider a map-to-curve algorithm that always returns points of a given prime order?

I think so, for the following two reasons.

>From a theoretical point, that will match exactly the assumption made in some PAKE use cases. What is precisely needed from hash-to-curve is a generator point, which by definition is a point that has a given prime order (i.e., a non-identity point in a prime-order subgroup).

>From the user’s perspective, there is also a perceived benefit to reduce a negligible probability to zero if you can. Given two systems which are basically the same except that A has a theoretical failure probability 1/2^{256}, while B has 0 under the same condition. Which system to choose? A rational mind will say it doesn’t really matter. It’s perfectly fine to use System A (indeed that’s very correct). However, if you ask ordinary users, given that there is also a choice of B, I bet many of them will opt for B without the slightest hesitation.

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.

Cheers,
Feng

From: Armando Faz <[e-mail]>
Date: Monday, 12 April 2021 at 23:51
To: Hao, Feng <[e-mail]>
Cc: IRTF CFRG <[e-mail]>
Subject: Re: [CFRG] Closure (was Re: Small subgroup question for draft-irtf-cfrg-hash-to-curve)
> "Hao, Feng" <[e-mail]>
> I asked for clarification on whether the small subgroup points can be removed from map-to-curve by design. The replies from the hash-to-curve authors indicated no: because 1) too much hassle; 2) not worth it for the negligible probability. I think the rationale is clear.

There were several comments about why clear-cofactor helps to map
low-order points to the identity, and why this might or might not be
an issue in higher protocols.
However, few comments addressed the problem of devising a map-to-curve
algorithm that always returns points of a given order. I consider this
is still an open problem in general, (which is another reason why the
draft takes a simpler  approach, namely clear-cofactor).
Also note that a similar function will be useful for CSIDH, which
needs to sample points in a desired torsion group. If I am not wrong,
CSIDH also uses the clear-cofactor technique to achieve this task.
Happy to hear more comments about this specific problem, (which is a
different  discussion from the implications of not having such a map).

--
Armando Faz
Cloudflare Inc.