Subject: Re: [Cfrg] Comments on draft-irtf-cfrg-hash-to-curve

From: Dan Brown <[email-masked]>
Date: Thu, 30 Aug 2018 13:36:55 +0000

Hi all,
I think the goal of this I-D has merit.
I skimmed it today, just to see what these comments were about. I have some very minor comments.

n=qh+r should be n=qh, since the remainder r=0.

I vaguely recall that not all supersingular curves have n=p^k+1, so there is not always the described map.

I agree with with Marek's comment. The curve size n being equal to 2^L does not depend on p. Usually, n=2^L is avoided, since q=2 is too small (and Pohlig--Hellman can be used to solve ECDLP. )

It was a little unclear to me what HashToBase meant. It is applied in SWU with p^k, but defined with only p, and the rounding is missing (unless defined elsewhere, etc.).
Similarly, the note about uniformity of HashToBase's output versus bias in bits of p is strange: the more biased p is towards 2^L, the less biased the output of HashToBase, ... 

I haven't made time yet to do a more thorough review that it deserves.
‎Best regards, 
Dan

From: Marek Jankowski
Sent: Thursday, August 30, 2018 7:46 AM
To: [email-masked]
Cc: [email-masked]
Subject: Re: [Cfrg] Comments on draft-irtf-cfrg-hash-to-curve

Hello Chris,

With regard to the tables in section 3 - I felt that I had to read them again to understand how they were supposed to be used. I think that a usage example will resolve the issue.

About section 2.1.1 - I meant that the paragraph deals with the fact that the size of the curve is not usually a power of two, so I don't think that there is a nee to restrict the discussion to non-binary curves (as the first sentence says), as this fact remains true in that case as well.

Thanks,
Marek

On Mon, Aug 27, 2018 at 4:21 AM Christopher Wood <[email-masked]> wrote:
Hi Marek,

Apologies for the delayed response. Please see inline below for a response.

On Mon, Jul 30, 2018 at 6:59 AM Marek Jankowski <[email-masked]> wrote:

In Section 2, page 2, the name Weierstrauss should be spelled Weierstrass.

Good catch — thanks!

Quite importantly, and also in Section 2, for a group of size n to have a subgroup of size q, the relation n = qh should hold with no remainder.

Indeed. We should specify that r = 0 here.

In Section 2..1.1, is E usually defined over GF(p^k) with p > 2? Koblitz has constructed binary elliptic curves (N. Koblitz, "CM-curves with good cryptographic properties", Advances in Cryptology - CRYPTO '91, pp. 279-287). In any case, it appears that the question of whether or not p = 2 is irrelevant to the current paragraph, as even in such a case, the size of the curve would not necessarily be 2^k.

We were not considering curves over fields with characteristic 2. I’m sure we could reconsider if folks feel it is important. 

In section 3, the relation between the two tables was not very clear to me on first reading. Perhaps the paragraph stating "To find the suitable algorithm..." should be clarified?

Can you please elaborate on what is unclear? This is arguably one of the more important parts of the document, so we want to be sure it is understandable.

In section 5.2.1, in the description of the method Icart at the top of page 7, why was the variable v not assigned like the rest of the variables?

No specific reason. I will update this to make it match the others.

In sections 5.2.2 and 5.2.3, because the square root of an element in GF(p^k) is not unique (unless p = 2), it would probably be better to require the use of a deterministic square root algorithm.

Valid point. We will consider including this change.

Best,
Chris