Re: [Cfrg] ECC mod 8^91+5

Hi CFRG,

A minor addition to this topic.

In my first email on this topic, and in my recent IETF 99 presentation, I mentioned that the proposed special curve 2y^2=x^3+x was similar to curves proposed in Miller's 1985 paper introducing of ECC. 

I went back and worked out some more details about this similarity (just some basic elliptic curve math).

To prepare, note that there exists a field element i in GF(8^91+5) with i^2=-1.

Putting x=iu and y=(-i/2)^(1/2)v defines a map to curve with equation v^2=u^3-u.  I believe (99% sure) that this map is an isomorphism (of GF(8^91+5)-rational points).  This equation has the same form as Miller's proposed equation y^2 = x^3 - ax, with a=1.

However, Miller does suggest that value a should not be a perfect square, which rules out a=1 above.  

I believe (50% sure) that Miller made this non-square a recommendation merely to help keep the group cofactor down (by ensuring a unique point of order 2, namely (0,0)).  

By contrast 2y^2=x^3+x, has a subgroup of order 8.  (With points O, (0,0), (i,0), (-i,0), (1,1), (1,-1), (-1,i), (-1,-i).)  A subgroup of order 4 (or 8) is nowadays considered (arguably) an advantage, because of various Edwards curves (but I am only 10% sure, since I haven't looked at this in a while, please correct me this is wrong).

So, the special curve 2y^2=x^3+x is isomorphic to a curve with an even more compact representation: y^2=x^3-x.  

Despite the more compact equation, the original form 2y^2=x^3+x is slightly preferable because it is already in the convenient Montgomery form, so I plan to use the original in the ID.   (But if somebody knows how to do the Montgomery ladder math equally as efficient on a Miller curve y^2=x^3-x, then I'm all ears :)

Best regards,

Dan

-----Original Message-----
From: Cfrg [mailto:cfrg-bounces@irtf.org] On Behalf Of Dan Brown
Sent: Tuesday, May 16, 2017 1:36 PM
To: cfrg@irtf.org
Subject: [Cfrg] ECC mod 8^91+5

Hi all,

I'm considering writing an I-D on doing ECC over the field of size
   8^91+5    (=2^273+5),
because it:
- is written in just 6 symbols (=low Kolmogorov complexity, heuristically minimizing threat of NOBUS-trapdoor),
- has easy and fast inversion, Legendre symbols, and square roots,
- has efficient arithmetic using at most five 64-bit words (use base 2^55),
- is at least 2^(256-epsilon),
- is (probably) prime, so not an extension field (has no subfields for descent-type attacks on ECDLP).
Other fields can improve on some of these properties, but might worsen the others.

For ECC with this field, I am also considering the special curve
   2y^2=x^3+x,
because it:
- is written in just 10 symbols (similar gains to 6-symbol field),
- has Montgomery form (and easily converts to Weierstrass),
- has efficient endomorphism (so it is a GLV curve),
- is similar to curves already suggested by Miller in 1985 (well-aged),
- is similar to sect256k1 already used in bitcoin (incentivized),
- has an small enough cofactor 72 (over field size 8^91+5),
- avoids the main ECDLP attacks: Pohlig-Hellman, Menezes-Okamoto-Vanstone, etc.,
- is similar to the special curves of Koblitz-Menezes [ia.cr/2008/390, Sec 11.1, Example 5] resisting a speculative attack.
The motivation for this special curve largely matches the motivation for the special field.

The curve's risks are at least:
- CM (endomorphism) makes it potentially weak (after 32 years of being safe) (note exactly opposing Koblitz-Menezes rationale),
- its small coefficients are weak for some unpublished reason (continuing trend of weak small-coefficients, y^2=x^3 (singular), supersingular, etc. being weak),
- weak twist order (so, it requires a static ECDH Montgomery ladder to use public key validation),
- weak Cheon resistance (but this is an attack with many queries, much computation, and faulty or no KDF).
- den Boer or Maurer-Wolf reductions are not tight as possible, so perhaps it has a big gap between DHP and DLP Other curves (over this field) can reduce these risks, but may also lose some of the benefits.

Overall, E(GF(8^91+5)):2y^2=x^3+x might offer competitive efficiency with fairly reasonable security (for 128-bit symmetric keys). It is only an incremental change over other standard ECC curves, not anything too radical.  

I'd be happy to hear what CFRG thinks, or if the CFRG would welcome such an I-D as a CFRG work item.  I hope to have this topic presented briefly at an upcoming CFRG meeting.

Best regards,

Dan Brown

_______________________________________________
Cfrg mailing list
Cfrg@irtf.org
https://www.irtf.org/mailman/listinfo/cfrg