Subject: Re: [Cfrg] Adoption request: draft-hdevalence-cfrg-ristretto

From: "Filippo Valsorda" <[email-masked]>
Date: Wed, 24 Jul 2019 12:24:52 +0200

What are the next steps in discussing adoption of this draft?

I believe it would be especially timely, as ristretto255 provides a
better prime-order group than Curve25519 for OPRFs and PAKEs that are
being discussed by this group.

Moreover, Cas Cremers and Dennis Jackson recently published a new round
of small subgroup attacks that would have been avoided by Ristretto
adoption, as they mention in the paper.

https://eprint.iacr.org/2019/526.pdf

2019-05-18 00:22 GMT+02:00 Filippo Valsorda <[email-masked]>:
> Hello,
> 
> I'd like to request for the group to adopt
> draft-hdevalence-cfrg-ristretto for publication as an Informational RFC.
> 
> https://datatracker.ietf.org/doc/draft-hdevalence-cfrg-ristretto/
> 
> Ristretto255 is a prime-order group designed by Henry de Valence,
> based on Mike Hamburg's Decaf. It provides a safe, efficient, and
> implementor-friendly abstraction for a prime-order group, enabling safer
> and simpler design of higher-level protocols. Its order is the same as
> the prime-order subgroup of Curve25519.
> 
> Ristretto255 can easily be implemented on top of an existing Curve25519
> library, and the authors are providing multiple implementations in
> different languages: curve25519-dalek in Rust, by Isis Lovecruft
> and Henry de Valence; curve25519-elisabeth in Java, by Jack Grigg;
> ristretto255 in Go (implemented clean-room from the spec),
> by George Tankersley and myself; and ristretto-donna (forthcoming) in
> C, by Isis Lovecruft. We are also aware of other implementations we
> have not personally tested for interoperability, including one in Frank
> Denis's libsodium.
> 
> https://github.com/dalek-cryptography/curve25519-dalek
> https://github.com/cryptography-cafe/curve25519-elisabeth
> https://github.com/gtank/ristretto255
> 
> Importantly, ristretto255 is a flexible abstraction, and can be
> implemented with different, more efficient curves than Curve25519. The
> draft only provides implementation details for a Curve25519 backend,
> but it defines the interface contract which is required of compliant
> implementations, allowing alternate backends.
> 
> The group has already been adopted by some higher level protocols,
> including Bulletproofs by Chain, and has been subject of discussion on
> this list, including some good posts by Tony Arcieri. More information
> is available at https://ristretto.group and in the draft, and the
> authors and I are available to answer questions.
> 
> Best, Filippo
>

---

From: "Paterson Kenneth" <[email-masked]>
Date: Wed, 24 Jul 2019 10:29:28 +0000

Hi Filippo,

It's on the chair's "to do" list to reach out to the authors of that document and discuss the next steps. 

Thanks for your patience during the delay. There's a lot of CFRG docs in the works at the moment.

Regards

Kenny (for the chairs)

-----Original Message-----
From: Cfrg <[email-masked]> on behalf of Filippo Valsorda <[email-masked]>
Date: Wednesday, 24 July 2019 at 12:26
To: "[email-masked]" <[email-masked]>
Cc: "[email-masked]" <[email-masked]>
Subject: Re: [Cfrg] Adoption request: draft-hdevalence-cfrg-ristretto

    

    > authors and I are available to answer questions.
    
    _______________________________________________
    Cfrg mailing list
    [email-masked]
    https://www.irtf.org/mailman/listinfo/cfrg

---

From: Jeff Burdges <[email-masked]>
Date: Wed, 24 Jul 2019 12:47:12 +0200

> It's on the chair's "to do" list to reach out to the authors of that document and discuss the next steps. 

Wonderful!  We'll save considerable headache and effort by moving people
towards Ristretto and Ristretto variants for other Edwards curves.

I'd expect the only contentious issue around Ristretto might be the
decision that a mapping from Ristretto to Ed25519 should not be
standardized.

It's clear such a map is useful, so often people start off favoring one,
but it's also clear such a map leads to non-compliant implementations,
so similarly often people eventually come around to the opinion that
such a map should not be standardized.

It might also be worth noting how Ristretto differs from Section 7? of
Mike Hamberg's Decaf paper that lays out doing Decarf for Edwards curves
with cofactor 8.  I glanced at this once, concluded some differences
exist, but only minor ones, and promptly forgot the details.  ;)  At
least once upon a time the Decaf paper seemed a clearer reference for
why Ristretto actually works, so this mattered, but maybe not anymore
with more recent Ristretto documentation providing good exposition.

I'm not suggesting either of these requires changes to the draft, only
pointing everyone to relevant discussion topics.

Best,
Jeff

---

From: "Riad S. Wahby" <[email-masked]>
Date: Wed, 24 Jul 2019 14:20:30 -0700

Hello Jeff,

I think I'm being a little slow here---sorry! But:

> such a map should not be standardized.

Can you please explain in a little more detail what you mean by
"such a map leads to non-compliant implementations"? The most naive
interpretation appears to be: currently a bunch of people do different
things, so if the document requires one thing, some of those people
will be non-compliant. Is that right? Or do you mean that somehow
it would be impossible for (some) implementations to comply with any
particular spec? (If so, why?)

In any case, it seems to me that what we should care about is
interoperability, not compliance for its own sake. Is it the case
that dictating the Edwards mapping just doesn't matter, because
implementations will be able to interoperate despite using different
mappings internally? (I assume yes, based on my understanding of
Decaf.) If that's right, it seems reasonable to give implementors
latitude to make decisions that have no effect on interoperability.
(As a very rough analogy, RFC7748 doesn't say "you MUST do modular
reductions in such-and-such way," because that doesn't matter from
an interop perspective.)

If my interpretation is correct, then I suggest the authors provide
a mapping that implementations MAY use, as a way of assisting
implementors in getting things right. This is probably as simple as
citing the birational map between edwards25519 and curve25519 from
Section 4.1 of RFC7748, and explaining how to use this map in concert
with the Ristretto functions.

Also, a couple general comments for the authors regarding the document
as it currently stands:

First, the text of section 1 makes repeated reference to Edwards
curves, but the document deals with a Montgomery curve (and, per the
above, explicitly *does not* deal with an Edwards curve)---and the
word Montgomery *never appears in the document*! Of the curves are
equivalent, but the document should be intelligible even to readers
who don't instantly recall this fact. I'm happy to suggest specific
(likely minor) edits to the intro to help clarify this point.

Second, to make extremely clear what's going on with the Ristretto
functions, it probably makes sense to reiterate, for each function,
the types of the input and output. For example, I think the document
is saying that DECODE takes a 32-octet string as input and returns
a point (X : Y : Z : T) on curve25519 (i.e., the Montgomery curve)
equivalent to the affine point (x, y) = (X/Z, Y/Z) (and analogously
for the rest). Is this right? To my reading, this is not obvious from
the document. That might be me being slow---sorry!---but perhaps in
that case the authors will interpret this as feedback from a very
naive reader who would love some extra handholding :)

