[curves] A new curve

[Michael Scott]

Thanks for the kind comments. Its a straight-forward Edwards implementation
a la Curve 41417.

I should have mentioned that the trace of the Frobenius is
-82761451378269664604762234204878960657558723706922


Mike

On Thu, Mar 19, 2015 at 5:29 PM, Mike Hamburg <mike at shiftleft.org> wrote:

>
>
> 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
>



-- 
Michael Scott
Chief Cryptographer
CertiVox Ltd
Tel (353) 86 3888746
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20150319/7c97706e/attachment.html>