[curves] BADA55 elliptic curves

[Trevor Perrin]

On Wed, May 21, 2014 at 7:45 PM, Samuel Neves <sneves at dei.uc.pt> wrote:
>
> 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.

I agree the "SafeCurves" distinction between "somewhat rigid" and
"fully rigid" is less sharp than the other distinctions [1], but I
think it still makes sense.  Here's my understanding of the rigidity
levels:

"Trivially manipulatable" : no searching required

"Manipulatable" : search space limited by compute resources (e.g. 2^80)?

"Somewhat rigid" : search space limited by arbitrariness in a
"pseudorandom search".  BADA55 demonstrates ~17 bits of arbitrariness
in a Brainpool-like search for pseudorandom coefficients (A,B).  When
pseudorandom primes are also considered (per Brainpool), there's
probably at least a 2^20 search space by varying:
 - seed constant(s)
   - choice of zero, pi, e, sin(1), cos(1), sqrts, etc [2]
   - number of bits from seed constant
   - relationship between seeds for different parameters (prime, A, B)
     - chained (Brainpool A and B), subsequent bits (Brainpool
different curves), different constants (Brainpool prime vs A/B),
complemented (BADA55), etc
 - choice of crypto function (sha1, ripemd, sha2-256/384/512,
sha3-256/384/512, AES128/256, etc.)
 - how to iterate crypto function for larger outputs
   - OFB, CTR (size and endianness, how to combine with seed -
prepend, postpend, etc), OFB+CTR (HKDF), etc.
   - order of concatenating crypto outputs; remainder bits from left or right
 - how to iterate crypto function for multiple candidates
   - OFB, CTR, etc.

"Fully rigid" : You're right that people can propose a lot of things
under the cover of efficiency, and SafeCurves would count these as
"fully rigid" if the decisions are "fully explained".  So I think the
point of the "fully rigid" category is not to remove all flexibility
in design choices, but to minimize design choices which are arbitrary.

Some arbitrary choices will remain, as you point out:

>  - 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?

But that's only a few bits.  The remaining design choices - in
particular prime size and shape, seem mainly driven by efficiency.

So I think the question becomes: how rigid can we make the efficiency
criteria?  If we're looking for one or two extra-strength curves, can
we apply a simple metric (like [3]) to select them with high rigidity,
or is rigidity going to dissolve in debates about target platforms, or
be lost due to having many choices of equivalent efficiency?

Trevor

[1] http://safecurves.cr.yp.to/rigid.html
[2] http://en.wikipedia.org/wiki/Nothing_up_my_sleeve_number
[3] https://docs.google.com/a/trevp.net/spreadsheet/ccc?key=0Aiexaz_YjIpddFJuWlNZaDBvVTRFSjVYZDdjakxoRkE&usp=sharing#gid=0