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

[Mike Hamburg <[e-mail]>]

On Jan 20, 2014, at 10:44 PM, Robert Ransom <[e-mail]> wrote:

> 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.

Yeah, I love the Jacobi thing because it's a cool trick, but I still think the low bit is probably better for these reasons.

>>> 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.

For practical purposes, you're right: it's probably at most a wash even at longer bit lengths.

I actually measured it for a 252-bit prime, 250-bit curve by microbenching some old code.  I measured a constant-time Edwards scalar multiply (no conversion to/from affine) vs a constant-time Montgomery scalar multiply (start in affine, but no conversion back to affine at the end). The result was pretty close, within the margin of error of the benchmark on Sandy Bridge.

The code is using "extensible coordinates" for the accumulating point (a lazy man's version of Hisil et al's extended with lookahead, which would give the same result) and gives you that 8M/add without putting the table in affine (it's in "projective half-Niels coordinates", i.e. 4-coordinate readd form).

Otherwise your math is fine.  You're trading off a constant-time lookup in a big table every k bits, and some precomputation (slightly cheaper than the lookups) in the Edwards version vs a conditional swap every bit, a multiplication by a small number and a couple of extra additions for the Montgomery ladder.

After about 300 bits, extrapolation suggests that a 5-bit window should be faster than a 4-bit one, if only marginally.  All in all, by 448 bits (extrapolating to Ed448-Goldilocks timing measurements) the Edwards implementation is maybe half a multiply per bit ahead of the Montgomery one, before compression and decompression are taken into account.

But then there's compression and decompression.  I'm pretty sure a Montgomery implementation can always use the inverse square root trick at worst, whereas Edwards always has to take a square root and a full inversion separately (to decompress and to compress, respectively).  I don't have a timing for blind-and-EGCD on me.  Maybe it's half a mul per bit, and then the whole thing is a wash.  Maybe it's 0.3, and that giant pile of complexity and memory thrashing bought you a 2% win.  Woo.

So Montgomery is the better choice on Sandy Bridge out to 448 bits and probably to 521 as well.

Cheers,
-- Mike