[curves] A-shirt Edwards curve parameters

[David Gil]

Part II of some off-and-on work to quantify just how rigid
rigid curves are.

Part I, which needs revision, was here: 
https://moderncrypto.org/mail-archive/curves/2014/000315.html
## Minimal-cost curve parameters

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.

Choosing curve parameters. Suppose that we want an Edwards
curve; so we have a cofactor != 1.

Cofactor choices:
- q == 1 mod 4
  - h = 2^n, ht = 2^m, n <= 3, m <= 3
  - h = 8, ht = 4
- q == 3 mod 4
  - h = 4, ht = 4

Curve 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
for 3 mod 4 primes, and (perhaps) 12 for choosing Edwards
curves for 1 mod 4 primes. Perhaps the cofactor requirement
is more appropriately handled in a discussion of the rigidity
of "safety" definitions...)

## More exotic things that seem possible

"Signature-friendly" curves: Require, in addition, that #E/h be
pleasant to reduce modulo. (By choosing a sufficiently dense family
of reduction-friendly primes, not by CM.)

## "Verifiably random" curve parameters

How much less rigid is the choice of "verifiably random" curve
parameters?

How to sample:
  - by rejection of candidates of bitlength ceil(log2(q))
  - by modular reduction of candidates of bitlength 2*ceil(log2(q))

(And then by rejection of unsafe proposals.)

PRF keys:
  - 0
  - {big,little}-endian representation of ceil(log2(q))
  - (is anything else plausible if you make a choice before knowing
  the maximum key-length of the PRF -- i.e., in the equivalent of
  Rawlsian ignorance?)

PRFs:
  - AES{128,256}-CTR
  - {ChaCha,Salsa}20
  - SHAKE{128,256}

(This gives 36 choices for verifiably random curves. This, of course,
would need to be multiplied by 6 or 12.)