Re: [Cfrg] Call for adoption: draft-hdevalence-cfrg-ristretto-01

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

Filippo Valsorda <[e-mail]> wrote:
> I definitely agree that there should be a standard path from non-uniform
> inputs to ristretto255 points, and after some experimentation I
> am fairly convinced the best solution is for hash-to-curve to
> define the input processing (as well as the domain separation)
> homogeneously with the other target curves, and then use the
> ristretto255 FROM_UNIFORM_BYTES API as the abstraction point. This way
> hash-to-curve users will be presented a uniform API, and ristretto255
> internal types won't leak into neither the hash-to-curve spec nor its
> implementations.

Hi Filippo,

I'm glad that Ristretto is moving forward, and I eagerly await its
widespread use :)

As we're prepping hash-to-curve-05, one of the changes was to ensure
that the hash function from arbitrary strings to the base field has
an indifferentiability proof and that the domain separation design
is conservative. In doing so, I've become (more) convinced that this
is something that is easy to get subtly wrong, and that we should do
as much as possible to encourage carefully vetted solutions.

With that as backdrop, I'm a bit nervous about the FROM_UNIFORM_BYTES
API. Specifically, I worry that this API will encourage implementors
to cook up ad-hoc methods of turning strings into "uniform" bytes.
As one (possibly simple-minded) example, I worry that even the name
of the API is misleading, because in almost all cases uniformity is
not really enough. Meanwhile, FROM_INDEPENDENT_UNIFORM_BYTES starts
sounding a little ridiculous, and isn't yet exhaustive... :)

Here's one possible course of action:

1. Remove the function that takes uniform bytes and replace it with
   one that takes an element of the base field. Let's call this the
   MAP function.

2. As you said in your email, recommend (or even require) the use of
   hash_to_base (Section 5 of hash-to-curve) to produce the input to
   the MAP function.

3. Define a new hash-to-curve suite based on MAP. I don't know whether
   this should live in hash-to-curve or Ristretto, but I tend to think
   the latter.

4. Define MAP in terms of the Elligator 2 map in hash-to-curve, with
   the goal of allowing code reuse and minimizing redundancy between
   the two documents. (I realize that this is a contentious request.
   I make it again because I'm still convinced this is both possible
   and a good idea. If you think it's not, can you please explain in
   detail why not? All the past explanations I've seen have been too
   vague to be convincing.)

Even if (4) really is impossible, (1)-(3) still look to me like they
would help avoid confusion and steer implementors towards safe choices.

Looking forward to working with you on this,

-=rsw