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

["Filippo Valsorda" <[e-mail]>]

2019-10-25 19:25 GMT+01:00 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... :)

Hi Riad,

Thanks for getting in touch about the hash-to-curve integration.

As far as I understand, you have concerns about two parts that feel
independent to me:

(a) the conversion from uniform bytes to the field element—this is
defined in the draft, so if you think there is an issue with it, please
let us know so we can address it;

(b) the generation of uniform bytes by the application—of course we
want to make sure this is not hard to get right, so can you share what
kind of issues we should be thinking about, based on your work on
hash-to-curve? Would SHA-512($STRING) be sufficient? We were already
planning to recommend (RECOMMEND, if you feel it would be appropriate)
to use hash-to-curve for domain separation purposes, so there is a
standard and vetted way to do it.

Again, we care about maintaining the abstraction of ristretto255
as nothing else than an abstract prime-order group, and abstract
prime-order groups don't have a base field, that's an implementation
detail that should not leak through the API. Integrating hash-to-curve
on top of FROM_UNIFORM_BYTES also maintains some compatibility between
the existing deployments which already use FROM_UNIFORM_BYTES and the
RFC.

> 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.)

Multiple people made different arguments about this, but mine is
simple: there should be hash-to-curve libraries, and there should be
ristretto255 libraries. The ristretto255 libraries MUST NOT expose the
underlying curve points because it's an abstraction breach, because
it's encouraging implementors to do unsafe operations, and because
it makes interoperability with ristretto255 implementations based on
an alternative curve impossible. If the ristretto255 libraries don't
expose those internals, though, there is no way for hash-to-curve
libraries to do (4) without being one and the same, and I don't see why
a hash-to-curve library should be forced to implement ristretto255 and
vice-versa.