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

From: Dan Brown <[email-masked]>
Date: Tue, 16 May 2017 17:35:33 +0000

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

---

From: David Jacobson <[email-masked]>
Date: Tue, 16 May 2017 21:25:27 -0700

8^91+5 is provably prime.

In Mathematica I loaded the PrimalityProving module, and checked whether 
8^91+5 was prime, and got True, along with a "Certificate" that is about 
2 pages long.  I don't know the math of certificates, but if anyone in 
interested I can post the certificate.

     --David

On 5/16/17 10:35 AM, Dan Brown wrote:
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Dan Brown <[email-masked]>
Date: Thu, 18 May 2017 19:14:55 +0000

Clarifying a few things over my previous message:
- 8^91+5 has fast modular reduction mainly due its being close to a power of 2 (in contrast to 7^98-2).
- 8^91+5 is a little further than I first thought from the specifics of Koblitz-Menezes Example 5, because the conductor seems to have several more prime factors, rather than the single prime in the KM construction - sorry if I gave the wrong impression.  Perhaps portions of the KM example 5 argument might yet apply to 2y^2=x^3+x/GF(8^91+5).
- 8^91+5 as a field size might be a little awkward.  For ECDH, we take advantage of the endomorphism (x,y)->(-x,iy), to drop a sign bit from x.  This fits x into 34 bytes.  This is larger than the usual 128-bit secure ECC curves, which can use 32 bytes, so they require extra data to send and store.  The byte length is not a multiple of 4, let alone power of two, but I am not sure how much trouble that would be.