Re: [CFRG] (suggested language re mixing square roots and inversions) Re: Comment on draft-irtf-cfrg-hash-to-curve-10

[Daira Hopwood <[e-mail]>]

On 23/04/2021 21:47, Rene Struik wrote:
> Hi Riad:
> 
> Text along the following lines would avoid implementation detail, but 
> would illustrate how one could "mix" inversions and square roots:
> 
> The inverses of two nonzero elements y1 and y2 of GF(q) can be computed 
> by first computing the inverse z of y1*y2 and by subsequently computing 
> y2*z=:1/y1 and y1*z=:1/y2.
> 
> This method can be used to compute the inverse and a square root, 
> respectively, of two nonzero elements x and y of GF(q) (where y is a 
> square in GF(q)) by first computing a square root z of 1/(y*x^2) and by 
> subsequently computing a square root of y as x*y*z and the inverse of x 
> as x*y*z^2.

But computing the inverse and the square root in parallel isn't what
we're doing. The combined inverse-and-sqrt method we're referring to
here isn't rocket science, it will be familiar to anyone who has
implemented Ed25519.

> I think this would be easier to read than any "div" verbiage and avoids 
> having to deal with divisions by zero.

Just to be clear, there are no divisions by zero in the specification
I gave in my previous post:

  Let h be some fixed nonsquare in Fq. Define sqrt_ratio for
  u ∊ Fq and v ∊ Fq* as:

    sqrt_ratio(u, v) = (true, sqrt(u/v)),    if u/v is square in Fq
                     = (false, sqrt(h*u/v)), otherwise.

Notice that sqrt_ratio is not defined for v = 0, and it is easily proven
that it is never applied with v = 0.

-- 
Daira Hopwood