Re: [Cfrg] Internet-Draft: Collective Edwards-Curve Digital Signature Algorithm

"Slamanig, Daniel" <> Mon, 03 July 2017 22:39 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 03519131696 for <>; Mon, 3 Jul 2017 15:39:22 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -4.3
X-Spam-Status: No, score=-4.3 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_MED=-2.3, RP_MATCHES_RCVD=-0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (1024-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id c4b5XiuPl-4C for <>; Mon, 3 Jul 2017 15:39:18 -0700 (PDT)
Received: from ( []) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 7918D131638 for <>; Mon, 3 Jul 2017 15:39:18 -0700 (PDT)
Received: from ( []) by (8.14.9/8.14.9) with ESMTP id v63MdEUY008925 (version=TLSv1/SSLv3 cipher=ECDHE-RSA-AES256-SHA384 bits=256 verify=OK); Tue, 4 Jul 2017 00:39:14 +0200
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=mailrelay; t=1499121556; bh=Q9ynHFeo9QLGUJMVTHoR2m0r7QXJPTYwdzsN1OCfQl4=; h=From:To:CC:Subject:Date; b=LZctkRqiK4AjgkgEv6eXj+Q2lmdHingvt+huyZh4FUs8vceLAWRqNCqDUEmPu7Sk4 ish0tN/NTgxZUqB3Ug2rE/1w753WjlNx9aQ1nIsvSMNJQCzOdeGgUHps2C4JUh1xXW iCTbHVnjqQbQBi2nN6ay39MowPJcZrx+nrn0wuP4=
Received: from MBX0002.tugraz.local (2002:811b:3045::811b:3045) by MBX0002.tugraz.local (2002:811b:3045::811b:3045) with Microsoft SMTP Server (TLS) id 15.0.1263.5; Tue, 4 Jul 2017 00:39:12 +0200
Received: from MBX0002.tugraz.local ([fe80::5556:4aaf:d0f8:46ec]) by MBX0002.tugraz.local ([fe80::5556:4aaf:d0f8:46ec%12]) with mapi id 15.00.1263.000; Tue, 4 Jul 2017 00:39:12 +0200
From: "Slamanig, Daniel" <>
To: Philipp Jovanovic <>
CC: "" <>
Thread-Topic: [Cfrg] Internet-Draft: Collective Edwards-Curve Digital Signature Algorithm
Thread-Index: AQHS9E0xFuwNyQq3DkK9EtFcxMSBZg==
Date: Mon, 03 Jul 2017 22:39:12 +0000
Message-ID: <>
Accept-Language: de-AT, en-US
Content-Language: de-AT
x-ms-exchange-transport-fromentityheader: Hosted
Content-Type: multipart/alternative; boundary="_000_8a0d8aec86404fada692c405cd05973eemailandroidcom_"
MIME-Version: 1.0
X-TUG-Backscatter-control: lAa1Aa+Pa1hp/miybLoRww
X-Spam-Scanner: SpamAssassin 3.003001
X-Spam-Score-relay: -1.9
X-Scanned-By: MIMEDefang 2.74
Archived-At: <>
Subject: Re: [Cfrg] Internet-Draft: Collective Edwards-Curve Digital Signature Algorithm
X-Mailman-Version: 2.1.22
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Mon, 03 Jul 2017 22:39:22 -0000

Hi again,

For instance, a malicious A^* could just take some key from A,
say A_j, and compute and publish A^*=a^*A_j.

sry, there is a typo. Should be A^*=a^*P+A_j assuming A_j=a_jP.


 then given a collective
signature (R,s,Z) where A_j participated, the signer can update s to s^*
= s+a^*c as well as Z^* to exclude A_j and include A^* (as Z is not
committed in the signature generation) and the signature (R,s^*,Z^*)
will be a valid signature that certifies that A^* participated in
signing - although he didn't.

If Z is committed as proposed above and it is checked during the
verification, then this should no longer work. One could also adapt the
hash c=H(R||pk_ch||CH(Z'||A)||S) to include a chameleon hash to
CH(Z||A'), where A' is the real set of signers that participated in the
signature generation and is adapted before finalizing the signature when
known as above.

I hope that what I proposed is not just complete nonsense :) Also it
produces quite a bit of an overhead. There may also be easier ways to
avoid the issues.

Some editorial issues: the message to be signed is sometimes called a
satement S and later then message msg. S could be confusing as part of
the signature is s and your semantic is that scalars are lowercase and
points are uppercase. Also in 4.2 "Signature Generation" steps 2 and 3
are confusing as I guess that in the protocol all the signer compute
their own [r_i]B values and R=\sum R_i instead of R=[r]B which would
mean that they would send their r_i's (hope they will not do so).

Also I find it somewhat confusing that the bitmask Z identifies the
non-signers with a bit set to 1. Why not identifying the signers with a
bit set to 1?


[1] Hugo Krawczyk, Tal Rabin: Chameleon Signatures. NDSS 2000

On 01.07.2017 23:58, Philipp Jovanovic wrote:
> Hi CFRG,
> Here’s a first version of an Internet-Draft on “Collective Edwards-Curve Digital Signature Algorithms” based on Ed25519 and Ed448:
> We plan to give a short presentation on that topic at the next CFRG meeting in Prague.
> Any feedback is more than welcome. Thanks!
> All the best,
> Philipp
> _______________________________________________
> Cfrg mailing list

Dr. Daniel Slamanig
Institute for Applied Information Processing and Communications
Graz University of Technology
Inffeldgasse 16a, 8010 Graz, Austria.
Phone: +43 316 873 5509

Cfrg mailing list