[curves] The great debate over point formats (Mike Hamburg)

[Michael Hamburg]

On Feb 20, 2014, at 12:19 PM, Samuel Neves <sneves at dei.uc.pt> wrote:

> On 02-02-2014 21:52, Michael Hamburg wrote:
>> I was referring to the Weierstrass form with this comment, not the prime shape.  I agree with Robert and Watson from a few posts ago (and, it seems, with you) that it’s dangerous to try to reuse Weierstrass implementations with new curves, because they’ll have the problems of the old ones (incomplete formulas) and the new (cofactors), and possibly worse ones from the combination (cofactors leading to corner cases).
> 
> The recent report by Bos et al [1] might be helpful here to get actual
> drop-in replacements to the NIST curves. The reported speeds of the
> proposed Weierstrass curves are not so bad in comparison with Edwards,
> although those cycle counts are still rather high compared to the
> current state of the art.
> 
> [1] https://research.microsoft.com/apps/pubs/default.aspx?id=209303

That’s a neat report.  I look forward to seeing their source code.  Their timings look competitive, especially for the 384-bit curves.

I’m a little bit surprised that their variable-base Edwards implementation is so much faster than the Montgomery ladder.  It helps that they aren’t compressing points, but I would still expect it to be closer.  $w$=7 also seems pretty large, and I wonder how they’re handling constant-time lookups into a table that size.

I’m pretty sure they’d get significantly better numbers for fixed-base with a signed-all-bits-set comb.

It’s not clear whether drop-in replacements are desirable, but these seems like good options if we want to go that route.

Cheers,
— Mike