Subject: Re: [Cfrg] Benchmarks: 384 vs 389 vs Goldilocks vs ... on Haswell

From: "Paterson, Kenny" <[email-masked]>
Date: Sat, 3 Jan 2015 14:40:22 +0000

Hi Mike,

On 31/12/2014 22:18, "Michael Hamburg" <[email-masked]> wrote:

>I¹m still a little bit perplexed about why you asked me to do this
>exercise.  The argument at the WF128 level seems to be about the existing
>trust and deployment of Curve25519 compared to a ³rigidly-generated²
>ed-256-mers.  At the WF192 and WF256 levels, there are no widely deployed
>³safe" curves, and it is between this same notion of ³rigidity² vs more
>³efficient² curves such as Curve41417, Ed448-Goldilocks and E-521.
>[Scarequoted because it¹s MSR's definition of rigidity, DJB and Tanja¹s
>safety criteria, and Trevor¹s and my efficiency metric.]

I asked because Watson had explicitly said that the 384-bit MGN prime
would be slower than others at WF192. I wanted to find out whether that
was really the case or not, with hard numbers:

https://www.ietf.org/mail-archive/web/cfrg/current/msg05691.html

>Is the introduction of another efficient curve near WF192 suggested to
>sway the rigidity camp¹s opinion about any of these proposals?
>Especially with people so sick of the endless arguments that they¹re
>cutting backroom deals?

The MGN proposal (draft-black) includes a specific curve at WF192, and I
simply wanted to understand its relative performance. If it was hopelessly
slow, then this would reasonably be interpreted as a negative point for
the specific curve and the MGN proposal in general (since it seems to be
an "take it or leave it" proposal, though I'd better let the proposers of
it speak to that detail). If the curve was competitive, then it could be
seen as a positive, and maybe some more people would become more amenable
to the proposal. As usual, I am trying to find a way forward here that
most people can live with.

Not sure if this answers your question or not...

>
>If you think data has a chance of moving things forward, I suggest that
>benchmarks of the Microsoft curves¹ (or at least primes¹) performance on
>ARM scalar/NEON would be more informative, because they¹d help determine
>whether the efficiency camp¹s curves are broadly more efficient and by
>how much.

I think hard data can only help, but I don't expect you to do the work
here!

Cheers

Kenny

---

From: "Paterson, Kenny" <[email-masked]>
Date: Sat, 3 Jan 2015 18:15:57 +0000

Hi Watson,

Following up on a recent message that specifically asked a question to me.

On 31/12/2014 21:01, "Watson Ladd" <[email-masked]> wrote:

>On Wed, Dec 31, 2014 at 3:01 PM, Paterson, Kenny
><[email-masked]> wrote:
>> Hi Mike,
>>
>> Thanks a lot for doing this work, especially over the holiday season -
>> it's much appreciated.
>>
>> My take-away from your work is that there's no strong reason (in
>> performance terms) to prefer P389 over P384-mers or vice-versa - the
>>8-9%
>> difference is there, yes, but could easily disappear or increase with
>> further optimisations on either side.
>
>Would you say the same about 2^255-19 vs 2^256-189? That also had a 8%
>performance increase iirc, for very similar reasons.

Yes, I would. But there, we have running code and deployment in favour of
the curve Curve25519 (used in various algorithms which may or may not be
the ones we want to recommend - still tbd). That's not the case at WF192.

> One could also try 2^382-31, which would be much more similar to the
>gain at the lower security level.

"One" could try many things. But someone has to do the work to implement
and benchmark. I asked Mike to do some work here, because he had the tools
at his disposal, and he very kindly agreed to help - thanks again Mike. In
the interests of making progress, I'd encourage others to do more of the
same.

>Furthermore, if the faster one was more optimized, and the slower one
>not as much, that would be a reasonable conclusion. But we are
>comparing a C implementation written yesterday to a handwritten
>assembler one, with the C outperforming the assembly.

Yes, I'm aware of this. And so, like you (I infer), I'd expect the
currently faster one to improve more and the gap to widen further.

Cheers,

Kenny

---

From: Brian Smith <[email-masked]>
Date: Sat, 3 Jan 2015 11:54:10 -0800

Paterson, Kenny <[email-masked]> wrote:
> performance terms) to prefer P389 over P384-mers or vice-versa - the 8-9%
> Does that seem fair to you? Please feel free to give an alternative
> interpretation if you like.

FWIW, I don't think it's fair to assume that P384-mers 8-9%
performance disadvantage can be optimized away, especially when the
thing that's 9% faster is also slightly stronger, when there are two
significantly stronger curves (P448 and P480) with the same measured
performance, and when there was significant effort (AFAICT) already
spent optimizing it. In fact, I think it would be safer to assume that
none of these curves can be optimized further, if speculation about
such things is a factor in the decision making.

Cheers,
Brian

---

From: Tony Arcieri <[email-masked]>
Date: Sat, 3 Jan 2015 15:33:11 -0800

On Sat, Jan 3, 2015 at 11:54 AM, Brian Smith <[email-masked]> wrote:

> thing that's 9% faster is also slightly stronger

If future optimizations are a concern, given the P389 implementation is
completely new, I think it should probably be given the benefit of the
doubt as to how much it can be optimized. Especially given remarks like
this:

On Mon, Dec 29, 2014 at 3:14 PM, Mike Hamburg <[email-masked]> wrote:

> The P389 code is probably less tuned than its competitors. The MS code is
> written in pure asm, but it doesn't take advantage of BMI2.  The Goldilocks
> and P389 code are C with an asm multiply/accumulate intrinsic, but I spent
> more time tuning the Goldilocks code.

-- 
Tony Arcieri