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

Dan Brown <> Mon, 08 December 2014 18:46 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id E525F1ACD98 for <>; Mon, 8 Dec 2014 10:46:45 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.9
X-Spam-Status: No, score=-1.9 tagged_above=-999 required=5 tests=[BAYES_00=-1.9] autolearn=ham
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id GdXELmryPD-M for <>; Mon, 8 Dec 2014 10:46:44 -0800 (PST)
Received: from ( []) by (Postfix) with ESMTP id 7EC2D1ACD75 for <>; Mon, 8 Dec 2014 10:46:26 -0800 (PST)
Received: from ([]) by with ESMTP/TLS/AES128-SHA; 08 Dec 2014 13:46:15 -0500
Received: from ([fe80::45d:f4fe:6277:5d1b]) by ([fe80::9c22:d9c:c906:c488%16]) with mapi id 14.03.0210.002; Mon, 8 Dec 2014 13:46:14 -0500
From: Dan Brown <>
To: "''" <>, "''" <>
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: <>
References: <> <>
In-Reply-To: <>
Accept-Language: en-CA, en-US
Content-Language: en-US
X-MS-Has-Attach: yes
x-originating-ip: []
Content-Type: multipart/signed; protocol="application/x-pkcs7-signature"; micalg=SHA1; boundary="----=_NextPart_000_0063_01D012ED.53DE6FA0"
MIME-Version: 1.0
Subject: Re: [Cfrg] Complete additon for cofactor 1 short Weierstrass curve?
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, 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
> 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
> not happen in cofactor 1. More generally, Arene,  Kohel, and Ritzenthaler
> (, Theorem 4.3) have shown that any
> curve, regardless of cofactor, has a complete addition formula in the
[DB] Thanks, very helpful!

So ... the table from - 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

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,