[Cfrg] ECC mod 8^91+5

[Dan Brown <[e-mail]>]

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