Re: [Cfrg] ECC reboot

[Phillip Hallam-Baker <[e-mail]>]

On Thu, Oct 23, 2014 at 4:14 PM, Michael Hamburg <[e-mail]> wrote:

>
> > On Oct 23, 2014, at 11:22 AM, Andy Lutomirski <[e-mail]>
> wrote:
>
> Goldilocks should work well in 512-bit registers.  If Intel has
> single-cycle PMUL[U]DQ on 512 bits, that will become the largest multiplier
> on the chip: 8x32x32 -> 8x64 compared to the 64x64->128 scalar multiplier.
> The ARM NEON Karatsuba implementation should translate pretty well to that
> primitive, but the devil is in the details.
>

OK so that is an important data point.

What I am trying to get to here is to get people to explain those details
in terms more abstract than 'I ran X on Y and got time Z'.


On the other hand, Broadwell is slated to introduce ADCX/ADOX scalar
> carry-handling primitives which should mitigate some of the carry handling
> issues for packed NUMSp512 math.  It probably won’t be as big a difference
> as AVX-512, but it’s something.
>

Thats the point, if there is a 512 bit wide register and there is an
application that can be accelerated if 512 wide instructions are available
there is a reasonable expectation that we can get them implemented.

Adding in a Manchester carry chain isn't a big cost, nor is providing a
primitive for a fast 512 bit multiply. 512 bit multiply



> @PHB: How much experience do you have actually implementing elliptic
> curves or similar primitives?  You have an awful lot to say about why 512
> will be fast in the long run, and I’m curious where that comes from.  Is it
> “just common sense”, or have you done experiments?
>

Having built large parallel machines and used them for very large tasks, I
am going by a little more than common sense. 512 bit arithmetic operations
are certainly going to be faster than 521. Now what that implies for
implementing
Knotted Weierstrass curves with a double Irish Dutch sandwich or whatever
is what I am looking for an explanation of in terms that I can explain to
the general security community.


What I began arguing is that 521 is going to break stride on a 512 bit
architecture and should be taken off the table unless the speed advantage
is enormous. I don't think we need to implement the algorithm to see that.

Now if you are arguing that 512 will also break stride on a 512 bit
architecture then that is an important data point that by the same logic
argues for looking at a curve that does fit and maybe Golilocks is actually
the one.

But before conceding that point I would like to see more of an explanation
of the optimization being used and how much it delivers.