[curves] BADA55 elliptic curves

[Samuel Neves]

On 05/21/2014 10:09 PM, Trevor Perrin wrote:
> http://safecurves.cr.yp.to/bada55.html
>
> elaborates on some points from:
>
> http://safecurves.cr.yp.to/rigid.html
>
> The BADA55-VR curves are generated by what the "Rigidity" page calls a
> "manipulatable" method (similar to NIST curves), and the BADA55-VPR
> curve by a "somewhat rigid" method (similar to Brainpool).
>
> I think the main point is how much freedom remains within the
> "somewhat rigid" approach.  BADA55-VPR makes a small number of
> innocent-looking choices ("nothing-up-my sleeve number" as seed,
> deterministic search based on hashing seed || counter), but still is
> able to satisfy a roughly 1-in-2^17 property (it claims
> "one-in-a-million" (~2^20), but note BADA55 doesn't appear at the
> beginning of BADA55-VPR-224's A).

While random seeds are an obvious target of bruteforce for someone looking for "verifiably random" curves with specific
properties, I don't see how the same goal cannot be achieved with "fully rigid" curves.

Rigidity only makes sense if the process is defined ahead of time, and preferably not by the authors of the curves
themselves. Suppose we want to get one of those one-in-a-million curves, could we get one million of possible candidates?

  - The prime shape gives us at least a handful of bits to work with. Do we use a pseudo-Mersenne prime? A Montgomery
prime? A binary field? Do we slightly undersize it or oversize it relatively to the target security level? 3 mod 4 or 1
mod 4 prime? etc

 - What curve shape do we minimize the coefficients against? Montgomery, Weierstrass, Edwards, other? even within such
coefficients, do we optimize for absolute size or (say) Hamming weight?

 - Other properties can be made up on the spot if we get a hit on an undesired curve. Say, too low of a discriminant,
embedding degree, or something else.

These can also all be innocent-looking choices, much like the VPR curves. So simply having the parameters explained
might not be enough: one must be restricted by them. Otherwise someone sufficiently clever can manipulate design choices
until they get a curve with the required property. Efficiency reasons are a particularly good cover, since they keep
changing, are often not entirely clear, and allow for manipulation of almost all aspects of the curve.