Looking forward to Ristretto,

-=rsw

---

From: Jack Grigg <[email-masked]>
Date: Thu, 25 Jul 2019 00:31:48 +0100

Hi Riad,

On Wed, Jul 24, 2019 at 10:20 PM Riad S. Wahby <[email-masked]> wrote:

> Decaf.)

The ability for ristretto255 implementations to interoperate, despite using
different internal representations, is contingent on implementors following
the normative requirement that the internal representations are not
exposed, or operated on except via the Ristretto APIs. This precludes any
mapping from ristretto255 elements to edwards25519 points.

Put another way: if a mapping from ristretto255 elements to edwards25519
points existed, any higher-level protocol that leveraged this mapping would
only work with ristretto255 implementations specifically constructed over
edwards25519, breaking interoperability across ristretto255 implementations.

It is an explicit design decision to define the Ristretto API solely in
terms of the four provided operations:

> ristretto255 is an abstraction which exposes a prime-order group, and
> ristretto255 elements are represented by curve points, but they are
> not curve points. The API needs to reflect that: the type
> representing an element of the group SHOULD be opaque and MUST NOT
> expose the underlying curve point.

>From an interoperability perspective, users of ristretto255 rely on the
fact that e.g. DECODE(x) will always return the same ristretto255 element
given a valid encoding x. They do not need to care how it is implemented,
or even that the same internal representation is always used. From section
3.2.3:

> Note that the equality function always returns TRUE when applied to
> an internal representation and to the internal representation
> obtained by encoding and then re-decoding it. However, the internal
> representations themselves might not be identical.

> If that's right, it seems reasonable to give implementors

I agree! This is what the current draft aims to do, by allowing
implementors to use whatever internal representation they choose.
Specifically, the document intends to specify the normative behavior of the
group and the API, while providing informationally the details of one
possible implementation, the one based on edwards25519. If there are ways
we can make this more clear, please do send suggestions.

> with the Ristretto functions.

Per above, the way to ensure implementors get things right is to prohibit
such a mapping (which would necessarily be breaking the API provided by the
Ristretto functions, rather than being a mapping operating behind them).

> (likely minor) edits to the intro to help clarify this point.

This is a salient point. We in fact mean edwards25519 throughout the text,
but almost every implementation of edwards25519 that isn't built into an
Ed25519 implementation is provided in a Curve25519 library, and I figure
the latter is more familiar to readers (even RFC7748 only contains a single
occurrence of "edwards25519"). I personally would be happy to replace all
occurrences of "Curve25519" with "edwards25519", but I would like to hear
from the other authors on this point.

> naive reader who would love some extra handholding :)

If all occurrences of "Curve25519" were replaced with "edwards25519", would
this be clearer? For this particular example, the intention is that DECODE
takes a 32-byte string and returns either an error, or a ristretto255
element that is internally represented as a point (X : Y : Z : T) on
edwards25519. Part of the fun here is figuring out how to make these types
clear and the ristretto255 API well-defined, while enabling implementors to
use concrete internal implementations outside of what is provided in the
draft.

Thanks for the feedback,
Jack

---

From: Jeff Burdges <[email-masked]>
Date: Thu, 25 Jul 2019 02:31:30 +0200

On 25.07.19 01:31, Jack Grigg wrote:
> The ability for ristretto255 implementations to interoperate, despite
> using different internal representations, is contingent on implementors
> following the normative requirement that the internal representations
> are not exposed, or operated on except via the Ristretto APIs. This
> precludes any mapping from ristretto255 elements to edwards25519 points.

This does not explain the problem because an implementation could use
any representation it liked and still expose or not expose any maps it
likes.  We still using GF(2^255-19) after all, so it's just a bit more
work for some than for others.

The real issue is that there are two such mappings, depending upon the
branch of the inverse square root chosen.  These two interoperate
seamlessly, provided the mapping is not exposed.  If however the mapping
is exposed later then they suddenly differ.  The problematic scenario goes:

Joe implements the basic Ristretto using generic math libraries that
expose suitable arithmetic, so Joe does not delve into the arithmetic
further.  Joe's Ristretto passes all test vectors for functionality he
implemented, making it fully compliant with the basic implementation.

Joe later expands his protocol by adding and using the mapping, using
the form of the mapping natural given the arithmetic he inherited.
Again everything works, so now people depend upon Joe's mapping.  Joe
does not however check all newly applicable test vectors from the
standard because everything works fine.

Joe expands his protocol to interoperate with another implementation.
Now suddenly everything breaks because the mappings differ.  Yet both
incompatible forms are deployed.

If almost all uses needed the mapping, then yes you could standardize
it, but most do not, and using the mapping incurs cofactor worries.  So
the mapping would occupy a niche poorly implemented layer of the
standard, and the above scenario sounds likely.

Jeff

---

From: "Riad S. Wahby" <[email-masked]>
Date: Wed, 24 Jul 2019 17:46:33 -0700

Hi Jack,

Thanks very much for the answers. Can you please help me understand
a bit more what's going on?

