Subject: [Cfrg] How rigid is rigid enough?

From: David Leon Gil <[email-masked]>
Date: Wed, 7 Jan 2015 22:49:16 -0800

# How rigid are rigid curves?

(About 138 reasonable choices of curve for the range 2^300
to 2^521.)

## Rigid fast primes in the range 2^300 to 2^521

Mersennes:
  2^521 - 1       == 3 mod 4   M521

(Granger-Scott have presented a fast algorithm for platforms where
the number of limbs is too small for FFT-based multiplication to
be efficient.)

A minimal Crandall is a prime of the form:

  2^n - c, !E c' < c : is_prime(2^n - c)

Crandalls are fast when log2(c) <<< limb_bits. If we want a Crandall
that's fast on any platform, this effectively restricts us to c < 32.
(LCD platform: JavaScript, where bignums typically use 12/24 limbs.)

Crandalls:
  2-bit:
    2^336 -  3    == 1 mod 4
    2^452 -  3    == 1 mod 4   C452 (???)

  4-bit:
    2^321 -  9    == 3 mod 4
    2^322 - 11    == 1 mod 4
    2^338 - 15    == 1 mod 4

  5-bit:
    2^414 - 17    == 3 mod 4   C414 (djb)
    2^444 - 17    == 3 mod 4
    2^468 - 17    == 3 mod 4
    2^488 - 17    == 3 mod 4
    2^379 - 19    == 1 mod 4
    2^389 - 21    == 3 mod 4   C389 (rr?)
    2^413 - 21    == 3 mod 4
    2^489 - 21    == 3 mod 4
    2^324 - 23    == 1 mod 4
    2^369 - 25    == 3 mod 4   C369 (???)
    2^383 - 31    == 1 mod 4   C383 (NUMS)
    2^401 - 31    == 1 mod 4
    2^495 - 31    == 1 mod 4

Define an `m`-splitting `Ridinghood` as a prime of the form:

    2^n - 2^(n/2) - 1, n|2 /\ (n/2)|2^m

There is at most one Ridinghood per `n`. (And these are,
in fact, extremely rare primes.)

(Michael Hamburg has described how multiplication modulo these
primes can take advantage of their Karatsuba-friendly shape.)

Ridinghoods:
  5-splitting:
    2^448 - 2^224 - 1 == 3 mod 4  R448 (mh)
  4-splitting:
    2^480 - 2^240 - 1 == 3 mod 4  R480 (mh)
    2^416 - 2^208 - 1 == 3 mod 4
  1-splitting:
    2^322 - 2^161 - 1 == 3 mod 4
    2^450 - 2^225 - 1 == 3 mod 4

So, in total: 22 plausible fast primes. (There are really
fewer than this, even; some of these are not sufficiently
larger than 2^255-19 to be interesting.)

## Minimal-cost curve parameters and corresponding basepoints

Minimal curve parameters. Let `c(x)` be a cost function, and
choose the value of a free parameter `x` such that there
does not exist another `x' != x` with `c(x') <= c(x)`.

Safe curves. Set `c(x) == \inf` if `#E/h` and `#Et/ht` are
not prime, or if some set of safety criteria are not
satisfied. (Insert SafeCurves criteria here.)

Choosing basepoints. Choose the unique point of order `#E/h`
whose single-coordinate representation in the chosen curve
model is minimal in value.

Choosing curve parameters. Suppose that we want an Edwards
curve; so we have a cofactor != 1. Choose the cofactor to
be minimal consistent with safety. Then:

    q == 1 mod 4: h = 8, ht = 4
    q == 3 mod 4: h = 4, ht = 4

Curve form and parameter, *x*:
- Proposed:
  BLE form, a=-1: d
  BLE form, a=+1: d
  Montgomery form: A
- Possible:
  Weierstrass, a=-3: b
- For mathematicians, mainly:
  Legendre form: lambda
  j-invariant

Cost functions, *c(x)*:
  - Proposed:
    min(x)
    min(abs(x))
  - Possible:
    min( (hamming(x), x) )

Am I missing any plausible proposals?

This gives 6 proposed methods of choosing Edwards curves.
Several of these are always equivalent up to isogeny, but for
the choice of basepoint.

# How rigid is rigid enough?

One way we might answer this is by asking whether there are any
cryptographically interesting properties of curves that we know of
that occur with probability on the order of 1/132.

There's at least one, now historical, example:

Only about 1/50 prime-order Weierstrass curves at this
bitlength is twist-secure. (See, e.g., traces for the prime
Salinas384; available at https://github.com/coruus/sally)

(Or, had CFRG then been in the business of choosing curves,
there would have been -- assuming that the CFRG process
is an effective means of selecting a curve uniformly at random
-- a < 0.2% chance of getting P384 right.)

So...is rigidity good? Yes. Do we know that a "rigid" choice
is, in fact, rigid enough to prevent an adversary from selecting
a curve with a chosen, cryptographically interesting property?
. . . . ?

Perhaps we can now hope -- with all of our problems for the
moment solved -- for an end to the rigider-than-thou holy wars,
and a return to collaborating to make ECC safer.

- dlg

---

From: David Leon Gil <[email-masked]>
Date: Fri, 9 Jan 2015 23:29:15 -0800

On Wed, Jan 7, 2015 at 10:49 PM, David Leon Gil <[email-masked]> wrote:
>     2^389 - 21    == 3 mod 4   C389 (wl)

And, to correct the record: 2^389 - 21 should be attributed to Watson
Ladd. Robert Ransom has been perhaps its most vocal critic. (As he has
noted, it would be painful to implement.)