search

cfrg / draft-irtf-cfrg-hash-to-curve

Hashing to Elliptic Curves
Other
79 stars 27 forks source link

Composition of encoding + Ristretto/Decaf #43

Closed samscott89 closed 5 years ago

samscott89 commented 6 years ago

The Decaf approach

https://www.shiftleft.org/papers/decaf/

https://ristretto.group/

samscott89 commented 6 years ago

To be discussed: how to best handle this. Although these seem like "the right choices" for implementers choosing a curve, they aren't yet fully specified.

It would be ideal if we could (a) add them when well specified, and (b) target compatibility between the hashing approaches.

chris-wood commented 6 years ago

Based on the meeting, we will update the such that the curve->algorithm table maps curves->output group, where output group is one of (all)P-256, Ristretto (prime order subgroup of Curve25519), etc.

grittygrease commented 6 years ago

After a deeper dive into Ristretto, I no longer think this is necessary. If the output of h2c is an Edwards point, the algorithm can treat that as the representative element of the Ristretto group. From there they can use regular Edwards arithmetic and the Ristretto comparison function. When they need to serialize a point in the group, they can use the Ristretto encoding.

kwantam commented 5 years ago

See this comment re: Ristretto h2c

burdges commented 5 years ago

In fact, Ristretto has two possible implementations based on an Ed25519, depending upon the branch of the inverse square root used. These two choices result in compatible wire formats, so any purely Ristretto tests would pass no matter which you choose, but If two implementations employ different branches then they have different map between Edwards and Ristretto.

Ristretto authors have chosen never to expose the map, which prevents interoperation of protocols using Ed25519 and Ristretto keys, and prevents extending older Ed25519 protocols with Ristretto in particular, but their choice ensures Ristretto itself has less risk of non-compliant implementations.

kwantam commented 5 years ago

We're in the process of hashing out separation of responsibilities between h2c and the ristretto draft with the ristretto authors. The most likely path seems to be that there will not be a map specified in h2c for Ristretto. I am closing this; we will create a new issue to track action items once the path ahead is clear.

(#174 is tracking the discussion with Ristretto authors for now)

paulmillr commented 4 years ago

What's status of this? I don't see an alternative mentioned in current draft besides h_eff.

kwantam commented 4 years ago

The decision is that Ristretto will specify its own hash-to-group interface (FROM_UNIFORM_BYTES is what it's called in the current draft). I am not sure whether there will be a discussion of higher-level primitives, i.e., how to go from an arbitrary message to the input bytes. (In principle it's possible to do this using the expand_message variants in h2c, or with something like HKDF, a PRG, etc.)