Subject: Re: [Cfrg] BLS standard draft

From: Sergey Gorbunov <[email-masked]>
Date: Thu, 14 Mar 2019 09:50:19 -0400

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 <[email-masked]>
> To: "[email-masked]" <[email-masked]>
> Subject: Re: [Cfrg] BLS standard draft
> Message-ID:
>         <CAEseHRpH2s0i7=u4ZoSCMX9ghiSN_0Y=
> [email-masked]>
> 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 <[email-masked]>
> 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 <[email-masked]> on behalf of Sergey Gorbunov <
> > [email-masked]>
> > *Date: *Saturday, 23 February 2019 at 20:26
> > *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
> >
> -------------- 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
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>
>
> ------------------------------
>
> End of Cfrg Digest, Vol 167, Issue 7
> ************************************
>

---

From: Antonio Sanso <[email-masked]>
Date: Mon, 18 Mar 2019 09:54:30 +0000

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: Thursday, March 14, 2019 at 2:51 PM
To: "[email-masked]" <[email-masked]>
Subject: Re: [Cfrg] BLS standard draft

Dear All:

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 <[email-masked]<mailto:[email-masked]>>
To: "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>
Subject: Re: [Cfrg] BLS standard draft
Message-ID:
        <CAEseHRpH2s0i7=u4ZoSCMX9ghiSN_0Y=[email-masked]<mailto:[email-masked]>>
Content-Type: text/plain; charset="utf-8"

Mike

On Tue, Mar 5, 2019 at 1:48 PM John Mattsson <[email-masked]<mailto:[email-masked]>>
wrote:

> Hi Sergey,
>
>
>
> I think this is interesting and likely something worth spending time on. I
> be good in many IoT applications, I assume that the pairing operations are
> relatively expensive.
>
>
>
> *From: *Cfrg <[email-masked]<mailto:[email-masked]>> on behalf of Sergey Gorbunov <
> [email-masked]<mailto:[email-masked]>>
> *To: *"[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>, David Wong <
> [email-masked]<mailto:[email-masked]>>, "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>,
> Eric Rescorla <[email-masked]<mailto:[email-masked]>>
> On Sun, Feb 17, 2019 at 3:00 PM <[email-masked]<mailto:[email-masked]>> wrote:
>
> Message: 1
> From: David Wong <davidwong.crypto@gmail..com<mailto:[email-masked]>>
> To: ??? <[email-masked]<mailto:[email-masked]>>
> Cc: Eric Rescorla <[email-masked]<mailto:[email-masked]>>, CFRG <[email-masked]<mailto:[email-masked]>>,  Sergey
>         Gorbunov <[email-masked]<mailto:[email-masked]>>
> [email-masked]<mailto:[email-masked]>>
> [email-masked]<mailto:[email-masked]>
-------------- 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
[email-masked]<mailto:[email-masked]>
https://www.irtf.org/mailman/listinfo/cfrg