[curves] Ed448-Goldilocks on NEON; point encoding

[Trevor Perrin]

On Wed, Mar 11, 2015 at 3:34 PM, Michael Hamburg <mike at shiftleft.org> wrote:
>
> Second, there is a question of point formats.  Ed448-Goldilocks may end up in TLS or other standards alongside Curve25519, and so it will probably need a point format which matches *25519 point formats.  The most likely option would be that for ECDH, we would use x-coordinates on an isogenous Montgomery curve with small A = 2-4*-39081.  This allows reuse of the Curve25519 ladder code, though it loses the advantages of the fancy point formats in the original Goldilocks and in the Decaf branch.  Perhaps one of those should be brought back for signatures, but again possibly not because parallel construction to Curve25519 is desirable.


Agreed that aligning with 25519 is good.

I like the Montomgery-x for ECDH.  For other protocols I like adding
the Edwards sign bit to that for a "full-format" public-key which can
be easily converted to a "DH-only" key (this isn't exactly a unified
format, but it's close).

But there are ergonomic questions about how DH-only and full-format
keys would interact [1]:
 (A) Sign bit omitted when converting full -> DH-only
 (B) Sign bit ignored when converting full -> DH-only
 (C) Sign bit always included
 (D) Sign bit always excluded (Jivsov or Ransom tricks)

Part of the difficulty comes from the idea of overloading the unused
bit in Curve25519 Montgomery-X public keys as a sign bit.  That means
the receiver can't distinguish public keys with omitted sign bits or
sign bit = zero.

Since that overloading can't be done in Goldilocks anyways, perhaps a
cleaner and more aligned approach would be to *not* overload that bit,
and always store the sign bit in a separate byte.  So:

DH-only keys:
 - 32 bytes Curve25519 (mont-X)
 - 56 bytes Goldilocks (mont-X)

Full-format keys:
 - 33 bytes Curve25519 (mont-X + ed-sign)
 - 57 bytes Goldilocks (mont-X + ed-sign)

This would eliminate ambiguity in protocol specs between whether a
DH-only or full-format key was expected, and whether a sign bit is
present or not.

Thoughts?

Trevor