search

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

Hashing to Elliptic Curves
Other
79 stars 27 forks source link

add hash_to_field_divrem in appx #286

Closed kwantam closed 4 years ago

kwantam commented 4 years ago

This PR adds an alternative version of hash_to_field that is approriate for high-degree extensions of smallish characteristic. I'm posting this here so that we can refer to specifies in the discussion in #284. Not clear that we should actually apply this change, though.

closes #284

chris-wood commented 4 years ago

Just ACKing this for now. @kwantam, do we have a concrete use case for this? I wonder if we should ask folks on the list if they think it'd be helpful?

armfazh commented 4 years ago

A different approach to handle this case, it could be to define and/or recommend what are the properties needed by an alternative algorithm for hash_to_field, instead of proposing the full description of an alternate method, which, at the end of the day, might or might not be the best method.

This would be similar to the way we described a variant for expand_message (other than XMD and XOF).

For example, we didn't describe any method for hashing to GF(2^n), (of course, the draft restricts to large prime characateristic), however, this is the other extreme and we could give some recommendations -- Imagine someone interested in using a binary curve for lightweight computing.

kwantam commented 4 years ago

do we have a concrete use case for this?

The only one I know of is https://github.com/pornin/curve9767

A different approach to handle this case, it could be to define and/or recommend what are the properties needed by an alternative algorithm for hash_to_field, instead of proposing the full description of an alternate method, which, at the end of the day, might or might not be the best method

This is a good observation. This could be done, for example, by expanding the paragraph at the start of Section 5 that says impls must not use rejection sampling. We could also add a subsection describing the properties, but really there are not many: must be statistaically close to uniform, must not use rejection sampling, should be specified with straight line impls in mind.

armfazh commented 4 years ago

This is a good observation. This could be done, for example, by expanding the paragraph at the start of Section 5 that says impls must not use rejection sampling. We could also add a subsection describing the properties, but really there are not many: must be statistaically close to uniform, must not use rejection sampling, should be specified with straight line impls in mind.

Agree, so we can remove the alternative method.

chris-wood commented 4 years ago

FWIW, I approved since this is a fairly simple algorithm, so I'm OK with the added complexity. But if you both think elaborating on the requirements would work, that's fine too. That we only know of one use case is, well, unfortunate. (So maybe I just talked myself in @armfazh's suggestion? :))

chris-wood commented 4 years ago

@kwantam, quick question:

This is a good observation. This could be done, for example, by expanding the paragraph at the start of Section 5 that says impls must not use rejection sampling. We could also add a subsection describing the properties, but really there are not many: must be statistaically close to uniform, must not use rejection sampling, should be specified with straight line impls in mind.

The third paragraph in Section 5 starts with, "Implementors MUST NOT use rejection sampling..." Perhaps we could add the properties you list to 5.1 (security considerations)?

chris-wood commented 4 years ago

I made that change over in #287. @armfaz, @kwantam, please have a look!

kwantam commented 4 years ago

I think we're all agreed that #287 is the better way to go, so I'm going to close this in favor of that one.