[curves] The Pareto frontiers of sleeveless primes

[Ben Harris]

There aren't many useful ones with low c then (I guess they'd already have
curves developed for them). 2^810-5 for the "now you are just being silly"
level, 2^216 - 2^108 - 1 for the "looks better on paper than 25519, and
probably strong enough", and 2^96 - 17 for the "hyperelliptic >80 criteria".

P.S. You've prepared lots of interesting stuff for Ed448, thanks. I'll try
and learn some more about ECC through a toy implementation of it in
[favourite language here].

On 31 October 2014 00:00, Mike Hamburg <mike at shiftleft.org> wrote:

>
> On 10/30/2014 06:58 AM, David Leon Gil wrote:
>
>> On Thu, Oct 30, 2014 at 12:44 AM, Ben Harris <mail at bharr.is> wrote:
>>
>>> Are there recommended
>>> limits on the small 'c' in Crandall primes? This list is only up to 32,
>>> but
>>> many on the SafeCurves list are in the 100s.
>>>
>> It's purely a matter of speed.
>>
>> I.e., large values of 'c' are all mainly due to targeting a specific
>> field-size, rather than a speed/security-optimal field size.
>>
>> Most of the Crandalls in SafeCurves with large 'c' are due to Aranha
>> et al.: http://eprint.iacr.org/2013/647
>>
> If you have more than log2 ((n-1)c + 1) + epsilon bits of headroom in
> your n limbs, then you can implement the multiplication and reduction all
> in one go without crossing limbs, and then do all the carry propagation.
> If you have 2 more bits on top of that, you have to propagate carries
> twice.
>
> So to maximize efficiency, you want limbs close to the word size and c
> small.
>
> -- Mike
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20141031/75e6353f/attachment.html>