(At the risk of protesting too much, I want to be clear that the
concerns below are sincere: I really cannot square the claims in
this thread with the content of the document or my understanding of
Decaf/Ristretto. As background, I've read the Decaf paper carefully
and implemented it fully. So I don't think it is much of a stretch
to suppose that if I can't parse what's going on in this document,
there are plenty of others out there who won't be able to, either.)

> mapping from ristretto255 elements to edwards25519 points.

Sorry, I don't understand. Per the rest of your email, DECODE as
specified in Section 3 is exactly such a mapping. So how am I to
interpret what you've said above?

Concretely: let's say I want to output the sum of two ristretto255
points, P1 and P2. To do that, I think I need to do something like this
(all functions as specified in Section 3):

    P1_decoded = DECODE(P1)
    P2_decoded = DECODE(P2)
    Q_decoded = P1_decoded (+) P2_decoded
    Q = ENCODE(Q_decoded)

The problem is, the document as currently written does not tell me
how to implement the (+) operator on the third line above. It implies
that such an operator exists (in Section 3.3), but as far as I can
tell it does not tell me what it is.

Is it edwards25519 point addition? If so, then I just don't see how
it can be true that the "internal representation" in Section 3 is
not an edwards25519 point. (Sure, equality testing is different.
What else is different? What is the same?)

> edwards25519, breaking interoperability across ristretto255 implementations.

It's not obvious (to me!) from the draft, the Decaf paper, etc.
why this should be true. So I think it will be important to spell it
out somewhere (or maybe I just need to read Decaf more carefully---in
which case, apologies).

Here's something I might stupidly decide to do:

    P_decoded = DECODE(P)
    P_montgomery = Edwards_To_Montgomery(P_decoded)
    Q_montgomery = my_scalar (*) P_montgomery
    Q_decoded = Montgomery_To_Edwards(Q_montgomery)
    Q = ENCODE(Q_decoded)

Here, P_montgomery and Q_montgomery are points on curve25519,
Edwards_To_Montgomery and Montgomery_To_Edwards correspond to
the birational map of RFC7748, Section 4.1, and (*) is scalar
multiplication on the Montgomery curve.

Meanwhile, a better implementor might instead do

    P_decoded = DECODE(P)
    R_decoded = my_scalar (*) P_decoded
    R = ENCODE(R_decoded)

Here, (*) is scalar multiplication on edwards25519.

So, finally, the question: is the claim that R != Q? I don't see
how that can be true given the birational equivalence of curve25519
and edwards25519.

Alternatively, if R == Q, then what's the problem with converting
back and forth between Edwards and Montgomery points, and why am
I not correct in thinking of P_decoded as an edwards25519 point?
Is it just that certain operations (equality checking, ...???)
don't work the same as a "real" edwards25519 point?

> terms of the four provided operations:

OK, but this can't actually be true, because there are other operations
alluded to (but not defined) in the document, and without those
operations (point addition, point inversion, scalar multiplication)
ristretto255 doesn't actually let me do anything.

> we can make this more clear, please do send suggestions.

I'm hoping to get to the point where I can make such suggestions,
but first I have to actually understand what's going on!

Here's my current best guess:

ENCODE and DECODE convert ristretto255 points into some internal
representation. For the algorithms in Section 3, that internal
representation is edwards25519, except that equality testing is
different (specifically, it must use EQUALS) and maybe some other
things are different (but I don't know what).

Operations are the same as for edwards25519, but the only ones that
are allowed are addition, inversion, and multiplication.

Implementors can maybe use a different internal representation. There
is no obvious way to do this given the information in the document.
In particular, there is no group isomorphic to Curve25519 with order l,
because Curve25519 has order 8 * l.

> Ristretto functions, rather than being a mapping operating behind them).

Does the document prohibit such a mapping? Is this the intent
of Section 3.3? What would go wrong if I did this, assuming that
after mapping (say) an edwards25519 point to a curve25519 point, I
continued to observe the restriction that only addition, inversion,
and multiplication are allowed?

(I think this is the same as my question about Q and R, above.)

> from the other authors on this point.

On the other hand, RFC7748 contains 12 occurrences of "curve25519"
(17 if you turn off case sensitivity) and every one of those refers
to the Montgomery curve, not the Edwards curve. So as far as I can
tell there is no way for a reader to understand this document as
currently written other than to guess that when you say "Curve25519"
you actually mean "edwards25519", not "curve25519".

> edwards25519.

Sure, that would help. But then it's impossible to understand the
claim from two emails ago that there's no mapping from ristretto255
to edwards25519, because ENCODE and DECODE appear to be exactly
such mappings!

Sure, it's non-normative, I get that, no worries. But how is it
possible for me to understand the claim that mapping to edwards25519
would break compatibility when the document demonstrates exactly such a
mapping and claims that all other mappings must be compatible with it?

Thank you preemptively for putting up with my confusion,

-=rsw

---

From: "Riad S. Wahby" <[email-masked]>
Date: Wed, 24 Jul 2019 18:09:45 -0700

> is exposed later then they suddenly differ.  The problematic scenario goes:

Just to clarify: the mappings you're talking about are the ones in
RFC7748, Section 4.1, and the value whose sign you're worried about
is sqrt(-486664) mod p, right?

A second clarification: we're really talking about mapping *from*
edwards25519 *to* curve25519, since what's in the Ristretto draft
Section 3 apparently works on edwards25519 points (I think).

> standard because everything works fine.

Again, "the mapping" being the one to curve25519?

> incompatible forms are deployed.

Same question as above re "the mappings".

Can you give a specific example of the kind of interop that would
break? In particular, provided that reverse_map(map(X)) == X for all
rational points X on edwards25519, wouldn't it always be safe to do
something like

    DECODE -> map -> (something) -> reverse_map -> ENCODE

provided that (something) includes only allowed operations (addition,
inversion, multiplication)?

-=rsw

---

From: "Filippo Valsorda" <[email-masked]>
Date: Thu, 25 Jul 2019 03:23:50 +0200

> ristretto255 doesn't actually let me do anything.

The critical section here is Section 3.3 of -01, which reads

> 3.3.  Operations on internal representations
>
>   Group addition, subtraction and (multi-)scalar multiplication are
>   performed without modification using the internal representations.
>
>   Implementations MUST NOT perform any other operation on internal
>   representations.

and explicitly allows addition and scalar multiplication. Maybe we
should also call out inversion, but I would want to hear from the other
authors before confirming that.

To get to the rest of your comments in aggregate: ristretto255 is, at
its core, an abstraction. To downstream users (specs and implementors)
it intentionally provides a specific closed set of operations on an
abstract prime-order group.

The main challenge that we'd appreciate wording help with is that
of defining the behavior of the group normatively through the example
of its edwards25519 implementation, while making it clear that the
edwards25519 internal representatives are an implementation choice,
and must not be directly generated nor accessed, in order to make
alternative implementations possible.

The other authors would be able to present the details and advantages of
the alternative implementations better than me, but with my API designer
hat on, I want to mention that there is inherent value in clearly
defining the public API surface of a cryptographic primitive: it can be
fully assessed in its security and fitness for the job, leaving no room
for misuse. We're here after all because Curve25519 was designed for
authenticated Diffie-Hellman key exchanges, but did not enforce that in
its API, and was used where it's not safe.

We believe sections 3.2 and 3.3 provide all operations necessary to
implement the "prime order group" interface (and if not, we should
specify the missing ones). Given that, we want to disallow abstraction
breaches that might or might not compromise its security.

(Notwithstanding the fact that someone who read the Decaf paper like
you might indeed make safe abstraction breaches—modulo alternative
implementation compatibility. The point is that we are designing a
primitive that aims to be misuse resistant because it neither requires
nor allows such attempts.)

---

From: "Filippo Valsorda" <[email-masked]>
Date: Thu, 25 Jul 2019 03:41:11 +0200

> inversion, multiplication)?

I think you and Jeff are talking about different things, and myself
and the rest of the authors are mostly concerned about yet a different
thing. Let me try to enumerate them.

This chain that you describe, if done correctly, would in fact be just
an alternative implementation of ristretto255, as it operates entirely
within the realm of internal representatives.

    ENCODE -> map -> (something) -> reverse_map -> DECODE

This, correct me if I'm wrong, is an example of the kind of map Jeff
is talking about: something that takes abstract ristretto255 elements
(which might be implemented with something else than edwards25519) and
maps them to edwards25519 points (NOT internal representatives).

