Re: [Cfrg] Complete additon for cofactor 1 short Weierstrass curve?

Dan Brown <dbrown@certicom.com> Mon, 08 December 2014 18:46 UTC

Return-Path: <dbrown@certicom.com>
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 E525F1ACD98 for <cfrg@ietfa.amsl.com>; Mon, 8 Dec 2014 10:46:45 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.9
X-Spam-Level:
X-Spam-Status: No, score=-1.9 tagged_above=-999 required=5 tests=[BAYES_00=-1.9] 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 GdXELmryPD-M for <cfrg@ietfa.amsl.com>; Mon, 8 Dec 2014 10:46:44 -0800 (PST)
Received: from smtp-p02.blackberry.com (smtp-p02.blackberry.com [208.65.78.89]) by ietfa.amsl.com (Postfix) with ESMTP id 7EC2D1ACD75 for <cfrg@irtf.org>; Mon, 8 Dec 2014 10:46:26 -0800 (PST)
Received: from xct101cnc.rim.net ([10.65.161.201]) by mhs215cnc.rim.net with ESMTP/TLS/AES128-SHA; 08 Dec 2014 13:46:15 -0500
Received: from XMB116CNC.rim.net ([fe80::45d:f4fe:6277:5d1b]) by XCT101CNC.rim.net ([fe80::9c22:d9c:c906:c488%16]) with mapi id 14.03.0210.002; Mon, 8 Dec 2014 13:46:14 -0500
From: Dan Brown <dbrown@certicom.com>
To: "'sneves@dei.uc.pt'" <sneves@dei.uc.pt>, "'cfrg@irtf.org'" <cfrg@irtf.org>
Thread-Topic: [Cfrg] Complete additon for cofactor 1 short Weierstrass curve?
Thread-Index: AdAQBRZ3YiRvE6KSQn+nT3ij0mFhSwBwC18AAFMFjzA=
Date: Mon, 8 Dec 2014 18:46:13 +0000
Message-ID: <810C31990B57ED40B2062BA10D43FBF5D23FBB@XMB116CNC.rim.net>
References: <810C31990B57ED40B2062BA10D43FBF5D21FA2@XMB116CNC.rim.net> <5483749E.1000504@dei.uc.pt>
In-Reply-To: <5483749E.1000504@dei.uc.pt>
Accept-Language: en-CA, en-US
Content-Language: en-US
X-MS-Has-Attach: yes
X-MS-TNEF-Correlator:
x-originating-ip: [10.65.160.252]
Content-Type: multipart/signed; protocol="application/x-pkcs7-signature"; micalg=SHA1; boundary="----=_NextPart_000_0063_01D012ED.53DE6FA0"
MIME-Version: 1.0
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/UBTZmlBEafFOaaicXgAnpbCLnKA
Subject: Re: [Cfrg] Complete additon for cofactor 1 short Weierstrass curve?
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: Mon, 08 Dec 2014 18:46:46 -0000

> -----Original Message-----
> From: Samuel Neves
> Sent: Saturday, December 06, 2014 4:27 PM
> 
> 
> If you read Lenstra-Bosma, you will see that what you call (G:H:I) is
already
> complete (in the field) for curves with cofactor 1: the exceptional points
for the
> second formula are exactly the points for which P1 - P2 has Y = 0, which
does
> not happen in cofactor 1. More generally, Arene,  Kohel, and Ritzenthaler
> (https://arxiv.org/abs/1102.2349, Theorem 4.3) have shown that any
elliptic
> curve, regardless of cofactor, has a complete addition formula in the
field.
> 
[DB] Thanks, very helpful!

So ... the table from http://safecurves.cr.yp.to/complete.html - which
"reports support for the complete elliptic scalar multiplication" - has an
entry of "False" in the row P256 because the complete formulas for P256 fall
under the proviso that they "are considerably slower and more complicated
than standard incomplete ... formulas".   Well, I missed that proviso, and
in particular, missed the fact that k-complete formula are known for all
curves.

Regarding that proviso, I wonder how much the second Bosma-Lenstra formula
(the one I called (G:H:I), which is the one that corresponds to the line
(0:1:0) in the Bosma-Lenstra paper) would be slower than the standard
incomplete formula.  That is, has anybody tried to optimize it?  (Naively,
with a small a_4, I get a cost of 51M, but I expect much better is
possible.)  Also, there seems to be many k-complete formula per curve, and
perhaps some are faster than others, is this studied?

Also, does the security gain of k-completeness warrant the efficiency loss,
if one, say had to use a cofactor 1 curve, e.g. a grandfathered
P256/Brainpool curve?  (I'm guessing that, in most cases, a Brier-Joye
(Montgomery) x-only ladder would be secure enough, and probably faster.)

Best regards,

Dan