Re: [Cfrg] New names for draft-ladd-safecurves

[Robert Ransom <[e-mail]>]

On 1/20/14, Mike Hamburg <[e-mail]> wrote:
>
> On Jan 20, 2014, at 9:06 PM, Robert Ransom <[e-mail]> wrote:
>> I would suggest using the Montgomery-form x coordinate with the sign
>> bit of the Edwards-form x coordinate.  (In fact, I *did* suggest that:
>> <http://www.ietf.org/mail-archive/web/cfrg/current/msg03868.html>
>> <http://www.ietf.org/mail-archive/web/cfrg/current/msg03870.html>)
>
> Amusingly, if you say that "sign" is "Jacobi symbol" (when p==3 mod 4), the
> two are the same for q-torsion points.  But either way, the difference is a
> couple of field muls vs a slightly messier spec.

The least significant bit of the least positive residue is easier to
compute during point compression, and is well-defined regardless of
the field order, so I would use that instead.

>> And yes, the Brier-Joye formulas to recover Montgomery-form y after
>> the Montgomery ladder would be faster than Brauer's algorithm on
>> Edwards-form points for variable-base single-scalar multiplication.

> Is this still true for large curves?  I don't think it's true
> asymptotically, and if people switch from inverse-by-exp to
> inverse-by-blind-and-EGCD, then you lose your free square root and the
> tradeoff might happen before 521 bits.  You might get your freebie back
> again if you spec that sign is Jacobi symbol and use a blind EGCD
> inverse-and-Jacobi-symbol, but again this only works for p==3 mod 4.

The Montgomery-form ladder takes 5M+4S+1*param+... per scalar bit.

Edwards-form Brauer (assuming a=-1) takes 3M+4S+... per doubling, and
1M (conversion to extended coordinates) + 7M+... (madd-2008-hwcd-4;
assuming the table is affine) per scalar limb, so it could (just
barely, counting multiplications only) appear to break even using
4-bit limbs.  But the table precomputation for that includes multiple
point additions and an inversion, and each 4-bit scalar limb requires
a constant-time lookup from a 7-element table, so even asymptotically,
you're eaten by overhead.


Robert Ransom