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

[Michael Hamburg]

Ah, thanks for this Dan.  I didn’t see the RWC talk, just the slides, and I didn’t realize that it was in service of 2^256-189 as well.

I do think it makes sense to consider 2^379-19 for curves around that level, though of course I like Goldilocks and 3-mod-4 primes in general.

On their “comparison” slide did they mention that the Ed448-Goldilocks and E-521 impls both use point compression, and therefore have a 10% penalty vs their Ted37919 numbers?  It seems a little dishonest if they didn’t.

— Mike

> On Jan 19, 2015, at 7: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.
> 
> A closer study of implementation techniques shows that choosing mediocre
> primes such as 2^256-189
> 
>   * doesn't hurt typical full-radix implementations but
>   * hurts typical reduced-radix implementations.
> 
> 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.
> 
> ---Dan
> _______________________________________________
> Curves mailing list
> Curves at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves