Re: [Cfrg] Adoption of threshold drafts by RG

Chelsea Komlo <> Tue, 29 September 2020 20:50 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 0AF923A1189 for <>; Tue, 29 Sep 2020 13:50:00 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2.096
X-Spam-Status: No, score=-2.096 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, HTML_MESSAGE=0.001, RCVD_IN_MSPIKE_H4=0.001, RCVD_IN_MSPIKE_WL=0.001, SPF_HELO_NONE=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 a_ZG-tUKExcv for <>; Tue, 29 Sep 2020 13:49:55 -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 483EB3A1186 for <>; Tue, 29 Sep 2020 13:49:53 -0700 (PDT)
Received: from pps.filterd ( []) by ( with SMTP id 08TKIGDh023269; Tue, 29 Sep 2020 16:21:29 -0400
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; h=from : to : cc : subject : date : message-id : references : in-reply-to : content-type : mime-version; s=default; bh=pMnsighsFCXeMlmrARK8tW76btRf0FAOnuE4SC5X3e0=; b=9XJIc4g7F96O61IYe+BNBIifY9KIA+ZvdoyoPr6/5TXcAeAD9kc08aFWb3Yhch3R7fFh rIV1uLuVYp/gR2PFfgrQWrnVt8yui/A5J7aF8s9K4/QxsPJGYI2REmXYUgBDBzZFNg5h qvQC/OXVtYI0enImiywb/W9vCx4t+kliPUA=
Received: from ( []) by with ESMTP id 33t2mgemvn-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-SHA256 bits=128 verify=NOT); Tue, 29 Sep 2020 16:21:29 -0400
Received: from ( by ( with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256_P256) id 15.1.2044.4; Tue, 29 Sep 2020 16:21:29 -0400
Received: from ([fe80::c509:52cf:5893:c3fa]) by ([fe80::c509:52cf:5893:c3fa%18]) with mapi id 15.01.2044.004; Tue, 29 Sep 2020 16:21:28 -0400
From: Chelsea Komlo <>
To: IRTF CFRG <>, Phillip Hallam-Baker <>
CC: Ian Goldberg <>, Watson Ladd <>
Thread-Topic: [Cfrg] Adoption of threshold drafts by RG
Thread-Index: AQHWkDO8jAIE8QI0b0+nx8IzpD1x2alz+L8AgAwyeID//98fpA==
Date: Tue, 29 Sep 2020 20:21:28 +0000
Message-ID: <>
References: <> <>, <>
In-Reply-To: <>
Accept-Language: en-US
Content-Language: en-US
x-originating-ip: []
Content-Type: multipart/alternative; boundary="_000_76cfa2f5d3c04193aa28d153ce7d4958uwaterlooca_"
MIME-Version: 1.0
X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 mlxlogscore=999 bulkscore=0 spamscore=0 lowpriorityscore=0 suspectscore=0 adultscore=0 priorityscore=1501 impostorscore=0 phishscore=0 clxscore=1015 malwarescore=0 mlxscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2006250000 definitions=main-2009290171
Archived-At: <>
Subject: Re: [Cfrg] Adoption of threshold drafts by RG
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Tue, 29 Sep 2020 20:50:00 -0000

Hi Phillip,

Here is a summary of how the Drivers attack [1] can be performed, and the implications for schemes that are insecure.

Let the threshold be t=2, and assume one signer is malicious. Let the number of victim's commitments that the attacker can learn *before* selecting their own commitment be k >= 2 (such as by opening many simultaneous signing connections).

After performing O(k*b*2^{1/lg(k)}) local computations (where b is the bitlength of the order of the group), the adversary can compute a valid forged signature. They do so by first completing the k signing executions, sending the victim k messages to sign of the adversary's choosing, along with their own commitments. From the victim's responses, the adversary can derive a partial forged signature for the victim over a message that the victim has never seen. The adversary then simply provides their own partial signature to complete what is a valid forged joint signature.

For a scheme defined over a group order of bitlength 256, an adversary that is allowed to make up to 3 concurrent signing operations reduces the security of the scheme to ~95 bits of security. Allowing up to 7 concurrent signing operations reduces the security to 75 bits, etc.

With that said, even if you did integrate a FROST-like approach into your scheme, after a quick look, there are parts of your design that remain insecure. For example, the stateless computation of the final share [2] would remain insecure against the Drijvers attack as the final signer is not required to commit to their nonce before seeing all other signers' commitments.

We would however like schemes that are designed for specific use cases to build upon FROST as needed. Because of the interest here and as expressed previously on this list, I would like to ask the chairs to consider moving our draft for FROST [3] forward.