[Cfrg] Edwards ladder

Watson Ladd <watsonbladd@gmail.com> Tue, 02 December 2014 17:06 UTC

Return-Path: <watsonbladd@gmail.com>
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 023F51A1AA7 for <cfrg@ietfa.amsl.com>; Tue, 2 Dec 2014 09:06:49 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2
X-Spam-Level:
X-Spam-Status: No, score=-2 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, SPF_PASS=-0.001] autolearn=ham
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 WiedZ4sM7TOK for <cfrg@ietfa.amsl.com>; Tue, 2 Dec 2014 09:06:46 -0800 (PST)
Received: from mail-yh0-x229.google.com (mail-yh0-x229.google.com [IPv6:2607:f8b0:4002:c01::229]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id C87BA1A1EF5 for <cfrg@irtf.org>; Tue, 2 Dec 2014 09:06:30 -0800 (PST)
Received: by mail-yh0-f41.google.com with SMTP id a41so6231034yho.28 for <cfrg@irtf.org>; Tue, 02 Dec 2014 09:06:30 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:date:message-id:subject:from:to:content-type; bh=ef9wq5kEIkaAA/QaZaeeSc+VrkhCnJM8GpOMbt/g8QI=; b=DBqiSck4VlFIT177lQCwPwSK2RrRGmFRAivLPqPOz1b+rpFblzjoS449AF+lyNh5JK mEYo5MbOTUX6dOQQN9qd20bkpnU/LjhGCe+lkGVbRCorPKwtNPS8LE77eXUzk4wJiJwv SVzUeyv9dHAOdV29hOiBGutAt2z8XAUDO7YMAWsMiC9iAVmhhofa1Z0ARNPq+g9cbAV7 cMFGBFShc7Es2H0nA6ey+up/Y14+NkOceGfUI/RPq4aBfrWSdZedxPmfJmwWEBX0r6tY YX+GBZU/4jlfV7O+Ye4PVPM7L7CiAV+Jc8fDj50j5nWIVpnrxgb51FI9/AoHCpo6OiBw 38QA==
MIME-Version: 1.0
X-Received: by 10.236.22.36 with SMTP id s24mr363573yhs.138.1417539990076; Tue, 02 Dec 2014 09:06:30 -0800 (PST)
Received: by 10.170.195.21 with HTTP; Tue, 2 Dec 2014 09:06:30 -0800 (PST)
Date: Tue, 2 Dec 2014 09:06:30 -0800
Message-ID: <CACsn0cmbFO8q--_=gwHUGO=aA=W_yJk3zGho1MWkiobB_qoQhw@mail.gmail.com>
From: Watson Ladd <watsonbladd@gmail.com>
To: "cfrg@irtf.org" <cfrg@irtf.org>
Content-Type: text/plain; charset=UTF-8
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/0H2VSkRl6Qov0Q6QEDYqfUIftWQ
Subject: [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 17:06:49 -0000

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.

The relatively little amount of thought I've given to this matter
hasn't produced an isogeny that makes d square. Furthermore, picking d
square makes the addition laws not complete: it's not possible to have
both the efficient ladder and a complete addition law simultaneously
when using Edwards coordinates.

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.

This leaves signatures and which form of Montgomery ladder ECDH to use
as open issues.

Sincerely,
Watson Ladd