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

[Alex Davidson <[e-mail]>]

Hi Greg,

I should have made it more explicit here that I'm assuming that the initial
hash
function evaluation is modelled as a random oracle.

In general, pseudorandom functions are designed to provide pseudorandom
outputs
(indistinguishable from the output of a uniformly sampled function) even
under
adversarially-chosen inputs. So in some sense requiring that the client in
an
OPRF protocol supplies uniformly sampled inputs due to internal
functionality
reasons is overly restrictive (and prevents some useful applications e.g.
[1,2]). As such, maintaining the ability of a client to supply non-uniform
inputs would seem to at least require some form of pre-processing before
using
the Ristretto point encoding API.

Alex

[1]: https://eprint.iacr.org/2016/799.pdf
[2]: https://eprint.iacr.org/2014/650.pdf

On Mon, Sep 30, 2019 at 5:37 PM Greg Hudson <[e-mail]> wrote:

> On 9/30/19 7:36 AM, Alex Davidson wrote:
> > For the second point, there is a possible solution in defining a
> > FROM_BYTES API
> > function as part of the Ristretto interface. This would take non-uniform
> > bytes,
> > transform them to uniform bytes, and then invoke FROM_UNIFORM_BYTES on
> the
> > output of this transformation. For ristretto255 it would be fine to use
> > SHA512, [...]
>
> Hashing non-uniform inputs does not produce uniform outputs.  Some
> obvious statistical biases may be eliminated, but certain outputs are
> still more likely than others (unless hash collisions manage to
> precisely cancel out the non-uniformity of the input).  Is Ristretto
> asking for too much by requiring a "uniformly distributed 64-byte string
> b"?
>