[curves] BADA55 elliptic curves

[Watson Ladd]

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

But with one critical caveat: the curve must be faster than all the
others! Whether or not some criterion enhances efficiency is clear:
you race a curve with it and without it.

Sincerely,
Watson Ladd



-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin