Re: [Cfrg] BLS standard draft

[Michael Scott <[e-mail]>]

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