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

From: Armando Faz <[email-masked]>
Date: Mon, 12 Apr 2021 15:50:55 -0700

> "Hao, Feng" <[email-masked]>
> 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.

---

From: "Hao, Feng" <[email-masked]>
Date: Tue, 13 Apr 2021 08:50:18 +0000

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 <[email-masked]>
Date: Monday, 12 April 2021 at 23:51
To: Hao, Feng <[email-masked]>
Cc: IRTF CFRG <[email-masked]>
Subject: Re: [CFRG] Closure (was Re: Small subgroup question for draft-irtf-cfrg-hash-to-curve)

--
Armando Faz
Cloudflare Inc.

---

From: Mike Hamburg <[email-masked]>
Date: Tue, 13 Apr 2021 10:05:55 -0300

> On Apr 13, 2021, at 5:50 AM, Hao, Feng <Feng.Hao=[email-masked]> wrote:
> 

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

---

From: Loup Vaillant-David <[email-masked]>
Date: Wed, 14 Apr 2021 16:10:05 +0200

On Mon, 2021-04-12 at 15:50 -0700, Armando Faz wrote:
> > 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.
> 
> 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).

Hi,

If we separate the map/hash to curve step from the higher-level
protocol that uses it, it is generally simpler to clear the cofactor
before the high-level protocol sees anything. (This ease of use is why
I wouldn't dare object to clearing the cofactor in the context of the
hash-to-curve RFC.)

On the other hand, there might be a small performance benefits in *not*
clearing the cofactor. Curve25519's cofactor for instance is 8 (2^3),
and requires 3 point doublings to clear. Depending on the context, this
could be considered a significant overhead, or a negligible one:

- Elligator2 based Map to Curve requires a single exponentiation.
  Adding 3 point doubling on top of that will likely add about 10%
  of overhead.
- If we're performing a scalar multiplication after clearing the
  cofactor (OPRF does), then the overhead drops down to 1% or so.

(The overhead for Curve448 are even lower: the curve is bigger, and
 requires only 2 points doubling to clear the cofactor.)

Negligible or no, the overhead is measurable, so there's the temptation
to skip it. And in many cases, we can: it turns out that regular X25519
(and X448) scalar multiplications ignore the cofactor to begin with.
They do this by clearing the 3 (or 2) least significant bit of the
scalar, thus making sure that the scalar is a multiple of the cofactor.

To sum it up, if cofactor clearing happens as a natural side effect of
the higher level protocol (such as scalar multiplication, where the
scalar is tweaked to clear the cofactor), then we can save a few cycles
and omit it. On the other hand, you really have to know what you're
doing.

---

Another reason not to clear the cofactor is when you also want to
provide the reverse map. Reverse map facilitate steganography and other
forms of meta-data hiding: if you map a random point on the curve, the
representative is indistinguishable from random. So when you send it
over the network, it looks random, without the statistical biases
associated with raw public keys.

The problem with the reverse mapping is that we need to pick a random
point over the *whole* curve, not just the prime order group (let's
ignore the fact that half of the points do not map at all). If we
restricted ourselves to the prime order group, the attacker could just
map it back and notice that by some amazing "coincidence", they always
get a point on the prime order group.

So the representative we send over the network for attackers to
eavesdrop must map to a point whose cofactor is *not* cleared. To do
that, it makes sense for a low-level cryptographic library to expose an
interface that does not clear the cofactors. One can then implement
Hash-To-Curve (which does clear the cofactor) on top of it.

---

Speaking of which, I found rather unfortunate incompatibilities between
the RFC's map-to-point step, and existing Elligator2 implementations
over Curve25519 I was referring to when I added Elligator2 to
Monocypher last year. I believe Mike Hamburg asked about them then.

As one can guess, I'm rather found of the reverse map, and what it
enables. In the specific case of Curve25519, mapping a point to a
representative will yield a 255-bit number. Note however that
representatives and their opposite (modulo 2^255-19) map to the same
curve point, so I always chose the positive representative. (The one
between 0 and p-2. I could instead discriminate with parity instead
like Ed25519 does, but the Elligator2 paper suggested otherwise).

The result is a 254-bit number. I can then just pad the two other bits
with random noise, and the decoding step will have to ignore those
bits. If I recall correctly, the Hash-To-Curve RFC however does not
ignore those two bit:

- Bit 256 is used to flip the sign of the mapped curve point, instead
  of just being ignored.
- The representative is encoded in 255 bits instead of 254 bits, which
  are enough for positive representatives.

Both of these incompatibilities are fairly easily worked around: we
don't care about the sign of the point to begin with if its purpose is
to use it in X-only ladders (and in many cases, it is), and
representatives are easily negated if need be. I also understand why
representatives use 255 bits: that's how existing decoding functions
work.

What I don't get is the rationale behind using bit 256 to flip the sign
of the curve point. It doesn't do anything that I can tell: if a point
can be mapped, then so can its opposite, so we won't even cover more
points that way. Unless perhaps as a way of highlighting implementation
errors?

---

Anyway, my thoughts.
Loup.