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

Samuel Neves <sneves@dei.uc.pt> Sat, 06 December 2014 21:27 UTC

Return-Path: <sneves@dei.uc.pt>
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 A52971A0172 for <cfrg@ietfa.amsl.com>; Sat, 6 Dec 2014 13:27:31 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.511
X-Spam-Level:
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 mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id GWr25ZrWBFQx for <cfrg@ietfa.amsl.com>; Sat, 6 Dec 2014 13:27:28 -0800 (PST)
Received: from smtp.dei.uc.pt (smtp.dei.uc.pt [193.137.203.253]) (using TLSv1 with cipher ADH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id E5F9C1A00EA for <cfrg@irtf.org>; Sat, 6 Dec 2014 13:27:27 -0800 (PST)
Received: from [192.168.90.50] ([37.189.68.171]) (authenticated bits=0) by smtp.dei.uc.pt (8.14.4/8.14.4) with ESMTP id sB6LQqXU028436 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for <cfrg@irtf.org>; Sat, 6 Dec 2014 21:26:58 GMT
Message-ID: <5483749E.1000504@dei.uc.pt>
Date: Sat, 06 Dec 2014 21:26:54 +0000
From: Samuel Neves <sneves@dei.uc.pt>
User-Agent:
MIME-Version: 1.0
To: cfrg@irtf.org
References: <810C31990B57ED40B2062BA10D43FBF5D21FA2@XMB116CNC.rim.net>
In-Reply-To: <810C31990B57ED40B2062BA10D43FBF5D21FA2@XMB116CNC.rim.net>
Content-Type: text/plain; charset=windows-1252
Content-Transfer-Encoding: quoted-printable
X-FCTUC-DEI-SIC-MailScanner-Information: Please contact helpdesk@dei.uc.pt 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)
X-FCTUC-DEI-SIC-MailScanner-From: sneves@dei.uc.pt
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/NR6obSz6F9Ydh0v7h3P12q8cQx4
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: 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 (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.