Re: [Cfrg] Signatures: curves, algorithms, etc

David Leon Gil <> Fri, 30 January 2015 16:32 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id 3EA121A6EEC for <>; Fri, 30 Jan 2015 08:32:05 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: 0.5
X-Spam-Status: No, score=0.5 tagged_above=-999 required=5 tests=[BAYES_20=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, J_CHICKENPOX_16=0.6, SPF_PASS=-0.001] autolearn=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id agfq3NU-LySl for <>; Fri, 30 Jan 2015 08:32:03 -0800 (PST)
Received: from ( [IPv6:2607:f8b0:4002:c01::232]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 8850F1A1B53 for <>; Fri, 30 Jan 2015 08:32:03 -0800 (PST)
Received: by with SMTP id t59so11330449yho.9 for <>; Fri, 30 Jan 2015 08:32:02 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20120113; h=mime-version:references:from:date:message-id:subject:to:cc :content-type; bh=xVqXa7FZ9Vut3Ds/+uevXTFXlqxffpBYX0Hdor3Ohyo=; b=z0gdKzipBkwtjaV7ByEy7N82zeendNpO4iENGAE5/7oe7b5osLmsLlbm2LvlmRbwYi LcElpwsFMKG8uafC3UMHdnbFBH7pHaSJHr7uphu/TlqaHpR6+WQMQZnfqG+0KfacC3yH BOB/Zi1QC+hfwC0zhxuiwL3bAMxYIyJ9fDTI320y/v0qsDPaKuTfLIwX6MJtIYZxsOhW qFlkWBKxPCN5GT0Otb84zTNTNokU1nMmIH/cuhvDoF3kYc04hTNp/0XrlBW0un+i1cSU TEZUwj6PNiTIzRmt4TwzNe84ADqqaDoWtIZqqIAUV0zbtAiaLLSiNw0FQKioyqR8O5mo F8bQ==
X-Received: by with SMTP id b123mr4024278ykb.38.1422635522750; Fri, 30 Jan 2015 08:32:02 -0800 (PST)
MIME-Version: 1.0
References: <> <>
From: David Leon Gil <>
Date: Fri, 30 Jan 2015 16:32:01 +0000
Message-ID: <>
To: Damien Miller <>, Tony Arcieri <>
Content-Type: multipart/alternative; boundary="001a113bb760fa813f050de124be"
Archived-At: <>
Cc: "" <>
Subject: Re: [Cfrg] Signatures: curves, algorithms, etc
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Fri, 30 Jan 2015 16:32:05 -0000

Some brief notes:

1. Hash functions. I'd really like to see a better hash function for any
options besides Ed25519. Two options for Ed25519:

1. Same point format. Keep the hash the same. Don't break compatibility.

2. New point format. Replace SHA2 with Blake2 or Prefix-MAC(SHAKE128).

For higher security strength curves, the EC-Schnorr security proofs suggest
2s hashing. Only SHAKE256 seems to work for that.

I mildly prefer EC-Schnorr to ECDSA, Franken- or not.


2. Signature schemes with coupons and tight reductions to CDH. Hashing to
an EC group is really easy with a variable-output-length keyed PRF. (Does
this have to be done in constant time?)

Pointcheval(?) has an interesting scheme involving 'coupons', in which all
scalar muls can be done *before* signing a message. The scheme has a tight
reduction to CDH.

This strikes me as potentially much more efficient than even Schnorr-EC for
signers: The scalarmuls are no longer in the critical path. So you get
asymmetric signatures for (very slightly more than) the latency of
computing a MAC[*]

[*] Note that this means you can compute coupons at periods of low
computational demand, which may be a substantial cost savings.

David Leon Gil
Senior Paranoid

PS. Sending via Gmail because the CFRG mailing list software attempts to
forge FROM addresses. And Yahoo sets a DMARC p=reject. Could
a list admin please configure the IRTF listserv to not blatantly violate
the IETF DMARC standard?
On Thu, Jan 29, 2015 at 9:27 PM Damien Miller <> wrote:

> On Tue, 27 Jan 2015, Tony Arcieri wrote:
> > I would like to hear the opinions of the chairs and other CFRG
> participants
> > on the following:
> > - Ed25519 and EdDSA
> > - FrankenECDSA (ECDSA in Edwards)
> > - ECDSA with Edwards keys on the wire (converted to Weierstrass to do
> > - Other interesting thoughts on digital signatures
> As you probably already know OpenSSH is already using Ed25519 for
> user and host authentication. We chose it because:
> 1) It's secure; well-reviewed and based on good "bones" (e.g. Schnorr sigs)
> 1a) It avoids the terrible failure modes of DSA/ECDSA
> 1b) It's hard for implementors to get wrong
> 2) It's fast
> 3) There are excellent reference implementations available
> We're not interested in adding more DSA/ECDSA variants unless there is some
> compelling reason (and I don't see any). EdDSA just seems a better
> algorithm.
> We're not super-interested in WF >2^128 EdDSA either, but would possibly
> consider EdDSA at ~WF 2^256 if our users start asking for it.
> We aren't likely to benefit from batch signing/verification.
> -d
> _______________________________________________
> Cfrg mailing list