While not an abstraction breach, this would be problematic for the
reasons Jeff mentions (that it would be a niche feature of the group
prone to errors), but most importantly IMHO because it would cause
confusion and those mapped edwards25519 points would end up being used
as internal representatives, breaching the abstraction.

    edwards25519 point -> (something) -> reverse_map -> ENCODE

    DECODE -> map -> edwards25519 point -> (something)

This is an abstraction breach, which if specified would make it
difficult if not impossible for non-edwards25519 implementations to
interoperate, and would risk compromising the safety of the primitive.

An example of this is draft-irtf-cfrg-voprf-01 defining its own map to
ristretto255 internal representatives.

In my previous email I was mostly addressing this last case, so
apologies if I ended up talking past you while you were talking about
the first one.

---

From: "Riad S. Wahby" <[email-masked]>
Date: Wed, 24 Jul 2019 18:52:59 -0700

Hello Filippo,

Thanks for the email. Answers inline below.

Filippo Valsorda <[email-masked]> wrote:
> RSW wrote:

Right, this is what is "alluded to" (self-quote above).

The problem, simply put, is that the document does not define how to
do these operations.

(Also: inversion, subtraction, either's fine.)

> alternative implementations possible.

I'm super duper willing to help. I want this document to succeed.
But I cannot help when the document as it stands cannot be parsed
except by its authors and/or without some educated guessing.

> I want to mention that there is inherent value in clearly
> defining the public API surface of a cryptographic primitive

Totally agreed! I want to be crystal clear, this is not my complaint.

> specify the missing ones).

Here is the problem: Sections 3.2 and 3.3 *do not* provide those
operations. For example, the document does not indicate how to perform
point addition, because nowhere in the document is it made clear that
the output of DECODE as defined in Section 3 is an edwards25519 point.

> nor allows such attempts.)

I promise, I really don't want to break the abstraction! I'm asking
these questions to try and triangulate what the document and the
claims in this thread mean, because right now it's totally unclear.

Again, thank you (all) for your patience with my questions,

-=rsw

---

From: "Riad S. Wahby" <[email-masked]>
Date: Wed, 24 Jul 2019 19:10:29 -0700

> within the realm of internal representatives.

Sweet! I think I'm starting to get it...

In this case, let's be clear that we're talking about DECODE and ENCODE
as defined in Section 3, i.e., working on edwards25519 points as the
"internal representation."

> maps them to edwards25519 points (NOT internal representatives).

Sorry, I don't understand this. edwards25519 points *are* valid
internal representations.

(I fully understand that munging the bitstring that comes out of
ENCODE is crazy and not allowedt, though!)

>     DECODE -> map -> edwards25519 point -> (something)

Wait, what is the type signature of reverse_map? ENCODE takes an
edwards25519 point (again, per Section 3), so to me this looks like
a type error, in which case I fully agree this can't return anything
intelligible.

> ristretto255 internal representatives.

As the Ristretto draft is currently written, that appears to be true
(or, at least, if it's false, it's only by chance).

(Not to muddy the waters, but for the record I'm strongly hoping
that the next Ristretto draft will replace its specification of
FROM_UNIFORM_BYTES with edwards25519-SHA256-EDELL2-RO. There's
no reason for Ristretto to be incompatible with hash-to-curve.
But let's worry about other issues first.)

-=rsw

---

From: "Filippo Valsorda" <[email-masked]>
Date: Thu, 25 Jul 2019 04:16:31 +0200

> the output of DECODE as defined in Section 3 is an edwards25519 point.

Oh, I understand now, thanks for patiently following up.

I think we put all that weight on this opening sentence (considering
s/Curve25519/edwards25519/ per previous discussion).

>    This documents describes how to implement the ristretto255 group
>    using Curve25519 points as an internal representation.

I fully agree that Section 3.3 should be expanded to clarify that the
operations are indeed edwards25519 addition, subtraction and scalar
multiplication (when using edwards25519 as internal representatives).

---

From: "Filippo Valsorda" <[email-masked]>
Date: Thu, 25 Jul 2019 04:31:50 +0200

> internal representations.

edwards25519 points generated by DECODE or FROM_UNIFORM_BYTES are *one
possible kind* of internal representatives.
 
> a type error, in which case I fully agree this can't return anything

That was a bad diagram on my part. This should be more accurate.

    (something) -> edwards25519 point -> ENCODE

where (something) is neither DECODE nor FROM_UNIFORM_BYTES from the same
edwards25519-based ristretto255 implementation.

To borrow your type error analogy, internal_representative is a
different type from edwards25519_point, although it might or might not
be an opaque wrapper around edwards25519_point, and ENCODE takes an
internal_representative, not an edwards25519_point.

Looking at the Go implementation might also help (although of course
the spec will need to stand on its own) as it puts this into actual types.

---

From: "Riad S. Wahby" <[email-masked]>
Date: Wed, 24 Jul 2019 20:49:58 -0700

> multiplication (when using edwards25519 as internal representatives).

Sweet! Thank you so much for your patience helping me understand.

Here's a concrete proposal to clarify the document:

1. Make the Section 3 implementations of ENCODE, DECODE, EQUALS, and
   FROM_UNIFORM_BYTES normative, and clarify that the inputs to ENCODE
   and EQUALS and the outputs of DECODE and FROM_UNIFORM_BYTES are
   edwards25519 points that are "internal representations."

2. As now, forbid implementors from exposing any point that is an
   internal representation.

3. Explicitly allow mapping any internal representation to any curve
   isomorphic to edwards25519, and state that the output of any such
   mapping remains an internal representation and thus subject to
   all of these requirements.

   (List the edwards25519/curve25519 isomorphism as an example,
   and direct the reader to the birational map in RFC7748.)

   I'd also get rid of the text in the Section 3 header that talks
   about groups of order l, since edwards25519 is not such a group
   and thus no group isomorphic to it is either.

4. Explicitly allow addition, subtraction / inversion, and
   multiplication on any point that is an internal representation.
   These operations MUST be isomorphic to addition, subtraction /
   inversion, and multiplication on edwards25519.

5. Explicitly state that any internal representation that is the
   result of a sequence of mapping operations MUST be converted back
   to edwards25519 internal representation via the inverse sequence
   of mappings before applying the ENCODE or EQUALS function.

6. Explain that implementors MAY compose (e.g.)  DECODE/mapping,
   FROM_UNIFORM_BYTES/mapping, reverse-mapping/ENCODE,
   reverse-mapping/EQUALS, and similar into monolithic functions.
   In other words, the idea isn't to dictate the structure of the code,
   only the underlying algebraic properties.

7. Make FROM_UNIFORM_BYTES incorporate edwards25519-SHA256-EDELL2-RO
   by reference, and specify a DST (domain separation tag, see Section
   5.1 and 5.3 of hash-to-curve), e.g., "Ristretto255-Hash".

I'm happy to read future drafts, create PRs, etc.---let me know how
I can help!

-=rsw

---

From: Watson Ladd <[email-masked]>
Date: Wed, 24 Jul 2019 22:25:24 -0700

> What else is different? What is the same?)

