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

Manuel Pégourié-Gonnard <mpg@elzevir.fr> Thu, 04 December 2014 22:34 UTC

Return-Path: <mpg@elzevir.fr>
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 131311A7010 for <cfrg@ietfa.amsl.com>; Thu, 4 Dec 2014 14:34:43 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 0.639
X-Spam-Level:
X-Spam-Status: No, score=0.639 tagged_above=-999 required=5 tests=[BAYES_40=-0.001, HELO_EQ_FR=0.35, MIME_8BIT_HEADER=0.3, T_RP_MATCHES_RCVD=-0.01] autolearn=no
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 c-hQXgbX6U8B for <cfrg@ietfa.amsl.com>; Thu, 4 Dec 2014 14:34:41 -0800 (PST)
Received: from mordell.elzevir.fr (mordell.elzevir.fr [92.243.3.74]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 5A5811A702C for <cfrg@irtf.org>; Thu, 4 Dec 2014 14:34:41 -0800 (PST)
Received: from thue.elzevir.fr (unknown [IPv6:2a01:e35:8a5d:80b0:be5f:f4ff:fe2c:95bc]) by mordell.elzevir.fr (Postfix) with ESMTPS id 45E9016150; Thu, 4 Dec 2014 23:34:39 +0100 (CET)
Received: from [172.17.16.252] (unknown [212.104.156.66]) by thue.elzevir.fr (Postfix) with ESMTPSA id 4E813216EC; Thu, 4 Dec 2014 23:34:37 +0100 (CET)
Message-ID: <5480E17B.4070008@elzevir.fr>
Date: Thu, 04 Dec 2014 23:34:35 +0100
From: =?windows-1252?Q?Manuel_P=E9gouri=E9-Gonnard?= <mpg@elzevir.fr>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.2.0
MIME-Version: 1.0
To: Dan Brown <dbrown@certicom.com>, "cfrg@irtf.org" <cfrg@irtf.org>
References: <810C31990B57ED40B2062BA10D43FBF5D21FA2@XMB116CNC.rim.net>
In-Reply-To: <810C31990B57ED40B2062BA10D43FBF5D21FA2@XMB116CNC.rim.net>
OpenPGP: id=98EED379; url=https://elzevir.fr/gpg/mpg.asc
Content-Type: text/plain; charset=windows-1252
Content-Transfer-Encoding: 7bit
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/MOr8wSWrqRL9bUN_sYihQb-jZXI
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: Thu, 04 Dec 2014 22:34:43 -0000

Hi,

On 04/12/2014 23:17, Dan Brown wrote:
> 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.
> 
I'm way too tired to check if the above is correct, but it seems to me that
complete laws for general curves are known, see eg 29.1.2.a of the Handbook of
Elliptic and Hyperelliptic Curve Cryptography (Cohen, Frey et al.).

I'm not sure it makes such a lot of sense to classify that as an efficiency
rather than security issue: in my opinion (which seems to be shared by many
people), conflicts between efficiency and security are to be avoided as much as
possible, since in practice, they will very often result in security issues.

Manuel.