Re: [Cfrg] How to (pre-)compute a ladder [revised version]
Peter Dettman <peter.dettman@bouncycastle.org> Fri, 16 June 2017 04:59 UTC
Return-Path: <peter.dettman@bouncycastle.org>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id ED1F01277BB for <cfrg@ietfa.amsl.com>; Thu, 15 Jun 2017 21:59:32 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.9
X-Spam-Level:
X-Spam-Status: No, score=-1.9 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_NONE=-0.0001] autolearn=ham autolearn_force=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 TDn7f7c4E-6p for <cfrg@ietfa.amsl.com>; Thu, 15 Jun 2017 21:59:29 -0700 (PDT)
Received: from tauceti.org.au (mail.tauceti.org.au [203.32.61.25]) by ietfa.amsl.com (Postfix) with ESMTP id D78981200F3 for <cfrg@irtf.org>; Thu, 15 Jun 2017 21:59:27 -0700 (PDT)
X-Default-Received-SPF: pass (skip=loggedin (res=PASS)) x-ip-name=ppp-27-55-143-82.revip3.asianet.co.th;
To: Francisco Rodriguez- Henriquez <francisco@cs.cinvestav.mx>, "cfrg@irtf.org" <cfrg@irtf.org>
References: <CAHOTMVKHA-yJR1oCyPtUp4-aJVc3dTdyxQHNo4xqnJt0hU6jVQ@mail.gmail.com> <CAMm+Lwgm8XzTBarZ1eFePTZGORorBJAeF7brDkhWGQKQVT0LPQ@mail.gmail.com> <CAMm+LwggT_AVv=KjzM1r=6UnkeK+g8zkticXFBDQ0cUXs_PP0A@mail.gmail.com> <CAHOTMVLHPFyi2VWpv85hrZ1MoXqeHYUv52wkMxjj3xp5B4V1cw@mail.gmail.com> <CAMm+Lwgfk1=yEJSbZbaZLvF5k5k66VVSx6MzKLM+DbUV7Ls6Xw@mail.gmail.com> <CAHOTMVK1gYrFiwd8f8zf2zPXYyCorp+jixkcY5FLhfHfv0NkWw@mail.gmail.com> <CAMm+LwjeZdR=ZGX0topN2w6P12jEmR-TQ8M9+anyETj43nbiqg@mail.gmail.com> <CAHOTMVL2e2UjVX6VKgHUbOHrb-gsU8kn_cxY1FdNrnj29cki9g@mail.gmail.com> <alpine.LFD.2.02.1703291804030.8996@delta.cs.cinvestav.mx> <alpine.LFD.2.02.1705111858040.25089@delta.cs.cinvestav.mx>
Cc: Julio César Lopez <jlopez@ic.unicamp.br>, Thomaz Oliveira <thomaz.figueiredo@gmail.com>, huseyin.hisil@yasar.edu.tr
From: Peter Dettman <peter.dettman@bouncycastle.org>
Message-ID: <02899a12-8cf7-c318-32ea-9491ec2a22c2@bouncycastle.org>
Date: Fri, 16 Jun 2017 11:58:54 +0700
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.11; rv:45.0) Gecko/20100101 Thunderbird/45.8.0
MIME-Version: 1.0
In-Reply-To: <alpine.LFD.2.02.1705111858040.25089@delta.cs.cinvestav.mx>
Content-Type: text/plain; charset="windows-1252"
Content-Transfer-Encoding: 8bit
X-Authenticated-User: peter.dettman@bouncycastle.org
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/39tfYKoF7W87DF6NxqWXtXc7Y7M>
Subject: Re: [Cfrg] How to (pre-)compute a ladder [revised version]
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.22
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: Fri, 16 Jun 2017 04:59:33 -0000
Hi Francisco, I've updated my (java) implementations of X25519 and X448 in line with your revised paper. My rough benchmark results for a complete ECDH are -17.7% and -19.5% time required for X25519 and X448 respectively. These are perhaps slightly more modest than the paper's estimates. Your paper already anticipates that (uncounted) field add/sub are significant in practice. Part of the difference however is that my implementation of Algorithm 3 handles the final 'q' bits using simple doublings, and removes redundant cswaps - just as Algorithm 5 does. Of course Alg. 3 is just as presented in RFC 7748, but it might be a fairer comparison to first apply to Alg. 3 those of your optimizations that are applicable. Also, my (32-bit) X448 implementation (Alg. 5) required a carry propagation for 'A' (line 10), due to tight bounds on limbs when squaring D, E. I did the same for (32-bit) X25519 although I haven't yet proved it necessary. An idea: for fixed-base X25519, why not precompute one doubling? i.e. just calculate (k/2) * 2P, needing only 2 final doublings (you even already have S of order 4). I am not sure whether this extends to precomputing (q-1) doublings. Another thought that occurred to me is that someone might get the idea to use your fixed-base ladder with some other point. Couldn't this go awry if that point were already "P + S" or similar? If so, a caution somewhere in the paper on preconditions for the fixed point might be advised. Regards, Pete Dettman On 12/05/2017 7:14 AM, Francisco Rodriguez- Henriquez wrote: > Dear CFRG community, > > We would like to draw your attention to an improved version of our IACR > pre-print 2017/264 now entitled: > > "How to (pre-)compute a ladder" > > In this revised version, we present an improved differential addition > formula that uses pre-computation to match the computational cost of the > classical Montgomery differential addition. > > Accordingly, our estimates suggest that a full implementation of our > pre-computable ladder proposal should outperform state-of-the-art > software implementations of the X25519 and X448 functions by a 40% > speedup when working in the fixed-point scenario. > > We would be delighted to receive feedback (including sightings of typos) > from the CFRG community. > > With best regards, > > Thomaz Oliveira, Julio López, Hüseyin Hisil and Francisco > Rodríguez-Henríquez > > > _______________________________________________ > Cfrg mailing list > Cfrg@irtf.org > https://www.irtf.org/mailman/listinfo/cfrg >
- [Cfrg] Interest in an "Ed25519-HD" standard? Tony Arcieri
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Aaron Zauner
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Phillip Hallam-Baker
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Phillip Hallam-Baker
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Dmitry Khovratovich
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Phillip Hallam-Baker
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Tony Arcieri
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Nadim Kobeissi
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Tony Arcieri
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Taylor R Campbell
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Phillip Hallam-Baker
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Tony Arcieri
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Phillip Hallam-Baker
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Tony Arcieri
- [Cfrg] A note on how to (pre-)compute a ladder Francisco Rodriguez- Henriquez
- Re: [Cfrg] A note on how to (pre-)compute a ladder Peter Dettman
- Re: [Cfrg] A note on how to (pre-)compute a ladder Peter Dettman
- Re: [Cfrg] A note on how to (pre-)compute a ladder Francisco Rodriguez- Henriquez
- Re: [Cfrg] A note on how to (pre-)compute a ladder Francisco Rodriguez- Henriquez
- [Cfrg] How to (pre-)compute a ladder [revised ver… Francisco Rodriguez- Henriquez
- Re: [Cfrg] How to (pre-)compute a ladder [revised… Mike Hamburg
- Re: [Cfrg] How to (pre-)compute a ladder [revised… Peter Dettman
- Re: [Cfrg] How to (pre-)compute a ladder [revised… Antonio Sanso
- Re: [Cfrg] How to (pre-)compute a ladder [full C … Francisco Rodriguez- Henriquez
- Re: [Cfrg] How to (pre-)compute a ladder [revised… Francisco Rodriguez- Henriquez
- Re: [Cfrg] How to (pre-)compute a ladder [revised… Francisco Rodriguez- Henriquez