Re: [Cfrg] How to (pre-)compute a ladder [revised version]

Mike Hamburg <mike@shiftleft.org> Fri, 12 May 2017 21:19 UTC

Return-Path: <mike@shiftleft.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 592CC13149B for <cfrg@ietfa.amsl.com>; Fri, 12 May 2017 14:19:45 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.001
X-Spam-Level:
X-Spam-Status: No, score=-2.001 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HTML_MESSAGE=0.001, RP_MATCHES_RCVD=-0.001, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=shiftleft.org
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 w0Ni5y8YwjNY for <cfrg@ietfa.amsl.com>; Fri, 12 May 2017 14:19:42 -0700 (PDT)
Received: from astral.shiftleft.org (vpn.shiftleft.org [52.40.228.30]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 68E16129C01 for <cfrg@irtf.org>; Fri, 12 May 2017 14:15:02 -0700 (PDT)
Received: from [10.184.148.249] (unknown [209.36.6.244]) (Authenticated sender: mike) by astral.shiftleft.org (Postfix) with ESMTPSA id 4161BA0061; Fri, 12 May 2017 14:15:01 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=shiftleft.org; s=sldo; t=1494623701; bh=cQmpyCZL/d8zBIuQZPEEfGDdCuNjWLmv6Y/hht9hF8A=; h=From:Subject:Date:In-Reply-To:Cc:To:References:From; b=Rg7/T1gXAI/YfNQldTJGllRaajY/MZ/LFc32M2IdAZ42RZZD5BC26IWkK7EmbT04e 4ptOK3VbpMzlCrpkGXxFJ9PU3w66M9jDeI5W8PaW5CIhBzpGhUwI4ZwOOUb739TlqQ vPbRx3jnxMSPa8I1liY0r1y+TtMowb9qtZ7p4MHU=
From: Mike Hamburg <mike@shiftleft.org>
Message-Id: <65F948B0-58FB-4073-B3D1-70B6ACB6C832@shiftleft.org>
Content-Type: multipart/signed; boundary="Apple-Mail=_09B506A7-1BBE-4797-A5E2-930E29C1F42E"; protocol="application/pkcs7-signature"; micalg=sha1
Mime-Version: 1.0 (Mac OS X Mail 10.3 \(3273\))
Date: Fri, 12 May 2017 14:15:00 -0700
In-Reply-To: <alpine.LFD.2.02.1705111858040.25089@delta.cs.cinvestav.mx>
Cc: "cfrg@irtf.org" <cfrg@irtf.org>, =?utf-8?Q?Julio_C=C3=A9sar_Lopez?= <jlopez@ic.unicamp.br>, Thomaz Oliveira <thomaz.figueiredo@gmail.com>, huseyin.hisil@yasar.edu.tr
To: Francisco Rodriguez- Henriquez <francisco@cs.cinvestav.mx>
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>
X-Mailer: Apple Mail (2.3273)
X-Virus-Scanned: clamav-milter 0.99.2 at astral
X-Virus-Status: Clean
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/f4F5A74jOeKhcAKqDpjTyW92Uv4>
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, 12 May 2017 21:19:45 -0000

Hello Francisco et al,

This is a clever and useful piece of work.  It’s a good intermediate between just using the standard Montgomery ladder for everything, and going to a full Edwards implementation with combs or something.  It especially seems useful where power analysis resistance is required, because other precomputation methods usually aren’t suitable.  The RTL Montgomery ladder (or Joye double-add ladder) is already known to be useful in this situation, at least with some modification to prevent coordinates from staying the same between iterations.  Since you’re speeding up the RTL Montgomery ladder, your optimization can slot right in to some implementations.

You should probably compare to existing Edwards precomputation methods in your paper, since they are the likely alternative to your technique.  In particular, I noticed that you compared against the EBACS version of Ed448-Goldilocks.  With a fixed base point, your method uses 41% less time for the Montgomery ladder with a 25kiB table.  However, the EBACS version of Ed448-Goldilocks doesn’t use the Montgomery ladder for fixed-base scalarmul.  Instead it uses a combs algorithm, which uses a 15kiB table and takes about 70% less time than the Montgomery ladder; see https://bench.cr.yp.to/results-dh.html <https://bench.cr.yp.to/results-dh.html>.  Libdecaf likewise uses precomputed combs for fixed-base scalarmul.  But your new technique is certainly simpler.

Cheers,
— Mike

> On May 11, 2017, at 5:14 PM, Francisco Rodriguez- Henriquez <francisco@cs.cinvestav.mx> 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