[Cfrg] Thoughts on a Next-Generation Elliptic Curve Signature Scheme?

Alyssa Rowan <akr@akr.io> Sat, 11 January 2014 18:35 UTC

Return-Path: <akr@akr.io>
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 7BAC01AE109 for <cfrg@ietfa.amsl.com>; Sat, 11 Jan 2014 10:35:47 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.902
X-Spam-Level:
X-Spam-Status: No, score=-1.902 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, SPF_HELO_PASS=-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 VntCih0FdPtH for <cfrg@ietfa.amsl.com>; Sat, 11 Jan 2014 10:35:45 -0800 (PST)
Received: from entima.net (entima.net [78.129.143.175]) by ietfa.amsl.com (Postfix) with ESMTP id 6FB6A1AE0E9 for <cfrg@irtf.org>; Sat, 11 Jan 2014 10:35:45 -0800 (PST)
Received: from [10.10.42.10] (cpc5-derb12-2-0-cust796.8-3.cable.virginm.net [82.31.91.29]) by entima.net (Postfix) with ESMTPSA id 688E2602F4; Sat, 11 Jan 2014 18:35:34 +0000 (GMT)
Message-ID: <52D18F07.90706@akr.io>
Date: Sat, 11 Jan 2014 18:35:51 +0000
From: Alyssa Rowan <akr@akr.io>
MIME-Version: 1.0
To: cfrg@irtf.org
References: <87eh4e7a2y.fsf@latte.josefsson.org> <52D17F30.1090008@drh-consultancy.co.uk> <CABqy+spAeJE9UcJccQ96s3stRkUvU8sHTzXgWp9pg99mKLkXiA@mail.gmail.com>
In-Reply-To: <CABqy+spAeJE9UcJccQ96s3stRkUvU8sHTzXgWp9pg99mKLkXiA@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 7bit
Subject: [Cfrg] Thoughts on a Next-Generation Elliptic Curve Signature Scheme?
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: Sat, 11 Jan 2014 18:35:47 -0000

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512

At some point, clearly we're going to need a signature scheme for
these "Chicago curves" specified in SafeCurves, for later use to
replace ECDSA with something which is a more convenient fit for them
and doesn't want random numbers for each signature, for future use in
certificates, authentication, and the like.

I feel like now would be a good point, hence this request for ideas.

On 11/01/2014 17:40, Robert Ransom wrote:
> Dr. Bernstein's EdDSA is even worse: it prohibits every curve that
>  Dr. Bernstein himself has specified since Curve25519.

EdDSA seem like a pretty good start for a new signature scheme to me,
even if as it stands I think it's closely tied to Ed25519 itself
(basically, due to the size and construction?).

Schnorr-type signatures using an Edwards representation would be the
obvious natural candidate.

Either the Edwards curves or the Edwards isomorphism of one of the
Montgomery curves would do, although the ones specified as Edwards
curves would likely be cleaner, particularly Curve1174, Curve3617 and
E521: in fact, those would be the three I'd plump for, as I think they
provide three pretty good security/efficiency points.

We're going to need a hash, too. I suggest that we should use one of
the new hash algorithms that came out of the SHA-3 competition. All
the finalists have something to recommend them (I really like Skein
and BLAKE myself): but the least controversial in my eyes, and so the
one I'd on consideration suggest, is Keccak, given it was the winner
and thus has the additional backing of being SHA-3. (I can see ways
its particular attributes might prove helpful, too.)

Do you have any thoughts?

- -- 
/akr
-----BEGIN PGP SIGNATURE-----

iQIcBAEBCgAGBQJS0Y8GAAoJEOyEjtkWi2t672AP/im0Ztbd7Y3Atl4OwXvutzJ9
X0eSWp2INfPaQ8XxddIM3Q0P1TbrUhIP8vbV15mGv9vjF2ZtmOmtimnF5crcha2A
Ss+sBiW/jUE/K8/y9y9hhyEKdJgZ+AQO0Zx6GL4nwu83Pn+sPs3LuAkpMWz7cItC
bmgxR9bU9N//xPa0KidFHmRgMCaR5QF49Cdmyf8m+U+W7Mpp3pLu9VOAYj8AA5Q0
lKPDTkp+QceRcBA6Mp5hMg5WZbz/uhqj52AFzbsM8rmvVTIPSQCy4v7qmS4zTHVa
G7VwgfauWSZ3PeAwRk1sfN4xRzzaBqQmhMps+sCZ6+JK2RAaZ0BVHIAaeAP8RBLr
ZMSglLd387yfRnMyMeg1PsNaWM0Y/SqQ3SKWSpqSiAut8Z/GoZ6V6FcmYDmyxrtE
Y/1HU2R8Ea6cUtdcwf05kHUpf78GMEQqAxG0+jaaBivEBR+B5RWHIwUfnL4+GdEj
kOx3o3gGEavGAHUGqvVZI4RoJYAVleAQFqnujldKI+8WhbtD1M4GxuIJSr9f4EA6
gKReED3mEXTzjmWEcdl5CyjF3hggwxdpEKSOjH0LSdZmHfatnSnjEHQY57LDSCWC
H+pfN9wb993VlCNK6vz9Rjn0K/oAkyYWZDRgvcE2eX0DAMgSXuPGshydp4kLZVCw
4xYIvNRTUS5Sv+s0iL7Y
=bB3k
-----END PGP SIGNATURE-----