Re: [Cfrg] Comparing ECC curves

Patrick Longa Pierola <> Thu, 24 July 2014 15:17 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id C8E091A0451 for <>; Thu, 24 Jul 2014 08:17:41 -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, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=ham
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id ASuQt-6trGbs for <>; Thu, 24 Jul 2014 08:17:39 -0700 (PDT)
Received: from ( []) (using TLSv1 with cipher ECDHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 393361A04BA for <>; Thu, 24 Jul 2014 08:15:09 -0700 (PDT)
Received: from ( by ( with Microsoft SMTP Server (TLS) id 15.0.990.7; Thu, 24 Jul 2014 15:15:07 +0000
Received: from ([]) by ([]) with mapi id 15.00.0990.007; Thu, 24 Jul 2014 15:15:07 +0000
From: Patrick Longa Pierola <>
To: David Jacobson <>, Phillip Hallam-Baker <>, "" <>
Thread-Topic: [Cfrg] Comparing ECC curves
Thread-Index: AQHPpsVlokHtIBVyPkOedmRlQCZAupuurLaAgACcX4CAAAfBEA==
Date: Thu, 24 Jul 2014 15:15:06 +0000
Message-ID: <>
References: <> <> <>
In-Reply-To: <>
Accept-Language: en-US
Content-Language: en-US
x-originating-ip: []
x-microsoft-antispam: BCL:0;PCL:0;RULEID:
x-forefront-prvs: 028256169F
x-forefront-antispam-report: SFV:NSPM; SFS:(6009001)(479174003)(243025005)(377454003)(13464003)(24454002)(189002)(199002)(106116001)(81542001)(50986999)(66066001)(83322001)(79102001)(15975445006)(76176999)(74662001)(86362001)(81342001)(77982001)(15202345003)(80022001)(2656002)(101416001)(105586002)(86612001)(33646002)(99396002)(99286002)(19580395003)(74316001)(46102001)(21056001)(19580405001)(76576001)(83072002)(20776003)(31966008)(85852003)(107046002)(74502001)(92566001)(76482001)(85306003)(107886001)(54356999)(64706001)(87936001)(4396001)(95666004)(106356001)(108616002)(24736002); DIR:OUT; SFP:; SCL:1; SRVR:BY2PR03MB476;; FPR:; MLV:sfv; PTR:InfoNoRecords; MX:1; LANG:en;
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
Subject: Re: [Cfrg] Comparing ECC 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: Thu, 24 Jul 2014 15:17:41 -0000

-----Original Message-----
From: David Jacobson [] 
Sent: Thursday, July 24, 2014 7:27 AM
To: Patrick Longa Pierola; Phillip Hallam-Baker;
Subject: Re: [Cfrg] Comparing ECC curves

On 7/23/14 11:36 PM, Patrick Longa Pierola wrote:
> An important related point: I haven't seen any result in the 
> literature demonstrating any meaningful performance advantage when 
> dropping one bit from 256 to 255 bits, or from 384 to 383, or from 512 
> to 511 (case of primes with the form 2^m - c). Our experiments [1] 
> reveal that one bit less injects less than 4% of performance 
> improvement. Under this light, we prefer the conservative approach:
> keep a traditional 2 x s bitlength, which is multiple of a computer 
> word of 64 bits (for a bit-security level s = {128,192,256}), maximize 
> ECDLP security and make the curve generation process as simple and 
> rigid as possible. This also helps to keep curve design at different 
> security levels consistent. And, arguably, all this together avoids 
> some potential errors and ease the work of implementers. At the other 
> side of the spectrum, I haven't seen any performance advantage of 
> increasing the prime bitlength beyond 2 x s. It is actually 
> potentially counterproductive: in [1] we show that increasing the 
> field representation by one word (which happens when moving from 512 
> bits to 521 bits for example) degrades performance by a factor 1.2. In 
> this case, the performance issues make the conservative approach even 
> more attractive, taking as a bonus all the benefits mentioned above.
> [1]

> David Jacobson wrote:
> You are addressing performance.  But what about the ease of making a constant time implementation?  The security value of 256 over 255 or 254 is not much.  It is
> just that 256 is a nice round number, and might be a checkbox item.  If we can accept 255 or 254, it might make constant time implementations easier.   Perhaps
> people who have done constant time implementations can comment.

All our implementations supporting different bitlenghts (255, 256, 383, 384, 511 and 512) are constant-time. They follow the standard approach using the
minimal word representation (e.g., 4 words to represent 255 and 256-bit field elements). Another alternative is to use an extended, unsaturated representation (e.g., in
the case of 255 and 256-bit one would use 5 words). Although the choice and preference is somehow subjective and depends on a given implementer's preference,
ultimately every prime under discussion can be implemented in any of these two methods. So really the difficulty of implementation is not a differentiating factor
in this case.