Re: [Cfrg] ECC reboot

> On Oct 23, 2014, at 11:22 AM, Andy Lutomirski <luto@amacapital.net> wrote:
> 
> On Thu, Oct 23, 2014 at 11:17 AM, Phillip Hallam-Baker
> <phill@hallambaker.com> wrote:
>> 
>> 
>> On Thu, Oct 23, 2014 at 1:49 PM, Andy Lutomirski <luto@amacapital.net>
>> wrote:
>>> 
>>> On Thu, Oct 23, 2014 at 10:41 AM, Alyssa Rowan <akr@akr.io> wrote:
>>>>> How long do you think it would take to make an HSM that supports
>>>>> our choice?
>>>> 
>>>> Depends: from what I've seen a few HSMs are flexible enough to run
>>>> whatever we choose. (I'll refrain from discussion of specific vendors:
>>>> it is for them to speak up if they wish.)
>>> 
>>> This seems like a good time to point out that Intel SGX is coming
>>> soon.  With SGX, some performance-critical HSM applications could be
>>> replaced with hardware-assisted secure *software* enclaves on
>>> supported Intel chips.
>>> 
>>> For this application, the relevant factors will be software speed
>>> (because it's just x86 software), freedom from timing attacks, and
>>> freedom from secrets being leaked in memory access patterns.
>>> 
>>> Some users might require certification, but there will be no
>>> additional hardware development effort whatsoever to add new curves.
>> 
>> 
>> And the AVX-512 extensions provide 512 bit native registers.
>> 
> 
> I feel like you're arguing against a straw man here.  Unless I
> misunderstand, the fastest implementations of 512-bit curves don't fit
> in 512-bit registers either.
> 
> Ed448-goldilocks, on the other hand, might.  Mike?

We don’t actually have alternative implementation of NUMS p512, so it’s hard to conclusively say that a 9x57 implementation will be faster, but it seems reasonably likely.

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.

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.

@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?

— Mike

>> I don't think it very likely we can persuade any chip vendor to lay down
>> extra signal lines for 521 bits and if they did a 1024 bit data path we
>> would be looking at using all of it, not just 9 extra bits.
> 
> Wait, what?  Are you suggesting using primes closer to 1024 bits?
> That seems even more excessive that 512 or 521 bits.
> 
> --Andy
> 
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg