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

From: [email-masked]
Date: Fri, 23 Mar 2018 03:13:10 -0700

A New Internet-Draft is available from the on-line Internet-Drafts directories.
This draft is a work item of the Crypto Forum RG of the IRTF.

        Title           : Hashing to Elliptic Curves
        Authors         : Nick Sullivan
                          Christopher A. Wood
	Filename        : draft-irtf-cfrg-hash-to-curve-00.txt
	Pages           : 18
	Date            : 2018-03-23

Abstract:
   This document specifies a number of algorithms that may be used to
   hash arbitrary strings to Elliptic Curves.

The IETF datatracker status page for this draft is:
https://datatracker.ietf.org/doc/draft-irtf-cfrg-hash-to-curve/

There are also htmlized versions available at:
https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-00
https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve-00

Please note that it may take a couple of minutes from the time of submission
until the htmlized version and diff are available at tools.ietf.org.

Internet-Drafts are also available by anonymous FTP at:
ftp://ftp.ietf.org/internet-drafts/

---

From: Dan Brown <[email-masked]>
Date: Fri, 23 Mar 2018 14:20:15 +0000

1) I never understood why this gets called "hashing".  It conflicts with the
2 usual meanings a hash: (a) creating a digest of a long message, (b) being
one-way (some application actually require the reverse operation, i.e.
"unhashing"?).  Can we devise a better term?

I suggest re-using the verb-pair "encoding/decoding", but flipping the input
nouns and output nouns.   So, traditional ECC encodes points to a byte
string, and decodes a byte string to a point.  By contrasting, this
"hashing" method does the opposite: it encodes byte string to a point, and
decodes a point as byte string.  I guess "embed/extract" could be used if
encode/decode is deems too overloaded.

I do not recall seeing verb "hash" on every paper on this topic, so (just)
maybe others might agree with me that some alternative is warranted.

2) For what little it's worth, (I think that) none of the algorithms
specified in this I-D work for 2y^2=x^3+x/GF(8^91+5), because p=1 mod 3, p=1
mod 4, and j=1728.  

For this special curve, I sketched a modification of Elligator 2, which I
called Elligator i, in Sections 5.2 (math) and C.10 (pseudocode) of
https://datatracker.ietf.org/doc/draft-brown-ec-2y2-x3-x-mod-8-to-91-plus-5/
though I am not sure which set of curves it would generalize to.  (I admit I
don't recall trying Icart or SWU on this special curve: maybe some
variations of these would have worked just as well.)

-----Original Message-----
From: Cfrg [mailto:[email-masked]] On Behalf Of
[email-masked]
Sent: Friday, March 23, 2018 6:13 AM
To: [email-masked]
Cc: [email-masked]
Subject: [Cfrg] I-D Action: draft-irtf-cfrg-hash-to-curve-00.txt

A New Internet-Draft is available from the on-line Internet-Drafts
directories.
This draft is a work item of the Crypto Forum RG of the IRTF.

Abstract:

_______________________________________________
Cfrg mailing list
[email-masked]
https://www.irtf.org/mailman/listinfo/cfrg

---

From: Dan Brown <[email-masked]>
Date: Fri, 23 Mar 2018 14:20:15 +0000

-----Original Message-----

Abstract:

---

From: Christopher Wood <[email-masked]>
Date: Mon, 26 Mar 2018 13:53:24 +0000

Hi Dan,

Please see inline below for comments.

> maybe others might agree with me that some alternative is warranted.

Fair point. While we are overloading the use of "hash" in this context, it
does seem appropriate for certain algorithms. If each algorithm were
invertible then I would be more inclined to go with terms such as
"encoding" and "decoding." Does anyone else have a strong preference?

> variations of these would have worked just as well.)

Thank you for pointing this out. I'll take a look at your modification. I
filed:
https://github.com/chris-wood/draft-sullivan-cfrg-hash-to-curve/issues/15

Best,
Chris

---

From: Christopher Wood <[email-masked]>
Date: Mon, 26 Mar 2018 13:53:24 +0000

Hi Dan,

Best,
Chris

---

From: Sam Scott <[email-masked]>
Date: Thu, 29 Mar 2018 15:07:24 -0400

Hi Chris,

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.

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

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.

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.

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

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

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.

This ended up being a much longer email than I intended! Hope it helps.

Cheers,

Sam

[1] https://eprint.iacr.org/2009/340

[2] https://eprint.iacr.org/2017/527

On 26/03/18 09:53, Christopher Wood wrote:
> On Fri, Mar 23, 2018 at 7:20 AM Dan Brown <[email-masked] 
> <mailto:[email-masked]>> wrote:
>
> Fair point. While we are overloading the use of "hash" in this 
> context, it does seem appropriate for certain algorithms. If each 
> algorithm were invertible then I would be more inclined to go with 
> terms such as "encoding" and "decoding." Does anyone else have a 
> strong preference?
>
>
>     https://datatracker.ietf..org/doc/draft-brown-ec-2y2-x3-x-mod-8-to-91-plus-5/
>     <https://datatracker.ietf.org/doc/draft-brown-ec-2y2-x3-x-mod-8-to-91-plus-5/>
> Thank you for pointing this out. I'll take a look at your 
> modification. I filed: