Re: [Cfrg] On relative performance of Edwards v.s. Montgomery Curve25519, variable base

Michael Hamburg <mike@shiftleft.org> Mon, 12 January 2015 06:52 UTC

Return-Path: <mike@shiftleft.org>
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 0CA021A8A56 for <cfrg@ietfa.amsl.com>; Sun, 11 Jan 2015 22:52:45 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 3.855
X-Spam-Level: ***
X-Spam-Status: No, score=3.855 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FH_HOST_EQ_D_D_D_D=0.765, FH_HOST_EQ_D_D_D_DB=0.888, HELO_MISMATCH_ORG=0.611, HOST_MISMATCH_NET=0.311, MANGLED_SMALL=2.3, RDNS_DYNAMIC=0.982, SPF_HELO_PASS=-0.001, 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 VkKL0T2bZIEk for <cfrg@ietfa.amsl.com>; Sun, 11 Jan 2015 22:52:43 -0800 (PST)
Received: from aspartame.shiftleft.org (199-116-74-168-v301.PUBLIC.monkeybrains.net [199.116.74.168]) (using TLSv1.1 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 6D8311A8A50 for <cfrg@irtf.org>; Sun, 11 Jan 2015 22:52:43 -0800 (PST)
Received: from [192.168.1.117] (unknown [192.168.1.1]) by aspartame.shiftleft.org (Postfix) with ESMTPSA id 2118A3AA12; Sun, 11 Jan 2015 22:49:47 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=shiftleft.org; s=sldo; t=1421045387; bh=2broj1f3E3iUaz8TnJ3lPbL/NyoiLZOv8hZ4UWqN5e8=; h=Subject:From:In-Reply-To:Date:Cc:References:To:From; b=K1LPqb+V+UDvm5xgf+h/dfK+hq53+yMbqoBAd55QUsi0Hu/yhIeNCgABfO+px9iZ+ pQf1wNqS3MhzZAAmRY/OAmRXpPF4/VBgCCG5ePY2V7WougSz+yWzbEHKKLk1xVO9F9 9aD+x+rFw9r3A36EWOelGYRlEy0LJdk8HbHyfwPs=
Content-Type: text/plain; charset=utf-8
Mime-Version: 1.0 (Mac OS X Mail 8.2 \(2070.1\))
From: Michael Hamburg <mike@shiftleft.org>
In-Reply-To: <54B36B4E.9010006@brainhub.org>
Date: Sun, 11 Jan 2015 22:52:41 -0800
Content-Transfer-Encoding: quoted-printable
Message-Id: <9A155377-9754-44AB-8C62-D2F10C444BCE@shiftleft.org>
References: <54AA4AB9.70505@brainhub.org> <54B315CA.6040900@brainhub.org> <88805D27-3B08-421D-B62A-2FC61AC5851A@shiftleft.org> <54B36B4E.9010006@brainhub.org>
To: Andrey Jivsov <crypto@brainhub.org>
X-Mailer: Apple Mail (2.2070.1)
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/ap6xwjuWbYjOp0GNNc7En82lxlw>
Cc: cfrg@irtf.org
Subject: Re: [Cfrg] On relative performance of Edwards v.s. Montgomery Curve25519, variable base
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, 12 Jan 2015 06:52:45 -0000

> On Jan 11, 2015, at 10:35 PM, Andrey Jivsov <crypto@brainhub.org> wrote:
> 
> On 01/11/2015 06:52 PM, Michael Hamburg wrote:
>> Thanks for your analysis!  However, please note that with lazy extended homogeneous coordinates on a twisted Edwards curve with a=-1, the cost of an Edwards addition to an accumulator is 8M and not 10M+1S, and the cost of a doubling is still 3M+4S, perhaps with an additional 1M to convert from this form to a suitable one for the window table.
> You are welcome. I would appreciate a pointer to the method.

For the method with lookahead, Hüseyin Hışıl, thesis, http://eprints.qut.edu.au/33233/1/H%C3%BCseyin_Hi%C5%9Fil_Thesis.pdf

For the method with a 5-element accumulator,
https://eprint.iacr.org/2012/309

This is also used in the Goldilocks code.

>> Furthermore, the multiplication by a constant in the Montgomery curve is not negligible, but neither is the cost of a constant-time lookup in the Edwards window table.
> 
> Right, I was ignoring additions and multiplication by a constant.
> 
> Assuming M/4 for a24 (e.g. 4-limb F(p) operations) and full M for d in t.Edwards (corresponding to the 37095705...283555 in draft-agl-cfrgcurve-00):
> 
> M: n*(5*M+4*S+M/4)+11*M + 245*S=1350*M + 1265*S
> tE: 2^(w-2)*(10*M+S+M) + 2^(w-2)*(3*M+4*S) + w*(ceil(n/w)-1)*(3*M+4*S)+(ceil(n/w)-1)*(10*M+S+M)+11*M + 245*S=1423*M + 1335*S

> 5.4%, 5.5% (M, S). Montgomery is better.

> With small curve constants (A, d), M/4 for the multiplication by these constants:
> M: currently optimal, same 1350*M + 1265*S
> tE: 2^(w-2)*(10*M+S+M/4) + 2^(w-2)*(3*M+4*S) + w*(ceil(n/w)-1)*(3*M+4*S)+(ceil(n/w)-1)*(10*M+S+M/4)+11*M + 245*S=1380*M + 1335*S
> 
> 2.2%, 5.5%. Montgomery is better.

If a readd is 8M (or 7M for a mixed add, 1M+1m to convert to readd form) then:

2^(w-2)*((7+1+1/4)*M) + 2^(w-2)*(3*M+4*S + M+M/4) + w*(ceil(n/w)-1)*(3*M+4*S)+(ceil(n/w)-1)*(8*M)+11*M + 245*S = 1261*M + 1277*S

That’s -12%M, -4%S vs Montgomery.  But the constant-time lookups may nullify that gain.

Cheers,
— Mike