Subject: [Cfrg] BLS standard draft

From: Sergey Gorbunov <[email-masked]>
Date: Fri, 8 Feb 2019 11:55:37 -0500

Dear Colleagues:

We submitted a draft-00 on the BLS signature scheme.
We received some preliminary feedback from interested parties, and we plan
to continue updating it as we receive more.
Please take a look.
We appreciate any additional feedback!
https://datatracker.ietf.org/doc/draft-boneh-bls-signature/

Abstract

   The BLS signature scheme was introduced by Boneh-Lynn-Shacham in
   2001.  The signature scheme relies on pairing-friendly curves and
   supports non-interactive aggregation properties.  That is, given a
   collection of signatures (sigma_1, ..., sigma_n), anyone can produce
   a short signature (sigma) that authenticates the entire collection.
   BLS signature scheme is simple, efficient and can be used in a
   variety of network protocols and systems to compress signatures or
   certificate chains.  This document specifies the BLS signature and
   the aggregation algorithms.

Regards,
Sergey
web <https://cs.uwaterloo.ca/~sgorbuno/>

---

From: William Whyte <[email-masked]>
Date: Sun, 10 Feb 2019 18:36:51 -0500

Hi all,

With no intent to cast aspersions on this particular scheme, I'm not sure
that CFRG should be putting a lot of time into non-quantum-safe schemes
these days unless there's a compelling reason to.

Cheers,

William

On Sun, Feb 10, 2019 at 5:44 PM Sergey Gorbunov <[email-masked]>
wrote:

>    the aggregation algorithms..
>
>
> Regards,
> Sergey
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

-- 

---

I may have sent this email out of office hours. I never expect a response
outside yours.

---

From: Michael Scott <[email-masked]>
Date: Mon, 11 Feb 2019 11:52:09 +0000

My take on this would be that

1) Pairing-based crypto threw open the doors to lots of nice new crypto
possibilities, enabling stuff that we couldn't do before

2) Gradually post-quantum crypto is catching up and demonstrating
capabilities that mirror some (but not all) of these achievements

3) Post-quantum crypto depends on hard problems that it will take time to
develop full confidence in, even in regard to attacks from non-quantum
computers

4) In the meantime (and that could be quite a long time) it makes perfect
sense to proceed with the development and standardization of non-quantum
safe methods.

5) In the year x out pops a quantum computer. However in the year x-1 out
popped well-developed and well-understood post-quantum crypto replacements
in which we can have
complete confidence.

Everyone is a winner! Well except for the guys who invested in a business
plan to develop a quantum computer on the basis that it would break all of
crypto.

Mike Scott

On Sun, Feb 10, 2019 at 11:37 PM William Whyte <[email-masked]>
wrote:

>> We received some preliminary feedback from interested parties, and we
>> plan to continue updating it as we receive more.
>> Please take a look.

---

From: david wong <[email-masked]>
Date: Mon, 11 Feb 2019 08:44:42 -0500

As we have no 100% certainty on if quantum computers that can break crypto will ever be a thing, why should that stop the standardizarion of any algorithms?

Great work Sergey,
David

> On Feb 11, 2019, at 6:52 AM, Michael Scott <[email-masked]> wrote:
> 
> 1) Pairing-based crypto threw open the doors to lots of nice new crypto possibilities, enabling stuff that we couldn't do before
> 
> 2) Gradually post-quantum crypto is catching up and demonstrating capabilities that mirror some (but not all) of these achievements
> 
> 3) Post-quantum crypto depends on hard problems that it will take time to develop full confidence in, even in regard to attacks from non-quantum computers
> 
> 4) In the meantime (and that could be quite a long time) it makes perfect sense to proceed with the development and standardization of non-quantum safe methods.
> 
> 5) In the year x out pops a quantum computer. However in the year x-1 out popped well-developed and well-understood post-quantum crypto replacements in which we can have 
> complete confidence. 
> 
> 
> Everyone is a winner! Well except for the guys who invested in a business plan to develop a quantum computer on the basis that it would break all of crypto.
> 
> 
> Mike Scott
> 
>> On Sun, Feb 10, 2019 at 11:37 PM William Whyte <[email-masked]> wrote:
>> Hi all,
>> 
>> With no intent to cast aspersions on this particular scheme, I'm not sure that CFRG should be putting a lot of time into non-quantum-safe schemes these days unless there's a compelling reason to.
>> 
>> Cheers,
>> 
>> William
>> 
>>> On Sun, Feb 10, 2019 at 5:44 PM Sergey Gorbunov <[email-masked]> wrote:
>>> Dear Colleagues: 
>>> 
>>> We received some preliminary feedback from interested parties, and we plan to continue updating it as we receive more. 
>>> Please take a look. 
>>> web
>> I may have sent this email out of office hours. I never expect a response outside yours.

