### Re: [Cfrg] Complexity of the Microsoft curve proposal

Michael Hamburg <mike@shiftleft.org> Wed, 15 October 2014 01:04 UTC

Return-Path: <mike@shiftleft.org>

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 477181A010A
for <cfrg@ietfa.amsl.com>; Tue, 14 Oct 2014 18:04:05 -0700 (PDT)

X-Virus-Scanned: amavisd-new at amsl.com

X-Spam-Flag: NO

X-Spam-Score: 1.556

X-Spam-Level: *

X-Spam-Status: No, score=1.556 tagged_above=-999 required=5
tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
DKIM_VALID_AU=-0.1, FH_HOST_EQ_D_D_D_D=0.765,
FH_HOST_EQ_D_D_D_DB=0.888, HELO_MISMATCH_ORG=0.611,
HOST_MISMATCH_NET=0.311, HTML_MESSAGE=0.001, RDNS_DYNAMIC=0.982,
SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=no

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 7h1tLVc7ZZFK for <cfrg@ietfa.amsl.com>;
Tue, 14 Oct 2014 18:04:01 -0700 (PDT)

Received: from aspartame.shiftleft.org
(199-116-74-168-v301.PUBLIC.monkeybrains.net [199.116.74.168])
(using TLSv1.1 with cipher AECDH-AES256-SHA (256/256 bits))
(No client certificate requested)
by ietfa.amsl.com (Postfix) with ESMTPS id 43B471A0104
for <cfrg@ietf.org>; Tue, 14 Oct 2014 18:04:00 -0700 (PDT)

Received: from [10.184.148.249] (unknown [209.36.6.242])
by aspartame.shiftleft.org (Postfix) with ESMTPSA id 1FCD73AA13;
Tue, 14 Oct 2014 18:02:08 -0700 (PDT)

DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=shiftleft.org; s=sldo;
t=1413334930; bh=uRhA/zE2q+BB8qBzsYiZhn4GPoBBbckejdsJKlpasNw=;
h=Subject:From:In-Reply-To:Date:Cc:References:To:From;
b=e2NlENmwhFfTnLx4IfSbDZu/Oc1LJ84esJW+C2hvnV+HuNcp/qiilPkNDDgj6Yvnp
k4fhEGE8DTURdmFgvmwERWKdyOYtgdj6r+ypHbZfRxYHKMrQV8QmSLZrJFzU2wOD/p
2SgR99V30+VHkc2p4q2wwUM52NVKWpnWf8ogUK2I=

Content-Type: multipart/alternative;
boundary="Apple-Mail=_535C04A8-C8D0-482E-BD3E-F5163A1E8968"

Mime-Version: 1.0 (Mac OS X Mail 8.0 \(1990.1\))

From: Michael Hamburg <mike@shiftleft.org>

In-Reply-To: <075fdb98d04b42d08e39dbc706cc21fa@DM2PR03MB495.namprd03.prod.outlook.com>

Date: Tue, 14 Oct 2014 18:03:55 -0700

Message-Id: <253D0648-0DDE-497E-8BC1-4DD2805640E4@shiftleft.org>

References: <075fdb98d04b42d08e39dbc706cc21fa@DM2PR03MB495.namprd03.prod.outlook.com>

To: Craig Costello <craigco@microsoft.com>

X-Mailer: Apple Mail (2.1990.1)

Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/r_5VxxJBwyJa6J3LF-T5w_avBJ4

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: Wed, 15 Oct 2014 01:04:05 -0000

> On Oct 14, 2014, at 4:54 PM, Craig Costello <craigco@microsoft.com> wrote: > > 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 <http://eprint.iacr.org/2014/027.pdf> or Section 3.3 of http://eprint.iacr.org/2014/130.pdf <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 <http://eprint.iacr.org/2011/368.pdf> ends up treating as a generic (large) field element. This is because Bernstein et al specified an isomorphic curve and not an isogenous one. They could have specified the 4-isogenous curve x^2 + y^2 = 1 + d x^2 y ^2 where d = (2-A)/4 = -121665. [ At least if I haven’t made a mistake: x = 4v(u^2-1) / ((u^2-1)^2+4v^2) y = u (4v^2 - (u^2-1)^2) / (2v^2(u^2+1) - u(u^2-1)^2) dual: u = y^2/x^2 v = y(x^2+y^2-2)/x^3 ] or the curve -x^2 + y^2 = 1 - d x^2 y^2 which is isomorphic to that one under the map x -> ix. Both of these curves are complete, because GF(2^255-16)(+-121665) is nonsquare. > All other things being equal, I therefore think that switching between coordinates (if desired) slightly favors p == 3 mod 4. There are advantages to p == 3 mod 4, but I don’t think this is one of them. Note that p == 1 mod 4 supports curves which are both twisted [a=-1] and complete, but 3 mod 4 does not. So in terms of coordinate systems, that’s the simplest, fastest option. You can recover most of that with the isogeny trick, but not all of it. > 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 inhttp://eprint.iacr.org/2014/526.pdf <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 <http://eprint.iacr.org/2014/027.pdf>). I think Watson’s points were: 1) If the NUMS curves are chosen, they should be changed to the isogenous untwisted ones. 2) Whatever curves are chosen, they should compress points. > 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. An isogeny is a bit more than just a change in coordinates, but I agree that it’s reasonable to pick a curve structure, and later discuss which isogenous or isomorphic curves and which coordinates should be used for which protocols. I don’t think everyone on this list would agree with the above statement, though. A pretty big part of Benjamin Black’s argument against \w+25519 is the idea that they are different curves, not just different coordinates for the same curve, even though the curves are isomorphic and not just isogenous. This is also why I listed “Curves isogenous to NUMS” as a separate candidate from NUMS in the “current candidates” email. > Cheers, > Craig Peace, — Mike

- [Cfrg] Complexity of the Microsoft curve proposal Watson Ladd
- Re: [Cfrg] Complexity of the Microsoft curve prop… Craig Costello
- Re: [Cfrg] Complexity of the Microsoft curve prop… Michael Hamburg
- [Cfrg] Fwd: Complexity of the Microsoft curve pro… Watson Ladd
- Re: [Cfrg] Complexity of the Microsoft curve prop… Benjamin Black