Re: [CFRG] Comment on draft-irtf-cfrg-hash-to-curve-10

[Loup Vaillant-David <[e-mail]>]

Hello,


> But as I said in my prior email, it seems like refactoring Appx. G to
> use divsqrt and adding a few implementations of that function for the
> relevant cases (3 mod 4, 5 mod 8, 9 mod 16, and general, perhaps?) is
> a nice way of cleaning things up. And it seems like the same refactor
> applied to SvdW and Elligator in Appx. G would help, too.

It would help quite a bit.

When I implemented Elligator 2 last year, I tried to read earlier
versions of this draft, and failed. I ended up using the original
instead.

Problem is, the original paper's simple equations involve *two*
exponentiations, while an optimised explicit formula only needs one.
That's a 2x speed difference. But the complexity section G.3.1 is such
that we're easily tempted to just give up and suffer a slower mapping.

For instance: Libsodium. While usually optimised to the brim, it chose
the simpler, slower formula. (It was first added in 2017, before this
draft even existed, but subsequent updates didn't address this.)

Compare the current section G.3.1 with an explicit formula that uses
invsqrt (Taken from my Python code, first gifted by Andrew Moon):

  ufactor = -non_square * sqrtm1
  vfactor = sqrt(ufactor)

  def fast_map_to_curve(r):
    t1 = r**2
    t1 = t1 * non_square
    u  = t1 + fe(1)
    t2 = u**2
    t3 = A**2
    t3 = t3 * t1
    t3 = t3 - t2
    t3 = t3 * A
    t1 = t2 * u
    t1, is_square = invsqrt(t3 * t1)
    u  = r**2
    u  = u * ufactor
    v  = r * vfactor
    if is_square: u = fe(1)
    if is_square: v = fe(1)
    v  = v * t3
    v  = v * t1
    t1 = t1**2
    u  = u * -A
    u  = u * t3
    u  = u * t2
    u  = u * t1
    if is_square != v.is_negative():
        v = -v
    return (u, v)

Quite a bit shorter, and needs fewer variables.

Personally, I'm looking forward to that refactoring. It has the
potential to make implementers' lives significantly easier.

Loup.