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

From: Alexey Melnikov <[email-masked]>
Date: Wed, 18 Sep 2019 17:44:22 +0100

Dear CFRG participants,

This email commences a 2-week call for adoption for 
draft-hdevalence-cfrg-ristretto-01 that will end on October 2nd 2019:

  https://datatracker.ietf.org/doc/draft-hdevalence-cfrg-ristretto/

Please give your views on whether this document should be adopted as a 
CFRG draft, and if so, whether you'd be willing to help work on 
it/review it. Please reply to this email (or in exceptional 
circumstances you can email CFRG chairs directly at [email-masked]).

Thank you,
Alexey (for the chairs)

---

From: Richard Barnes <[email-masked]>
Date: Wed, 18 Sep 2019 13:38:05 -0400

I am not in a position to evaluate the mathematics of this proposal, but
the idea of a curve that files down some of the unnecessary "sharp edges"
of Curve25519 is welcome.

As has been discussed previously on this list, it is helpful in some
contexts to have DH groups in which scalar multiplication commutes with the
private-to-public-key map, since this allows public keys to be transformed
in a way that the corresponding transformations on private keys are clear.
This is the case for the traditional NIST ECDH curves, but not for
Curve25519, due to the "clamping" it requires.  If I understand correctly,
Ristretto would have this property, and so would in some cases effectively
be a more useful version of Curve25519.

--RLB

On Wed, Sep 18, 2019 at 12:45 PM Alexey Melnikov <[email-masked]>
wrote:

> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: "Christopher Wood" <[email-masked]>
Date: Wed, 18 Sep 2019 15:36:15 -0700

I'm in favor of adoption as well, though am curious to know where folks stand on the issues discussed in [1] and earlier messages. What is the plan for reconciling this with the hash-to-curve draft? Of the three options Filippo outlines in [2], the third seems the most appealing and probably the most workable, though does muddy the "curve" focus of hash-to-curve.

Best,
Chris

[1] https://mailarchive.ietf.org/arch/msg/cfrg/w91AdGVdLWccafiPub862MObk5c
[2] https://mailarchive.ietf.org/arch/msg/cfrg/p_r53FtGcaNSB_HwIV0J9FSgYbg

On Wed, Sep 18, 2019, at 10:38 AM, Richard Barnes wrote:
> I am not in a position to evaluate the mathematics of this proposal, 
> but the idea of a curve that files down some of the unnecessary "sharp 
> edges" of Curve25519 is welcome. 
>
> contexts to have DH groups in which scalar multiplication commutes with 
> the private-to-public-key map, since this allows public keys to be 
> transformed in a way that the corresponding transformations on private 
> keys are clear. This is the case for the traditional NIST ECDH curves, 
> but not for Curve25519, due to the "clamping" it requires. If I 
> understand correctly, Ristretto would have this property, and so would 
> in some cases effectively be a more useful version of Curve25519.
> 
> --RLB
> 
> On Wed, Sep 18, 2019 at 12:45 PM Alexey Melnikov 
> <[email-masked]> wrote:
> > Dear CFRG participants,
> >

---

From: "Christopher Wood" <[email-masked]>
Date: Wed, 18 Sep 2019 16:27:07 -0700

On Wed, Sep 18, 2019, at 3:36 PM, Christopher Wood wrote:
> I'm in favor of adoption as well, though am curious to know where folks 
> stand on the issues discussed in [1] and earlier messages. What is the 
> plan for reconciling this with the hash-to-curve draft? Of the three 
> options Filippo outlines in [2], the third seems the most appealing and 
> probably the most workable, though does muddy the "curve" focus of 
> hash-to-curve.

Of course, if we're willing to budge on the API, there's also option #4 wherein FROM_UNIFORM_BYTES is replaced with FROM_BYTES that, internally, invokes hash-to-curve as needed. 

Best,
Chris

---

From: "Filippo Valsorda" <[email-masked]>
Date: Thu, 19 Sep 2019 13:44:22 +0200

> [2] https://mailarchive.ietf.org/arch/msg/cfrg/p_r53FtGcaNSB_HwIV0J9FSgYbg

We plan to prepare -02 to address all the unclear parts that emerged
from the discussion on this list. The reason it's taking longer
than we'd like is that we want to simultaneously port one of the
implementations to a different curve, so we can have discussions more in
concrete.

As for hash-to-curve, we agree that invoking FROM_UNIFORM_BYTES
from hash-to-curve is the best way forward. It preserves the API
abstraction and avoids leaking Ristretto internal representatives into
the hash-to-curve spec and its implementations, while still leaving
hash-to-curve in charge of domain separation and everything else.

Thank you,
Filippo

---

