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

Thomas Garcia <tgarcia.3141@gmail.com> Wed, 02 August 2017 07:52 UTC

Return-Path: <tgarcia.3141@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 5D37D126BF3 for <cfrg@ietfa.amsl.com>; Wed, 2 Aug 2017 00:52:11 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.448
X-Spam-Level:
X-Spam-Status: No, score=-2.448 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_ENVFROM_END_DIGIT=0.25, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id NwJiu1fOOlmC for <cfrg@ietfa.amsl.com>; Wed, 2 Aug 2017 00:52:08 -0700 (PDT)
Received: from mail-lf0-x234.google.com (mail-lf0-x234.google.com [IPv6:2a00:1450:4010:c07::234]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 079F01288B8 for <cfrg@irtf.org>; Wed, 2 Aug 2017 00:52:07 -0700 (PDT)
Received: by mail-lf0-x234.google.com with SMTP id d17so16520973lfe.0 for <cfrg@irtf.org>; Wed, 02 Aug 2017 00:52:07 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=OryFn5vO1Rx1MluFGkCe16QEzjlXwAs8jn+ez8esigs=; b=NBKuCAFVK56SSONZNp13LWZqkFEmitMyi5W0kEfFqp6LS872Eqcf3BIr4DzWkn9Tpm Tc/fNrHPTC9oA1l80c1aH8GiCAwZlbaarqoxvcaQHg/5dbV16wFomjAKKcsp9bn9Xn7T ttzXFiulFFpqDi6ZzKoOkMVk0IQB5Vx5Fa3S2h3Npc3pHgq5InBh4Bf+mDznIySANWJ0 jIUbCWviaNns1dcRQw/cDU+jaMAyQd6SWRU+4aVac5sF84xZdfoJRbZJhz7a4kprHaJw FBF7V7F6qzx8W487Iy4wLhk8mCAsdkDTxf5ghmD5HvfylFvoN/t1S3pI1DUgKfMPycOq kmBA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=OryFn5vO1Rx1MluFGkCe16QEzjlXwAs8jn+ez8esigs=; b=rRQ9+jAPtruMZ81noqTFqgVpgFHy+hkavovz1avSuJxG8XTJbz6ORalb//MvL87iTM Sa8/2xGd4I1sHjyf+SamHrzXIuM/sNoq86LJsv3NqZr1YY3CkF8DYD0/dZPLPvHZf/F3 CtE4XhWmuaVYWd4TRTdPDwk2amiLlLM5bikgj6dtiAPFSCL9e60mEl71DVEOaMc7286H ZSHvXIANqcX9pgoEVLexLCzLZdMvOF8WPa4rKuqizytZYowBS4h4ZwsADxuNbjL4qsqf KBdJkp0jzP7rn9vgK6gRrf7qexgUxYBPA/bRr8pu5sQ3lIlN8rsy8HPnRdVaBi+l2GrP 3yNQ==
X-Gm-Message-State: AIVw112iJhSftNWix9zzYHAS/T1VypSTGyLWfWqOzQhbXIrt+YOc3Eji lHr6KDWoL2PIKLPsgnCKRxYQM4o2tg==
X-Received: by 10.25.228.206 with SMTP id x75mr6450255lfi.94.1501660326035; Wed, 02 Aug 2017 00:52:06 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.25.22.40 with HTTP; Wed, 2 Aug 2017 00:52:05 -0700 (PDT)
In-Reply-To: <810C31990B57ED40B2062BA10D43FBF501B7969D@XMB116CNC.rim.net>
References: <810C31990B57ED40B2062BA10D43FBF501B181DA@XMB116CNC.rim.net> <810C31990B57ED40B2062BA10D43FBF501B7969D@XMB116CNC.rim.net>
From: Thomas Garcia <tgarcia.3141@gmail.com>
Date: Wed, 02 Aug 2017 08:52:05 +0100
Message-ID: <CAFTSWvf3-rpVG+GWh81an400dOwcwrZ=yRAjh1Bt7kkfvPJdRg@mail.gmail.com>
To: Dan Brown <danibrown@blackberry.com>
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Content-Type: multipart/alternative; boundary="94eb2c0c91664e85020555c08a42"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/d8PCHxU_g8vEyHHkJ8mLoaW3CXg>
Subject: Re: [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: Wed, 02 Aug 2017 07:52:11 -0000

Hi Dan,
The transformation you proposed (x->iu, y->(-i/2)^(1/2)v) does indeed
define an isomorphism between the curve (2y^2=x^3+x) and the curve
(v^2=u^3-u), modulo p=8^91+5. As this transformation is defined over GF(p),
it preserves the group of points modulo p.

Thomas G.

On Tue, Aug 1, 2017 at 10:22 PM, Dan Brown <danibrown@blackberry.com> wrote:

> 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
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>