[Cfrg] Rigidity and performance

[Michael Hamburg <[e-mail]>]

Hello CFRGers,

I tried to send this last night, and it was delivered to cfrg but didn’t go through somehow?  So I’m trying again with an abridged version.

It’s been argued a few times here that choosing primes for performance (or performance vs security trade-off) is too flexible.  In an effort to quantify how flexible this is, I searched for primes which could be advanced on these grounds in the range of about 192 to about 256 bits of security.  Specifically, I searched for primes which have something about their shape to recommend them (fast Montgomery or Barrett reduction, or Solinas or nearly-Solinas form).  I restricted my attention to primes which have the carry-handling properties that DJB and I have been recommending, on either 64-bit platforms or both 64-bit and 32-bit.

I also searched for numbers which had a nice shape and were not prime themselves, but were divisible by a large prime.

I then wrote a partial order on these primes, where one prime is potentially better than another if it’s 3 mod 4, or 5 mod 8, or larger, or sparser, or has fewer limbs, or has fewer non-1 coefficients, or has a Montgomery-friendly or Barrett-friendly or Karatsuba-friendly shape.  I eliminated primes which could not be defended because another prime in the same class was clearly better on every axis.  For example, 2^416 - 2^208 - 1 has the same performance as 2^448 - 2^224 - 1 on almost any platform, has the same sparsity and shape, the same residue mod 8, and so on, but it’s smaller and therefore has a worse security vs performance tradeoff.

Surely I missed some, but the goal of this exercise was to determine whether the number of primes which can be advanced on security vs performance reasons is in the dozens, or in the thousands or millions.  Here is what I found:

Performance should be fine on 32-bit or 64-bit machines:
2^521 - 1
  NIST-P521, E-521, of course.

2^392 - 2^280 + 1
  Good on 32-bit or 64-bit machines; 14 or 7 limbs
  This might not be a terrible idea at 192-bit security, since it falls within the 4-rho-bit limit set by Kenny.
  Too bad it’s 1 mod 8.

2^414 - 17
  Curve41417.

2^448 - 2^224 - 1
  Ed448-Goldilocks.

 2^416 - 18*2^364 + 1
  This is probably actually terrible, but it’s suitable for signed Montgomery reduction.

 2^408 - 13*2^204 - 11
  The best 5-mod-8 not-quite-Solinas-quadratic prime.  Probably terrible.

 (2^424 - 2^212 - 1) / 11
  Faster than the above prime but has a “cofactor"; clearly worse than Goldilocks unless you need 5 mod 8.

Performance is only good on 64-bit machines:
2^406 - 2^174 + 1
  Solinas, 7 limbs.

2^480 - 2^240 - 1 
  Ed480-Ridinghood.

2^480 - 47
  Nice except that it’s 1 mod 8.

 2^468 - 17
  3 mod 4.  There might be a larger prime with a bigger coefficient; I only searched up to -50.

 2^470 - 35
  5 mod 8.

 2^456 - 8*2^399 - 1
  Montgomery form.

As listed, some of these primes are probably not actually good enough to be advanced even on performance grounds, but then again, there are probably some other options which could be advanced.

Of this baker’s dozen of primes, four have already been proposed for cryptographic purposes.  This might just mean I’m not very creative, but it might also mean that the space of high-performance primes isn’t all that large.

Cheers,
— Mike