Re: [Cfrg] New names for draft-ladd-safecurves

Robert Ransom <rransom.8774@gmail.com> Tue, 21 January 2014 06:44 UTC

Return-Path: <rransom.8774@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 EB2C31A00E5 for <cfrg@ietfa.amsl.com>; Mon, 20 Jan 2014 22:44:36 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.75
X-Spam-Level:
X-Spam-Status: No, score=-1.75 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_ENVFROM_END_DIGIT=0.25, FREEMAIL_FROM=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 qxkJhb4A9cTO for <cfrg@ietfa.amsl.com>; Mon, 20 Jan 2014 22:44:35 -0800 (PST)
Received: from mail-qe0-x229.google.com (mail-qe0-x229.google.com [IPv6:2607:f8b0:400d:c02::229]) by ietfa.amsl.com (Postfix) with ESMTP id 709E61A0020 for <cfrg@irtf.org>; Mon, 20 Jan 2014 22:44:35 -0800 (PST)
Received: by mail-qe0-f41.google.com with SMTP id gc15so3936256qeb.28 for <cfrg@irtf.org>; Mon, 20 Jan 2014 22:44:35 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=IcfZyek3l/mNlCY3Zjd20jtnkdSUAOfvvusB/fjL0kY=; b=IQQUMbubbpsFPrZA10tKiAmisXe7JJthKgLatb6XzX5bsznbo/wKo0xEnKhTxZb8HA Kk8/XpnzpYFyLwLoiFSDRGTOcgXc1bpZ5IpS5i6+r3e5WVd2cyKptdnKYZNSnHvbNaTZ AAQ51qi2nWzKRvk7WVQposvxu9hgGmrp0WaZ+V4n+ePQA+1/d8BTu0UTC+3fNcVJCWfv n3UdV61x0BCVzpkaYUXv+qIDLeV6tZ/tysQg3QSgZQcUxoFPBpSefEgY4MmMNnmDTcZQ T1+ks/K+XlPl0K0TB1jPdWF7AxS++H/3hPO8vqShADb8yEoxIO1POX9E2W4eyIK9JLQq VguQ==
MIME-Version: 1.0
X-Received: by 10.224.111.195 with SMTP id t3mr34781175qap.2.1390286675120; Mon, 20 Jan 2014 22:44:35 -0800 (PST)
Received: by 10.229.181.132 with HTTP; Mon, 20 Jan 2014 22:44:34 -0800 (PST)
In-Reply-To: <1BDA9C49-6458-4005-9682-B8CEEA5C9257@shiftleft.org>
References: <CACsn0ck02mnETBUfuyJjLV9K8Yuiki8_-RG0tVszL8BDhkK27w@mail.gmail.com> <6489F7D3-BF54-416F-94BE-64FD1CFCCB1E@callas.org> <CACsn0cn0938BHMs7uFJYeB_q2VcGQULcF8fzc7KR67A_+mqzLw@mail.gmail.com> <264676DC-14DA-432E-81AB-CD0D852307A4@shiftleft.org> <CABqy+sr1zc-T-F3D_VOoz2B9GNZPsAxi=HeMoe=DwG5EJq8AuA@mail.gmail.com> <CACsn0ckg3Pna2bd9RPZnDGWa=GSaLGykkdqPwg3bat0+p2ZGcA@mail.gmail.com> <CABqy+sqb_CcSpg5g_N1TD1JcSktjtRE7Yj-aMjWpSN18Zuk6-Q@mail.gmail.com> <1BDA9C49-6458-4005-9682-B8CEEA5C9257@shiftleft.org>
Date: Mon, 20 Jan 2014 22:44:34 -0800
Message-ID: <CABqy+soScpQOdqnCh8m52-nNLA-kZ8O0NRNx4q0jV3mK24XO1w@mail.gmail.com>
From: Robert Ransom <rransom.8774@gmail.com>
To: Mike Hamburg <mike@shiftleft.org>
Content-Type: text/plain; charset=UTF-8
Cc: cfrg@irtf.org
Subject: Re: [Cfrg] New names for draft-ladd-safecurves
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, 21 Jan 2014 06:44:37 -0000

On 1/20/14, Mike Hamburg <mike@shiftleft.org> wrote:
>
> On Jan 20, 2014, at 9:06 PM, Robert Ransom <rransom.8774@gmail.com> wrote:
>> I would suggest using the Montgomery-form x coordinate with the sign
>> bit of the Edwards-form x coordinate.  (In fact, I *did* suggest that:
>> <http://www.ietf.org/mail-archive/web/cfrg/current/msg03868.html>
>> <http://www.ietf.org/mail-archive/web/cfrg/current/msg03870.html>)
>
> Amusingly, if you say that "sign" is "Jacobi symbol" (when p==3 mod 4), the
> two are the same for q-torsion points.  But either way, the difference is a
> couple of field muls vs a slightly messier spec.

The least significant bit of the least positive residue is easier to
compute during point compression, and is well-defined regardless of
the field order, so I would use that instead.

>> And yes, the Brier-Joye formulas to recover Montgomery-form y after
>> the Montgomery ladder would be faster than Brauer's algorithm on
>> Edwards-form points for variable-base single-scalar multiplication.

> Is this still true for large curves?  I don't think it's true
> asymptotically, and if people switch from inverse-by-exp to
> inverse-by-blind-and-EGCD, then you lose your free square root and the
> tradeoff might happen before 521 bits.  You might get your freebie back
> again if you spec that sign is Jacobi symbol and use a blind EGCD
> inverse-and-Jacobi-symbol, but again this only works for p==3 mod 4.

The Montgomery-form ladder takes 5M+4S+1*param+... per scalar bit.

Edwards-form Brauer (assuming a=-1) takes 3M+4S+... per doubling, and
1M (conversion to extended coordinates) + 7M+... (madd-2008-hwcd-4;
assuming the table is affine) per scalar limb, so it could (just
barely, counting multiplications only) appear to break even using
4-bit limbs.  But the table precomputation for that includes multiple
point additions and an inversion, and each 4-bit scalar limb requires
a constant-time lookup from a 7-element table, so even asymptotically,
you're eaten by overhead.


Robert Ransom