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
_______________________________________________
Curves mailing list
[email protected]
https://moderncrypto.org/mailman/listinfo/curves
