Re: [Cfrg] Edwards ladder

Mike Hamburg <mike@shiftleft.org> Tue, 02 December 2014 18:12 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 B342C1A6FB9 for <cfrg@ietfa.amsl.com>; Tue, 2 Dec 2014 10:12:00 -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 mA0YQgu5txLw for <cfrg@ietfa.amsl.com>; Tue, 2 Dec 2014 10:11:58 -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 6B8BA1A6FCD for <cfrg@irtf.org>; Tue, 2 Dec 2014 10:11:04 -0800 (PST)
Received: from [192.168.1.102] (unknown [192.168.1.1]) by aspartame.shiftleft.org (Postfix) with ESMTPSA id 0C64F3AA12; Tue, 2 Dec 2014 10:10:47 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=shiftleft.org; 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: <547E00B4.7040708@shiftleft.org>
Date: Tue, 02 Dec 2014 10:11:00 -0800
From: Mike Hamburg <mike@shiftleft.org>
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 <rransom.8774@gmail.com>, Watson Ladd <watsonbladd@gmail.com>
References: <CACsn0cmbFO8q--_=gwHUGO=aA=W_yJk3zGho1MWkiobB_qoQhw@mail.gmail.com> <CABqy+sphAzC-rX06f61YVT8rjZVZbyMjGneouTb=ry0S783_+A@mail.gmail.com>
In-Reply-To: <CABqy+sphAzC-rX06f61YVT8rjZVZbyMjGneouTb=ry0S783_+A@mail.gmail.com>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 7bit
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/jeowhfc3Tq8nX6ux1D1-YG4-Dvs
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] Edwards ladder
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: Tue, 02 Dec 2014 18:12:04 -0000

On 12/02/2014 09:53 AM, Robert Ransom wrote:
> On 12/2/14, Watson Ladd <watsonbladd@gmail.com>; 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
> <http://hyperelliptic.org/EFD/g1p/auto-edwards-yzsquared.html> 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