Re: [Cfrg] BLS standard draft

Sergey Gorbunov <sgorbunov@uwaterloo.ca> Thu, 14 March 2019 13:50 UTC

Return-Path: <sgorbunov@uwaterloo.ca>
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 95C8A130E2B for <cfrg@ietfa.amsl.com>; Thu, 14 Mar 2019 06:50:40 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.999
X-Spam-Level:
X-Spam-Status: No, score=-1.999 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_NONE=-0.0001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=uwaterloo.ca
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 5fotPh0bFbGu for <cfrg@ietfa.amsl.com>; Thu, 14 Mar 2019 06:50:36 -0700 (PDT)
Received: from psyche.uwaterloo.ca (psyche.uwaterloo.ca [129.97.128.244]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 3CC98130E79 for <cfrg@irtf.org>; Thu, 14 Mar 2019 06:50:35 -0700 (PDT)
Received: from mail-vk1-f176.google.com (mail-vk1-f176.google.com [209.85.221.176]) (authenticated bits=0) by psyche.uwaterloo.ca (8.14.4/8.14.4) with ESMTP id x2EDoVT7022334 (version=TLSv1/SSLv3 cipher=AES256-GCM-SHA384 bits=256 verify=OK) for <cfrg@irtf.org>; Thu, 14 Mar 2019 09:50:34 -0400
DKIM-Filter: OpenDKIM Filter v2.11.0 psyche.uwaterloo.ca x2EDoVT7022334
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=uwaterloo.ca; s=default; t=1552571434; bh=YyN17a2YOQ/lOb4n8rGZ9cDxaVtRIEA6G8OqrTdxs74=; h=References:In-Reply-To:From:Date:Subject:To:From; b=I8+jECDONCvaZGOFNjcnOm7/3sjIDpKNQInV9gtG4TbrWbyvDh69riwR36+U8+67K eLYqpRXouVILfr1p3TqxcJzZDf41n4JwlwXtP6mud72R+ksj+tHrfgw+TxFMPaLqi1 MWHa9jWUi3adsKxvnxcNTddhrmaciP524NB+/0DU=
Received: by mail-vk1-f176.google.com with SMTP id l17so1379697vke.7 for <cfrg@irtf.org>; Thu, 14 Mar 2019 06:50:34 -0700 (PDT)
X-Gm-Message-State: APjAAAUWjtZOUw5a/66Zdbe73gk0Sb+BX+K2NpYKiuXKtu3TOvzx+Pl7 GxD3QxeelrpPC58GQH0p52G7rG5EwGFHR2rgyMs=
X-Google-Smtp-Source: APXvYqzWkWsiTr8mdbjRDOdsWqXyXgwBGuyf0Dik2lMA9ty9AKw7r8eLLtGF9geIhWGLX9uI6GAko8W+br0m7rzQt44=
X-Received: by 2002:a1f:b47:: with SMTP id 68mr7181714vkl.29.1552571431339; Thu, 14 Mar 2019 06:50:31 -0700 (PDT)
MIME-Version: 1.0
References: <mailman.27.1551816005.6121.cfrg@irtf.org>
In-Reply-To: <mailman.27.1551816005.6121.cfrg@irtf.org>
From: Sergey Gorbunov <sgorbunov@uwaterloo.ca>
Date: Thu, 14 Mar 2019 09:50:19 -0400
X-Gmail-Original-Message-ID: <CACnav0pt0_+=r4-OH3_0nZe+3FxmApcGfF7CGkjR-NSvJ9t-mA@mail.gmail.com>
Message-ID: <CACnav0pt0_+=r4-OH3_0nZe+3FxmApcGfF7CGkjR-NSvJ9t-mA@mail.gmail.com>
To: cfrg@irtf.org
Content-Type: multipart/alternative; boundary="000000000000a75d6b05840e3430"
X-UUID: a4b91f0b-c468-460a-81f2-ed9f672710eb
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/F2jijdwJlvYMB2QI4C79COaQHhk>
Subject: Re: [Cfrg] BLS standard 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: Thu, 14 Mar 2019 13:50:41 -0000

Dear All:

Thanks for the continuing feedback!
Our draft is now on GitHub:
https://github.com/pairingwg/bls_standard
Please submit and comment on the issues to continue improving the draft.

Note that the parent working group also contains a related draft on
pairing-friendly curves:
https://github.com/pairingwg

Regards,
Sergey


> Message: 1
> Date: Tue, 5 Mar 2019 17:42:00 +0000
> From: Michael Scott <mike.scott@miracl.com>
> To: "cfrg@irtf.org" <cfrg@irtf.org>
> Subject: Re: [Cfrg] BLS standard draft
> Message-ID:
>         <CAEseHRpH2s0i7=u4ZoSCMX9ghiSN_0Y=
> bLj3_2E1gED+f3WJoQ@mail.gmail.com>
> Content-Type: text/plain; charset="utf-8"
>
> My understanding is that while shortness is a nice feature of BLS
> signature, its not the main selling point any more. That would be its
> aggregation and compression property.
>
> As it happens I just finished getting some timings for the BLS381 curve on
> an Arduino IoT MKR1000 board (48MHz clock, 32-bit ARM Cortex M0 chip - but
> no 32x32->64 multiplication instruction, 256K ROM, 32K RAM, no room for any
> precomputation :), no assembly language, pure C++, side channel resistant
> coding). Signature in G1, public key in G2, SHA3 message hashing.
>
> The test program occupies less than 56K of ROM, and (obviously) something
> less than 32K of RAM
>
> Key generation -  2.7 seconds
> Signature - 2.8 seconds
> Verification - 13.1 seconds
>
> Of course it would be a little crazy to do BLS signature verification on
> such a chip....
>
> Mike
>
>
> On Tue, Mar 5, 2019 at 1:48 PM John Mattsson <john.mattsson@ericsson.com>
> wrote:
>
> > Hi Sergey,
> >
> >
> >
> > I think this is interesting and likely something worth spending time on.
> I
> > agree with the opinion that quantum computers is not a reason to stop
> > looking at this, at least not yet.
> >
> >
> >
> > Some very quick high level comments:
> >
> >
> >
> > - It is stated the BLS12-381 yield signature sizes of 48 bytes when
> > signatures are in G1. I think the draft should also state what the public
> > keys sizes are in this case. I assume the "minimizing public key size"
> > option just swap the sizes.
> >
> >
> >
> > - It would be good if the draft gave some hint to potential implementors
> > regarding the amount of processing required. While short signatures would
> > be good in many IoT applications, I assume that the pairing operations
> are
> > relatively expensive.
> >
> >
> >
> > - The curve is called both BLS12-381 and BLS-381, I assume they are the
> > same curve.
> >
> >
> >
> > My memory of BLS (backed up by a book section by K.G.Paterson that I had
> > in my book shelf) is that BLS signatures where close to half the size of
> > ECDSA (170 vs. 320 bits for 80 bit security), I assume some new attacks
> > have changed this?
> >
> >
> >
> > /John
> >
> >
> >
> > *From: *Cfrg <cfrg-bounces@irtf.org> on behalf of Sergey Gorbunov <
> > sgorbunov@uwaterloo.ca>
> > *Date: *Saturday, 23 February 2019 at 20:26
> > *To: *"cfrg@irtf.org" <cfrg@irtf.org>rg>, David Wong <
> > davidwong.crypto@gmail.com>gt;, "ylzhao@fudan.edu.cn" <ylzhao@fudan.edu.cn
> >,
> > Eric Rescorla <ekr@rtfm.com>
> > *Subject: *Re: [Cfrg] BLS standard draft
> >
> >
> >
> > Thanks, David and everyone else for the feedback!
> >
> > We will create a github repository where anyone will be able to view and
> > comment on the latest draft and share the link.
> >
> >
> >
> > In the meantime, please continue sending us feedback by email.
> >
> >
> > Regards,
> >
> > Sergey
> >
> > web <https://cs.uwaterloo.ca/~sgorbuno/>
> >
> >
> >
> >
> >
> > On Sun, Feb 17, 2019 at 3:00 PM <cfrg-request@irtf.org> wrote:
> >
> > Message: 1
> > Date: Sun, 17 Feb 2019 08:54:36 -0800
> > From: David Wong <davidwong.crypto@gmail.com>
> > To: ??? <ylzhao@fudan.edu.cn>
> > Cc: Eric Rescorla <ekr@rtfm.com>om>, CFRG <cfrg@irtf.org>rg>,  Sergey
> >         Gorbunov <sgorbunov@uwaterloo.ca>
> > Subject: Re: [Cfrg] BLS standard draft
> > Message-ID:
> >         <CAK3aN2r9J9ToH6OZPNqUv4vNPx_DqJM+KQC=X=
> > rfHFEkM5hkdg@mail.gmail.com>
> > Content-Type: text/plain; charset="UTF-8"
> >
> > Hi again,
> >
> > I am not sure what the process is. If you have a github repo where we
> > can participate or if you want us to give you feedback here. So here
> > is some feedback from a first read. Feel free to ignore the bits you
> > don't agree with of course. Some common themes were:
> >
> > * Keep in mind that this is for implementations, so remove information
> > that belongs in a whitepaper
> > * Make the RFC timeless (we should be able to read it in 5 years and
> > understand it)
> > * Set things in stone so that the RFC is actionable, don't make it
> > vague. If people want to add to it, extensions and updates are
> > possible later.
> >
> > And here is the more detailed feedback:
> >
> > - abstract: re-write with "what is it?" in mind first, history bits
> > can wait until the introduction. I suggest using developer-friendly
> > terms like "compression" and define aggregation later if the term is
> > needed. Example:
> >
> >     BLS is a digital signature scheme with compression properties.
> > With a given set of signatures (sig_1, ..., sig_n) anyone can produce
> > a compressed signature sig_compressed. The same is true for a set of
> > private keys or public keys, while keeping the connection between sets
> > (a compressed public key is associated to its compressed public key).
> > Furthermore, the BLS signature scheme is deterministic, non-malleable,
> > and efficient. Its simplicity and cryptographic properties allows it
> > to be useful in a variety of use-cases, specifically when minimal
> > storage space or bandwidth are required.
> >
> > - intro:
> >     - "A signature scheme is a fundamental cryptographic primitive
> > used on the Internet that is used to protect integrity of
> > communication" -> not necessarily used on the internet, and not
> > necessarily for integrity of communications.
> >     - "2.  Verification requires 2 pairing operations." -> at this
> > point pairing is not defined, and what does that mean for the
> > developer? how does it compare to other signature schemes that do not
> > use pairing?
> >     - "we believe the scheme will find very interesting applications"
> > -> too temporal. At some point, it is possible that the scheme will be
> > popular and this sentence will seem out of place.
> >     - "the BLS signature scheme is already integrated" -> maybe out of
> > place (as too temporal as well). If not, sort the list by alphabetical
> > order, I think no one will mind that.
> >     - "BLS signatures are used for authenticating transactions as well
> > as votes during the consensus protocol" -> I suggest we itemize the
> > different use-cases of BLS (from PKI to blockchain).
> > - section "1.1.  Terminology"
> >     - "msg" -> I suggest we change that to "message"
> >     - "sigma" -> "signature"
> >     - "signer/verifier/aggregator" do we need roles for these? Can't
> > we do with just an API ("sign/verify/compress")
> >     - "P1" is defined but never seem to be used. Am I missing something?
> >     - I suggest we spell "e()" as "pairing()" in the algorithms, and
> > define it here
> > - section "1.2.  Signature Scheme Algorithms and Properties"
> >     - "A signature scheme comes with" -> "Like most signature schemes,
> > BLS comes with the following API", this way we can leverage the
> > reader's knowledge of other signature scheme.
> >     - "The signing algorithm may be deterministic or randomized,
> > depending on the scheme" -> as this is a spec, we need to make a
> > decision here. I think it makes more sense to make it deterministic.
> > - section "1..2.2.  Security" -> do we need these security properties
> > in the RFC? It sounds to me like they would belong in a whitepaper
> > instead..
> > - section "2."
> >     - "BLS signatures require pairing-friendly curves" -> I suggest
> > standardizing BLS with a set of curves. Extensions or updates can
> > later add more curves if needed.
> >     - "There are two variants of the scheme" -> It'd be nice if the
> > two variants were specified in this document, as they both have
> > use-cases.
> >     - "Put ... in G1" -> not clear, rephrase
> > - section "2.1.  Preliminaries". I recommend renaming "suite_string"
> > to "domain_separator" and having specific values for it instead of
> > potential values.. (We're standardizing something after all, ideally it
> > should be self-contained)
> > - section "2.4.  Verify: Signature Verification"
> >     - "4.  If r*Gamma != 0, output "INVALID" and stop" -> I had heard
> > a while ago that this membership check was patented for ECDH. Anyone
> > remembers something like this?
> > - section "2.5.  Aggregate"
> >     - it should be "sigma = E1_to_string(string_to_E1(sigma_1) + ... +
> > string_to_E1(sigma_n))"
> >     - you specify verifying aggregates of SAME msg and of DIFFERENT
> > msgs, but only have the aggregate algorithm for SAME msg specified.
> > - section "2.5.3.  Implementation optimizations". Two things:
> >     - this should be towards the end of the documentation as these are
> > optional recommendations. Perhaps after "security recommendations" or
> > as an appendix
> >     - is it really wise to have the standard contain this? Available
> > optimizations may change over time. I've also never seen an RFC
> > talking about optimizations.
> > - section "2.7.  Security analysis" -> I don't think this is necessary
> > to have that in the RFC.
> > - section "3.1. Verifying public keys"
> >     - define "G2 membership test"
> >     - "to prevent rogue key attacks" -> needs a reference
> > - section "3.4. Randomness considerations" needs a citation, for
> > example on ECDSA issues when the nonce is repeated
> > - section "4.  Implementation Status". Standards usually don't refer
> > to implementations AFAIK. I imagine this is because their state can
> > change, and new good implementations can arise after the RFC is set in
> > stone. I think this is good to have in the draft though, so perhaps
> > add an indication somewhere that this will be deleted in the final
> > document.
> > - section "6.  IANA Considerations". Do we need this?
> > - section "2.6.1.  Preliminaries", "In fact, we will pad each
> > substring with 0s so that the length of each substring is a multiple
> > of 8." specify that this is in bits.
> >
> > Cheers,
> > David
> >
> > _______________________________________________
> > Cfrg mailing list
> > Cfrg@irtf.org
> > https://www.irtf.org/mailman/listinfo/cfrg
> >
> -------------- next part --------------
> An HTML attachment was scrubbed...
> URL: <
> https://mailarchive.ietf.org/arch/browse/cfrg/attachments/20190305/1ee7766b/attachment.html
> >
>
> ------------------------------
>
> Subject: Digest Footer
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>
>
> ------------------------------
>
> End of Cfrg Digest, Vol 167, Issue 7
> ************************************
>