Re: [Cfrg] ECC reboot

[Watson Ladd <[e-mail]>]

On Oct 23, 2014 1:52 PM, "Phillip Hallam-Baker" <[e-mail]>
wrote:
>
>
>
> 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.

This is wrong. Many vector units operate on two independent halves
internally, introducing an extra delay for any operation that crosses the
halves. Furthermore, maximal gate delay times force strict limits on
circuit depth.

ADOX, ADCX, and MULX are nothing special in comparison.  They use existing
hardware in slightly nicer ways. The carryless multiply and AES
instructions are much more similar to what you propose, and took a long
time to get into silicon. Even then the multiply instruction was a
sixteenth of the size of what you propose.

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

But it impacts performance in ways that don't show up in benchmarks. If you
think 512 can go faster, roll up your sleeves and send it to SUPERCOP. If
what you want is hardware support, you will have to explain why it hasn't
already happened.

If you want to say performance doesn't matter, and the prime picking we use
isn't rigid enough, make that argument.  But don't say "this is faster"
when the benchmarks say otherwise.

Sincerely,
Watson Ladd
>
>
> 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.
>
>
> _______________________________________________
> Cfrg mailing list
>[e-mail]
>http://www.irtf.org/mailman/listinfo/cfrg
>