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

Samuel Neves <> Sat, 06 December 2014 21:27 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id A52971A0172 for <>; Sat, 6 Dec 2014 13:27:31 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.511
X-Spam-Status: No, score=-1.511 tagged_above=-999 required=5 tests=[BAYES_50=0.8, RCVD_IN_DNSWL_MED=-2.3, SPF_PASS=-0.001, T_RP_MATCHES_RCVD=-0.01] autolearn=ham
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id GWr25ZrWBFQx for <>; Sat, 6 Dec 2014 13:27:28 -0800 (PST)
Received: from ( []) (using TLSv1 with cipher ADH-AES256-SHA (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id E5F9C1A00EA for <>; Sat, 6 Dec 2014 13:27:27 -0800 (PST)
Received: from [] ([]) (authenticated bits=0) by (8.14.4/8.14.4) with ESMTP id sB6LQqXU028436 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for <>; Sat, 6 Dec 2014 21:26:58 GMT
Message-ID: <>
Date: Sat, 06 Dec 2014 21:26:54 +0000
From: Samuel Neves <>
MIME-Version: 1.0
References: <>
In-Reply-To: <>
Content-Type: text/plain; charset=windows-1252
Content-Transfer-Encoding: quoted-printable
X-FCTUC-DEI-SIC-MailScanner-Information: Please contact for more information
X-FCTUC-DEI-SIC-MailScanner-ID: sB6LQqXU028436
X-FCTUC-DEI-SIC-MailScanner: Found to be clean
X-FCTUC-DEI-SIC-MailScanner-SpamCheck: not spam, SpamAssassin (not cached, score=-60.25, required 3.252, autolearn=not spam, ALL_TRUSTED -10.00, BAYES_00 -0.25, L_SMTP_AUTH -50.00)
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: Sat, 06 Dec 2014 21:27:31 -0000

On 04-12-2014 22:17, Dan Brown wrote:
> Well, I haven't really studied these kinds of things before: I more often think of elliptic curves as generic groups, so I could easily be mistaken (e.g. maybe the incorrect outputs really can differ from (0:0:0), or something really wrong in the logic above).  So, I ask the experts here on this list: Is this addition law correct?  Is it complete in the same sense used for Edwards curves?
> If this is all correct, then I would suggest that cofactor 1 short Weierstrass do not have a security problem compared to Edwards curves (e.g. cofactor 4), in the sense of lacking a complete addition law, but rather, just an efficiency problem, in the sense of not having any (known) efficient complete law.

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 (, Theorem 4.3)
have shown that any elliptic curve, regardless of cofactor, has a complete addition formula in the field.