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

Peter Dettman <> Fri, 16 June 2017 04:59 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id ED1F01277BB for <>; Thu, 15 Jun 2017 21:59:32 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.9
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 ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id TDn7f7c4E-6p for <>; Thu, 15 Jun 2017 21:59:29 -0700 (PDT)
Received: from ( []) by (Postfix) with ESMTP id D78981200F3 for <>; Thu, 15 Jun 2017 21:59:27 -0700 (PDT)
X-Default-Received-SPF: pass (skip=loggedin (res=PASS));
To: Francisco Rodriguez- Henriquez <>, "" <>
References: <> <> <> <> <> <> <> <> <> <>
Cc: Julio César Lopez <>, Thomaz Oliveira <>,
From: Peter Dettman <>
Message-ID: <>
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: <>
Content-Type: text/plain; charset="windows-1252"
Content-Transfer-Encoding: 8bit
Archived-At: <>
Subject: Re: [Cfrg] How to (pre-)compute a ladder [revised version]
X-Mailman-Version: 2.1.22
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-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

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