Re: [Cfrg] Curve manipulation, revisited

Michael Hamburg <mike@shiftleft.org> Wed, 07 January 2015 18:34 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 B28781A014C for <cfrg@ietfa.amsl.com>; Wed, 7 Jan 2015 10:34:03 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 1.555
X-Spam-Level: *
X-Spam-Status: No, score=1.555 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, 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 iGUzKFkVQar9 for <cfrg@ietfa.amsl.com>; Wed, 7 Jan 2015 10:34:00 -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 5B3161A00B0 for <cfrg@irtf.org>; Wed, 7 Jan 2015 10:34:00 -0800 (PST)
Received: from [10.184.148.249] (unknown [209.36.6.242]) by aspartame.shiftleft.org (Postfix) with ESMTPSA id C6DDE3AA43; Wed, 7 Jan 2015 10:31:20 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=shiftleft.org; s=sldo; t=1420655480; bh=FTiQw7TLNYtBe1IlJzke7xF0SqYFOmkIalFDbtLmbc4=; h=Subject:From:In-Reply-To:Date:Cc:References:To:From; b=OG897iAqXbOItVnWSICHqN40ke4g5C9sxR9UXGSjHASOl6g5/9NrMnIDOUW0DVIA5 hWEfIE6pihiMBJOq4vOeQdwssCDKAtRybJkca8021PFAIEBrzjdiHJ8GCKTL4hA2tn VUpzgJxqe+oqFzFvgOBmcr+7zsHdaKcIiNmJZj3I=
Content-Type: text/plain; charset=utf-8
Mime-Version: 1.0 (Mac OS X Mail 8.2 \(2064\))
From: Michael Hamburg <mike@shiftleft.org>
In-Reply-To: <54A51E97.5060508@bouncycastle.org>
Date: Wed, 7 Jan 2015 10:33:58 -0800
Content-Transfer-Encoding: quoted-printable
Message-Id: <FE4218BA-0CE1-4971-8A7B-4E3440088560@shiftleft.org>
References: <CAMfhd9W684XMmXn3ueDmwrsQ_ZdiFG+VqYLxkvs7qDwiJdpk6w@mail.gmail.com> <1725646678.805875.1419539885135.JavaMail.yahoo@jws100115.mail.ne1.yahoo.com> <CAMfhd9Ua5fFZk46Xx1AN2VgyJ=Yng6fnO8aN-_ZfzXQn0Xbxhg@mail.gmail.com> <CA+Vbu7zqFcu8d1053mZ_eEm0q=np6T3snSQ4rfY0k1-4hBVDsA@mail.gmail.com> <CAMfhd9XEqMwFzJ4sK4aHGbke6REZb26uaEEv9gbM5v_goDzwUA@mail.gmail.com> <54A51E97.5060508@bouncycastle.org>
To: Peter Dettman <peter.dettman@bouncycastle.org>
X-Mailer: Apple Mail (2.2064)
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/yhP17YgbWN_x9m9e1oBYnE849GE
Cc: Adam Langley <agl@imperialviolet.org>, cfrg@irtf.org
Subject: Re: [Cfrg] Curve manipulation, revisited
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: Wed, 07 Jan 2015 18:34:03 -0000

> On Jan 1, 2015, at 2:16 AM, Peter Dettman <peter.dettman@bouncycastle.org>; wrote:
> 
> On 29/12/2014 8:31 pm, Adam Langley wrote:
>> (An implementation that wants to use a windowed method with a Montgomery-X *input* will need to perform a square-root first, but that's the same cost as a design where compressed Edwards points are sent. Note: smarter people than I might be able to eliminate the square-root but I don't see it)
> 
> I believe I can give an example of how to eliminate the square-root for a random-base scalar-mult. I'll use short Weierstrass to describe it though, as I'm less familiar with Edwards and Montgomery. I assume we can convert easily enough between forms, and that twist security carries across.
> 
> - Given input X0, use curve equation to calculate {Y0}^2, let K = {Y0}^2.
> - Initial point P0 is (X0,{Y0}) where {Y0} is unevaluated.
> - Change of variables to an isomorphic curve: x' = u^2.x, y' = u^3.y, a' = u^4.a, with u = {Y0} (b' = u^6.b, but not typically needed).
> - Can now write P0' as (K.X0, K^2) without unknowns.
> - Proceed with scalar multiplication of P0' to result point Pn'.
> - Recover output Xn from Pn' as Xn'/(K.Zn^2).
> 
> Note that the doubling formula is affected by the changed a' curve parameter (unless a==0); assume modified-Jacobian coordinates are used.
> 
> In the case where the original curve has a==-3, the extra cost of the windowing using the isomorphism in modified-Jacobian coordinates is +2S(quares) per addition (doubling cost is unchanged). The total extra cost using width 5 windows is therefore < 40% of the best-case cost of a sqrt.
> 
> However, there are actually good performance reasons to already be using an isomorphism: to allow mixed addition with precomputed points without needing an inversion in the precomputation. In that case, there is very little additional overhead for the scheme above.
> 
> Regards,
> Pete Dettman

This is neat.  Have you tested it?  Does it work, and do you know if it’s better than a Montgomery ladder?  From your high-level description it looks like it should be competitive with the short Weierstrass XZ Montgomery ladder (8M + 7S + 5m IIUC).

Cheers,
— Mike