Re: [Cfrg] Elliptic Curves - poll on specific curve around 256bit work factor (ends on February 23rd)

Michael Hamburg <> Mon, 23 February 2015 22:26 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id 141B41A0199 for <>; Mon, 23 Feb 2015 14:26:57 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: 3.455
X-Spam-Level: ***
X-Spam-Status: No, score=3.455 tagged_above=-999 required=5 tests=[BAYES_20=-0.001, 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 ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id SPtQSSkKn9qx for <>; Mon, 23 Feb 2015 14:26:55 -0800 (PST)
Received: from ( []) (using TLSv1.1 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 5A25F1A0143 for <>; Mon, 23 Feb 2015 14:26:55 -0800 (PST)
Received: from [] (unknown []) by (Postfix) with ESMTPSA id 8E2483AA12; Mon, 23 Feb 2015 14:25:07 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple;; s=sldo; t=1424730307; bh=sYH+WhqvT0D432LHm1v5trkQJ1oHSC0YvfHDKFUriAQ=; h=Subject:From:In-Reply-To:Date:Cc:References:To:From; b=G9fy/1pFvEBZmuff4+MIdjKkrLHx/OKhi4J5qj2kssJKSfMyZWXcQXY5a7BVGL8dj xLH5TvJ1Tca0uF8V9n0r96nIOOjqr00edogETrJ75MUpvwLHMwMCgApK7mM4GfzAIC ymuswPpQoEBzXgXjGIjoYTF5aRZGnlp+6HDmGpjw=
Content-Type: multipart/alternative; boundary="Apple-Mail=_E1D05519-D95D-44BB-B770-FCF2021FFBE0"
Mime-Version: 1.0 (Mac OS X Mail 8.2 \(2070.6\))
From: Michael Hamburg <>
In-Reply-To: <>
Date: Mon, 23 Feb 2015 14:26:51 -0800
Message-Id: <>
References: <> <> <>
To: Phillip Hallam-Baker <>
X-Mailer: Apple Mail (2.2070.6)
Archived-At: <>
Cc: Simon Josefsson <>, "" <>
Subject: Re: [Cfrg] Elliptic Curves - poll on specific curve around 256bit work factor (ends on February 23rd)
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Mon, 23 Feb 2015 22:26:57 -0000

Hi Phillip.

> On Feb 23, 2015, at 11:33 AM, Phillip Hallam-Baker <> wrote:
> Yes, I know there will be error bars on the numbers because the code will run at different speeds on different platforms. But lets face it, modern platforms don't actually vary a whole lot.

This assertion may be true for Sandy Bridge vs Haswell, or even for other 64-bit platforms like Bulldozer, MIPS64, AArch64 etc.  I believe it’s worth noting that there is a large difference between 64-bit, 32-bit with no bignum acceleration, 32-bit with UMAAL but no vector unit, 32-bit with a NEON vector unit, etc.

For this difference, we mostly have conjecture.  As far as I’m aware, Ed448-Goldilocks is the only one of the proposed stronger curves which has been implemented and benchmarked on both ARM32 and AMD64, so we can’t measure how much the architecture influences rankings of curve speed.  This curve was also designed explicitly with 32-bit performance in mind, and it performs very well on NEON.

> A 10% difference in speed might be enough to make an objective choice between Edwards and Montgomery but only experts know the difference between those.
> In short, I want to see the end of this particuar thread:
> <>
> At the time the code for E512-569 was actually 15% faster than for E521-1

I believe that the most recent discussion of the performance of strong curves is in this thread: <>

This is for field arithmetic on Haswell, and there are several caveats mentioned in that thread.  Some approximation of relative performance of the whole curve (across implementation tradeoffs, Montgomery vs Edwards, comb size etc) can be obtained by multiplying the M and S times by the number of bits in the field.  See <>

So for EG a 60:40 M:S ratio, normalized to MS NUMS P384, the rough curve timing ratios would be:

384: 1.00
389: 0.93
448: 1.17
480: 1.25
512: 2.21
521: 1.68

Note that the inflection point in performance is likely to occur lower on 32-bit.  In particular, I expect that the 480:448 cycle cost ratio is likely to be in the neighborhood of 1.5:1 on ARM32+NEON instead of 1.07:1.

> If Microsoft care enough about this that they are willing to put in more cycles optimizing open source code for their favored outcome than supporters of E521-1, then I say let them have it.

I don’t think that effort should be the main factor in standards.  But if you think so, would you also support the converse?

— Mike