Re: [Cfrg] Formal request from TLS WG to CFRG for new elliptic curves

Watson Ladd <> Mon, 21 July 2014 03:13 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id 3F29F1B2B16 for <>; Sun, 20 Jul 2014 20:13:31 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2
X-Spam-Status: No, score=-2 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, SPF_PASS=-0.001] autolearn=ham
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id zE8Mmnizo8ki for <>; Sun, 20 Jul 2014 20:13:29 -0700 (PDT)
Received: from ( [IPv6:2607:f8b0:4002:c07::235]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 59CB51B2AB1 for <>; Sun, 20 Jul 2014 20:13:29 -0700 (PDT)
Received: by with SMTP id q200so3474271ykb.12 for <>; Sun, 20 Jul 2014 20:13:28 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=Wnvee8j3G0ES/B9RL4lKtLiAkl31sOEmbhttEscjRjI=; b=pwlouQV02Q6qnO+pNbUM/GXfApZI8ebTlao8riCL7JPdz4JHR5jDYZB+AdNTLZ2T20 tHq3hSpKbqD/RqAaUDoe5EzErOy9m3/R0x5JKoimT8KNztCr8N5ZikrrE0RNf0UK3r/a UpGyELzloh3WJ6R1J5PNQucC7xQv18OS3eVb/R47VgBfeBN7KJzu6vHVCjoAJGNxaV0L Cg+/Z+y8JLVP3xB6NJZ5bN4jfskXR8gopSyNa9gbwWg5u8KdmeGSmdwlsd7sPN28AF4q +LIBzRH4ArMTc1nXnRPUuWgewyHp/l+TxvgXAfrlYoiKd18m4BlWXUycZeb1f5qV6uzq M8og==
MIME-Version: 1.0
X-Received: by with SMTP id d32mr35984742yhb.66.1405912408494; Sun, 20 Jul 2014 20:13:28 -0700 (PDT)
Received: by with HTTP; Sun, 20 Jul 2014 20:13:28 -0700 (PDT)
In-Reply-To: <>
References: <> <>
Date: Sun, 20 Jul 2014 20:13:28 -0700
Message-ID: <>
From: Watson Ladd <>
To: Andrey Jivsov <>
Content-Type: text/plain; charset=UTF-8
Cc: "" <>
Subject: Re: [Cfrg] Formal request from TLS WG to CFRG for new elliptic curves
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, 21 Jul 2014 03:13:31 -0000

On Sun, Jul 20, 2014 at 7:32 PM, Andrey Jivsov <> wrote:
>>  s: Denotes the bit length, here s in {256,384,512}.
>>  p: Denotes the prime number defining the base field.
>>  c: A positive integer used in the representation of the prime
>>          p = 2^s - c.
> In light of the recent discussion, would an attempt to reach a consensus on
> the value of p first has a higher chance for success at this point?

What is wrong with the program the chair outlined for a competition, and how
does your proposal fix them?

> Assuming we want a new p, some arguments for a fixed F(p) are:
> * the specs like Curve25519 are "stacks of layers", which prescribe a Curve,
> co-factor multiplication, F(p) operations, and an integer format (fixing p
> seems as one of the the least controversial tasks among these "layers")
> * the performance advantage are mostly attributed to the F(p) operations
> (factor of n improvement in F(p) results in ~ n^2 curve performance)
> * F(p) operations are platform-specific  (if there is assembler code used in
> the "stack", it will likely be restricted to the F(p))
> * F(p) clarity will let hardware vendors focus on optimizations (and not
> worry about the entire stack)
> * same F(p) doesn't prohibit multiple curves over it; ( fixing F(p) first
> and the curve or curves later will allow implementations to proceed sooner
> and enables a compromise )
> * fixed F(p) allows greater flexibility to upgrade the curves (future curves
> will likely have hardware support available, sensitive code resused).
> * fixed F(p) reduces the code size, increases interoperability (currently
> NUMS and Curve25519 are at odds here)

How long do you think this is going to take? It should be taking much
shorter than
the time it takes to design hardware. Furthermore, all of the choices
come with software
implementations liberally licensed.

I don't quite understand your replacement point: many tricks such as
endomorphisms (misleadingly called Koblitz curves), etc. require
primes with some special
properties or use extension fields. Even going to the Kummer surface
in genus 2 involves dropping
field size, so the F(p) will need to be sized differently.

Any future proposal if we need it can use an F(p) defined now, possibly.

> This narrow focus leads to these questions regarding the F(p):
> * is a pseudo-Mersenne p an appropriate p for the new curves (the only cons
> to this so far is that such a p fixes the Curve's order to be close to 2^s;
> besides the trivial one that this makes the Pollard-rho faster)
> * Curve25519 uses 255 instead of 256; however, CFRG can choose s=255 for 128
> bit security as well (citing "historic" reasons).

The extra word for the top bit is a pain. The loss of half a bit in
"security" is really de minimis.
> Should CFRG seek consensus on the above two questions first?

No, because that is not how this is being done, and there is a strong
(but rebuttable) presumption that
the chair knows what they are doing in organizing WG activities.

Watson Ladd

> _______________________________________________
> Cfrg mailing list

"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin