Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid v Pseudorandom

[Manuel Pégourié-Gonnard <[e-mail]>]

Hi Dan,

On 15/01/2014 18:02, Dan Brown wrote:
> I did ask earlier in this thread if I was misinterpreting the rigidity
> page. Specifically, I was trying to ask if it was claiming something
> stronger than NUMS.  Apparently I was indeed misinterpreting, at least
> in to-the-letter sense, because I was construing the page to say
> something more than NUMS.

We can probably take this as an indication that the document should be
very clear on that point (like, clearer that the safecurves pages).

> It seems to me that NUNS is not only formally stronger than NUMS, but
> is also preferable to just NUMS only, because we usually define
> algorithm security independently who the attacker is (not to be
> confused with the capabilities they have, where we might make
> distinctions.)
> 
I think we can agree that NUNS is a very desirable property, but that
almost by definition we can't produce a curve for which it holds with
absolute certainty: all we can do it try to maximise the probability,
under reasonable assumptions, that the curve has this property.

> I was really expecting, to no avail, somebody to finally concede this
> point, but contend that the improvement was just very slight, because
> of the reasonableness of the coefficient-size-independence assumption.
> Oh well.
> 
For what it's worth, my current understanding is that, for a
Brainpool-like construction to maximise the NUNS probability, the only
necessary assumption is that the PRF and the "NUMS" seed have no special
relationship with the potential attacks on curves, which certainly looks
like a very reasonable assumption to make. OTOH, for a Curve25519-like
"rigid" selection to provide NUNS (with high probability), a necessary
assumption is that the upcoming (or currently known only to a few)
attacks don't have a higher probability to apply on a curve with small
coefficients than on the set of all curves (resisting known attacks).

IIRC the discussions on the TLS list, Daniel Bernstein quite strongly
holds the opinion that this assumption is reasonable, and if I
understand your last email correctly, you're not claiming it's an
unreasonable assumption to make.

Obviously, a point in favour of the "PRF(NUMS seed)" construction is
that it's probably easier to believe in it without any particular
knowledge of the attacks on ECDLOG and the deeper properties that make them
work or not.

But my very humble opinion, mostly based on comments by people with more
knowledge than me on this topic, is that both assumptions are
reasonable enough to give us confidence in the security of the curves (both
Brainpool and "rigid" ones) against upcoming attacks.

Manuel.