Re: [Cfrg] Hashing to EC group elements

"Igoe, Kevin M." <kmigoe@nsa.gov> Wed, 08 January 2014 19:38 UTC

Return-Path: <kmigoe@nsa.gov>
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 8ACFC1AE125 for <cfrg@ietfa.amsl.com>; Wed, 8 Jan 2014 11:38:50 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -7.438
X-Spam-Level:
X-Spam-Status: No, score=-7.438 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_HI=-5, RP_MATCHES_RCVD=-0.538] 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 oxWoZLkooaYt for <cfrg@ietfa.amsl.com>; Wed, 8 Jan 2014 11:38:48 -0800 (PST)
Received: from nsa.gov (emvm-gh1-uea09.nsa.gov [63.239.67.10]) by ietfa.amsl.com (Postfix) with ESMTP id F2BBA1AE088 for <cfrg@irtf.org>; Wed, 8 Jan 2014 11:38:47 -0800 (PST)
X-TM-IMSS-Message-ID: <5c14c29700010e80@nsa.gov>
Received: from MSHT-GH1-UEA01.corp.nsa.gov ([10.215.227.18]) by nsa.gov ([63.239.67.10]) with ESMTP (TREND IMSS SMTP Service 7.1; TLSv1/SSLv3 AES128-SHA (128/128)) id 5c14c29700010e80 ; Wed, 8 Jan 2014 14:38:49 -0500
Received: from MSMR-GH1-UEA06.corp.nsa.gov (10.215.225.2) by MSHT-GH1-UEA01.corp.nsa.gov (10.215.227.18) with Microsoft SMTP Server (TLS) id 14.2.342.3; Wed, 8 Jan 2014 14:38:37 -0500
Received: from MSMR-GH1-UEA03.corp.nsa.gov ([10.215.224.3]) by MSMR-GH1-UEA06.corp.nsa.gov ([10.215.225.2]) with mapi id 14.01.0289.001; Wed, 8 Jan 2014 14:38:36 -0500
From: "Igoe, Kevin M." <kmigoe@nsa.gov>
To: 'Robert Ransom' <rransom.8774@gmail.com>, "cfrg@irtf.org" <cfrg@irtf.org>
Thread-Topic: [Cfrg] Hashing to EC group elements
Thread-Index: AQHPCY9fBioria4JF0qFnqayFjIfipp7M2hw
Date: Wed, 8 Jan 2014 19:38:36 +0000
Message-ID: <3C4AAD4B5304AB44A6BA85173B4675CABA9A1201@MSMR-GH1-UEA03.corp.nsa.gov>
References: <CABqy+sr2z5cV_7snYGz98Xj9QVj4xpYd1L+DQ6O7sO29zyYKKA@mail.gmail.com>
In-Reply-To: <CABqy+sr2z5cV_7snYGz98Xj9QVj4xpYd1L+DQ6O7sO29zyYKKA@mail.gmail.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
x-originating-ip: [10.215.225.46]
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: base64
MIME-Version: 1.0
Subject: Re: [Cfrg] Hashing to EC group elements
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: Wed, 08 Jan 2014 19:38:50 -0000

Robert:

  Thanks for the pointer to the paper, I'm enjoying working through it
in more detail.

   One of my coworkers reminded me of the Cardano's algorithm for solving
cubic equations (published in 1545). I'd long ago consigned this to my
ever growing list of interesting but basically useless mathematics.  
It is a deterministic algorithm for solving cubic equations, only
requiring the ability to solve quadratic equations and take cube roots.
At first look this seems to be constant time, might have to stray into
GF(q^6) arithmetic.  We're looking to see if the following idea would work:

	1) Pick an arbitrary y0 on GF(q).
	2) Use Cardano to find a root x0 \in GF(q^3) of x^3 + a*x + b = y0^2.
      3) Apply your I + \phi + \phi(\phi) map to drive (x0,y0) back
         to a point on (x1,y1) \in E/GF(q).

Doesn't give indistinguishability, but it would avoid DragonFly's hunt & peck.
At first glance it looks like it works, but I've learned the hard way to never 
trust anything like this until I've actually programmed it up.

> -----Original Message-----
> From: Cfrg [mailto:cfrg-bounces@irtf.org] On Behalf Of Robert Ransom
> Sent: Saturday, January 04, 2014 3:56 PM
> To: cfrg@irtf.org
> Subject: [Cfrg] Hashing to EC group elements
> 
> For any odd-characteristic elliptic curve with a rational point of
> order 2, the ‘Elligator 2’ injective map described in
> <http://elligator.cr.yp.to/elligator-20130828.pdf> can be used to map
> an element of the coordinate field to a point on the curve.
> 
> If a curve in short-Weierstrass form (y^2 = x^3 + ax + b) has no
> rational points of order 2, then x^3 + ax + b is irreducible and the
> curve has full 2-torsion over the degree-3 extension of its coordinate
> field.  It's straightforward to modify the Elligator 2 formulas to map
> to a curve in short-Weierstrass form *given the x coordinate of a point
> of order 2*; once one has hashed to a point P over the extension field,
> P + f(P) + f(f(P)) (where f is the Frobenius automorphism of the
> extension field holding the base field fixed) is a point over the base
> field.  (If the input to the Elligator map is in the base field, an
> equivalent formulation is to use the Elligator 2 formulas with each of
> the three 2-torsion points, and add the resulting points.)
> 
> 
> Robert Ransom
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman	/listinfo/cfrg