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>, David Wong < > > davidwong.crypto@gmail.com>, "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>, CFRG <cfrg@irtf.org>, 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 > ************************************ >
- [Cfrg] BLS standard draft Sergey Gorbunov
- Re: [Cfrg] BLS standard draft William Whyte
- Re: [Cfrg] BLS standard draft Michael Scott
- Re: [Cfrg] BLS standard draft david wong
- Re: [Cfrg] BLS standard draft Tony Arcieri
- Re: [Cfrg] BLS standard draft Eric Rescorla
- Re: [Cfrg] BLS standard draft 赵运磊
- Re: [Cfrg] BLS standard draft David Wong
- Re: [Cfrg] BLS standard draft Sergey Gorbunov
- Re: [Cfrg] BLS standard draft John Mattsson
- Re: [Cfrg] BLS standard draft Michael Scott
- Re: [Cfrg] BLS standard draft Sergey Gorbunov
- Re: [Cfrg] BLS standard draft Antonio Sanso
- Re: [Cfrg] BLS standard draft Antonio Sanso
- Re: [Cfrg] BLS standard draft Marek Jankowski