Re: [Cfrg] Edwards ladder

Mike Hamburg <> Tue, 02 December 2014 18:12 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id B342C1A6FB9 for <>; Tue, 2 Dec 2014 10:12:00 -0800 (PST)
X-Virus-Scanned: amavisd-new at
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 ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id mA0YQgu5txLw for <>; Tue, 2 Dec 2014 10:11:58 -0800 (PST)
Received: from ( []) (using TLSv1.1 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 6B8BA1A6FCD for <>; Tue, 2 Dec 2014 10:11:04 -0800 (PST)
Received: from [] (unknown []) by (Postfix) with ESMTPSA id 0C64F3AA12; Tue, 2 Dec 2014 10:10:47 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple;; s=sldo; t=1417543847; bh=d4HxjH55qv07UtxalGJsQPQglu0eQINFEmg73vXpLI8=; h=Date:From:To:CC:Subject:References:In-Reply-To:From; b=I7rCuHfkjS1Qpj4RdcIfvHjCdgf5RaySeUQNCN0QFvZmMKdJnha0sHoCuv2V4z3nX BjQoAjRx98kYtqtvkokc1/O3P/ovGpaJnQ9GyCEwb1H5d01tBj10cDglEzPckzBIMp NJcszv+b3ERd6ggA/dVUfjTphSOTIeJHTq3zvWVc=
Message-ID: <>
Date: Tue, 02 Dec 2014 10:11:00 -0800
From: Mike Hamburg <>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.2.0
MIME-Version: 1.0
To: Robert Ransom <>, Watson Ladd <>
References: <> <>
In-Reply-To: <>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 7bit
Cc: "" <>
Subject: Re: [Cfrg] Edwards ladder
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Tue, 02 Dec 2014 18:12:04 -0000

On 12/02/2014 09:53 AM, Robert Ransom wrote:
> On 12/2/14, Watson Ladd <>; wrote:
>> Dear all,
>> The formulas on the EFD for a y-coordinate only Edwards ladder require
>> d to be a square. They are slightly more efficient than the Montgomery
>> ladder when squaring is specially optimized. Unfortunately, the
>> Edwards curve formulas we are considering don't have d square.
> In order for the ladder formula shown on
> <> to be
> even close to more efficient, s must be chosen to be a small integer;
> r is then a ratio of small integers and 1*r requires two small-integer
> multiplies.
> Mike Hamburg tried that formula with an earlier version of his Ed448
> software, and found that they were slower than the Montgomery-form
> ladder.
IIRC I just guessed at the Edwards ladder's based on microbenchmarks, 
and figured it would be slower.  What was slower in my measurements, but 
faster in Microsoft's, was Edward fixed-window, which I may have 
mistakenly called "Edward ladder" in an email.  The discrepancy was 
partly because it requires point decompression, but MS ECCLib doesn't 
implement that, and partly for reasons unknown.
>> As a result, I think we don't have an alternative to Montgomery
>> x-coordinate only that is as efficient and as secure, and certainly
>> not as simple.  I think that most people on the list are in agreement
>> about this.
Yep.  There's also the option of a single-coordinate unified format, but 
those add quite a bit of complexity.  The one I used in Goldilocks also 
doesn't work when p==1 mod 4.

-- Mike