Re: [Cfrg] ECC reboot (Was: When's the decision?)

Alyssa Rowan <> Thu, 16 October 2014 18:29 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id 1138D1A7018 for <>; Thu, 16 Oct 2014 11:29:54 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.902
X-Spam-Status: No, score=-1.902 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=ham
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id F8A3u5ogbojM for <>; Thu, 16 Oct 2014 11:29:52 -0700 (PDT)
Received: from ( []) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 9B5681A8032 for <>; Thu, 16 Oct 2014 11:29:51 -0700 (PDT)
Message-ID: <>
Date: Thu, 16 Oct 2014 19:29:51 +0100
From: Alyssa Rowan <>
MIME-Version: 1.0
To: "" <>
References: <>
In-Reply-To: <>
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: 8bit
Subject: Re: [Cfrg] ECC reboot (Was: When's the decision?)
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: Thu, 16 Oct 2014 18:29:54 -0000

Hash: SHA512

On 16/10/2014 17:08, Paterson, Kenny wrote:

> Our first task should be to finalise the requirements that we will
> use to guide the selection process. I think we are close, with a
> couple of outstanding issues:

Alright, so let's try to get things in high gear and argue those out…?

> 1. Amount of "wiggle room" that should be permitted.

Broadly: I think what we're aiming for is probably one faster/strong
curve, and one stronger/fast curve.

Given the strong preferences of some to minimise the number of curves,
it looks to me like ­≈384 is almost-definitely dropped, leaving us
with something near ≈256 and something near ≈512.

We seem to be in agreement that wiggle room on ≈256 would include
fields of 2^255-19 as well as 2^256-189 in scope.

For the paranoid-strong, performance-second ≈512, 2^512-569 very
obviously falls within scope.

I put forth that 2^521-1 also falls within scope. It's not very far
away, and it's a true Mersenne prime rather than a pseudo-Mersenne,
and they do not grow on trees - no others fall near our criteria (the
next lowest is 2^127-1 which is way too small, and the next biggest is
2^607-1). They are very attractive - attractive enough for 4 (?)
independent research groups to independently arrive on E-521, and
SECG/NIST to have independently picked the same prime years ago for

[Previous discussion countering this point: Sean Parkinson @ RSA
suggested stepping over a power of 2 is "only going to hurt
performance in the future". Phillip Hallam-Baker also thought anything
that is not less than a clean multiple of a power of two "may cause
severe performance hits on future architectures", mentioning 512-bit
memory buses on graphics cards?! - although I'm not convinced that's
actually primarily relevant to an implementation of a high-strength
curve. We will, of course, evaluate performance of contenders in Phase
II, future architectures can be more-or-less anything that works well,
and performance implications usually aren't anything like so obvious…
Aren't Mersennes actually particularly _good_ performance-wise?]

I put forth that 2^414-17 and 2^448-2^224-1 might fall outside "wiggle
room" there, although I do so very reluctantly as I think it's a shame
to exclude them on that basis if they have otherwise nice properties,
and they do seem to have very good performance for their strength.

> 2. A more nuanced set of hardware requirements.

See other thread.

> So here's a proposal for a new schedule which I believe to be
> feasible: 24/10/14 (1 week from now): we finalise requirements,
> including hardware requirements.

Optimistic? One way to find out. <g>

> 31/10/14 (2 weeks from now): we agree on whatever benchmarking
> system we're going to use for performance measurements. (Right now,
> supercop seems like the front runner to me.)

Consider this an early +1 to SUPERCOP.

> 30/11/14 (6 weeks from now): we deliver our recommendations to the

Let's give it a try!

- --