Re: [CFRG] hash_to_field requires implementing a new 25519 field op

["Riad S. Wahby" <[e-mail]>]

Hey again Filippo,

Filippo Valsorda <[e-mail]> wrote:
> Is the h2c spec supposed to expose a safe, universal hash_to_field
> function, or is it just a component of higher-level functions? Are
> developers expected to swap in arbitrary curves into the spec,
> or are they supposed to use specific instantiations? Is an h2c
> library expected to work with all possible curves, or is h2c one
> of the features of a curve-specific library?

These are great questions. I don't have any particular opinion on the
third one, but with respect to the first two my opinion is that there
are really two separate roles here. One is a developer who implements
an existing suite. The other is an application designer, who needs to
hash to some curve in their application that we (the h2c authors) did
not anticipate. For the second role it should be easy to start with a
curve spec and end up with a secure hash-to-curve suite.

> Myself, I believe elliptic curves are not a safe abstraction (as
> opposed to prime order groups, as you might have expected ;-),
> which I believe should include a fixed-length-string-to-element
> map as part of the abstraction, solving the issue) so I wouldn't
> try to write something that generalizes over arbitrary elliptic curves

Totally agreed that elliptic curves have plenty of sharp edges! But I
am not convinced that hash-to-curve is the culprit here---mostly it's
protocols that are designed assuming "elliptic curve" == "prime-order
group," whereas h2c explicitly deals with composite order. And in any
case, I cannot stop anyone from using a composite-order group, but at
least h2c can help them get one tricky part right!

(Moreover, one of h2c's main users is pairing-friendly curves. Do any
nice composite-order abstractions exist for these? I do not know any.
But they *do* seem to be a moving target! which suggests that we have
to assume the suites in h2c won't suffice forever...)

> That's not true for unsaturated limbs like the popular 51-bit limb
> schedule used by most 64-bit implementations of Curve25519. Reduction
> in multiplication is carried out simultaneously with multiplication,
> and it yields double-wide _limbs_, which are carried very differently
> from a wide reduction. https://git.io/JlTG0

Surely there is nothing magic about unsaturated limbs! It's true that
the code you linked would need an "adapter" morally equivalent to the
code on lines 79--117; but after writing that adapter, lines 146--162
could be shared with the wide reduction routine.

So it is not true that we could get away without new tests, contra my
prior email's claim---mea culpa!---but certainly the adapter would be 
much simpler than either lines 79--117 or lines 146--162: split a 384
bit number into 8 * 51 bits with some shifts and masks; call addMul64
three times; continue at line 146. Is that 10 lines of code? 20?

I freely admit that this is just one point of view and that there are
good arguments in the other direction. And talk is cheap for me since
I don't have to maintain those 20 lines of code! :) But I don't think
those lines suffice to justify dramatically increasing the likelihood
that an application designer gets confused and specifies a broken h2c
suite for next year's shiny new elliptic curve...

Best regards,

-=rsw