[curves] Ed448-Goldilocks on NEON; point encoding

Michael Hamburg mike at shiftleft.org
Thu Mar 12 14:17:55 PDT 2015


> On Mar 12, 2015, at 2:07 PM, Trevor Perrin <trevp at trevp.net> wrote:
> 
> 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)

What’s the difference between (A), (B) and (C) here?  Is it that (A) erases the sign bit, (B) preserves it but ignores it in ECDH, and (C) demands that the Montgomery ladder produce it?

> 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



More information about the Curves mailing list