[curves] A new curve

[Mike Hamburg]

On 03/19/2015 10:03 AM, Michael Scott wrote:
>
> Its nice to find a new Elliptic curve that bucks the complexity curve. 
> Nothing nicer than more security for less cost.
>
> So introducing the Edwards curve E-3363
>
> x^2+y^2=1+11111.x^2.y^2 mod 2^336-3
>
> The modulus works particularly well with the Granger-Scott approach to 
> modular multiplication. Observe that 336=56*6=28*12. The order is 8 
> times a prime, the twist is 4 times a prime. 11111 is the smallest 
> positive value to yield a twist secure curve with cofactors less than 
> or equal to 8. Not only is it “rigid”, it even looks rigid!
>

Great, that looks like a very implementation-friendly prime.

> This is merely billions of times more secure than the already secure 
> Curve25519. It fills a gap in terms of existing proposals, coming as 
> it does between WF-128 and WF-192. My implementation takes 333,000 
> cycles on a 64-bit Intel Haswell for a variable point multiplication, 
> but it is also 32-bit-friendly. The modulus is 5 mod 8, but with 
> Curve25519 we have gotten over that already.
>

Is this the Montgomery ladder, or a (twisted) Edwards implementation?  
Just curious.  The timing is very good.  It hits the "Curve25519 plus 
roughly Karatsuba scaling" efficiency curve, and it ought to do at least 
as well on ARM NEON with your 28x12 layout.

> Note that with this curve we follow others in moving away from the 
> artificial constraint imposed by the desire to use a fully saturated 
> representation, whereby the modulus should be an exact multiple of the 
> word-length, and the associated idea of using a Solinas prime. In my 
> view this approach is (a) not necessarily optimal, (b) encourages 
> non-portable implementation, and (c) is harder to make side-channel 
> secure.
>
> At the very least Curve E-3363 provides a useful data-point on the 
> security-cost curve.
>
> Mike

Yeah, Crandall primes are definitely a better choice than Solinas primes 
in most cases.  Especially when they end up with a coefficient that's 
both small and aligned.

Thanks for this,
-- another Mike