Let's look at the Decaf paper: The group is E/E[4] for E some curve.
So if you represent with points there is an arbitrary element of E[4]
floating around, and it's an implementation detail what that is
provided you normalize on output. That's the whole story. I would
recommend an algebra book to learn more.

Of course a similar story is common in elliptic curve cryptography.
Any point has multiple projective representations, but the final
normalization obscures this. Likewise one can use any desired
coordinate system or formula for the calculations, provided the right
answer is arrived at for the end.

---

From: "Riad S. Wahby" <[email-masked]>
Date: Wed, 24 Jul 2019 23:26:03 -0700

Watson Ladd <[email-masked]> wrote:
> I would recommend an algebra book to learn more.

(Watson, it sure looks like you're intentionally misinterpreting me.  
I'm honestly not sure if my meaning went entirely over your head, so
unlike you I'll choose the charitable interpretation.)

From your reply I assume either that I was being extremely unclear or
that you really like the current text. Or something else?

Maybe you just want me to stop sending so much mail to the list :)

-=rsw

---

From: "Riad S. Wahby" <[email-masked]>
Date: Thu, 25 Jul 2019 07:36:26 -0700

With apologies for a self-reply, a few addenda to my suggestions
based on off-list discussions:

0. Define the term "internal representation" up front. Make clear
   that it's a restricted version of an elliptic curve point that
   is defined over some underlying curve, and that all operations on
   intenal representations not explicitly allowed by the text of the
   document are prohibited.

>    edwards25519 points that are "internal representations."

Clarify in the above that inputs to ENCODE and EQUALS MUST be internal
representations; any other inputs are prohibited.

Also clarify that the only way to get an internal representation
is from DECODE, FROM_UNIFORM_BYTES, or from a permitted operation
applied to an existing internal representation.

>    5.1 and 5.3 of hash-to-curve), e.g., "Ristretto255-Hash".

Also, rename FROM_UNIFORM_BYTES to either FROM_BYTES or FROM_STRING,
and remove the length and distribution requirements on the input.
The hash-to-curve document handles the uniformity internally while
ensuring that conforming usage meets relevant security requirements.
There's no reason to make higher-level protocols reinvent the wheel.

Again, happy to write a PR for this and/or read future drafts,

-=rsw

---

From: Henry de Valence <[email-masked]>
Date: Fri, 26 Jul 2019 13:09:07 -0700

(resending under IETF alias address)

Hi all,

Thanks for the detailed comments, Riad.  I'm not currently subscribed
to this list so I hope I will be forgiven if I missed any comments
which were not addressed to me, as well as for responding to points
made in various emails all at once instead of individually.

First, here are some comments on points made in the preceding
discussion, followed by comments on Riad's proposal.

I will annotate some possible clarifications with capital letters (A),
(B), (C), etc., and compile them into a list at the end.

> (likely minor) edits to the intro to help clarify this point.

The text of section 1 makes reference to Curve25519, meaning the
abstract elliptic curve, following the naming scheme posted to this
list by its designer five years ago [1], and referenced on the second
line of its Wikipedia page [2].  That email suggests using
"Curve25519" to refer to the underlying elliptic curve, "X25519" and
"Ed25519" to refer to particular DH and signature schemes using that
curve, and names for various coordinate systems found in the
academic literature.  Our draft follows this terminology.

The reason the word Montgomery never appears in the document is that
the document explicitly deals with Edwards coordinates for Curve25519,
as described in Section 2, "Notation and Conventions
Used In This Document":

> Elliptic curve points in this document are represented in extended
> coordinates in the (x, y, z, t) format [Twisted].

where [Twisted] is a reference to the HWCD08 "Twisted Edwards Curves
Revisited" paper which defined them.

We could (and probably should) add an explicit note to this section
that "Curve25519" refers to the abstract elliptic curve (A), if that
would help clear up confusion.  However, the source of that confusion
is ultimately the decision to use the same name for an X-coordinate DH
system and its underlying (abstract) elliptic curve, and then to amend
terminology a decade later, and resolving it completely is out of
scope for our draft.

> tell it does not tell me what it is.

The document does not define elliptic curve addition, because, as
described at the beginning of Section 3, "This document describes how
to implement the ristretto255 group using Curve25519 points as an
internal representation".

The document does describe how to implement the (+) operator, in
Section 3.3, which reads in its entirety: "Group addition, subtraction
and (multi-)scalar multiplication are performed without modification
using the internal representations. Implementations MUST NOT perform
any other operation on internal representations."

> Is it edwards25519 point addition?

Yes, as described in Section 3.3, quoted above.

> If so, then I just don't see how it can be true that the "internal
> representation" in Section 3 is not an edwards25519 point.

Yes, the internal representation is a Curve25519 point.  However, what
Jack said is "any mapping from ristretto255 elements", and a
ristretto255 group element is not the same as its internal
representation, as Watson alluded to.

The draft notes in Section 2 that "Each group element can have
multiple equivalent internal representations", and also in Section 4
that "ristretto255 elements are represented by curve points, but they
are not curve points ... the type ... SHOULD be opaque."

We can of course add an more explicit note in Section 2 that
ristretto255 group elements are not the same type as their internal
representations (B) if this was unclear.

