# [curves] A-shirt Edwards curve parameters

David Gil dgil at yahoo-inc.com
Fri Dec 26 11:01:54 PST 2014

```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.)
```