Re: [Cfrg] Formal request from TLS WG to CFRG for new elliptic curves

[Andrey Jivsov <[e-mail]>]

On 7/20/2014 11:13 PM, Watson Ladd wrote:
> On Sun, Jul 20, 2014 at 7:32 PM, Andrey Jivsov <[e-mail]> wrote:
>>>   s: Denotes the bit length, here s in {256,384,512}.
>>>   p: Denotes the prime number defining the base field.
>>>   c: A positive integer used in the representation of the prime
>>>           p = 2^s - c.
>>
>> In light of the recent discussion, would an attempt to reach a consensus on
>> the value of p first has a higher chance for success at this point?
> What is wrong with the program the chair outlined for a competition, and how
> does your proposal fix them

I meant this as an additional nice to have property. I could state a 
specific requirement, e.g. "2^s-C with s max",  but my main point is to 
show a benefit to have a commitment to a fixed p for each s.

>
>> Assuming we want a new p, some arguments for a fixed F(p) are:
>>
>> * the specs like Curve25519 are "stacks of layers", which prescribe a Curve,
>> co-factor multiplication, F(p) operations, and an integer format (fixing p
>> seems as one of the the least controversial tasks among these "layers")
>> * the performance advantage are mostly attributed to the F(p) operations
>> (factor of n improvement in F(p) results in ~ n^2 curve performance)
>> * F(p) operations are platform-specific  (if there is assembler code used in
>> the "stack", it will likely be restricted to the F(p))
>> * F(p) clarity will let hardware vendors focus on optimizations (and not
>> worry about the entire stack)
>> * same F(p) doesn't prohibit multiple curves over it; ( fixing F(p) first
>> and the curve or curves later will allow implementations to proceed sooner
>> and enables a compromise )
>> * fixed F(p) allows greater flexibility to upgrade the curves (future curves
>> will likely have hardware support available, sensitive code resused).
>> * fixed F(p) reduces the code size, increases interoperability (currently
>> NUMS and Curve25519 are at odds here)
> How long do you think this is going to take? It should be taking much
> shorter than
> the time it takes to design hardware. Furthermore, all of the choices
> come with software
> implementations liberally licensed.

If there is an unquestionable winner, similar to an AES finalist, then 
there is no worry about universal adoption.

The issue with ECC has always been fragmented ecosystem. At this point 
we are looking at SuiteB / CFRG's choice split. A consensus on F(p) has 
benefits to get more support behind the CFRG choice.

The availability of software libraries is not helping the products that 
need hardware acceleration.

> I don't quite understand your replacement point: many tricks such as
> hyper-and-elliptic,
> endomorphisms (misleadingly called Koblitz curves), etc. require
> primes with some special
> properties or use extension fields. Even going to the Kummer surface
> in genus 2 involves dropping
> field size, so the F(p) will need to be sized differently.

The importance of these other possibilities should be considered, of 
course. I had current contenders in mind. Fewer choices helps with adoption.


>
> Any future proposal if we need it can use an F(p) defined now, possibly.
Right, a fixed p with typical constrains on p covers many important 
choices of curves. We can hope that a large class of future curves 
should be able to use the same F(p) layer.

There is also hope that national standards may feel motivated to use the 
"standard p" on performance/hardware reasons with "their" curves, as 
opposed to completely defining the entirely new stack.

>
>> This narrow focus leads to these questions regarding the F(p):
>> * is a pseudo-Mersenne p an appropriate p for the new curves (the only cons
>> to this so far is that such a p fixes the Curve's order to be close to 2^s;
>> besides the trivial one that this makes the Pollard-rho faster)
>> * Curve25519 uses 255 instead of 256; however, CFRG can choose s=255 for 128
>> bit security as well (citing "historic" reasons).
> The extra word for the top bit is a pain. The loss of half a bit in
> "security" is really de minimis.
Could you please be more specific about how this brings in a new word?

( Even with the off-the-shelf CPUs, we currently have x86, x86_64, 
AVX2-256, and upcoming AVX-512. Please define your target instruction set)

>> Should CFRG seek consensus on the above two questions first?
> No, because that is not how this is being done, and there is a strong
> (but rebuttable) presumption that
> the chair knows what they are doing in organizing WG activities.
>
> Sincerely,
> Watson Ladd
>
>>
>>
>> _______________________________________________
>> Cfrg mailing list
>> [e-mail]
>> http://www.irtf.org/mailman/listinfo/cfrg
>
>