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, 1 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>rg>, David Wong <
> davidwong.crypto@gmail.com>gt;, "ylzhao@fudan.edu.cn" <ylzhao@fudan.edu.cn>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
>