[curves] Balancing reduced-radix and full-radix performance for extra-strength primes

[Watson Ladd]

On Mon, Jan 19, 2015 at 8:26 PM, Trevor Perrin <trevp at trevp.net> wrote:
> On Mon, Jan 19, 2015 at 5:03 PM, D. J. Bernstein <djb at cr.yp.to> wrote:
>> http://bench.cr.yp.to/impl-scalarmult/curve25519.html compares speeds of
>> various Curve25519 implementations on various platforms. Longa was
>> presenting a small extract from this data.
>>
>> For "64-bit" platforms the best non-vectorized radix is sometimes 2^64,
>> sometimes 2^51, for reasons explained in the Ed25519 paper. Vectorized
>> speed records---e.g., speed records on typical smartphones---typically
>> use radix 2^25.5.
>>
>> Longa seemed to be trying to mislead people into believing that this
>> platform variation in _implementation_ techniques creates a platform
>> variation in _prime_ choices. It should be obvious that these data
>> points say nothing about prime choice: they're all for one prime.
>
> You're disputing his Slide 9 I think ("Comparison of x64
> implementations Unsaturated versus Saturated"). That slide may be
> simplistic, but his overall point seems correct that platform
> variation in implementation techniques might favor different primes.
>
> It seems like you and Mike agree that full-radix might be more
> efficient on some platforms.
>
> It also seems true that some primes will be more or less efficient in
> a full-radix implementation, For example, I would think primes that
> slightly spill over into the next word are less efficient in
> full-radix (like 2^389-21, or 2^2521-1).

This would seem to me its the only effect if we use Barrett reduction. Or
am I not understanding the algorithms used in the full radix case?

In particular, the reason I picked 2^389-21 was the complaints about
dropping security below 384. But now it seems we can go down much lower: it
may be that 2^379-19 is the best choice in exponents from 352 to 384. But
my guess is all these other primes have the same speed on full radix
implementations.

Of course, users care what the fastest implementation on a CPU is, not
whether it uses full or reduced radix.

>
> So his argument that we should consider full-radix when choosing
> performance-oriented primes seems reasonable to me. Seems like we
> should try to get more analysis and timings for full-radix Ted37919,
> Curve41417, Goldilocks, E-521, etc.
>
>
>> A closer study of implementation techniques shows that choosing mediocre
>> primes such as 2^256-189
>
> He was using this argument for 2^379-19, not 2^256-189. Obviously
> 2^256-189 was chosen based on different criteria, with less emphasis
> on performance.
>
>
>> In other words, switching to mediocre primes hurts some platforms and
>> doesn't help others. To avoid seeing this damage, one has to ignore all
>> the reduced-radix implementations and ignore all the platforms where
>> those implementations are best---and even within these blinders there's
>> no advantage to the mediocre primes. Not A Tough Decision(tm).
>>
>> I'm not saying that at _every_ security level there's a unique standout
>> cross-platform prime; I'm just saying that Longa wasn't looking at the
>> right data for the decision that he claimed to be interested in.
>>
>>> 2) Full-radix may be safer and easier to implement, since
>>> reduced-radix requires "Bound analysis" to prevent inadvertent word
>>> spilling, thus is "error prone, errors are more difficult to catch".
>>
>> There's a long history of hard-to-catch errors in full-radix software.
>> https://cryptojedi.org/papers/#verify25519 is the first step towards
>> confidently getting out of this mess---and it's significantly _easier_
>> for reduced-radix software than for full-radix software.
>
> That's interesting and not intuitive to me. I'd think reduced-radix
> was trickier to implement and analyze. Huh...
>
> Trevor
> _______________________________________________
> Curves mailing list
> Curves at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves

--
"Those who would give up Essential Liberty to purchase a little Temporary
Safety deserve neither Liberty nor Safety."
-- Benjamin Franklin
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20150120/9f929e2f/attachment.html>