Re: [Cfrg] Complexity of the Microsoft curve proposal

Craig Costello <craigco@microsoft.com> Tue, 14 October 2014 23:54 UTC

Return-Path: <craigco@microsoft.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 0D12A1A005F for <cfrg@ietfa.amsl.com>; Tue, 14 Oct 2014 16:54:38 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.901
X-Spam-Level:
X-Spam-Status: No, score=-1.901 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=ham
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 J-fC7je9fM6l for <cfrg@ietfa.amsl.com>; Tue, 14 Oct 2014 16:54:35 -0700 (PDT)
Received: from na01-bn1-obe.outbound.protection.outlook.com (mail-bn1bon0774.outbound.protection.outlook.com [IPv6:2a01:111:f400:fc10::1:774]) (using TLSv1 with cipher ECDHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id E02C61A0060 for <cfrg@ietf.org>; Tue, 14 Oct 2014 16:54:34 -0700 (PDT)
Received: from DM2PR03MB495.namprd03.prod.outlook.com (10.141.85.149) by DM2PR03MB495.namprd03.prod.outlook.com (10.141.85.149) with Microsoft SMTP Server (TLS) id 15.0.1049.19; Tue, 14 Oct 2014 23:54:11 +0000
Received: from DM2PR03MB495.namprd03.prod.outlook.com ([10.141.85.149]) by DM2PR03MB495.namprd03.prod.outlook.com ([10.141.85.149]) with mapi id 15.00.1049.012; Tue, 14 Oct 2014 23:54:11 +0000
From: Craig Costello <craigco@microsoft.com>
To: "watsonbladd@gmail.com" <watsonbladd@gmail.com>
Thread-Topic: Re: [Cfrg] Complexity of the Microsoft curve proposal
Thread-Index: Ac/oCgRJQ9masmK0T320ahMLKTrEgw==
Date: Tue, 14 Oct 2014 23:54:11 +0000
Message-ID: <075fdb98d04b42d08e39dbc706cc21fa@DM2PR03MB495.namprd03.prod.outlook.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
x-ms-exchange-transport-fromentityheader: Hosted
x-originating-ip: [2001:4898:80e0:ee43::2]
x-microsoft-antispam: BCL:0;PCL:0;RULEID:;SRVR:DM2PR03MB495;
x-forefront-prvs: 03648EFF89
x-forefront-antispam-report: SFV:NSPM; SFS:(10019020)(199003)(189002)(243025005)(76482002)(20776003)(92566001)(19580395003)(19300405004)(19625215002)(64706001)(31966008)(33646002)(110136001)(87936001)(15202345003)(101416001)(122556002)(40100003)(74316001)(15975445006)(16236675004)(120916001)(19617315012)(2656002)(85852003)(21056001)(99396003)(1411001)(4396001)(106356001)(107046002)(2351001)(85306004)(2501002)(105586002)(108616004)(54356999)(86362001)(50986999)(97736003)(95666004)(46102003)(80022003)(99286002)(76576001)(24736002)(3826002); DIR:OUT; SFP:1102; SCL:1; SRVR:DM2PR03MB495; H:DM2PR03MB495.namprd03.prod.outlook.com; FPR:; MLV:sfv; PTR:InfoNoRecords; A:1; MX:1; LANG:en;
Content-Type: multipart/alternative; boundary="_000_075fdb98d04b42d08e39dbc706cc21faDM2PR03MB495namprd03pro_"
MIME-Version: 1.0
X-OriginatorOrg: microsoft.onmicrosoft.com
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/zeH3yEDi7JaDGYxPs1IoR7hoCdg
Cc: "cfrg@ietf.org" <cfrg@ietf.org>
Subject: Re: [Cfrg] Complexity of the Microsoft curve proposal
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Tue, 14 Oct 2014 23:54:38 -0000

Hi Watson,

To elaborate a little on what Mike said, when p == 3 mod 4, defining searches for twist-secure curves that minimize the absolute value of the Montgomery constant automatically minimize the absolute value of the constant on the isogenous (complete) Edwards curve and the absolute value of the constant on the isogenous twisted Edwards curve. So regardless of whether our curves are implemented using Edwards coordinates, twisted Edwards coordinates, or Montgomery coordinates, the corresponding curve constant will be small (see Section 2 of http://eprint.iacr.org/2014/027.pdf or Section 3.3 of http://eprint.iacr.org/2014/130.pdf to see that there is no problem here).

On the other hand, I'm not sure if this happens when p == 1 mod 4: for example, the Edwards version of Curve25519 has a curve constant that's a fraction of small numbers, which the implementation documented in http://eprint.iacr.org/2011/368.pdf ends up treating as a generic (large) field element.

All other things being equal, I therefore think that switching between coordinates (if desired) slightly favors p == 3 mod 4. Furthermore, in this case, if the curve is defined as an a=1 (complete) Edwards curve, implementers then have the option of staying in Edwards form at the expense of 1 field multiplication per addition operation (like the implementation of Curve41417 in http://eprint.iacr.org/2014/526.pdf does) or of using Mike's isogeny trick for enhanced performance: http://eprint.iacr.org/2014/027.pdf).

In any case, this is (as you say) about the coordinates, not the curve. However, changing coordinates can change the corresponding curve constant, but when p == 3 mod 4 small constants will remain small irrespective of the coordinate system.

Cheers,
Craig