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

[Watson Ladd <[e-mail]>]

On Wed, Jul 24, 2019 at 5:48 PM Riad S. Wahby <[e-mail]> wrote:
>
> 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?)

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.