Subject: Re: [Cfrg] I-D Action: draft-irtf-cfrg-hash-to-curve-04.txt

From: Björn Haase <[email-masked]>
Date: Mon, 22 Jul 2019 22:08:25 +0200

Dear Rene,

As a general rule for avoiding complexity as possible error source, I
would always only considera single mapping: the most efficient mapping
that is safely not covered by patents for a curve.

This means: For any Montgomery or Edwards curve, we probably should
concentrate on Elligator2 and not suggest use of SWU.

The second simple question IMO is P384. I'd not consider Icart's mapping
as long as the patents apply. I'd use plain SWU here.

Choice for P256 and other curves such as Brainpool with q = 3 mod 4
might be a bit more difficult. I'd suggest that we carry out a patent
review and stick to a simplified SWU version which avoids "-1" as
non-square if we have all consensus that this is not covered by known
patents. In case that there remains any un-certainty, I'd suggest to
stick to plain SWU as single mapping proposal for P256.

I believe that the possible benefit of the mapping for protocols such as
OPAQUE or AuCPace is so large that we should really avoid any doubt by
some people that the mapping might be covered by patents.

Yours,

Björn.

Am 22.07.2019 um 20:53 schrieb Rene Struik:
> Hi Armando:
>
> Thanks for your note. Curve448 is defined over a field GF(q) with q=3
> (mod 4), so it seems the simplified SWU mapping, as well as
> "Elligator2" (which can be viewed as a "repackaged" version of
> simplified SWU for Montgomery curves) both apply.
>
> Rene

---

From: "Riad S. Wahby" <[email-masked]>
Date: Mon, 22 Jul 2019 16:22:45 -0400

>as long as the patents apply. I'd use plain SWU here.

The generalized version of Simplified SWU given in -04 also applies to P384. So the question of which map to use for P384 is an instance of the broader question you asked, namely, are we comfortable with the IPR situation surrounding Simplified SWU? (I don't know! but maybe we'll understand more about this soon.)

So: if P256 ends up using Simplified SWU, P384 can as well.

(I certainly agree that we should be leery of the Icart IPR issues.)

-=rsw

---

From: Dan Harkins <[email-masked]>
Date: Mon, 22 Jul 2019 14:10:00 -0700

> (I certainly agree that we should be leery of the Icart IPR issues.)

   My original request to add back SWU was so I could have 1 method that 
worked
for the majority of curves that can be instantiated with a particular curve
and a particular hash function. I thought the trend from -03 to -04 was for
ciphersuite-style methods where if you're using curve foo you do one kind of
hash to curve with one particular hash algorith and if you're using 
curve bar
you use a different hash to curve method with a different hash 
algorithm. From
a programming point of view the latter is sub-optimal as I have to implement
a whole slew of hash to curve methods if I want to support a slew of curves
(where slew > 3).

   If the Simplified SWU of -04 also applies to all the curves that SWU 
does
then that complaint goes away. One issue with the Simplified SWU of -04, 
though,
is that I need the parameter Z for the curve so I either need to derive a Z
for every curve my code is going to support and store it (perhaps along with
the rest of the domain parameter set) or I derive it on the fly which sounds
like more looping which I want to avoid.

   So I still have a slight preference for the long-form SWU from -03 to
return in -05. Having ciphersuites for people who prefer that sort of thing
is fine but just don't make that the only way to go. Patents are, of course,
show stoppers.

   regards,

   Dan.

---

From: Björn Haase <[email-masked]>
Date: Mon, 22 Jul 2019 23:25:50 +0200

Dear Riad,

> So: if P256 ends up using Simplified SWU, P384 can as well.

Yes. Sorry for the confusion. I thought that the simplified SWU did not
work for P384. Anyway I'd clearly would like to advocate for a per-curve
mapping algorithm standard. This would any way apply to Edwards and
Montgomery curves. If we could uniformly use simplfied SWU on most
short-Weierstrass curves, I believe that this would be fine.

Yours,

Björn.

---

From: "Riad S. Wahby" <[email-masked]>
Date: Tue, 23 Jul 2019 13:25:30 -0700

Hello Dan,

Thanks (again!) for helping us make the draft better.

Dan Harkins wrote:
>   My original request to add back SWU was so I could have 1 method that worked
> hash to curve with one particular hash algorith and if you're using curve bar
> you use a different hash to curve method with a different hash algorithm. From

It's true that Suites in -04 is revised and somewhat expanded from
-03, but the intent of this section remains the same: offering an
easy way to choose an efficient hash function for common curves.
In other words, Suites are suggested, not required.

    (Aside: This is more pragmatic than anything else: even if Suites
    were "required," implementors would find reasons to ignore them.
    So the document may as well reflect the reality that some will
    treat suites as a suggestion---if only as a warning to others!)

If your preference is to specify a single method for all ciphersuites
in a higher-level protocol, that is totally reasonable. On the other
hand, since maps do not interoperate, if a standard specifies Elligator
for one curve and Simplified SWU for another, there's little choice
but to implement both. (Fortunately, those two maps cover the lion's
share of curves.)

    (Corollary to the prior "aside": It seems reasonable to assume that
    some standards will specify only the fastest maps for the curve(s)
    they select---so unfortunately it's not obvious how we'll avoid having
    to implement more than one hash-to-curve method in practice. As an
    extreme example, even if we said every curve MUST use the same method,
    one assumes that would be summarily---I daresay lustily---ignored!)

>   If the Simplified SWU of -04 also applies to all the curves that SWU does

I agree it would be nicer if we could dispense with Z. As a small
silver lining, Z is essentially always a signed 8-bit integer, so
storing it is cheap. (As you say, deriving on the fly seems ugly.)

One thing we probably should do is provide (pseudo)code that outputs
Z as specified for each map. I've taken a note on this.

By the way, one of the reasons for the addition of per-curve Zs is
that we're trying to systematically handle exceptional cases, and Z
is a knob that we can turn for most maps.

> is fine but just don't make that the only way to go. Patents are, of course,

Fully understood and agreed. We will clarify that Suites are (intended
as) conveniences, not straightjackets :)

As far as a one-size-fits-all method, probably the best choice is
Shallue and van de Woestijne (ANTS 06), which works for *any* curve
over large prime fields (including j-invariants 0 and 1728). The
current description of Shallue and van de Woestijne (Section 6.9.1
of -04) isn't fully general, but this is something we will address
in the near future (I have something mostly worked out on paper).

By the way, it turns out there's another pretty strong (in my opinion)
reason to avoid resurrecting plain SWU: its interface doesn't match
the other mapping functions'. In particular, it takes a pair of field
elements as input, rather than one like other maps. In principle
this is a minor thing, and indeed it's totally surmountable if
necessary. But it risks unclarity and forces expenditure of effort
on a map that offers few clear advantages when compared to Simplified
SWU or Shallue and van de Woestijne:

- compared to Simplified SWU (as described in -04), SWU supports the same
  curves but runs much more slowly; and

- compared to Shallue and van de Woestijne, SWU supports fewer curves
  and has essentially identical performance.

So I'm still holding out hope that we can avoid bringing Plain SWU back.
But---of course---we will do what's necessary to make the draft useful.

Thanks again (again!) for the feedback!

-=rsw