Subject: Re: [Cfrg] A draft merging rpgecc and thecurve25519function.

From: David Rufino <[email-masked]>
Date: Fri, 2 Jan 2015 03:05:15 +0000

Apologies for inserting my 2c...

Perhaps it's worth making an explicit decision on whether or not 'rigidity'
is actually a required feature. The very rough consensus appears to be
'no', because it's regarded as improbable ('alien technology') that anyone
would be able to 'backdoor' the elliptic curve. In either case it appears
to me that deciding this question ought to fix the curve on purely
technical grounds (no -> curve25519, yes -> rpgecc)

Regards,
David

---

From: Tanja Lange <[email-masked]>
Date: Fri, 2 Jan 2015 20:38:19 +0100

>    Perhaps it's worth making an explicit decision on whether or not
>    'rigidity' is actually a required feature. The very rough consensus
>    appears to be 'no', because it's regarded as improbable ('alien
>    technology') that anyone would be able to 'backdoor' the elliptic curve.
>    In either case it appears to me that deciding this question ought to fix
>    the curve on purely technical grounds (no -> curve25519, yes -> rpgecc)
>
This would be quite a mischaracterization of X25519. The 2006 paper
contains full justifications about every single choice made and
X25519 is historically the first fully rigid curve (unless one includes
Koblitz curves or other curves with very special properties which
coincidentally limit the choice down to just one curve). Its coefficient
A is the smallest one achieving all required properties. The reason
that this draft finds a different (isogenous) curve is that it searches
for the smallest coefficient d for a curve in _Edwards_ form rather 
than for the smallest coefficient A for a curve in _Montgomery_ form. 

This 'wiggle room' of choosing a curve shape cannot be eliminated
but it's quite small. (Note that the paper introducing the NUMS curves
had 26 curves spread over 3 levels of security, because of this and
a similar decision of how to optimize the prime choice.)

I don't understand why the procedure should be part of the draft 
anyways. A description of how to rigidly choose curves already
appears in ACM-CSS 2013 [1]. This could be cited along with the 
NUMS paper as informative references in the security considerations. 
The generation method does not matter for the implementor

Regards
	Tanja

[1] "Elligator: Elliptic-curve points indistinguishable from uniform 
random strings", Bernstein, Hamburg, Krasnova, Lange, ACM-CCS 2013,
http://dx.doi.org/10.1145/2508859.2516734 (Open Access)

---

From: David Rufino <[email-masked]>
Date: Mon, 5 Jan 2015 18:34:50 +0000

Ok, thank you (and Watson) for pointing that out. So presumably
modifying one of draft-black/draft-turner/draft-cfrgcurve to use the
montgomery-style NUMS procedure, which will generate curve25519 at
WF128, should satisfy everyone's requirements ?

Cheers,
David