[Cfrg] ECC mod 8^91+5

Dan Brown <danibrown@blackberry.com> Tue, 16 May 2017 17:40 UTC

Return-Path: <danibrown@blackberry.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost []) by ietfa.amsl.com (Postfix) with ESMTP id 5B4ED129B74 for <cfrg@ietfa.amsl.com>; Tue, 16 May 2017 10:40:13 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 0.099
X-Spam-Status: No, score=0.099 tagged_above=-999 required=5 tests=[BAYES_50=0.8, RCVD_IN_DNSWL_LOW=-0.7, RP_MATCHES_RCVD=-0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id ppvv62jdrmEV for <cfrg@ietfa.amsl.com>; Tue, 16 May 2017 10:40:11 -0700 (PDT)
Received: from smtp-p02.blackberry.com (smtp-p02.blackberry.com []) (using TLSv1.2 with cipher RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 29E5312EC16 for <cfrg@irtf.org>; Tue, 16 May 2017 10:35:35 -0700 (PDT)
Received: from smtp-pop.rim.net (HELO XCT103CNC.rim.net) ([]) by mhs214cnc.rim.net with ESMTP/TLS/DHE-RSA-AES256-SHA; 16 May 2017 13:35:34 -0400
Received: from XMB116CNC.rim.net ([fe80::45d:f4fe:6277:5d1b]) by XCT103CNC.rim.net ([fe80::b8:d5e:26a5:f4d6%17]) with mapi id 14.03.0319.002; Tue, 16 May 2017 13:35:34 -0400
From: Dan Brown <danibrown@blackberry.com>
To: "cfrg@irtf.org" <cfrg@irtf.org>
Thread-Topic: ECC mod 8^91+5
Thread-Index: AdLNjx77PpyZT1/ZSIWijHcZu9CKCQ==
Date: Tue, 16 May 2017 17:35:33 +0000
Message-ID: <810C31990B57ED40B2062BA10D43FBF501B181DA@XMB116CNC.rim.net>
Accept-Language: en-US, en-CA
Content-Language: en-US
x-originating-ip: []
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/74QgWGbDHbWxV32UunmejL0mIMY>
Subject: [Cfrg] ECC mod 8^91+5
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.22
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Tue, 16 May 2017 17:40:13 -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
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