Re: [Cfrg] Comparing ECC curves

[Patrick Longa Pierola <[e-mail]>]

-----Original Message-----
From: David Jacobson [mailto:[e-mail]] 
Sent: Thursday, July 24, 2014 7:27 AM
To: Patrick Longa Pierola; Phillip Hallam-Baker; [e-mail]
Subject: Re: [Cfrg] Comparing ECC curves

On 7/23/14 11:36 PM, Patrick Longa Pierola wrote:
[snip]
> An important related point: I haven't seen any result in the 
> literature demonstrating any meaningful performance advantage when 
> dropping one bit from 256 to 255 bits, or from 384 to 383, or from 512 
> to 511 (case of primes with the form 2^m - c). Our experiments [1] 
> reveal that one bit less injects less than 4% of performance 
> improvement. Under this light, we prefer the conservative approach:
> keep a traditional 2 x s bitlength, which is multiple of a computer 
> word of 64 bits (for a bit-security level s = {128,192,256}), maximize 
> ECDLP security and make the curve generation process as simple and 
> rigid as possible. This also helps to keep curve design at different 
> security levels consistent. And, arguably, all this together avoids 
> some potential errors and ease the work of implementers. At the other 
> side of the spectrum, I haven't seen any performance advantage of 
> increasing the prime bitlength beyond 2 x s. It is actually 
> potentially counterproductive: in [1] we show that increasing the 
> field representation by one word (which happens when moving from 512 
> bits to 521 bits for example) degrades performance by a factor 1.2. In 
> this case, the performance issues make the conservative approach even 
> more attractive, taking as a bonus all the benefits mentioned above.
> [1] http://eprint.iacr.org/2014/130.pdf
[snip]

> David Jacobson wrote:
> You are addressing performance.  But what about the ease of making a constant time implementation?  The security value of 256 over 255 or 254 is not much.  It is
> just that 256 is a nice round number, and might be a checkbox item.  If we can accept 255 or 254, it might make constant time implementations easier.   Perhaps
> people who have done constant time implementations can comment.

All our implementations supporting different bitlenghts (255, 256, 383, 384, 511 and 512) are constant-time. They follow the standard approach using the
minimal word representation (e.g., 4 words to represent 255 and 256-bit field elements). Another alternative is to use an extended, unsaturated representation (e.g., in
the case of 255 and 256-bit one would use 5 words). Although the choice and preference is somehow subjective and depends on a given implementer's preference,
ultimately every prime under discussion can be implemented in any of these two methods. So really the difficulty of implementation is not a differentiating factor
in this case.

Patrick