Re: [CFRG] Status of BLS Signatures CFRG Internet draft

Jeff Burdges <burdges@gnunet.org> Sun, 01 August 2021 07:19 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 8A3D03A306A for <cfrg@ietfa.amsl.com>; Sun, 1 Aug 2021 00:19:20 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.897
X-Spam-Level:
X-Spam-Status: No, score=-1.897 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_MSPIKE_H3=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
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 5mcLjwezWz9f for <cfrg@ietfa.amsl.com>; Sun, 1 Aug 2021 00:19:16 -0700 (PDT)
Received: from mail-out1.informatik.tu-muenchen.de (mail-out1.in.tum.de [131.159.0.8]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 28B2C3A3068 for <cfrg@irtf.org>; Sun, 1 Aug 2021 00:19:15 -0700 (PDT)
Received: from mailrelay1.rbg.tum.de (mailrelay1.in.tum.de [131.159.254.14]) by mail-out1.informatik.tu-muenchen.de (Postfix) with ESMTP id 4D035240326 for <cfrg@irtf.org>; Sun, 1 Aug 2021 09:19:14 +0200 (CEST)
Received: by mailrelay1.rbg.tum.de (Postfix, from userid 112) id 4AE9618C; Sun, 1 Aug 2021 09:19:14 +0200 (CEST)
Received: from mailrelay1.rbg.tum.de (localhost [127.0.0.1]) by mailrelay1.rbg.tum.de (Postfix) with ESMTP id 05AAB188 for <cfrg@irtf.org>; Sun, 1 Aug 2021 09:19:14 +0200 (CEST)
Received: from sam.net.in.tum.de (sam.net.in.tum.de [IPv6:2001:4ca0:2001:42:225:90ff:fe6b:d60]) by mailrelay1.rbg.tum.de (Postfix) with ESMTP id 04853182 for <cfrg@irtf.org>; Sun, 1 Aug 2021 09:19:14 +0200 (CEST)
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 CEA5E1C006D for <cfrg@irtf.org>; Sun, 1 Aug 2021 09:22:31 +0200 (CEST)
From: Jeff Burdges <burdges@gnunet.org>
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Mime-Version: 1.0 (Mac OS X Mail 13.4 \(3608.120.23.2.7\))
Date: Sun, 1 Aug 2021 09:19:13 +0200
References: <CABPapSGitrjc0YRLKiSVTKQLzvPZBRK2Se-AvZS9-7nyoQpsgA@mail.gmail.com> <1e6bbac4-cb1d-7f07-a945-ddfb6c39faf2@isode.com> <F91C36C4-1FDA-4AFA-8A6F-48622000B7BE@gnunet.org>
To: IRTF CFRG <cfrg@irtf.org>
In-Reply-To: <F91C36C4-1FDA-4AFA-8A6F-48622000B7BE@gnunet.org>
Message-Id: <0898A47A-EB58-4FA9-B851-62CCC2211961@gnunet.org>
X-Mailer: Apple Mail (2.3608.120.23.2.7)
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/prxosMsRO8aqrrxfWUxhdD_EJTY>
Subject: Re: [CFRG] Status of BLS Signatures CFRG Internet draft
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, 01 Aug 2021 07:19:21 -0000

I’ve no looked too closely, but this draft seemingly ignores aggregation over identical messages.  Aggregate BLS signatures on distinct messages and keys have verification like 100 times slower than batched Ed25519 verification, making it rather pointless.  

I doubt aggregation over keys ever makes much sense, so probably worth suggesting that BLS only makes sense when doing same message aggregation, which mostly limits use cases to consensus protocols.  



> On 1 Aug 2021, at 09:01, Jeff Burdges <burdges@gnunet.org> wrote:
> 
> Appears someone believed the BLS signature draft's flawed suggestion of actually doing multiplications in the target group.
> https://github.com/zkcrypto/bls12_381/issues/68
> 
> It’s obvious one should never do multiplications in the target group, and instead always use a multi-miller loop, so not sure why the draft proposes doing target group multiplications. 
> 
> There are numerous other optimizations without which BLS signatures look fairly useless, but omitting multi-miller loops really stands out.  
> 
> Jeff