Re: [Cfrg] BLS - proofs of possession may not be enough?

Jeff Burdges <burdges@gnunet.org> Sun, 17 November 2019 19:48 UTC

Return-Path: <burdges@gnunet.org>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 33DCC12001E for <cfrg@ietfa.amsl.com>; Sun, 17 Nov 2019 11:48:45 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -3.533
X-Spam-Level:
X-Spam-Status: No, score=-3.533 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_MED=-2.3, SPF_HELO_NONE=0.001, SPF_SOFTFAIL=0.665, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
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 yLZs2QXbD8tV for <cfrg@ietfa.amsl.com>; Sun, 17 Nov 2019 11:48:43 -0800 (PST)
Received: from mail-out2.informatik.tu-muenchen.de (mail-out2.in.tum.de [131.159.0.36]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id DB2B0120128 for <cfrg@irtf.org>; Sun, 17 Nov 2019 11:48:42 -0800 (PST)
Received: from [127.0.0.1] (sam.net.in.tum.de [IPv6:2001:4ca0:2001:42:225:90ff:fe6b:d60]) by sam.net.in.tum.de (Postfix) with ESMTP id C9AA61C00D2 for <cfrg@irtf.org>; Sun, 17 Nov 2019 20:51:14 +0100 (CET)
From: Jeff Burdges <burdges@gnunet.org>
Content-Type: multipart/signed; boundary="Apple-Mail=_8387D7BF-D144-4FCC-BB1B-D35D6A43F701"; protocol="application/pgp-signature"; micalg=pgp-sha512
Mime-Version: 1.0 (Mac OS X Mail 11.5 \(3445.9.1\))
Date: Sun, 17 Nov 2019 20:48:32 +0100
References: <D40667F2-5A6E-44A1-AEDE-A90346230CAF@gmail.com>
To: cfrg@irtf.org
In-Reply-To: <D40667F2-5A6E-44A1-AEDE-A90346230CAF@gmail.com>
Message-Id: <25E48781-EEBC-4A8C-823E-CA6714A95745@gnunet.org>
X-Mailer: Apple Mail (2.3445.9.1)
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/pmlKCjBtMLlofbY37Rx3fmlG-Mc>
Subject: Re: [Cfrg] BLS - proofs of possession may not be enough?
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Sun, 17 Nov 2019 19:48:45 -0000

I’d still characterise sum_i sk_i = 0 as an unusual DGK that changes the properties of the signature similarly to any other DKG does.  In particular, any proof-of-possesion security proof should show this does not impact other signers under normal threat models.

As we discussed, there are threat models with non-standard interactions between signatures in which sum_i sk_i = 0 does facilitate attacks, namely when a signer waits for other signers and can be punished for signing too early.  I’ll note however that BLS cannot achieve security for that signer anyways because the earlier signers can subtract their signatures even without any relationship among the secret keys.

> On 17 Nov 2019, at 14:12, Kobi Gurkan <kobigurk@gmail.com>; wrote:
> It seems that delinearization, as described in https://crypto.stanford.edu/~dabo/pubs/papers/BLSmultisig.html, is strictly stronger than proofs of possession in terms of security - as this attack does not effect protocols that use them.

I suspect it’s strictly stronger but actually nobody proved this.  An approach for showing that delinearization is stronger than proof-of-possesion might be working in some composability framework, but this gets delicate because classically these handle state poorly.

Jeff