Re: [Cfrg] draft-ladd-safecurves-02

Michael Hamburg <mike@shiftleft.org> Fri, 10 January 2014 19:50 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 298CD1AE1C9 for <cfrg@ietfa.amsl.com>; Fri, 10 Jan 2014 11:50:31 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 1.556
X-Spam-Level: *
X-Spam-Status: No, score=1.556 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_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 57TZK-mQENCq for <cfrg@ietfa.amsl.com>; Fri, 10 Jan 2014 11:50:29 -0800 (PST)
Received: from aspartame.shiftleft.org (199-116-74-157-v301.PUBLIC.monkeybrains.net [199.116.74.157]) by ietfa.amsl.com (Postfix) with ESMTP id DC5981AE1C4 for <cfrg@irtf.org>; Fri, 10 Jan 2014 11:50:29 -0800 (PST)
Received: from [10.184.148.249] (w035.z205158021.lax-ca.dsl.cnc.net [205.158.21.35]) by aspartame.shiftleft.org (Postfix) with ESMTPSA id A859E3AA04; Fri, 10 Jan 2014 11:48:54 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=shiftleft.org; s=sldo; t=1389383335; bh=XS70KsmaQhEAvOHef3See6n8j5V4SafD98KxQaTvw24=; h=Subject:From:In-Reply-To:Date:Cc:References:To:From; b=jPwcrQFkzQaY59wxdIiWSF4IG10SRDNs0k63Ma56ph5tFwyBid9AvRrqPkkj/zSx+ 6BRATWm0bOrOdHDCgYIpZP98NNaTOJYKnuSd8MHjhblOFIbg4wFj8QCc+pN1PGqt0w WAY6rNc9yc2c4Z6VPp5TOZvrW/dgGxJz1jsv/bNw=
Content-Type: text/plain; charset=windows-1252
Mime-Version: 1.0 (Mac OS X Mail 7.1 \(1827\))
From: Michael Hamburg <mike@shiftleft.org>
In-Reply-To: <CACsn0c=Kq3TjCyBmU7xcEorFFjZ7T4u4DboOw68FXC_QKeMQ5Q@mail.gmail.com>
Date: Fri, 10 Jan 2014 11:50:16 -0800
Content-Transfer-Encoding: quoted-printable
Message-Id: <6D692972-8A38-4588-B666-A5E481759003@shiftleft.org>
References: <CACsn0c=uuzsH3Zd-tPEAMsxAbk-RpQEHpfbTh9gHJi5ggjT+qg@mail.gmail.com> <CAGZ8ZG1D6284J35hgtBvcT3U46C30wSxZ=c+dV-csoXzPTGxZg@mail.gmail.com> <CACsn0c=Kq3TjCyBmU7xcEorFFjZ7T4u4DboOw68FXC_QKeMQ5Q@mail.gmail.com>
To: Watson Ladd <watsonbladd@gmail.com>
X-Mailer: Apple Mail (2.1827)
Cc: Trevor Perrin <trevp@trevp.net>, "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] draft-ladd-safecurves-02
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: Fri, 10 Jan 2014 19:50:31 -0000

On Jan 10, 2014, at 11:25 AM, Watson Ladd <watsonbladd@gmail.com> wrote:

> On Fri, Jan 10, 2014 at 11:20 AM, Trevor Perrin <trevp@trevp.net> wrote:
>> On Fri, Jan 10, 2014 at 11:11 AM, Watson Ladd <watsonbladd@gmail.com> wrote:
>>> Added: explicit formulas and a point format (big endian with a bit for
>>> the missing coordinate).
>> 
>> I don't see the draft yet, but if you're including point formats, any
>> thoughts on Jivsov's trick?
>> 
>> http://tools.ietf.org/html/draft-jivsov-ecc-compact-03
> 
> Assumes short Weierstrass form. I did put in x coordinate only for
> Montgomery, but it's not the same thing.

Well, you can do it in any coordinate system where negating one coordinate negates the point.  You just have to change section 4.3 to use the curve’s formula instead of the short Weierstrass formula.  For example, you can do it with Edwards curves and negate x instead of y.

This trick is neat, but it saves only one bit, and restricts to a subset of EC points.  You can do the same thing with some other subset, particularly with Edwards curves.  For example, you could restrict to only q-torsion or only 2q-torsion points, or only Elligator-encodable points.

I think the fastest way to do this is the one I posted with the inverse square root on the isomorphic Montgomery curve, but there are other options which basically accomplish the same thing.

— Mike