IETF Logo Mail Archive

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

Samuel Neves <sneves@dei.uc.pt> Mon, 08 December 2014 21:12 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 62A8F1ACE1C for <cfrg@ietfa.amsl.com>; Mon, 8 Dec 2014 13:12:17 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -4.211
X-Spam-Level:
X-Spam-Status: No, score=-4.211 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, 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 KNlLBE_uMSyQ for <cfrg@ietfa.amsl.com>; Mon, 8 Dec 2014 13:12:13 -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 274AB1A1B06 for <cfrg@irtf.org>; Mon, 8 Dec 2014 13:12:06 -0800 (PST)
Received: from [10.9.0.1] (gtDEI-Vlans.dei.uc.pt [193.137.203.232]) (authenticated bits=0) by smtp.dei.uc.pt (8.14.4/8.14.4) with ESMTP id sB8LBQNM017405 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Mon, 8 Dec 2014 21:11:27 GMT
Message-ID: <548613FE.8060107@dei.uc.pt>
Date: Mon, 08 Dec 2014 21:11:26 +0000
From: Samuel Neves <sneves@dei.uc.pt>
User-Agent:
MIME-Version: 1.0
To: Dan Brown <dbrown@certicom.com>, "'cfrg@irtf.org'" <cfrg@irtf.org>
References: <810C31990B57ED40B2062BA10D43FBF5D21FA2@XMB116CNC.rim.net> <5483749E.1000504@dei.uc.pt> <810C31990B57ED40B2062BA10D43FBF5D23FBB@XMB116CNC.rim.net>
In-Reply-To: <810C31990B57ED40B2062BA10D43FBF5D23FBB@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: sB8LBQNM017405
X-FCTUC-DEI-SIC-MailScanner: Found to be clean
X-FCTUC-DEI-SIC-MailScanner-SpamCheck: not spam (whitelisted), 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/_osc2pzUELnnOC6BTeBZbnN74R0
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: Mon, 08 Dec 2014 21:12:18 -0000

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