Subject: Re: [Cfrg] BLS standard draft

From: Marek Jankowski <[email-masked]>
Date: Mon, 1 Apr 2019 03:00:54 +0200

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=
[email-masked]> 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 <[email-masked]> on behalf of Sergey Gorbunov <
> [email-masked]>
> *Date: *Saturday, February 23, 2019 at 8:25 PM
> *To: *"[email-masked]" <[email-masked]>, David Wong <
> [email-masked]>, "[email-masked]" <[email-masked]>,
> Eric Rescorla <[email-masked]>
> *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 <[email-masked]> wrote:
>
> Message: 1
> Date: Sun, 17 Feb 2019 08:54:36 -0800
> From: David Wong <[email-masked]>
> To: ??? <[email-masked]>
> Cc: Eric Rescorla <[email-masked]>, CFRG <[email-masked]>,  Sergey
>         Gorbunov <[email-masked]>
> Subject: Re: [Cfrg] BLS standard draft
> Message-ID:
>         <CAK3aN2r9J9ToH6OZPNqUv4vNPx_DqJM+KQC=X=
> [email-masked]>
> 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
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>