Re: [Cfrg] patent situation regarding hash2curve as used in some PAKE nominations

["Riad S. Wahby" <[e-mail]>]

Hi Bjorn,

Thank you for the detailed analysis. One small comment:

Björn Haase <[e-mail]> wrote:
> Also for p != 3 mod 4  (e.g. P-384) when using generic simplified
> SWU we have differences between the patent and draft 04, but it’s
> still somewhat similar. We probably might be better off with avoid
> simplified SWU for P-384.

I might be missing something, but I believe P-384 is over GF(p) for
    p = 2**384-2**128-2**96+2**32-1
which is congruent to 3 mod 4, so the same method should work.

For curves where p = 5 mod 8, a similar process works:

- Compute x1 = X1(t), x2 = X2(t), and g(x1) in the usual way
- Compute tmp = g(x1) ** ((p + 3) / 8) and tmp2 = tmp * sqrt(-1)
- If tmp ** 2 == g(x1), return (x1, tmp)
- If tmp2 ** 2 == g(x1), return (x1, tmp2)
- Let tmp = tmp * t ** 3 and tmp2 = tmp * sqrt(-1)
- If tmp ** 2 == g(x2), return (x2, tmp)
- Else return (x2, tmp2)

One can keep generalizing for p = 9 mod 16, 17 mod 32, etc. Eventually
it gets unwieldy, but most of the time one chooses a prime where p - 1
is divisible by only a small power of 2 to avoid this (and there exist
methods that handle ugly cases: http://cr.yp.to/papers.html#sqroot).

Regards,

-=rsw