Subject: Re: [Cfrg] hash-to-curve updates and suite reduction

From: Mike Hamburg <[email-masked]>
Date: Fri, 1 May 2020 16:52:36 -0700

Hello Christopher,

Sorry to be so late in the game on this, but I have a concern about Elligator 2 as defined in hash-to-curve.

One of the nice properties of Elligator 2 is that it’s an injective map on [0..(p-1)/2], which is useful for canonically inverting the map.  However, the draft version is not injective on this domain.  Wouldn’t it be better to choose sgn(t) according to is_square(gx1) instead of according to sgn(u)?  That would also make it match the paper, except for the different definitions of sgn().

Cheers,
— Mike

> On Apr 28, 2020, at 5:39 AM, Christopher Wood <[email-masked]> wrote:
> 
> Hi folks,
> 
> The hash-to-curve authors spun draft-irtf-cfrg-hash-to-curve-07 recently [1]. Some of the major changes focus on how we handle DSTs for domain separation in hash_to_field. If you have some spare cycles, please have a look and provide feedback! 
> 
> In addition to this change, I'd also like to call attention to the section on suites [2]. We've heard criticism that there are currently too many suites defined, which can complicate implementations and protocols [3]. The list should likely be reduced. In particular, the document should probably specify at most one recommended suite covering both the RO and NU cases for each curve. (Alternatives could be defined elsewhere, i.e., in separate documents if needed.) 
> 
> In this interest of document clarity and ease of use by the community, we'd like to know what folks think about this proposal. Some questions to consider are:
> 
> - What should be the preferred mapping function for each curve? For example, P-256 specifies P256_XMD:SHA-256_SSWU_RO_  and P256_XMD:SHA-256_SVDW_RO_, which use the Simplified SWU (SSWU) and Shallue-van de Woestijne maps, respectively. Considering libraries that might implement the Shallue-van de Woestijne for more than one curve, should we err towards code re-use or stick with the less-general SSWU map?
> - Should each curve have one suite for the RO case and another for the NU case? Doing so assumes implementers know when and how to choose between these two variants. This is something the document mostly skips over, saying simply, "When the required encoding is not clear, applications SHOULD use a random oracle."
> 
> Thanks in advance for your time and consideration.
> 
> Best,
> Chris
> 
> [1] https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-07
> [2] https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-07#section-8
> [3] https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve/issues/235
> 
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

---

From: "Christopher Wood" <[email-masked]>
Date: Thu, 07 May 2020 08:36:15 -0700

Hi Mike,

Apologies for the delay, and thanks for raising this point. Please see inline below.

On Fri, May 1, 2020, at 4:52 PM, Mike Hamburg wrote:
> One of the nice properties of Elligator 2 is that it’s an injective map 
> on [0..(p-1)/2], which is useful for canonically inverting the map.  
> However, the draft version is not injective on this domain.  Wouldn’t 
> it be better to choose sgn(t) according to is_square(gx1) instead of 
> according to sgn(u)?  That would also make it match the paper, except 
> for the different definitions of sgn().

I agree that inverting the map can be quite useful for some applications. However, to the best of my recollection, we haven't heard requests for this injective property in the past. I don't have a particularly strong opinion on this point, so I'm curious to hear what others here think about this proposal. 

Best,
Chris