Re: [Cfrg] I-D Action: draft-irtf-cfrg-hash-to-curve-00.txt

[Christopher Wood <[e-mail]>]

Hi Sam,

Many thanks for your feedback! Please see inline below for comments.

> On Mar 29, 2018, at 12:07 PM, Sam Scott <[e-mail]> wrote:
> 
> First of all, this thread shows exactly why a good standard would be useful, the current terminology is a bit confusing. So thank you for the effort in putting this together, and I hope the following can be useful.
> 
> In my opinion, the distinction should be made as follows:
> 
> Point -> bitstring is serialisation. Includes concepts such as compression of points, cofactor eliminating (e.g. Decaf) and indifferentiability (e.g. Elligator). Interestingly the latter of these doesn't necessarily apply to all curve points. Serialisation is generally only used for transport, or producing a canonical version of a point for further processing (input to hash function or kdf) and should be fast.
> 
> Bitstring -> points is encoding. Main use case is for turning plaintext messages into curve points. Potentially needs to be constant time if input is private, e.g. a message, password or key. Decoding needed when input is a message, in encryption for example. 
> 
Thanks for the suggestion. I am not opposed to this terminology. It seems to better capture the intent of each algorithm. 
> Of course, in some cases deserialisation is equivalent to encoding, or decoding to serialisation.
> 
> It would be interesting to outline what the current encoding examples give you over, for example, scalar multiplication (x -> xG for some generator G). Or when using Montgomery x-only scalar multiplication, you can basically skip encoding all together (if your application permits using the twisted curve as well).
> 
Indeed. Prior to its initial publication, we discussed this topic, though we never got around to including it. I will try include it in the next revision.
> So where does hashing come into it? Well it depends on the purpose. Arguably for "hashing onto the curve" people usually require a random oracle onto the curve. Which is then instantiated via a hash function modelled as a ROM, plus an encoding. But for this to actually be a RO, the encoding function better be full domain (otherwise need additional proof to show this is okay). Brier et al's paper [1] makes a succinct point on this in 5.2, and is overall a great read on the topic. 
> 
Good point. The scenarios and use cases in which RO properties from the “hashing” operation are not well articulated. Also, as currently written, it seems we (implicitly) assume each variant is a hash function. This is clearly an error. For example, Elligator2 is both invertible and not a FDH. (Though, following your suggestion below, we can make it one.)
> Given this, I would argue that this document in its current format is misleading, verging on dangerous... One might infer that any encoding function is okay, and end up using x -> h(x)G. Which will probably break most applications.
> Some areas which I think need to be covered:
> 
>  - A description of different forms of encoding, and properties associated with them. Including the additional encoding methods I mentioned above. If this is deemed too much or out of scope, I think it should at least refer to these as unsuitable encoding methods for constructing a RO.
> 
I believe this is in scope. I filed: https://github.com/chris-wood/draft-sullivan-cfrg-hash-to-curve/issues/17
>  - What properties can be achieved by hashing to the curve. As far as I'm aware most applications need a random oracle? I would be interested to know about requirements for other applications.
> 
Likewise! If there are applications that do not need a RO, I would be inclined to include them with accompanying discussion text.
>  - If you want to construct a RO into the curve, then an explanation that this either requires: (a) using a full domain hash as in [1], or (b) a proof showing that a random oracle over the subset of points is okay, in which case you have Icart's method, SWU or Elligator. 
> For example, (a) can be constructed using Elligator (as f) in the form of f(h(x)) + h(x)*G, which is reasonably performant, and close to just using Elligator when using precomputation for the h(x)*G part.
> 
This is cute. I’m not sure if spelling out such techniques are in scope or not. We could, for example, simply state that a FDH is required. I’d be curious to hear what others think. 
> As it turns out, we used pretty much all of the above for our updatable encryption scheme [2]. We needed message encoding/decoding for the plaintext, a RO from a counter, and de/serialisation for storage/transport. I think I got pretty much every single part wrong in every possible combination before arriving at the above.
> 
I was not aware of this paper — thanks for sharing!
> This ended up being a much longer email than I intended! Hope it helps.
> 
It was very helpful. Thanks again for taking the time to share your thoughts. I will do my best to integrate them into the draft.

Best,
Chris