Riad S. Wahby <[email-masked]> wrote:
> Here's my current best guess: ENCODE and DECODE convert ristretto255
> points into some internal representation.
>
> For the algorithms in
> Section 3, that internal representation is edwards25519, except that
> equality testing is different (specifically, it must use EQUALS) and
> maybe some other things are different (but I don't know what).
>

I don't think any guessing is required here, because all of these
points are described fairly explicitly in the draft already.

The ENCODE and DECODE functions are described on page 2 of the draft:

> *  "ENCODE", an encoding function from internal representations to
>    bytestrings so that all equivalent representations on the same
>    ristretto255 element are encoded as identical bytestrings;
>
> *  "DECODE", a decoding function from bytestrings to internal
>    representations with built-in validation, so that only the
>    canonical encodings of valid ristretto255 elements are accepted;

The provided (and allowed) operations are described on the following
paragraph, and again in Section 3.3.

And indeed, there is no obvious way to use a different curve given the
information in the draft, which is also described on page 2:

> It is also possible and allowed to implement ristretto255 using a
> different elliptic curve internally, but that construction is
> out-of-scope for this document.

> because Curve25519 has order 8 * l.

The requirement is that the "isomorphic group" provided by an
implementation is isomorphic to the ristretto255 group, not to
Curve25519, so this is not an obstruction.  (The referent of "they" is
"implementations", but we can make the sentence more explicit that the
isomorphism is to the ristretto255 group (C) since it seems to have
been unclear).

And of course, ristretto255 is not isomorphic to Curve25519, for the
reason you mention.

> the output of DECODE as defined in Section 3 is an edwards25519 point.

I think this is made clear throughout the draft for all the reasons
mentioned above (modulo adding an explicit note (A) that Curve25519
refers to the abstract elliptic curve).

> internal representations.

No, not all Curve25519 points are valid internal representations.
Valid internal representations are representations constructed via the
DECODE and FROM_UNIFORM_BYTES functions, as mentioned in paragraph 3
of Section 4 ("implementations ... MUST NOT construct group elements
except via...") and described in detail in Section 6:

> There is no function to test whether an elliptic curve point is a
> valid internal representation of a group element.  The decoding
> function always returns a valid internal representation, or an error,
> and allowed operations on valid internal representations return valid
> internal representations.  In this way, an implementation can
> maintain the invariant that an internal representation is always
> valid, so that checking is never necessary, and invalid states are
> unrepresentable.

The draft does not go into detail about criteria for validity because
it is written for implementors, and the functions-to-be-implemented
are carefully constructed so that invalid representations are
unrepresentable, so implementors don't need to worry about it.

>    intenal representations not explicitly allowed by the text of the

This is already defined up front in Section 2, "Notation and
Conventions Used In This Document".

>    edwards25519 points that are "internal representations."

I don't understand how these implementations can be normative (an
implementation MUST implement them) without making a normative choice
of curve to use internally (which prevents an implementor from
changing the curve, as is currently explicitly allowed and which you
suggest in (3) below).

The *behaviour* of the encoding and decoding is already normative
(cf. the beginning of Section 3), and the provided test vectors ensure
consistency between the encoding and the group operation.

> 1.1. Clarify in the above that inputs to ENCODE and EQUALS MUST be
> internal representations; any other inputs are prohibited.  Also
> clarify that the only way to get an internal representation is from
> DECODE, FROM_UNIFORM_BYTES, or from a permitted operation applied to
> an existing internal representation.

We can repeat the definitions of ENCODE and EQUALS from Section 1 in
Section 3, and repeat the requirements from Section 4 and Section 6 in
Section 1 to make this even more clear, but I think these requirements
are already described fairly explicitly.

> 2. As now, forbid implementors from exposing any point that is an

Yes, I agree that this should remain in the draft.

>    all of these requirements.

The header of Section 3 already allows an implementor to use any curve
model they want internally, as long as it provides an isomorphic group
with the same byte encoding.

>    and direct the reader to the birational map in RFC7748.)

I would rather direct the reader (and list it as an informative
reference (D)) to the Ristretto notes linked in the document, which
explain in detail which other curves can be used internally and the
particular role that the birational map plays in the Ristretto
construction (see comments on 5 & 6 below).

>    and thus no group isomorphic to it is either.

The Section 3 header talks about groups of order l because
ristretto255 is such a group, and a compatible implementation provides
a group isomorphic to the one described in the document.

>    inversion, and multiplication on edwards25519.

These operations are already explicitly allowed, and the group
operations are already required to match the ones specified in the
test vectors.  As noted in Appendix A.1, these test vectors encode
elements with a defined relation to each other in terms of the group
operation, so they test the definition of the group operation as well
as the definition of the encoding.

Since ristretto255 is not isomorphic to Curve25519 for the reason you
mentioned above -- they're different groups, one of which MAY be
implemented using the other -- I don't think it makes sense to define
anything in terms of isomorphism to Curve25519.

>    only the underlying algebraic properties.

I think these are already covered by the fact that their
implementations are not normative (cf. your suggestion 1), and the
Section 3 header.  Implementations using different curves internally
will presumably have different implementations of encoding and
decoding.

As explained in the Decaf paper, as well as the
https://ristretto.group website referenced in Section 1, Decaf and
Ristretto initially construct an encoding on a Jacobi quartic, then
transport that encoding along a 2-isogeny to one of a number of
possible curves which are used internally to actually perform group
operations.

Of course, this complexity only plays a role in the abstract
construction, *not* in the concrete implementation: these maps compose
into the simple formulas in the document, each of which fit into half
a page of ASCII spec.

An implementation which wanted to use a different elliptic curve
internally (say, the 4-isogenous "small-d, Ed448-style" Edwards curve
described on the Ristretto website and below) would have different
encoding and decoding formulas, because those formulas are obtained by
transporting the Jacobi quartic encoding along a different 2-isogeny.

In fact, the birational map you mentioned in suggestion 3 is already
used to construct the encoding given in the draft, by transporting the
Jacobi quartic encoding along a 2-isogeny to the Montgomery form of
Curve25519 and then along the birational map to the Edwards form, as
explained on the Ristretto website.