From: Alex Davidson <[email-masked]>
Date: Mon, 30 Sep 2019 12:36:56 +0100

I would like to include my support for the adoption of this draft. From the
perspective of the ongoing effort for standardising the construction of
OPRFs in
prime-order groups (draft-irtf-cfrg-voprf-01), the abstraction of the
elliptic
curve interface made by Ristretto is much more preferable than interacting
with
Curve25519-type curves directly. In particular removing the necessity to
check
whether points are actually defined in the prime-order group, which is a
frequent source of errors.

Apart from this, I have a few points about how certain aspects of this
draft may
have implications for the OPRF use-case going forward.

Firstly, it has been noted recently that OPRFs can be used to instantiate an
oracle for constructing q-Strong-DH samples [1]. This leads to attacks that
can
reduce security by up to log_2(m) bits where m queries are made [2,3]. A
future
OPRF draft will address this by declaring ciphersuites with curve choices
that
provide > 128 bits of security. With this in mind, it would be useful if
Ristretto groups could also be defined for curves with larger security
parameters (such as providing an interface for Curve448). I'm not sure if
this
is a direction that is currently being considered?

Secondly, and to add to the discussion on the FROM_UNIFORM_BYTES API, I
agree
that it would be useful to refactor some form of this functionality to
match the
expectations set out in the hash-to-curve draft. This would then provide a
single point of reference for developers/other drafts to implement moving
from
bytes to group elements. However, my concern is that if the API remains as
it is
specified in the current I-D, then this may rule out valid applications of
OPRFs
where the input bytes are not uniformly distributed. If the only way to move
from bytes to a Ristretto group is to use the FROM_UNIFORM_BYTES function,
then
this means that we would have to define a separate interface for Ristretto
ciphersuites in the OPRF draft for extracting random bytes from potentially
non-uniform inputs. If so, this will produce somewhat incompatible
Ristretto and
non-Ristretto ciphersuite configurations, which is something that we may
want to
avoid going forward.

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,
but if we want to support larger groups then this would not be enough. In
these
cases, it would be necessary to use something like HKDF_Expand to expand the
output of SHA512 to the appropriate level. This sort of transformation would
also be valid in ristretto255, and would appear to be quite similar to the
hash_to_base function defined in the hash-to-curve draft.

With the above in mind, it could be worth realigning the Ristretto point
encoding mechanism around hash-to-curve by running hash_to_base and then
calling
an appropriate hash_to_curve method for producing similar outputs to those
given
by FROM_UNIFORM_BYTES. Since these outputs appear to be even Edwards points
(unless I'm mistaken), then this could potentially be achieved by running
edwards25519-SHA256-EDELL2-RO and then doubling the output point?

Happy to discuss these points further.

Thanks,
Alex

[1]: http://ai.stanford.edu/~xb/eurocrypt04a/bbsigs.pdf
[2]: https://eprint.iacr.org/2004/306
[3]: https://www.iacr.org/archive/eurocrypt2006/40040001/40040001.pdf

---

From: Greg Hudson <[email-masked]>
Date: Mon, 30 Sep 2019 12:37:10 -0400

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
> 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"?

---

From: Alex Davidson <[email-masked]>
Date: Mon, 30 Sep 2019 19:20:19 +0100

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

---

From: "Riad S. Wahby" <[email-masked]>
Date: Mon, 30 Sep 2019 16:22:30 -0700

Alexey Melnikov <[email-masked]> wrote:
> Please give your views on whether this document should be adopted as a CFRG
> draft, and if so, whether you'd be willing to help work on it/review it.
> Please reply to this email (or in exceptional circumstances you can email
> CFRG chairs directly at [email-masked]).

Standardizing Decaf and/or Ristretto is a great idea--strongly support!

I'm happy to work with the Ristretto authors to make sure that this
document and hash-to-curve are well aligned and to give feedback on
the Ristretto document.

-=rsw

---

From: "Riad S. Wahby" <[email-masked]>
Date: Mon, 30 Sep 2019 17:12:04 -0700

Alex Davidson <[email-masked]> wrote:
> With this in mind, it would be useful if Ristretto groups could
> also be defined for curves with larger security parameters (such
> as providing an interface for Curve448). I'm not sure if this is
> a direction that is currently being considered?

For the specific case of Curve448, Ristretto isn't necessary because
the cofactor is only 4---so Hamburg's Decaf construction [1] (which
precedes Ristretto, and seemingly inspired it) suffices.

It might be interesting for the proposed draft to cover both, though
one could argue that this is feature creep. Probably it's worthwhile
for the Ristretto authors to weigh in on how much it would increase
complexity to cover both constructions in one document.

[1] https://eprint.iacr.org/2015/673

-=rsw