IETF Logo Mail Archive

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

Nathaniel McCallum <npmccallum@redhat.com> Mon, 02 November 2015 16:39 UTC

Return-Path: <npmccallum@redhat.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 41EF71B497F for <cfrg@ietfa.amsl.com>; Mon, 2 Nov 2015 08:39:48 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -5.91
X-Spam-Level:
X-Spam-Status: No, score=-5.91 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HK_RANDOM_ENVFROM=0.001, HK_RANDOM_FROM=1, RCVD_IN_DNSWL_HI=-5, SPF_HELO_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 QpiJwi_CDpSL for <cfrg@ietfa.amsl.com>; Mon, 2 Nov 2015 08:39:46 -0800 (PST)
Received: from mx1.redhat.com (mx1.redhat.com [209.132.183.28]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 8AD911B4980 for <cfrg@irtf.org>; Mon, 2 Nov 2015 08:39:46 -0800 (PST)
Received: from int-mx13.intmail.prod.int.phx2.redhat.com (int-mx13.intmail.prod.int.phx2.redhat.com [10.5.11.26]) by mx1.redhat.com (Postfix) with ESMTPS id CA28B8C1D2; Mon, 2 Nov 2015 16:39:45 +0000 (UTC)
Received: from dhcp137-102.rdu.redhat.com (dhcp137-102.rdu.redhat.com [10.13.137.102]) by int-mx13.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id tA2Gdiq2000880 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=NO); Mon, 2 Nov 2015 11:39:45 -0500
Message-ID: <1446482378.890.40.camel@redhat.com>
From: Nathaniel McCallum <npmccallum@redhat.com>
To: Watson Ladd <watsonbladd@gmail.com>, Dan Brown <dbrown@certicom.com>
Date: Mon, 02 Nov 2015 11:39:38 -0500
In-Reply-To: <CACsn0c=Q=idWRNLMJhntpdYx60h-0BSCvc=7z2v3tGAyt0L4Qw@mail.gmail.com>
References: <810C31990B57ED40B2062BA10D43FBF5D21FA2@XMB116CNC.rim.net> <5483749E.1000504@dei.uc.pt> <810C31990B57ED40B2062BA10D43FBF5D23FBB@XMB116CNC.rim.net> <548613FE.8060107@dei.uc.pt> <810C31990B57ED40B2062BA10D43FBF5E76B45@XMB116CNC.rim.net> <CACsn0c=Q=idWRNLMJhntpdYx60h-0BSCvc=7z2v3tGAyt0L4Qw@mail.gmail.com>
Content-Type: text/plain; charset="UTF-8"
Mime-Version: 1.0
Content-Transfer-Encoding: 8bit
X-Scanned-By: MIMEDefang 2.68 on 10.5.11.26
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/YvnV3TMBreQzMEz7raYzuNP3jB8>
Cc: "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: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Mon, 02 Nov 2015 16:39:48 -0000

On Mon, 2015-11-02 at 11:20 -0500, Watson Ladd wrote:
> It's completely irrelevant in practice. Multiplying points by 4 or 8
> before hashing and after subtracting for equality checks produces a
> prime order group without the efficiency loss inherent to these
> formulas. Furthermore, applications we have today only rely on ECDH
> and signatures

... and SPAKE. Chromium already implements it. MIT krb5 has an
implementation in a branch.

> On Mon, Nov 2, 2015 at 10:49 AM, Dan Brown <dbrown@certicom.com>
> wrote:
> > http://ia.cr/2015/1060
> > 
> > seems to finally have more efficient answers to the old questions
> > above and
> > below.
> > 
> > > -----Original Message-----
> > > From: Samuel Neves [mailto:sneves@dei.uc.pt]
> > > Sent: Monday, December 08, 2014 4:11 PM
> > > To: Dan Brown; 'cfrg@irtf.org'
> > > Subject: Re: [Cfrg] Complete additon for cofactor 1 short
> > > Weierstrass
> > curve?
> > > 
> > > On 08-12-2014 18:46, Dan Brown wrote:
> > > > 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?
> > > 
> > > Both Arene-Kohel-Ritzenhaler (https://arxiv.org/abs/1102.2349,
> > > Remark 4.4)
> > > and Bos-Costello-Longa-Naehrig (https://eprint.iacr.org/2014/130,
> > > pg 37)
> > > present simplified formulas, both beating 51M. I don't know of
> > > other
> > attempts
> > > to optimize complete Weierstrass formulas.
> > 
> > 
> > _______________________________________________
> > Cfrg mailing list
> > Cfrg@irtf.org
> > https://www.irtf.org/mailman/listinfo/cfrg
> > 
> 
> 
>

v2.23.0 | Report a Bug | By Email