This construction places the Edwards form of Curve25519 (a "large-d,
Montgomery-style" Edwards curve) in the correct spot on the isogeny
graph, so that the Jacobi-Edwards 2-isogeny lands on a "small-d,
Ed448-style" Edwards curve, allowing an implementation of ristretto255
to use this curve, which is 4-isogenous to Curve25519 but has a
smaller (17-bit) Edwards d parameter, while retaining wire-compatible
(even for hash-to-group, as described below!) with implementations
which use Curve25519.

However, as described in Section 1, these details are out-of-scope:
"It is also possible and allowed to implement ristretto255 using a
different elliptic curve internally, but that construction is
out-of-scope for this document."

Instead, the draft, as written, has two goals:

1. To provide test vectors for the ristretto255 encoding, decoding,
group-operations, and from-uniform-bytes functions (Appendix A), which
provide sufficient rigidity that passing them enforces compatibility
between implementations, regardless of which curve is used internally;

2. To provide concrete formulas aimed at allowing implementors to add
support for ristretto255 to an existing Ed25519 implementation.  I
think that the speed with which a conformant ristretto255
implementation was added to libsodium following publication of the
draft is illustrative of its success with respect to this goal.

> 7.1. Also, rename FROM_UNIFORM_BYTES to either FROM_BYTES or FROM_STRING,

I don't think this suggestion is a good idea, for a number of reasons:

1. edwards25519-SHA256-EDELL2-RO is not compatible with ristretto255, as
it does not produce valid internal representatives;

2. even if it did, ristretto255 implementations are not required to
use Curve25519 internally, so the hash-to-group method cannot be
defined in terms of Curve25519;

3. ristretto255 already provides a hash-to-group method, which is defined
so that implementations remain wire-compatible even when changing the
curve used internally, as noted in the Ristretto website and the Decaf
paper;

4. requiring use of a specific hash function is a layering violation,
as the definition of an elliptic curve should not depend on use of a
particular symmetric primitive.

The FROM_UNIFORM_BYTES function provides a generic hook which handles
all of the details specific to the ristretto255 group, whose input
uniformity requirement retains composability with various symmetric
constructions.  This isn't requiring higher-level protocols to
reinvent the wheel, but retaining compatibility with them.

For instance, why should a higher-level protocol that everywhere else
uses domain-separated SHA3 be forced to use SHA2 for hash-to-group?

Or, consider a protocol that uses a duplex construction to ensure that
hash output is not just bound to a single domain separator, but to an
entire message transcript with arbitrary application domain separation
messages (e.g., https://merlin.cool).  Why should it be forced to
launder its domain-separated hash output through a second HKDF
construction?

Of course, it would be most preferable to achieve compatibility
between the ristretto255 draft and the hash-to-curve draft.  But since
the hash-to-curve draft describes hash-to-curve methods for various
elliptic curve groups (P-256, secp256k1, Curve25519, etc), while this
draft is tightly focused on describing a specific group, it seems like
the cleaner layering would be for the hash-to-curve draft to
incorporate this draft by reference, and use this draft's
FROM_UNIFORM_BYTES function to define a

ristretto255-SHA256-RISTRETTO-RO

or similar (I'm not 100% confident in my understanding of your naming
scheme).

In this way, the hash-to-curve draft defines hash-to-curve methods for
various elliptic-curve-based groups (P-256, secp256k1, Curve25519, and
ristretto255), while the ristretto255 draft remains focused on
definining a single group and retains compatibility with other
symmetric constructions (e.g., sponge constructions).

Cheers,
Henry de Valence

(A): Clarify that "Curve25519" refers to the abstract elliptic curve,
as described in the references below.

(B): Copy the note that ristretto255 elements and their internal
representations are distinct types from Section 4 to Section 2.

(C): Clarify that the isomorphism is an isomorphism to the
ristretto255 group.

(D): Add the Ristretto website as an informative reference, not just
an in-body link.

[1]: https://mailarchive.ietf.org/arch/msg/cfrg/-9LEdnzVrE5RORux3Oo_oDDRksU
[2]: https://en.wikipedia.org/wiki/Curve25519

---

From: "Filippo Valsorda" <[email-masked]>
Date: Fri, 26 Jul 2019 23:02:54 +0200

The discussion about draft-hdevalence-cfrg-ristretto so far brought up a
number of areas worth clarifying which we plan to address in -02. Aside
from that, if I'm not mistaken, the only other topic of discussion was
the interaction with draft-irtf-cfrg-hash-to-curve.

I am bringing it into its own thread and adding my remarks at the bottom.

> symmetric constructions (e.g., sponge constructions).

I agree with Henry, and I think it helps to think about it in terms of
implementations. As I see it, there are three options.

Option 1: use an existing hash-to-curve method

This is definitely unworkable. A method that hashes to Curve25519 points
is not fit for hashing to ristretto255 because ristretto255 internal
representatives are a different type from Curve25519 points. Internal
representatives are an opaque type that might or might not be a wrapper
around a Curve25519 point, and there's no map between Curve25519 points
and internal representatives.

Option 2: specify FROM_UNIFORM_BYTES in hash-to-curve

This would require putting a method that returns a ristretto255 internal
representative in hash-to-curve. On top of moving a lot of the Ristretto
math to hash-to-curve, that would leak all the complexity of specifying
behavior without mandating the actual curve to the hash-to-curve
specification, and is a major breach of the ristretto255 abstraction.

Think about a ristretto255 implementation,
https://github.com/gtank/ristretto255 for example. The spec requires
it to keep its element type opaque (to preserve the group abstraction,
to guarantee interoperability with other implementations, to prevent
misuse, to allow switching curve, ...), so there is no way for a
hash-to-curve implementation to construct an element from an internal
representative. It's internal after all!

Consequently forcing ristretto255 implementations to also implement
hash-to-curve and making it impossible for generic hash-to-curve
implementations to offer the ristretto255 method sounds wrong.

Option 3: use FROM_UNIFORM_BYTES from hash-to-curve

This is what Henry is suggesting, and it looks like the natural
separation of concerns to me. hash-to-curve is in charge of
parametrizing hashes, defining domain separation, and all the things it
already does. It then generates uniform bytes, and ristretto255 defines
the interoperable map to an opaque group element.

Of course, we'd be happy to contribute such a method to hash-to-curve,
but unlike Option 2 it should be fairly trivial (which in itself
suggests we hit the right level of abstraction).

---

From: "Riad S. Wahby" <[email-masked]>
Date: Fri, 26 Jul 2019 19:16:25 -0700

Hi Henry,

I really appreciate that you took the time to read my emails and
give a point-by-point response.

From your email, it's obvious that the document is clear to you.
This is great! since that's obviously a prerequisite for writing a
good document. My purpose in reviewing your document was to try and
give you the perspective of a reader who is familiar with the area
but does not already have the meaning of your document committed
to memory. So while I appreciate the in-depth response and your
attempts to clarify, probably we can agree that explaining what you
meant to write on this mailing list doesn't scale to the (hopefully)
many readers who will come after me.

This is closely related to the "curse of knowledge": it's very hard
to know whether something you've written is clear or not, because of
course it's clear to *you*. That's why we have reviewers: because this
is (the?) one aspect of the document for which ignorance is a virtue.

...and I am very virtuous :)

As one high-level comment: many of your responses are dedicated to
carefully maintaining the fiction that there exist curves other than
those isomorphic to Curve25519 which could be useful for implementing
ristretto255. To me, this idea is plainly unhelpful. The reality is
that, to first order, *every* ristretto255 implementation will use
edwards25519 or curve25519 internally. The document should be written
to acknowledge that reality, and to assist those implementations.
Implementors who know enough to get fancy don't need your help.

To that end, there are several spots below where one might be tempted
to respond "ah, but that's only true if the internal representation
is isomorphic to Curve25519." Yes! and so it is (true).

Another high-level comment: many of the explanations you've given
about why things work or don't work are, frankly, quite hand-wavy.
This relates to but is not identical to the "fiction" issue. As
a specific example, (far) below I've quoted your line about how the
hash I suggested does not give valid internal representations. I think
everyone on this list would appreciate, when you make such a claim,
if you would back it up with a technical justification. I'm happy
to dig into the details on my own, but at some point it goes from
"reviewing your document" to "rederiving your document," and that
just wastes time and makes me less useful as a virtuous reviewer :)

Finally, lest it be lost in the back-and-forth soup below: the primary
reason I'd like to see Ristretto incorporate hash-to-curve by reference
is that it means that there's one source of truth for implementors
of conforming mappings to elliptic curves, which in turn means that
one Elligator2 implementation suffices for any application involving
Curve25519 (including, per the above, Ristretto). To me, this is far
more important than an extraneous HKDF invocation here or there. To
be clear: the hash-to-curve document can change to accommodate this.

Some further inline comments below.

Henry de Valence <[email-masked]> wrote:
> That email suggests using "Curve25519" to refer to the underlying
> elliptic curve, "X25519" and "Ed25519" to refer to particular
> DH and signature schemes using that curve, and names for various
> coordinate systems found in the academic literature.  Our draft
> follows this terminology.

