Re: [Cfrg] BLS standard draft
Marek Jankowski <mjankowski309@gmail.com> Mon, 01 April 2019 13:11 UTC
Return-Path: <mjankowski309@gmail.com>
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 F255B120120 for <cfrg@ietfa.amsl.com>; Mon, 1 Apr 2019 06:11:23 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.698
X-Spam-Level:
X-Spam-Status: No, score=-0.698 tagged_above=-999 required=5 tests=[AC_DIV_BONANZA=0.001, BAYES_00=-1.9, DATE_IN_PAST_12_24=1.049, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_ENVFROM_END_DIGIT=0.25, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=no autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
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 4_Pvg-E_xpjs for <cfrg@ietfa.amsl.com>; Mon, 1 Apr 2019 06:11:21 -0700 (PDT)
Received: from mail-it1-x135.google.com (mail-it1-x135.google.com [IPv6:2607:f8b0:4864:20::135]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 8C0A112011E for <cfrg@irtf.org>; Mon, 1 Apr 2019 06:11:21 -0700 (PDT)
Received: by mail-it1-x135.google.com with SMTP id u65so15094210itc.2 for <cfrg@irtf.org>; Mon, 01 Apr 2019 06:11:21 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=AIBNuu3IgymreagJWDSL2taj7ZubLherUR0OgBgyfIg=; b=HHKo71OBEFllPxvSzWgnwBiDp4LfbxkviElfbI3G39KXhcFmm02ag4wFhf+OvQIObo ZYk/9SFg3IT6o18Yd8VRQXML5OMoqA1bGjWdJvxyghawzLgXlajgXq7NUuQs44Y1vvT7 5RPPioz6L3gpSvDeytYGUt99G1KFE/gyPJaHvFnkzz18dJxgRkDhrXJyNfDD0A6/e7Fd UZIzKOifbfiWl3cI0CydYX2sU7DqW0+Oi399TPs1f4TuLFJHvUqDdjGhPuMsRNVhzRZ2 bWXH7fQaiUDt0/avSbIF/CUs1iX8O6GoZBDwPTO8GNwJ7MOsauU6tqjwhQFwZlW3G8xz axUg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=AIBNuu3IgymreagJWDSL2taj7ZubLherUR0OgBgyfIg=; b=sKBzrk3o0xbzexL6ivpisFnnopHGTNK/TjEWM4WLBseCZvjqp23iKTAsN6H6bieHEU HGauv1W0D6TGavHrfpLyHUV8xGeg4tQcUeaMr3W5btm8Tbvm2hohmx2mp3S0I+DH/7I2 vpOTn3s+qSh8hnh7CAsP2x9JH7YqnjrwLbceHdEuPYdbzdrRjoNaIf7w9EErWYhHIsC9 k/WD4p62xaYjTcWlxfGXvtztJSIQlNByK9VsQaAusWZWZ5hzNi0Tbbqvy8sIFS8m1AXi lQFx3PQLjsA1j3CIR9yxtjoP4/wqt9wEDrHQau5JTQBYF4GpWKmb91/MxefM/3SvqEvr IF4Q==
X-Gm-Message-State: APjAAAWPMoP4WbJ9h47+Bi8yviByYfs8UP/rYdXetFPwt3JdWxcAc09N q8MgMAwyCF4P1+mOPEzxHav3Z93KRuxpXgtE7Kw=
X-Google-Smtp-Source: APXvYqxe8+4zibwrvH769zdsAUddZovXM+soxfWGWQN02h5kQVtuaDr+d8wrsyHtSlprajLnoAsEkSswC5++x4OIChI=
X-Received: by 2002:a24:2a88:: with SMTP id w130mr14454763itw.95.1554124280748; Mon, 01 Apr 2019 06:11:20 -0700 (PDT)
MIME-Version: 1.0
References: <CACnav0oDeJ14LphESnrsD8C1C+4iFByPqp4tfqxGT4hwbe1ucg@mail.gmail.com> <9470C30B-93D9-4425-A411-031E0D440B81@adobe.com>
In-Reply-To: <9470C30B-93D9-4425-A411-031E0D440B81@adobe.com>
From: Marek Jankowski <mjankowski309@gmail.com>
Date: Mon, 01 Apr 2019 03:00:54 +0200
Message-ID: <CAMCcN7QyKfLKtsx52OJoZrwA=5AXh1FCmKsRspcp+RzHW0OA5Q@mail.gmail.com>
To: Antonio Sanso <asanso=40adobe.com@dmarc.ietf.org>
Cc: Sergey Gorbunov <sgorbunov@uwaterloo.ca>, "cfrg@irtf.org" <cfrg@irtf.org>
Content-Type: multipart/alternative; boundary="000000000000b0e194058577c18a"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/szrMOoRV82pPRHVJttXcuAX8JdU>
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: Mon, 01 Apr 2019 13:11:24 -0000
Dear Boneh, Gorbunov, Wee and Zhang, I have a few comments regarding the BLS Signature Scheme I-D. In the Introduction (Section 1), it is noted that a collection of n signatures can be verified using only n+1 pairings. It may be useful to note that if a single message is signed with n private keys, verification is reduced to n additions and 2 pairings ("Verify-Aggregated-1", Section 2.5.1). Following that thought, one concludes that the same computational guarantees can be made for the case of many messages signed by a single entity. It may be useful for software update -- the software may be split into modules, each module is signed separately while verification can be aggregated. Sesction 1.2 - I think probabilistic guarantees more accurately represent what is required from a signature scheme. Consider the following revision: "Verify(PK, msg, sigma) is VALID for any sigma = Sign(SK, msg) and INVALID for any other sigma with overwhelming probability", when in this case "overwhelming probability" is roughly 1 - 1/r for r = |GT|. Section 2.6.2.2 - "plen" should probably be "padlen". In addition, the wording of Step 11, bullet #3 confuses me. If I understand correctly, please allow me to suggest a maybe clearer formulation: "there should be a pair of ys that differ by the parity of their respective first coordinates". Section 2.6.3 - the input parameters of hash_to_G1_try_and_increment are written without line breaks, unlike any other algorithm in the draft. Thank you, Marek. On Fri, Mar 22, 2019 at 10:51 AM Antonio Sanso <asanso= 40adobe.com@dmarc.ietf.org> wrote: > Hi Sergey, > > Great work so far. > > > > Not quite the same. Just wanted to point out that recently Luca De Feo, > Simon Masson, Christophe Petit and myself published a paper that > generalizes the BLS construction (employing isogenies). > > You can find the paper in https://eprint.iacr.org/2019/166.pdf > > > > Regards > > > > antonio > > > > > > > > *From: *Cfrg <cfrg-bounces@irtf.org> on behalf of Sergey Gorbunov < > sgorbunov@uwaterloo.ca> > *Date: *Saturday, February 23, 2019 at 8:25 PM > *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 >
- [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