[curves] Second day NIST workshop notes

[David Leon Gil]

On Mon, Jun 15, 2015 at 1:24 PM, Trevor Perrin <trevp at trevp.net> wrote:
> On Mon, Jun 15, 2015 at 11:54 AM, Watson Ladd <watsonbladd at gmail.com> wrote:
>>
>> On Jun 15, 2015 11:32 AM, "Trevor Perrin" <trevp at trevp.net> wrote:
>>>
>>> Lochter's complaint may be more about the tone of BADA55 than its
>>> contents, but he has a point - BADA55 focuses on
>>> "nothing-up-my-sleeve" curves, but doesn't do a similarly deep
>>> analysis of the flexibility of performance-based curve choices like
>>> 25519 or 448.
>>
>> That flexibility is far less.
>
> Maybe.  My point was neither the BADA55 paper - nor yourself - are
> quantifying that flexibility and providing a serious analysis, like
> BADA55 did for Brainpool.
>
> Even your sketch below suggests thousands of choices.
>
> If this is between a 1-in-few-thousand process (performance-based) vs
> 1-in-a-million (nothing-up-my-sleeve-numbers-based), it's not clear
> this is an important distinction - or that these analyses are accurate
> enough to be meaningful.
>
> Anyways, more precision here would be useful, if anyone wants to take that up.

I thought that I had previously posted on here some summaries of "good
primes" (for various definitions of good, including NUMS-like
definitions) and curve selection criteria that might be useful, in the
rigid curve case.

There certainly aren't 2^24 choices -- or even 2^16 -- in a given
security range.

And you don't do very much worse from adopting a (minimal in size of
description) procedure for choosing a random prime and random curve.
(Say only 2^8 at most.)

(The Brainpool procedure certainly isn't that, however; as the BADA55
paper correctly notes, choosing an arbitrary number-theoretic constant
gives a large number of degrees of freedom.)

--

To suggest a more empirical approach, though: Why not just count the
number of curves people have actually implemented around a given
security level?

This gives a relatively small number of choices, and does not seem as
prone to dispute as the numerology above.

(Of course, should someone actually release code to generate
implementations of arbitrary curves over arbitrary finite fields, this
situation may rather change...)