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

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

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

Jack Grigg <[e-mail]> 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.

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

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

> It is an explicit design decision to define the Ristretto API solely in
> 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.

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

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.

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

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

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

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

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

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