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

Watson Ladd <watsonbladd@gmail.com> Fri, 05 December 2014 04:47 UTC

Return-Path: <watsonbladd@gmail.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 6723A1AC3F0 for <cfrg@ietfa.amsl.com>; Thu, 4 Dec 2014 20:47:27 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 1
X-Spam-Level: *
X-Spam-Status: No, score=1 tagged_above=-999 required=5 tests=[BAYES_50=0.8, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, MIME_8BIT_HEADER=0.3, SPF_PASS=-0.001] 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 jOwlL2_cfpik for <cfrg@ietfa.amsl.com>; Thu, 4 Dec 2014 20:47:25 -0800 (PST)
Received: from mail-yh0-x22f.google.com (mail-yh0-x22f.google.com [IPv6:2607:f8b0:4002:c01::22f]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 586851AC3EE for <cfrg@irtf.org>; Thu, 4 Dec 2014 20:47:25 -0800 (PST)
Received: by mail-yh0-f47.google.com with SMTP id f73so8947993yha.6 for <cfrg@irtf.org>; Thu, 04 Dec 2014 20:47:24 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:content-transfer-encoding; bh=N//i5P6VdSWl0+2pMrfQDrNj2nOt/779U7Fgjtcuv8s=; b=rg1CLXtJ/IdKG+1UH9hHM3tlESkvSJlVJ57mRe3gkIRg6zoB6sx7HCj7rl62YH/ZQh 7aTqaJRV7AL6SOzgR6z1BXtNBiNgBwNxcrKDxUDLFKVioDbXmNksGII23YFqC7Mxs4Ia oS4JUWQf39f+hrv0UHbY8er6S5rXMyrXS7PsUV1lL/i+D2bzXJ0AxXNULSuSZhTkW6ZX QyvQ7y+aMy7Hg/JaKXwltbVOyt4XhD5ArecuQSTWeBbJrKrHnkM50GxpF5yhhlSGhPBy Vx7ApDmWrOjUJhi4w161Z2RR0iIbbCWCJJpi096E5/P/X8dniofWCxzq5gbTexF33Bj+ 9CZA==
MIME-Version: 1.0
X-Received: by 10.236.30.197 with SMTP id k45mr18018064yha.163.1417754844508; Thu, 04 Dec 2014 20:47:24 -0800 (PST)
Received: by 10.170.195.21 with HTTP; Thu, 4 Dec 2014 20:47:24 -0800 (PST)
In-Reply-To: <5480E17B.4070008@elzevir.fr>
References: <810C31990B57ED40B2062BA10D43FBF5D21FA2@XMB116CNC.rim.net> <5480E17B.4070008@elzevir.fr>
Date: Thu, 4 Dec 2014 20:47:24 -0800
Message-ID: <CACsn0cm34Z+PZUstpy+xMhuB8mxD4OFSvDqzFKM=yoiZN1-VQA@mail.gmail.com>
From: Watson Ladd <watsonbladd@gmail.com>
To: =?UTF-8?Q?Manuel_P=C3=A9gouri=C3=A9=2DGonnard?= <mpg@elzevir.fr>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/6fJp823Y3jVohRo49sI_hDCUhRs
Cc: Dan Brown <dbrown@certicom.com>, "cfrg@irtf.org" <cfrg@irtf.org>
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: Fri, 05 Dec 2014 04:47:27 -0000

On Thu, Dec 4, 2014 at 2:34 PM, Manuel Pégourié-Gonnard <mpg@elzevir.fr>; wrote:
> 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.).

That formula is accompanied by a discussion pointing out there is an
exceptional case, and so one has to switch between two different
formulas by reversing the order of coordinates under some conditions.
It's also unclear that infinity as an output or as an input is handled
correctly. (In fact, I think they aren't: if we add P to -P, the
denominator does not vanish, unless I'm missing something) Those
formulas would be "strongly unified" in the language of the EFD if I
understand correctly, but not "complete".

Sincerely,
Watson Ladd