IETF Logo Mail Archive

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

Dan Brown <dbrown@certicom.com> Mon, 02 November 2015 15:49 UTC

Return-Path: <dbrown@certicom.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 529851B48CA for <cfrg@ietfa.amsl.com>; Mon, 2 Nov 2015 07:49:59 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.6
X-Spam-Level:
X-Spam-Status: No, score=-2.6 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_LOW=-0.7] 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 u1m0ssiwySX3 for <cfrg@ietfa.amsl.com>; Mon, 2 Nov 2015 07:49:58 -0800 (PST)
Received: from smtp-p01.blackberry.com (smtp-p01.blackberry.com [208.65.78.88]) by ietfa.amsl.com (Postfix) with ESMTP id CB3C11B48C5 for <cfrg@irtf.org>; Mon, 2 Nov 2015 07:49:57 -0800 (PST)
Received: from xct102cnc.rim.net ([10.65.161.202]) by mhs212cnc.rim.net with ESMTP/TLS/AES256-SHA; 02 Nov 2015 10:49:56 -0500
Received: from XMB116CNC.rim.net ([fe80::45d:f4fe:6277:5d1b]) by XCT102CNC.rim.net ([fe80::2066:5d4f:8c45:af55%17]) with mapi id 14.03.0210.002; Mon, 2 Nov 2015 10:49:55 -0500
From: Dan Brown <dbrown@certicom.com>
To: "'sneves@dei.uc.pt'" <sneves@dei.uc.pt>, "'cfrg@irtf.org'" <cfrg@irtf.org>
Thread-Topic: [Cfrg] Complete additon for cofactor 1 short Weierstrass curve?
Thread-Index: AdAQBRZ3YiRvE6KSQn+nT3ij0mFhSwBwC18AAFMFjzAAEQVdAECL+Klw
Date: Mon, 02 Nov 2015 15:49:54 +0000
Message-ID: <810C31990B57ED40B2062BA10D43FBF5E76B45@XMB116CNC.rim.net>
References: <810C31990B57ED40B2062BA10D43FBF5D21FA2@XMB116CNC.rim.net> <5483749E.1000504@dei.uc.pt> <810C31990B57ED40B2062BA10D43FBF5D23FBB@XMB116CNC.rim.net> <548613FE.8060107@dei.uc.pt>
In-Reply-To: <548613FE.8060107@dei.uc.pt>
Accept-Language: en-CA, en-US
Content-Language: en-US
X-MS-Has-Attach: yes
X-MS-TNEF-Correlator:
x-originating-ip: [10.65.160.249]
Content-Type: multipart/signed; protocol="application/x-pkcs7-signature"; micalg="SHA1"; boundary="----=_NextPart_000_002C_01D1155C.35001F30"
MIME-Version: 1.0
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/KPWpdKGGzu7zKK7OFT_Ffswd5zs>
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 15:49:59 -0000

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.

v2.23.0 | Report a Bug | By Email