Re: [Cfrg] Comparing ECC curves

David Jacobson <dmjacobson@sbcglobal.net> Thu, 24 July 2014 14:27 UTC

Return-Path: <dmjacobson@sbcglobal.net>
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 36D731A03A4 for <cfrg@ietfa.amsl.com>; Thu, 24 Jul 2014 07:27:08 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2
X-Spam-Level:
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, RCVD_IN_DNSWL_NONE=-0.0001] autolearn=ham
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 V41CtCvzsCAV for <cfrg@ietfa.amsl.com>; Thu, 24 Jul 2014 07:27:05 -0700 (PDT)
Received: from nm27-vm7.access.bullet.mail.gq1.yahoo.com (nm27-vm7.access.bullet.mail.gq1.yahoo.com [216.39.63.205]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 645261A0375 for <Cfrg@irtf.org>; Thu, 24 Jul 2014 07:26:55 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sbcglobal.net; s=s2048; t=1406212014; bh=qcg6+e/xHTk0G6VmvY4als7kiZnF7E+39Wz0j1JQUHA=; h=Received:Received:Received:DKIM-Signature:X-Yahoo-Newman-Id:X-Yahoo-Newman-Property:X-YMail-OSG:X-Yahoo-SMTP:Message-ID:Date:From:User-Agent:MIME-Version:To:Subject:References:In-Reply-To:Content-Type:Content-Transfer-Encoding; b=dwogdNUw6hJByo0tgQlLNK8Myxun3+B3BHYrD53z08YnBwOTDTSUH8VYc08j88dbflpU0y48aU9X+OIOQsC43b/x9+okKClavxvnJfGv0h01C/pRM8Jtkvq20QGQQ44BBj7srzOxTCQEMKwDkZV3P8aSYN7MVJ6Irs15HiWA22g8Y+ScU0VYSmgranN/I6BfeLNx+TC+MZ1IWEJRbjUNIBIY6HPrfJOor/vzU/J31ClNeJavR9h0juGhN3MlyzfOadoyQsx2ysN77H0S1FN0yAgmwKKcFkB9E0EdwKjqoz1No4Tqn+zolUdKZnLwrN6IzDLp6A5hppkbvpRt8LLGcA==
DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=s2048; d=sbcglobal.net; b=icAo1AsNcysBgdd6o+ElkUPKY+s5IEqVO6wqf/9djbb3iBYanlTYWYWn5ZFzcyvy1tWClC6WZk5gZmNOupKlDAmtXaZ9PtPD7P2edqyt+l2+AFDh1bzCJsBMRt3/pjYXBA0cqaX7saIONIQP6fBsbhb1hOk/0cdKRJwqf7bSG0pFZQ6f9v4LNvf3V7vbD03njwnoNfQQduqqDoX8PjWSU1R6+0rYtuY3H+kRzniwhcdlJ0TLrucFHyOFdxxcUZr3/y851WTNJm+G79ZEoELz294OP0VuLTwD2BqFg4iKm/Q00YniDxvKJfjurP/oE2eSICFYQLOAvKFDJsQQVLzisw==;
Received: from [216.39.60.167] by nm27.access.bullet.mail.gq1.yahoo.com with NNFMP; 24 Jul 2014 14:26:54 -0000
Received: from [67.195.23.146] by tm3.access.bullet.mail.gq1.yahoo.com with NNFMP; 24 Jul 2014 14:26:54 -0000
Received: from [127.0.0.1] by smtp118.sbc.mail.gq1.yahoo.com with NNFMP; 24 Jul 2014 14:26:54 -0000
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sbcglobal.net; s=s1024; t=1406212014; bh=qcg6+e/xHTk0G6VmvY4als7kiZnF7E+39Wz0j1JQUHA=; h=X-Yahoo-Newman-Id:X-Yahoo-Newman-Property:X-YMail-OSG:X-Yahoo-SMTP:Message-ID:Date:From:User-Agent:MIME-Version:To:Subject:References:In-Reply-To:Content-Type:Content-Transfer-Encoding; b=0OTyPBfJvl+1BkgmSIIgqYBD3lMmXPO0/RnvGQZ50cqx9/KfMGUkXA8iz5aVz6abi+47o6pJME/AGr7cJPnXiaRkiqNoYb7vLsDxVojvyDubo0ibxg75csLU8GrcwS5aB+EU5YsCZohkQfSh/oFta5BfWXOFrt49cfsEmVZ5doE=
X-Yahoo-Newman-Id: 826701.55532.bm@smtp118.sbc.mail.gq1.yahoo.com
X-Yahoo-Newman-Property: ymail-3
X-YMail-OSG: bPmX46IVM1lNtFwtIRVdLHlO7Lu_YnTJtGR9.tHNl5QJCEx Y1WM5TRszrvn3E1KSWEX4uxI8KTwXOVu6rCDPk5SCeJdVnWhpyJWVRIl.28g VBEv2TNVqIH8QJ4zUtpLmSZUMrdp20AyEjdHVrUOzXvJRDUYmPnth2A0o2g4 F7vlsvZDUVAZi5Y0XJaElFsfT7ypzaYx5mJxW2lL4JCftkyR0lVKvf9axdNe oTBwu7MX_yqX6uXzUdr1hvvZ_UPKj0vZVyu_rMqy1Yq_YY2HVSihGUDWBjKC hjVZ1KjlHp5k0Psz1al.f5CgLcU0ftnwIf5T7xMBhFMrPqwRBlv_wZBPteUH 3ozQTiJ90ImmVrZlS7gtptAvGS5HnVTNqXScNZqDCKbLBz8T9LrQ27Z._Vmr 6.SfrTBuOkrakjTLBMRc3z2TO8InnC0.avulnhG4faih3HZFYivcfuehZmGJ EHsyJ2Cf7zk9Ie5Trz77cFUMcsNhtuvaaw_FMzVBHjTg7sOFsIbeEPsYCNsh 4X6_8angIHOyrYct3eYk2aHKWKayjerLtitf0T7NSjGEDxnEMjimu2zqr6PO lrfVtfuDrxe6f3YmHbIVB6_bNcQGsIFI1MmGxmX.VSsrahWArxtFp0QPYRJo feIYug_vl
X-Yahoo-SMTP: nOrmCa6swBAE50FabWnlVFUpgFVJ9Gbi__8U5mpvhtQq7tTV1g--
Message-ID: <53D117AD.8060506@sbcglobal.net>
Date: Thu, 24 Jul 2014 07:26:53 -0700
From: David Jacobson <dmjacobson@sbcglobal.net>
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:24.0) Gecko/20100101 Thunderbird/24.6.0
MIME-Version: 1.0
To: Patrick Longa Pierola <plonga@microsoft.com>, Phillip Hallam-Baker <phill@hallambaker.com>, "Cfrg@irtf.org" <Cfrg@irtf.org>
References: <CAMm+Lwj9EPJ9v92xrkM1ceAbkWYe22fpOOBObUbUJjkk8X0dng@mail.gmail.com> <bf68fd7300e14fb58330b094f4795f30@BY2PR03MB474.namprd03.prod.outlook.com>
In-Reply-To: <bf68fd7300e14fb58330b094f4795f30@BY2PR03MB474.namprd03.prod.outlook.com>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/NEV9Na9YMQk_IhA2ew3eHOy713Q
Subject: Re: [Cfrg] Comparing ECC curves
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: Thu, 24 Jul 2014 14:27:08 -0000

On 7/23/14 11:36 PM, Patrick Longa Pierola wrote:
[snip]
> 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] http://eprint.iacr.org/2014/130.pdf
[snip]

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.

     --David