search

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

Hashing to Elliptic Curves
Other
79 stars 27 forks source link

a different way around the k issue #227

Closed kwantam closed 4 years ago

kwantam commented 4 years ago

I'm helping to implement hash-to-curve in RELIC, and as I'm doing this I'm realizing that the way we've specified k inherently requires a judgement call, which is annoying. This is related to @armfazh's issue with calling k the security parameter---that's subjective and will change over time, and even now people will disagree on how to define it.

So how could we do this in an objective way? One way would be to say

L = ceil(1.5 * ceil(log2(p)) / 8)

in other words, we replace k with ceil(log2(p)) / 2. But this is too conservative for curves with large cofactors (like pairing-friendly curves).

How about this:

p_bits = ceil(log2(p))
r_bits = ceil(log2(r))  # the bit-length of the prime subgroup order
L = ceil((p_bits + ceil(r_bits / 2)) / 8)

This is essentially how we have been picking k already---in particular, I think this will not change any of the hash-to-field parameters in the Suites at all---but it's a totally objective measure, which is nice...

I can put together a PR if this seems reasonable.

chris-wood commented 4 years ago

Rather than replace k entirely, perhaps we can note that k could be computed as you suggest? I think having a target security level will be important for folks looking to adopt one of these in their applications or protocols.

kwantam commented 4 years ago

Great point! We can add this in the "defining new suites" section, maybe.