Your draft is a proposal to create an IETF document; as such, it
certainly seems sensible to write it using the same terminology that
other IETF documents do. That means, in this case, citing RFC7748
and using its terminology.

At a guess, your target audience is not going to trawl the CFRG
mailing list for djb's posts explaining your document.

> Yes, as described in Section 3.3, quoted above.

I'd go back and check that quote again. It certainly does not say
anything about edwards25519 point addition.

With apologies for repeating myself: you know what you mean; your
readers do not, because they do not assimilate every word of the
document in a single pass---especially words several pages away.

> Curve25519, so this is not an obstruction.

In that case, it's definitionally true. I'd strongly recommend
removing it, as it does not help the reader to understand what's
going on and---as we've now seen---can have the opposite effect.

> refers to the abstract elliptic curve).

See comments above re: curse of knowledge.

> Conventions Used In This Document".

This certainly seems like the right place for it, but please compare
the content of my proposed definition to the content (read: the
words on the screen) of Section 2. To my eyes, anyway, the latter
is incomplete.

> of curve to use internally

Apologies that I was not clear. My feedback is that the document
*should* make this choice, up to isomorphisms. Otherwise it is not
specific enough to help implementors do their job.

To say it another way: the document should enshrine Curve25519
(the abstract curve) as *the* correct internal representation.
To do that, the functions should be written in terms of some concrete
instantiation---Edwards seems reasonable---and should detail precisely
the ways in which implementors may inject isomorphisms in order to
arrive at the curve they want to operate on internally.

This was the content of my suggestions #1, #3, and #6. Again, sorry
that I was unclear the first time.

> are already described fairly explicitly.

I'm not asking for repetition, I'm asking for clarification.
Specifically, my request is that "internal representation" should be
completely defined, in one place in the document, in terms of (and
with references to concrete definitions of) the operations that are
allowed and disallowed.

By the way, the clarity problem I'm alluding to is perfectly
illustrated by the mishmash of section numbers you had to list above.

> with the same byte encoding.

The point of this comment is that it does so only implicitly, and it
does not give sufficient explanation *how* this should be done.

> construction (see comments on 5 & 6 below).

This suggestion was grounded in an (unstated) assumption, namely,
that many readers will be using this document to add ristretto255
support to an existing Curve25519 implementation. If this is true,
then readers of this document will likely be familiar with RFC7748
already. Those readers will appreciate if you anchor this document
to another one with which they're familiar.

I see no issue with *also* referring interested readers to the details
at https://ristretto.group, or to informative implementations, etc.
But those should not be required reading.

> a group isomorphic to the one described in the document.

This is too high-level a statement, possibly for the whole document
but certainly for Section 3. And as I observed above, this is the
definition of a compatible implementation, not an explanation of how
to build one.

> test vectors.

I understand that Section 3.3 is trying to say this. Again, this is
clear *to you*. I am suggesting a way of making it clear to everyone
else. This suggestion is related to what I said above about defining
"internal representations" up front in terms of what's allowed and
what's not.

> anything in terms of isomorphism to Curve25519.

Section 3 appears to disagree with you.

Again: the point is to explicitly define what *concrete* operations
are allowed on internal representations.

> Section 3 header.

Yes, of course they're covered, and yes, of course this is clear to
you. But no, unfortunately, the document as it stands does not make
this clear to the reader.

Put another way: your response makes clear that the reader has to
extract this information from a synthesis of several paragraphs of
text. In fact, it seems from your response ("I think...") that even
you---the author of the document!---are not certain whether these
are covered or not.

> https://ristretto.group website referenced in Section 1
[snip, with apologies]

The document needs to be written clearly enough to stand alone as a
reference for implementing Ristretto.

Pace Watson, I don't care if it justifies the algebra---citations for
that are better---but if a reader has to go to https://ristretto.group
to make sense of this document, that's a failure.

> draft is illustrative of its success with respect to this goal.

I think you're missing a goal, namely, to allow a competent implementor
generally familiar with the area to create a de novo implementation of
Ristretto using this document, any referenced RFCs, and a reasonable
set of standard reference books.

In particular, readers should not need to consult your website or
your code in order to get things running.

> it does not produce valid internal representatives;

Whoops, this is true! Sorry :)

But as far as I can tell, only because of the cofactor clearing
step. Elligator to edwards25519 and a multiplication by 2 (rather than
8) gives [2]E, whereupon torque-and-quotient gives a valid encoding.
So it would appear that this is easily fixed.

If that's not right, could you please clarify precisely the issue?

> defined in terms of Curve25519;

Given the current definition of FROM_UNIFORM_BYTES, you have to admit
that this is pretty hilarious as written.

In any case, it's false. As an example, the Decaf map is to a Jacobi
quartic isogenous to Curve25519, but another completely valid way of
defining the map would be via a map to some concrete instantiation
of Curve25519 followed by a map to the quartic. Something slightly
more complicated but analogous works for Ristretto.

The point is, the above is not a real objection; it's another piece
of fiction-scaffolding supporting the claim that Curve25519 isn't
the internal representation.

> curve used internally, as noted in the Ristretto website and the Decaf

Taken together, my suggestions (modulo the cofactor clearing issue)
also give a map that is consistent independent of the internal
representation, so this is not an argument against what I've suggested.

> particular symmetric primitive.

This is a fair criticism.

(But of course, specifying hash-to-curve alongside a curve is also
a layering violation, since there are plenty of mappings to choose
from, just like there are plenty of cryptographic hash functions to
choose from.)

The solution is not, I think, to redefine Elligator in the Ristretto
document when it's already available in the h2c doc. Instead, the
right solution is probably to define a family of hash-to-curve suites,
parameterized in H, that use Elligator2 to map to edwards25519,
and map the result to [2]E.

Happy to chat more about this if there are details that seem wrong
or if we can make life easier for you in h2c, of course.

> Why should it be forced to launder its domain-separated hash output
> through a second HKDF construction?

It sounds so dramatic when you say it this way :)

But the reality is, it makes no difference to the performance, and it
(extract-and-expand) is far more misuse resistant. To me, the benefit
(preventing mistakes) outweighs the cost (~none).

Anyway, to me the above is missing the point. As I said (far) above,
forcing an implementor to build yet another hash-to-curve construction
just for ristretto255 when they could have have used the one they
already wrote for edwards25519 is a failure. Between "invoke HKDF one
more time before doing a slew of curve ops" and "implement another
tricky hash-to-curve algorithm," I know which one seems worse to me.

> it seems like the cleaner layering would be for the hash-to-curve
> draft to incorporate this draft by reference

Hey, that's a plausible solution, too! I'd be curious to hear what
other people think. I'm in favor of whatever is cleanest and clearest.

-=rsw