---

From: Tony Arcieri <[email-masked]>
Date: Mon, 11 Feb 2019 06:56:49 -0800

> capabilities that mirror some (but not all) of these achievements

I'd agree with this: it is great people are working on post-quantum
cryptography, but I do not view the threat as particular urgent (i.e. 10+
years away, if ever), and therefore think it makes sense to continue to
work on pre-quantum and post-quantum schemes in parallel.

Furthermore I'd like to add that pairings-based signature schemes like this
have somewhat unique and highly useful properties around offline signature
aggregation and small signature sizes. At least to my knowledge, there is
no post-quantum secure equivalent of bilinear pairings (perhaps I'm
mistaken?), so if we focus exclusively on post-quantum schemes we leave all
of these benefits on the table, even in the event large QCs capable of
attacking this class of elliptic curve prove to be intractable.

-- 
Tony Arcieri

---

From: Eric Rescorla <[email-masked]>
Date: Tue, 12 Feb 2019 21:19:03 -0800

FWIW, I have more than once wanted a scheme with the properties of BLS. I'm
not an expert in this area, but assuming that BLS is still the state of the
art here, it seems like it would be useful to document it in CFRG.

-Ekr

On Mon, Feb 11, 2019 at 6:57 AM Tony Arcieri <[email-masked]> wrote:

> Furthermore I'd like to add that pairings-based signature schemes like
> this have somewhat unique and highly useful properties around offline
> signature aggregation and small signature sizes. At least to my knowledge,
> there is no post-quantum secure equivalent of bilinear pairings (perhaps
> I'm mistaken?), so if we focus exclusively on post-quantum schemes we leave
> all of these benefits on the table, even in the event large QCs capable of

---

From: 赵运磊 <[email-masked]>
Date: Wed, 13 Feb 2019 15:32:59 +0800 (GMT+08:00)

For existing applicaitons like blockchain and cryptosystems, aggregate signature is indeed highly desirable. BLS is based on bilinear maps, and an aggregate signature from the general elliptic curves without using pairings may also be desirable (particularly for blockchain). 

Andy Yao and I designed a signature scheme, named Gamma-signature, and we recently shew that Gamma-signature well supports signature aggregation. For more details and comparisons with BLS, please refer to https://eprint.iacr.org/2018/414

We wonder whether it is possible to document in CFRG. Any comments are appreciated.

All my best
Yunlei
Fudan University, Shanghai, China

-----原始邮件-----
发件人:"Eric Rescorla" <[email-masked]>
发送时间:2019-02-13 13:19:03 (星期三)
收件人: "Tony Arcieri" <[email-masked]>
抄送: CFRG <[email-masked]>
主题: Re: [Cfrg] BLS standard draft

FWIW, I have more than once wanted a scheme with the properties of BLS. I'm not an expert in this area, but assuming that BLS is still the state of the art here, it seems like it would be useful to document it in CFRG.

-Ekr

I'd agree with this: it is great people are working on post-quantum cryptography, but I do not view the threat as particular urgent (i.e. 10+ years away, if ever), and therefore think it makes sense to continue to work on pre-quantum and post-quantum schemes in parallel.

Furthermore I'd like to add that pairings-based signature schemes like this have somewhat unique and highly useful properties around offline signature aggregation and small signature sizes. At least to my knowledge, there is no post-quantum secure equivalent of bilinear pairings (perhaps I'm mistaken?), so if we focus exclusively on post-quantum schemes we leave all of these benefits on the table, even in the event large QCs capable of attacking this class of elliptic curve prove to be intractable.

--

Tony Arcieri

---

From: David Wong <[email-masked]>
Date: Sun, 17 Feb 2019 08:54:36 -0800

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