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

From: Daira Hopwood <[email-masked]>
Date: Mon, 3 May 2021 07:08:45 +0100

On 23/04/2021 20:30, Riad S. Wahby wrote:
> Hello Daira,
> 
> Thanks for clarifying your feedback.
> 
> I remain concerned about mixing implementation detail with high-level
> description. Here I am referring to using divsqrt in place of natural
> field arithmetic operations (sqrt, inversion, etc.) in the body text.
> Describing the algorithm independent of the implementation details is
> a way of specifying the mathematical properties of the algorithm, and
> having this specification explicit in the document has value, from my
> perspective.

The description of divsqrt (or sqrt_ratio) I gave *does* specify the
high-level mathematical properties of the algorithm, and keeps that
separate from how to implement it.

> 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.

I think that if you explain the general case then the specializations to
{3 mod 4, 5 mod 8, 9 mod 16} are immediate and simple.

> And it seems like the same refactor
> applied to SvdW and Elligator in Appx. G would help, too.
> 
> This isn't something I can do in the near term, but I'm very happy to
> spend time on this once I've got some! I'm hopeful that's about three
> weeks from now, but I've been called an optimist before.
> 
> Thanks again for the feedback and best regards,

You're welcome.

-- 
Daira Hopwood

---

From: Daira Hopwood <[email-masked]>
Date: Mon, 3 May 2021 07:23:06 +0100

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

---

From: Rene Struik <[email-masked]>
Date: Mon, 3 May 2021 09:29:22 -0400

Two sentences are all that is needed to describe taking a square root 
and any number of inversions ("Montgomery's trick"), in an easy to read 
format by humans.

On 2021-05-03 2:23 a.m., Daira Hopwood wrote:
>> 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.
>>
>> 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.
>
>> I think this would be easier to read than any "div" verbiage and 
>> avoids having to deal with divisions by zero.
>

-- 
email: [email-masked] | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 287-3867