Re: [Cfrg] Point format for Edwards curves

Resending with more information because it didn’t seem to go through last time?

I agree that CFRG really ought to choose a point format sometime soon, and (x,sign y) is as good as any.

If you want to spend complexity to get a point format compatible with the curves draft, please consider the "half-caf” solution, which is related to Jivsov’s trick: Montgomery x such that Montgomery y/x is positive, or 0 for the cases Curve25519 would say 0 (i.e. the identity and 2tor points).  Positive means even, or in [0,(p-1)/2], or similar.  The point encoding can be found by replacing (x,y) with (1/x, -y/x^2) if x/y is odd, since this changes the sign of y/x.  No adjustment to the secret scalar is required.

This method quotients out the 2-torsion of the group (or to be precise, one of the 2-torsion points if in case there’s more than 1).  This causes no problems with the final output if you clear the cofactor, or use the same encoding for the output, or both.  This means that it can interoperate with the systems in the curves draft, which clear the cofactor (but of course do not use the same encoding for output).

Using this change does mean that if you need to compare two points internally for some reason, and you haven’t cleared the cofactor yet, then you need to compare (in Edwards coordinates) both X:Y:Z and -X:-Y:Z.  (In the decaf version of this you only need to compare X:Y, so it actually makes your equality checker simpler, but I haven’t checked whether that works for half-caf.)  For SPAKE you don’t ever compare points, so this doesn’t matter.

Anyway, I think that this trick is simpler, faster and less stateful than Jivsov’s trick, and it generalizes better to other protocols.

— Mike

> On May 17, 2015, at 8:56 PM, Andrey Jivsov <crypto@brainhub.org> wrote:
> 
> On 05/16/2015 03:02 PM, Watson Ladd wrote:
>> Dear all,
>> 
>> I hope to upload version 02 of my SPAKE2 draft soon, however, I was
>> hoping to have points on Ed448Goldilocks and Ed25519 in it. This can't
>> currently happen because we've not decided on a point format for
>> Edwards curves. The existing point formats in the CFRG draft will not
>> work because I need addition. I'm aware this has taken quite a bit of
>> conversation spread out, but something like a little endian y
>> coordinate and sign bit of x doesn't seem to be wrong enough to not
>> put forward.
> 
> The sign bit of T can also be implicit when T=wM+xG in your draft is required to have the positive 't_x' for T={t_x, t_y}  (or "compliant" T). The "encoding" of T can be done very efficiently because the sender chooses a random x.
> 
> https://tools.ietf.org/html/draft-jivsov-ecc-compact-05#section-4.2.3 describes the algorithm for the sum of points.
> 
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg