CFRG                                                            D. Boneh
Internet-Draft                                                  R. Wahby
Expires: February 9, 2020                            Stanford University
                                                             S. Gorbunov
                                     Algorand and University of Waterloo
                                                                  H. Wee
                                                 Algorand and ENS, Paris
                                                                Z. Zhang
                                                                Algorand
                                                          August 8, 2019


                  draft-irtf-cfrg-bls-signature-00.txt
                    draft-irtf-cfrg-bls-signature-00

Abstract

   BLS is a digital signature scheme with compression properties.  With
   a given set of signatures (signature_1, ..., signature_n) anyone can
   produce a compressed signature signature_compressed.  The same is
   true for a set of secret keys or public keys, while keeping the
   connection between sets (i.e., a compressed public key is associated
   to its compressed secret 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.

Status of This Memo

   This Internet-Draft is submitted in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current Internet-
   Drafts is at https://datatracker.ietf.org/drafts/current/.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   This Internet-Draft will expire on February 9, 2020.







Boneh, et al.           Expires February 9, 2020                [Page 1]


Internet-Draft                BLS-signature                  August 2019


Copyright Notice

   Copyright (c) 2019 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents
   (https://trustee.ietf.org/license-info) in effect on the date of
   publication of this document.  Please review these documents
   carefully, as they describe your rights and restrictions with respect
   to this document.  Code Components extracted from this document must
   include Simplified BSD License text as described in Section 4.e of
   the Trust Legal Provisions and are provided without warranty as
   described in the Simplified BSD License.

Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   3
     1.1.  Comparison with ECDSA . . . . . . . . . . . . . . . . . .   4
     1.2.  Organization of this document . . . . . . . . . . . . . .   4
     1.3.  Terminology and definitions . . . . . . . . . . . . . . .   5
     1.4.  API . . . . . . . . . . . . . . . . . . . . . . . . . . .   7
     1.5.  Requirements  . . . . . . . . . . . . . . . . . . . . . .   7
   2.  Core operations . . . . . . . . . . . . . . . . . . . . . . .   7
     2.1.  Variants  . . . . . . . . . . . . . . . . . . . . . . . .   7
     2.2.  Parameters  . . . . . . . . . . . . . . . . . . . . . . .   8
     2.3.  KeyGen  . . . . . . . . . . . . . . . . . . . . . . . . .   9
     2.4.  KeyValidate . . . . . . . . . . . . . . . . . . . . . . .  10
     2.5.  CoreSign  . . . . . . . . . . . . . . . . . . . . . . . .  11
     2.6.  CoreVerify  . . . . . . . . . . . . . . . . . . . . . . .  11
     2.7.  Aggregate . . . . . . . . . . . . . . . . . . . . . . . .  12
     2.8.  CoreAggregateVerify . . . . . . . . . . . . . . . . . . .  12
   3.  BLS Signatures  . . . . . . . . . . . . . . . . . . . . . . .  13
     3.1.  Basic scheme  . . . . . . . . . . . . . . . . . . . . . .  13
       3.1.1.  AggregateVerify . . . . . . . . . . . . . . . . . . .  14
     3.2.  Message augmentation  . . . . . . . . . . . . . . . . . .  14
       3.2.1.  Sign  . . . . . . . . . . . . . . . . . . . . . . . .  14
       3.2.2.  Verify  . . . . . . . . . . . . . . . . . . . . . . .  15
       3.2.3.  AggregateVerify . . . . . . . . . . . . . . . . . . .  15
     3.3.  Proof of possession . . . . . . . . . . . . . . . . . . .  16
       3.3.1.  Parameters  . . . . . . . . . . . . . . . . . . . . .  16
       3.3.2.  PopProve  . . . . . . . . . . . . . . . . . . . . . .  17
       3.3.3.  PopVerify . . . . . . . . . . . . . . . . . . . . . .  17
       3.3.4.  FastAggregateVerify . . . . . . . . . . . . . . . . .  18
   4.  Ciphersuites  . . . . . . . . . . . . . . . . . . . . . . . .  18
     4.1.  Ciphersuite format  . . . . . . . . . . . . . . . . . . .  19
     4.2.  Ciphersuites for BLS12-381  . . . . . . . . . . . . . . .  19
       4.2.1.  Basic . . . . . . . . . . . . . . . . . . . . . . . .  20



Boneh, et al.           Expires February 9, 2020                [Page 2]


Internet-Draft                BLS-signature                  August 2019


       4.2.2.  Message augmentation  . . . . . . . . . . . . . . . .  20
       4.2.3.  Proof of possession . . . . . . . . . . . . . . . . .  21
   5.  Security Considerations . . . . . . . . . . . . . . . . . . .  22
     5.1.  Validating public keys  . . . . . . . . . . . . . . . . .  22
     5.2.  Skipping membership check . . . . . . . . . . . . . . . .  22
     5.3.  Side channel attacks  . . . . . . . . . . . . . . . . . .  22
     5.4.  Randomness considerations . . . . . . . . . . . . . . . .  22
     5.5.  Implementing hash_to_point and hash_pubkey_to_point . . .  23
   6.  Implementation Status . . . . . . . . . . . . . . . . . . . .  23
   7.  Related Standards . . . . . . . . . . . . . . . . . . . . . .  23
   8.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .  24
   9.  References  . . . . . . . . . . . . . . . . . . . . . . . . .  24
     9.1.  Normative References  . . . . . . . . . . . . . . . . . .  24
     9.2.  Informative References  . . . . . . . . . . . . . . . . .  24
     9.3.  URIs  . . . . . . . . . . . . . . . . . . . . . . . . . .  26
   Appendix A.  BLS12-381  . . . . . . . . . . . . . . . . . . . . .  26
   Appendix B.  Test Vectors . . . . . . . . . . . . . . . . . . . .  27
   Appendix C.  Security analyses  . . . . . . . . . . . . . . . . .  27
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .  27

1.  Introduction

   A signature scheme is a fundamental cryptographic primitive that is
   used to protect authenticity and integrity of communication.  Only
   the holder of a secret key can sign messages, but anyone can verify
   the signature using the associated public key.

   Signature schemes are used in point-to-point secure communication
   protocols, PKI, remote connections, etc.  Designing efficient and
   secure digital signature is very important for these applications.

   This document describes the BLS signature scheme.  The scheme enjoys
   a variety of important efficiency properties:

   1.  The public key and the signatures are encoded as single group
       elements.

   2.  Verification requires 2 pairing operations.

   3.  A collection of signatures (signature_1, ..., signature_n) can be
       compressed into a single signature (signature).  Moreover, the
       compressed signature can be verified using only n+1 pairings (as
       opposed to 2n pairings, when verifying n signatures separately).

   Given the above properties, the scheme enables many interesting
   applications.  The immediate applications include





Boneh, et al.           Expires February 9, 2020                [Page 3]


Internet-Draft                BLS-signature                  August 2019


   o  authentication and integrity for Public Key Infrastructure (PKI)
      and blockchains.

      *  The usage is similar to classical digital signatures, such as
         ECDSA.

   o  compressing signature chains for PKI and Secure Border Gateway
      Protocol (SBGP).

      *  Concretely, in a PKI signature chain of depth n, we have n
         signatures by n certificate authorities on n distinct
         certificates.  Similarly, in SBGP, each router receives a list
         of n signatures attesting to a path of length n in the network.
         In both settings, using the BLS signature scheme would allow us
         to compress the n signatures into a single signature.

   o  consensus protocols for blockchains.

      *  There, BLS signatures are used for authenticating transactions
         as well as votes during the consensus protocol, and the use of
         aggregation significantly reduces the bandwidth and storage
         requirements.

1.1.  Comparison with ECDSA

   The following comparison assumes BLS signatures with curve BLS12-381,
   targeting 128 bits security.

   For 128 bits security, ECDSA takes 37 and 79 micro-seconds to sign
   and verify a signature on a typical laptop.  In comparison, for the
   same level of security, BLS takes 370 and 2700 micro-seconds to sign
   and verify a signature.

   In terms of sizes, ECDSA uses 32 bytes for public keys and 64 bytes
   for signatures; while BLS uses 96 bytes for public keys, and 48 bytes
   for signatures.  Alternatively, BLS can also be instantiated with 48
   bytes of public keys and 96 bytes of signatures.  BLS also allows for
   signature compression.  In other words, a single signature is
   sufficient to anthenticate multiple messages and public keys.

1.2.  Organization of this document

   This document is organized as follows:

   o  The remainder of this section defines terminology and the high-
      level API.





Boneh, et al.           Expires February 9, 2020                [Page 4]


Internet-Draft                BLS-signature                  August 2019


   o  Section 2 defines primitive operations used in the BLS signature
      scheme.  These operations MUST NOT be used alone.

   o  Section 3 defines three BLS Signature schemes giving slightly
      different security and performance properties.

   o  Section 4 defines the format for a ciphersuites and gives
      recommended ciphersuites.

   o  The appendices give test vectors, etc.

1.3.  Terminology and definitions

   The following terminology is used through this document:

   o  SK: The secret key for the signature scheme.

   o  PK: The public key for the signature scheme.

   o  message: The input to be signed by the signature scheme.

   o  signature: The digital signature output.

   o  aggregation: Given a list of signatures for a list of messages and
      public keys, an aggregation algorithm generates one signature that
      authenticates the same list of messages and public keys.

   o  rogue key attack: An attack in which a specially crafted public
      key (the "rogue" key) is used to forge an aggregated signature.
      Section 3 specifies methods for securing against rogue key
      attacks.

   The following notation and primitives are used:

   o  a || b denotes the concatenation of octet strings a and b.

   o  A pairing-friendly elliptic curve defines the following primitives
      (see [I-D.yonezawa-pairing-friendly-curves] for detailed
      discussion):

      *  E1, E2: elliptic curve groups defined over finite fields.  This
         document assumes that E1 has a more compact representation than
         E2, i.e., because E1 is defined over a smaller field than E2.

      *  G1, G2: subgroups of E1 and E2 (respectively) having prime
         order r.





Boneh, et al.           Expires February 9, 2020                [Page 5]


Internet-Draft                BLS-signature                  August 2019


      *  P1, P2: distinguished points that generate of G1 and G2,
         respectively.

      *  GT: a subgroup, of prime order r, of the multiplicative group
         of a field extension.

      *  e : G1 x G2 -> GT: a non-degenerate bilinear map.

   o  For the above pairing-friendly curve, this document writes
      operations in E1 and E2 in additive notation, i.e., P + Q denotes
      point addition and x * P denotes scalar multiplication.
      Operations in GT are written in multiplicative notation, i.e., a *
      b is field multiplication.

   o  For each of E1 and E2 defined by the above pairing-friendly curve,
      we assume that the pairing-friendly elliptic curve definition
      provides several primitives, described below.
      Note that these primitives are named generically.  When referring
      to one of these primitives for a specific group, this document
      appends the name of the group, e.g., point_to_octets_E1,
      subgroup_check_E2, etc.

      *  point_to_octets(P) -> ostr: returns the canonical
         representation of the point P as an octet string.  This
         operation is also known as serialization.

      *  octets_to_point(ostr) -> P: returns the point P corresponding
         to the canonical representation ostr, or INVALID if ostr is not
         a valid output of point_to_octets.  This operation is also
         known as deserialization.

      *  subgroup_check(P) -> VALID or INVALID: returns VALID when the
         point P is an element of the subgroup of order r, and INVALID
         otherwise.  This function can always be implemented by checking
         that r * P is equal to the identity element.  In some cases,
         faster checks may also exist, e.g., [Bowe19].

   o  I2OSP and OS2IP are the functions defined in [RFC8017], Section 4.

   o  hash_to_point(ostr) -> P: a cryptographic hash function that takes
      as input an arbitrary octet string and returns a point on an
      elliptic curve.  Functions of this kind are defined in
      [I-D.irtf-cfrg-hash-to-curve].  Each of the ciphersuites in
      Section 4 specifies the hash_to_point algorithm to be used.







Boneh, et al.           Expires February 9, 2020                [Page 6]


Internet-Draft                BLS-signature                  August 2019


1.4.  API

   The BLS signature scheme defines the following API:

   o  KeyGen(IKM) -> PK, SK: a key generation algorithm that takes as
      input an octet string comprising secret keying material, and
      outputs a public key PK and corresponding secret key SK.

   o  Sign(SK, message) -> signature: a signing algorithm that generates
      a deterministic signature given a secret key SK and a message.

   o  Verify(PK, message, signature) -> VALID or INVALID: a verification
      algorithm that outputs VALID if signature is a valid signature of
      message under public key PK, and INVALID otherwise.

   o  Aggregate(signature_1, ..., signature_n) -> signature: an
      aggregation algorithm that compresses a collection of signatures
      into a single signature.

   o  AggregateVerify((PK_1, message_1), ..., (PK_n, message_n),
      signature) -> VALID or INVALID: an aggregate verification
      algorithm that outputs VALID if signature is a valid aggregated
      signature for a collection of public keys and messages, and
      outputs INVALID otherwise.

1.5.  Requirements

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in [RFC2119].

2.  Core operations

   This section defines core operations used by the schemes defined in
   Section 3.  These operations MUST NOT be used except as described in
   that section.

2.1.  Variants

   Each core operation has two variants that trade off signature and
   public key size:

   1.  Minimal-signature-size: signatures are points in G1, public keys
       are points in G2.  (Recall from Section 1.3 that E1 has a more
       compact representation than E2.)

   2.  Minimal-pubkey-size: public keys are points in G1, signatures are
       points in G2.



Boneh, et al.           Expires February 9, 2020                [Page 7]


Internet-Draft                BLS-signature                  August 2019


       Implementations using signature aggregation SHOULD use this
       approach, since the size of (PK_1, ..., PK_n, signature) is
       dominated by the public keys even for small n.

2.2.  Parameters

   The core operations in this section depend on several parameters:

   o  A signature variant, either minimal-signature-size or minimal-
      pubkey-size.  These are defined in Section 2.1.

   o  A pairing-friendly elliptic curve, plus associated functionality
      given in Section 1.3.

   o  H, a hash function H that MUST be a secure cryptographic hash
      function, e.g., SHA-256 [FIPS180-4].  For security, H MUST output
      at least ceil(log2(r)) bits, where r is the order of the subgroups
      G1 and G2 defined by the pairing-friendly elliptic curve.

   o  hash_to_point, a function whose interface is described in
      Section 1.3.  When the signature variant is minimal-signature-
      size, this function MUST output a point in G1.  When the signature
      variant is minimal-pubkey size, this function MUST output a point
      in G2.  For security, this function MUST be either a random oracle
      encoding or a nonuniform encoding, as defined in
      [I-D.irtf-cfrg-hash-to-curve].

   In addition, the following primitives are determined by the above
   parameters:

   o  P, an elliptic curve point.  When the signature variant is
      minimal-signature-size, P is the distinguished point P2 that
      generates the group G2 (see Section 1.3).  When the signature
      variant is minimal-pubkey-size, P is the distinguished point P1
      that generates the group G1.

   o  r, the order of the subgroups G1 and G2 defined by the pairing-
      friendly curve.

   o  pairing, a function that invokes the function e of Section 1.3,
      with argument order depending on signature variant:

      *  For minimal-signature-size:
         pairing(U, V) := e(U, V)

      *  For minimal-pubkey-size:
         pairing(U, V) := e(V, U)




Boneh, et al.           Expires February 9, 2020                [Page 8]


Internet-Draft                BLS-signature                  August 2019


   o  point_to_pubkey and point_to_signature, functions that invoke the
      appropriate serialization routine (Section 1.3) depending on
      signature variant:

      *  For minimal-signature-size:
         point_to_pubkey(P) := point_to_octets_E2(P)
         point_to_signature(P) := point_to_octets_E1(P)

      *  For minimal-pubkey-size:
         point_to_pubkey(P) := point_to_octets_E1(P)
         point_to_signature(P) := point_to_octets_E2(P)

   o  pubkey_to_point and signature_to_point, functions that invoke the
      appropriate deserialization routine (Section 1.3) depending on
      signature variant:

      *  For minimal-signature-size:
         pubkey_to_point(ostr) := octets_to_point_E2(ostr)
         signature_to_point(ostr) := octets_to_point_E1(ostr)

      *  For minimal-pubkey-size:
         pubkey_to_point(ostr) := octets_to_point_E1(ostr)
         signature_to_point(ostr) := octets_to_point_E2(ostr)

   o  pubkey_subgroup_check and signature_subgroup_check, functions that
      invoke the appropriate subgroup check routine (Section 1.3)
      depending on signature variant:

      *  For minimal-signature-size:
         pubkey_subgroup_check(P) := subgroup_check_E2(P)
         signature_subgroup_check(P) := subgroup_check_E1(P)

      *  For minimal-pubkey-size:
         pubkey_subgroup_check(P) := subgroup_check_E1(P)
         signature_subgroup_check(P) := subgroup_check_E2(P)

2.3.  KeyGen

   The KeyGen algorithm generates a pair (PK, SK) deterministically
   using the secret octet string IKM.

   KeyGen uses HKDF [RFC5869] instantiated with the hash function H.

   For security, IKM MUST be infeasible to guess, e.g., generated by a
   trusted source of randomness.  IKM MUST be at least 32 bytes long,
   but it MAY be longer.





Boneh, et al.           Expires February 9, 2020                [Page 9]


Internet-Draft                BLS-signature                  August 2019


   Because KeyGen is deterministic, implementations MAY choose either to
   store the resulting (PK, SK) or to store IKM and call KeyGen to
   derive the keys when necessary.

   (PK, SK) = KeyGen(IKM)

   Inputs:
   - IKM, a secret octet string. See requirements above.

   Outputs:
   - PK, a public key encoded as an octet string.
   - SK, the corresponding secret key, an integer 0 <= SK < r.

   Definitions:
   - HKDF-Extract is as defined in RFC5869, instantiated with hash H.
   - HKDF-Expand is as defined in RFC5869, instantiated with hash H.
   - L is the integer given by ceil((1.5 * ceil(log2(r))) / 8).
   - "BLS-SIG-KEYGEN-SALT-" is an ASCII string comprising 20 octets.
   - "" is the empty string.

   Procedure:
   1. PRK = HKDF-Extract("BLS-SIG-KEYGEN-SALT-", IKM)
   2. OKM = HKDF-Expand(PRK, "", L)
   3. x = OS2IP(OKM) mod r
   4. xP = x * P
   5. SK = x
   6. PK = point_to_pubkey(xP)
   7. return (PK, SK)

2.4.  KeyValidate

   The KeyValidate algorithm ensures that a public key is valid.

   result = KeyValidate(PK)

   Inputs:
   - PK, a public key in the format output by KeyGen.

   Outputs:
   - result, either VALID or INVALID

   Procedure:
   1. xP = pubkey_to_point(PK)
   2. If xP is INVALID, return INVALID
   3. If pubkey_subgroup_check(xP) is INVALID, return INVALID
   4. return VALID





Boneh, et al.           Expires February 9, 2020               [Page 10]


Internet-Draft                BLS-signature                  August 2019


2.5.  CoreSign

   The CoreSign algorithm computes a signature from SK, a secret key,
   and message, an octet string.

   signature = CoreSign(SK, message)

   Inputs:
   - SK, the secret key output by an invocation of KeyGen.
   - message, an octet string.

   Outputs:
   - signature, an octet string.

   Procedure:
   1. Q = hash_to_point(message)
   2. R = SK * Q
   3. signature = point_to_signature(R)
   4. return signature

2.6.  CoreVerify

   The CoreVerify algorithm checks that a signature is valid for the
   octet string message under the public key PK.

   The public key PK must satisfy KeyValidate(PK) == VALID
   (Section 2.4).

   result = CoreVerify(PK, message, signature)

   Inputs:
   - PK, a public key in the format output by KeyGen.
   - message, an octet string.
   - signature, an octet string in the format output by CoreSign.

   Outputs:
   - result, either VALID or INVALID.

   Procedure:
   1. R = signature_to_point(signature)
   2. If R is INVALID, return INVALID
   3. If signature_subgroup_check(R) is INVALID, return INVALID
   4. xP = pubkey_to_point(PK)
   5. Q = hash_to_point(message)
   6. C1 = pairing(Q, xP)
   7. C2 = pairing(R, P)
   8. If C1 == C2, return VALID, else return INVALID




Boneh, et al.           Expires February 9, 2020               [Page 11]


Internet-Draft                BLS-signature                  August 2019


2.7.  Aggregate

   The Aggregate algorithm compresses multiple signatures into one.

   signature = Aggregate(signature_1, ..., signature_n)

   Inputs:
   - signature_1, ..., signature_n, octet strings output by
     either CoreSign or Aggregate.

   Outputs:
   - signature, an octet string encoding a compressed signature
     that compbines all inputs; or INVALID.

   Procedure:
   1. accum = signature_to_point(signature_1)
   2. If accum is INVALID, return INVALID
   3. for i in 2, ..., n:
   4.     next = signature_to_point(signature_i)
   5.     If next is INVALID, return INVALID
   6.     accum = accum + next
   7. signature = point_to_signature(accum)
   8. return signature

2.8.  CoreAggregateVerify

   The CoreAggregateVerify algorithm checks an aggregated signature over
   several (PK, message) pairs.

   All public keys PK_i must satisfy KeyValidate(PK_i) == VALID
   (Section 2.4).




















Boneh, et al.           Expires February 9, 2020               [Page 12]


Internet-Draft                BLS-signature                  August 2019


 result = CoreAggregateVerify((PK_1, message_1), ..., (PK_n, message_n),
                              signature)

 Inputs:
 - PK_1, ..., PK_n, public keys in the format output by KeyGen.
 - message_1, ..., message_n, octet strings.
 - signature, an octet string output by Aggregate.

 Outputs:
 - result, either VALID or INVALID.

 Procedure:
 1. R = signature_to_point(signature)
 2. If R is INVALID, return INVALID
 3. If signature_subgroup_check(R) is INVALID, return INVALID
 4. C1 = 1 (the identity element in GT)
 5. for i in 1, ..., n:
 6.     xP = pubkey_to_point(PK_i)
 7.     Q = hash_to_point(message_i)
 8.     C1 = C1 * pairing(Q, xP)
 9. C2 = pairing(R, P)
 10. If C1 == C2, return VALID, else return INVALID

3.  BLS Signatures

   This section defines three signature schemes: basic, message
   augmentation, and proof of possession.  These schemes differ in the
   ways that they defend against rogue key attacks (Section 1.3).

   All of the schemes in this section are built on a set of core
   operations defined in Section 2.  Thus, defining a scheme requires
   fixing a set of parameters as defined in Section 2.2.

   All three schemes expose the KeyGen and Aggregate operations that are
   defined in Section 2.  The sections below define the other API
   functions (Section 1.4) for each scheme.

3.1.  Basic scheme

   In a basic scheme, rogue key attacks are handled by requiring all
   messages signed by an aggregate signature to be distinct.  This
   requirement is enforced in the definition of AggregateVerify.

   The Sign and Verify functions are identical to CoreSign and
   CoreVerify (Section 2), respectively.  AggregateVerify is defined
   below.





Boneh, et al.           Expires February 9, 2020               [Page 13]


Internet-Draft                BLS-signature                  August 2019


   All public keys PK supplied as arguments to Verify and
   AggregateVerify MUST satisfy KeyValidate(PK) == VALID (Section 2.4).

3.1.1.  AggregateVerify

   This function first ensures that all messages are distinct, and then
   invokes CoreAggregateVerify.

result = AggregateVerify((PK_1, message_1), ..., (PK_n, message_n),
                         signature)

Inputs:
- PK_1, ..., PK_n, public keys in the format output by KeyGen.
- message_1, ..., message_n, octet strings.
- signature, an octet string output by Aggregate.

Outputs:
- result, either VALID or INVALID.

Procedure:
1. If any two input messages are equal, return INVALID.
2. return CoreAggregateVerify((PK_1, message_1), ..., (PK_n, message_n),
                              signature)

3.2.  Message augmentation

   In a message augmentation scheme, signatures are generated over the
   concatenation of the public key and the message, ensuring that
   messages signed by different public keys are distinct.

   All public keys PK supplied as arguments to Verify and
   AggregateVerify MUST satisfy KeyValidate(PK) == VALID (Section 2.4).

3.2.1.  Sign

   To match the API for Sign defined in Section 1.4, this function
   recomputes the public key corresponding to the input SK.
   Implementations MAY instead implement an interface that takes the
   public key as an input.

   Note that the point P and the point_to_pubkey function are defined in
   Section 2.2.









Boneh, et al.           Expires February 9, 2020               [Page 14]


Internet-Draft                BLS-signature                  August 2019


   signature = Sign(SK, message)

   Inputs:
   - SK, a secret key output by an invocation of KeyGen.
   - message, an octet string.

   Outputs:
   - signature, an octet string.

   Procedure:
   1. xP = SK * P
   2. PK = point_to_pubkey(xP)
   3. return CoreSign(SK, PK || message)

3.2.2.  Verify

   result = Verify(PK, message, signature)

   Inputs:
   - PK, a public key in the format output by KeyGen.
   - message, an octet string.
   - signature, an octet string in the format output by CoreSign.

   Outputs:
   - result, either VALID or INVALID.

   Procedure:
   1. return CoreVerify(PK, PK || message, signature)

3.2.3.  AggregateVerify

  result = AggregateVerify((PK_1, message_1), ..., (PK_n, message_n),
                           signature)

  Inputs:
  - PK_1, ..., PK_n, public keys in the format output by KeyGen.
  - message_1, ..., message_n, octet strings.
  - signature, an octet string output by Aggregate.

  Outputs:
  - result, either VALID or INVALID.

  Procedure:
  1. for i in 1, ..., n:
  2.    mprime_i = PK_i || message_i
  3. return CoreAggregateVerify((PK_1, mprime_1), ..., (PK_n, mprime_n),
                                signature)




Boneh, et al.           Expires February 9, 2020               [Page 15]


Internet-Draft                BLS-signature                  August 2019


3.3.  Proof of possession

   A proof of possession scheme uses a separate public key validation
   step, called a proof of possession, to defend against rogue key
   attacks.  This enables an optimization to aggregate signature
   verification for the case that all signatures are on the same
   message.

   The Sign, Verify, and AggregateVerify functions are identical to
   CoreSign, CoreVerify, and CoreAggregateVerify (Section 2),
   respectively.  In addition, a proof of possession scheme defines
   three functions beyond the standard API (Section 1.4):

   o  PopProve(SK) -> proof: an algorithm that generates a proof of
      possession for the public key corresponding to secret key SK.

   o  PopVerify(PK, proof) -> VALID or INVALID: an algorithm that
      outputs VALID if proof is valid for PK, and INVALID otherwise.

   o  FastAggregateVerify(PK_1, ..., PK_n, message, signature) -> VALID
      or INVALID: a verification algorithm for the aggregate of multiple
      signatures on the same message.  This function is faster than
      AggregateVerify.

   All public keys used by Verify, AggregateVerify, and
   FastAggregateVerify MUST be accompanied by a proof of possession
   generated by PopProve, and the result of PopVerify on this proof MUST
   be VALID.

3.3.1.  Parameters

   In addition to the parameters required to instantiate the core
   operations (Section 2.2), a proof of possession scheme requires one
   further parameter:

   o  hash_pubkey_to_point(PK) -> P: a cryptographic hash function that
      takes as input a public key and outputs a point in the same
      subgroup as the hash_to_point algorithm used to instantiate the
      core operations.
      For security, this function MUST be orthogonal to the
      hash_to_point function.  In addition, this function MUST be either
      a random oracle encoding or a nonuniform encoding, as defined in
      [I-D.irtf-cfrg-hash-to-curve].  The RECOMMENDED way of
      instantiating hash_pubkey_to_point is to use the same hash-to-
      curve function as hash_to_point, with a different domain
      separation tag (see [I-D.irtf-cfrg-hash-to-curve], Section 5.1).





Boneh, et al.           Expires February 9, 2020               [Page 16]


Internet-Draft                BLS-signature                  August 2019


3.3.2.  PopProve

   This function recomputes the public key coresponding to the input SK.
   Implementations MAY instead implement an interface that takes the
   public key as input.

   Note that the point P and the point_to_pubkey and point_to_signature
   functions are defined in Section 2.2.  The hash_pubkey_to_point
   function is defined in Section 3.3.1.

   proof = PopProve(SK)

   Inputs:
   - SK, a secret key output by an invocation of KeyGen.

   Outputs:
   - proof, an octet string.

   Procedure:
   1. xP = SK * P
   2. PK = point_to_pubkey(xP)
   3. Q = hash_pubkey_to_point(PK)
   4. R = SK * Q
   5. proof = point_to_signature(R)
   6. return signature

3.3.3.  PopVerify

   Note that the following uses several functions defined in Section 2.
   The hash_pubkey_to_point function is defined in Section 3.3.1.





















Boneh, et al.           Expires February 9, 2020               [Page 17]


Internet-Draft                BLS-signature                  August 2019


   result = PopVerify(PK, proof)

   Inputs:
   - PK, a public key inthe format output by KeyGen.
   - proof, an octet string in the format output by PopProve.

   Outputs:
   - result, either VALID or INVALID

   Procedure:
   1. R = signature_to_point(proof)
   2. If R is INVALID, return INVALID
   3. If signature_subgroup_check(R) is INVALID, return INVALID
   4. If KeyValidate(PK) is INVALID, return INVALID
   5. xP = pubkey_to_point(PK)
   6. Q = hash_pubkey_to_point(PK)
   7. C1 = pairing(Q, xP)
   8. C2 = pairing(R, P)
   9. If C1 == C2, return VALID, else return INVALID

3.3.4.  FastAggregateVerify

   Note that the following uses several functions defined in Section 2.

   result = FastAggregateVerify(PK_1, ..., PK_n, message, signature)

   Inputs:
   - PK_1, ..., PK_n, public keys in the format output by KeyGen.
   - message, an octet string.
   - signature, an octet string output by Aggregate.

   Outputs:
   - result, either VALID or INVALID.

   Procedure:
   1. accum = pubkey_to_point(PK_1)
   2. for i in 2, ..., n:
   3.     next = pubkey_to_point(PK_i)
   4.     accum = accum + next
   5. PK = point_to_pubkey(accum)
   6. return CoreVerify(PK, message, signature)

4.  Ciphersuites

   This section defines the format for a BLS ciphersuite.  It also gives
   concrete ciphersuites based on the BLS12-381 pairing-friendly
   elliptic curve [I-D.yonezawa-pairing-friendly-curves].




Boneh, et al.           Expires February 9, 2020               [Page 18]


Internet-Draft                BLS-signature                  August 2019


4.1.  Ciphersuite format

   A ciphersuite specifies all parameters from Section 2.2, a scheme
   from Section 3, and any parameters the scheme requires.  In
   particular, a ciphersuite comprises:

   o  ID: the ciphersuite ID, an ASCII string.  The RECOMMENDED format
      for this string is
      "BLS_SIG_" || H2C_SUITE || "_" || SC_TAG || "_"

      *  strings in double quotes are literal ASCII octet sequences

      *  H2C_SUITE is the name of the hash-to-curve ciphersuite used to
         define the hash_to_point and hash_pubkey_to_point functions.

      *  SC_TAG SHOULD be "NUL" when SC is basic, "AUG" when SC is
         message-augmentation, or "POP" when SC is proof-of-possession.

   o  SC: the scheme, either basic, message-augmentation, or proof-of-
      possession.

   o  SV: the signature variant, either minimal-signature-size or
      minimal-pubkey-size.

   o  EC: a pairing-friendly elliptic curve, plus all associated
      functionality (Section 1.3).

   o  H: a cryptographic hash function.

   o  hash_to_point: a hash from arbitrary strings to elliptic curve
      points.  It is RECOMMENDED that hash_to_point be defined in terms
      of a hash-to-curve suite [I-D.irtf-cfrg-hash-to-curve] with domain
      separation tag equal to the ID string.

   o  hash_pubkey_to_point (only specified when SC is proof-of-
      possession): a hash from serialized public keys to elliptic curve
      points.  It is RECOMMENDED that hash_pubkey_to_point be defined in
      terms of a has-to-curve suite [I-D.irtf-cfrg-hash-to-curve], with
      domain separation tag constructed similarly to the ID string,
      namely:
      "BLS_POP_" || H2C_SUITE || "_" || SC_TAG || "_"

4.2.  Ciphersuites for BLS12-381

   The following ciphersuites are all built on the BLS12-381 elliptic
   curve.  The required primitives for this curve are given in
   Appendix A.




Boneh, et al.           Expires February 9, 2020               [Page 19]


Internet-Draft                BLS-signature                  August 2019


   These ciphersuites use the hash-to-curve suites BLS12381G1-SHA256-
   SSWU-RO- and BLS12381G2-SHA256-SSWU-RO- defined in
   [I-D.irtf-cfrg-hash-to-curve].  Each ciphersuite defines a unique
   hash_to_point function by specifying a domain separation tag (see
   [@I-D.irtf-cfrg-hash-to-curve, Section 5.1).

4.2.1.  Basic

   The ciphersuite with ID BLS_SIG_BLS12381G1-SHA256-SSWU-RO-_NUL_ uses
   the following parameters, in addition to the common parameters below.

   o  SV: minimal-signature-size

   o  hash_to_point: BLS12381G1-SHA256-SSWU-RO- with the ASCII domain
      separation tag
      BLS_SIG_BLS12381G1-SHA256-SSWU-RO-_NUL_

   The ciphersuite with ID BLS_SIG_BLS12381G2-SHA256-SSWU-RO-_NUL_ uses
   the following parameters, in addition to the common parameters below.

   o  SV: minimal-pubkey-size

   o  hash_to_point: BLS12381G2-SHA256-SSWU-RO- with the ASCII domain
      separation tag
      BLS_SIG_BLS12381G2-SHA256-SSWU-RO-_NUL_

   The above ciphersuites share the following common parameters:

   o  SC: basic

   o  EC: BLS12-381, as defined in Appendix A.

   o  H: SHA-256

4.2.2.  Message augmentation

   The ciphersuite with ID BLS_SIG_BLS12381G1-SHA256-SSWU-RO-_AUG_ uses
   the following parameters, in addition to the common parameters below.

   o  SV: minimal-signature-size

   o  hash_to_point: BLS12381G1-SHA256-SSWU-RO- with the ASCII domain
      separation tag
      BLS_SIG_BLS12381G1-SHA256-SSWU-RO-_AUG_

   The ciphersuite with ID BLS_SIG_BLS12381G2-SHA256-SSWU-RO-_AUG_ uses
   the following parameters, in addition to the common parameters below.




Boneh, et al.           Expires February 9, 2020               [Page 20]


Internet-Draft                BLS-signature                  August 2019


   o  SV: minimal-pubkey-size

   o  hash_to_point: BLS12381G2-SHA256-SSWU-RO- with the ASCII domain
      separation tag
      BLS_SIG_BLS12381G2-SHA256-SSWU-RO-_AUG_

   The above ciphersuites share the following common parameters:

   o  SC: message-augmentation

   o  EC: BLS12-381, as defined in Appendix A.

   o  H: SHA-256

4.2.3.  Proof of possession

   The ciphersuite with ID BLS_SIG_BLS12381G1-SHA256-SSWU-RO-_POP_ uses
   the following parameters, in addition to the common parameters below.

   o  SV: minimal-signature-size

   o  hash_to_point: BLS12381G1-SHA256-SSWU-RO- with the ASCII domain
      separation tag
      BLS_SIG_BLS12381G1-SHA256-SSWU-RO-_POP_

   o  hash_pubkey_to_point: BLS12381G1-SHA256-SSWU-RO- with the ASCII
      domain separation tag
      BLS_POP_BLS12381G1-SHA256-SSWU-RO-_POP_

   The ciphersuite with ID BLS_SIG_BLS12381G2-SHA256-SSWU-RO-_POP_ uses
   the following parameters, in addition to the common parameters below.

   o  SV: minimal-pubkey-size

   o  hash_to_point: BLS12381G2-SHA256-SSWU-RO- with the ASCII domain
      separation tag
      BLS_SIG_BLS12381G2-SHA256-SSWU-RO-_POP_

   o  hash_pubkey_to_point: BLS12381G2-SHA256-SSWU-RO- with the ASCII
      domain separation tag
      BLS_POP_BLS12381G2-SHA256-SSWU-RO-_POP_

   The above ciphersuites share the following common parameters:

   o  SC: proof-of-possession

   o  EC: BLS12-381, as defined in Appendix A.




Boneh, et al.           Expires February 9, 2020               [Page 21]


Internet-Draft                BLS-signature                  August 2019


   o  H: SHA-256

5.  Security Considerations

5.1.  Validating public keys

   All algorithms in Section 2 and Section 3 that operate on public keys
   require first validating these keys.  For the basic and message
   augmentation schemes, the use of KeyValidate is REQUIRED.  For the
   proof of possession scheme, each public key MUST be accompanied by a
   proof of possession, and use of PopVerify is REQUIRED.

   Note that implementations MAY cache validation results for public
   keys in order to avoid unnecessarily repeating validation for known
   keys.

5.2.  Skipping membership check

   Some existing implementations skip the signature_subgroup_check
   invocation in CoreVerify (Section 2.6), whose purpose is ensuring
   that the signature is an element of a prime-order subgroup.  This
   check is REQUIRED of conforming implementations, for two reasons.

   1.  For most pairing-friendly elliptic curves used in practice, the
       pairing operation e (Section 1.3) is undefined when its input
       points are not in the prime-order subgroups of E1 and E2.  The
       resulting behavior is unpredictable, and may enable forgeries.

   2.  Even if the pairing operation behaves properly on inputs that are
       outside the correct subgroups, skipping the subgroup check breaks
       the strong unforgeability property.

5.3.  Side channel attacks

   Implementations of the signing algorithm SHOULD protect the secret
   key from side-channel attacks.  One method for protecting against
   certain side-channel attacks is ensuring that the implementation
   executes exactly the same sequence of instructions and performs
   exactly the same memory accesses, for any value of the secret key.
   In other words, implementations on the underlying pairing-friendly
   elliptic curve SHOULD run in constant time.

5.4.  Randomness considerations

   BLS signatures are deterministic.  This protects against attacks
   arising from signing with bad randomness, for example, the nonce
   reuse attack on ECDSA [HDWH12].




Boneh, et al.           Expires February 9, 2020               [Page 22]


Internet-Draft                BLS-signature                  August 2019


   As discussed in Section 2.3, the IKM input to KeyGen MUST be
   infeasible to guess and MUST be kept secret.  One possibility is to
   generate IKM from a trusted source of randonmess.  Guidelines on
   constructing such a source are outside the scope of this document.

5.5.  Implementing hash_to_point and hash_pubkey_to_point

   The security analysis models hash_to_point and hash_pubkey_to_point
   as random oracles.  It is crucial that these functions are
   implemented using a cryptographically secure hash function.  For this
   purpose, implementations MUST meet the requirements of
   [I-D.irtf-cfrg-hash-to-curve].

   In addition, ciphersuites MUST specify unique domain separation tags
   for hash_to_point and hash_pubkey_to_point.  The domain separation
   tag format used in Section 4 is the RECOMMENDED one.

6.  Implementation Status

   This section will be removed in the final version of the draft.
   There are currently several implementations of BLS signatures using
   the BLS12-381 curve.

   o  Algorand: bls_sigs_ref [1]

   o  Chia: spec [2] python/C++ [3].  Here, they are swapping G1 and G2
      so that the public keys are small, and the benefits of avoiding a
      membership check during signature verification would even be more
      substantial.  The current implementation does not seem to
      implement the membership check.  Chia uses the Fouque-Tibouchi
      hashing to the curve, which can be done in constant time.

   o  Dfinity: go [4] BLS [5].  The current implementations do not seem
      to implement the membership check.

   o  Ethereum 2.0: spec [6]

7.  Related Standards

   o  Pairing-friendly curves draft-yonezawa-pairing-friendly-curves [7]

   o  Pairing-based Identity-Based Encryption IEEE 1363.3 [8].

   o  Identity-Based Cryptography Standard rfc5901 [9].

   o  Hashing to Elliptic Curves draft-irtf-cfrg-hash-to-curve-04 [10],
      in order to implement the hash function hash_to_point.




Boneh, et al.           Expires February 9, 2020               [Page 23]


Internet-Draft                BLS-signature                  August 2019


   o  EdDSA rfc8032 [11]

8.  IANA Considerations

   TBD (consider to register ciphersuite identifiers for BLS signature
   and underlying pairing curves)

9.  References

9.1.  Normative References

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119,
              DOI 10.17487/RFC2119, March 1997,
              <https://www.rfc-editor.org/info/rfc2119>.

   [ZCash]    Electric Coin Company, "BLS12-381", July 2017,
              <https://github.com/zkcrypto/pairing/blob/master/src/
              bls12_381/README.md#serialization>.

9.2.  Informative References

   [BDN18]    Boneh, D., Drijvers, M., and G. Neven, "Compact multi-
              signatures for shorter blockchains", December 2018,
              <https://link.springer.com/
              chapter/10.1007/978-3-030-03329-3_15>.

   [BGLS03]   Boneh, D., Gentry, C., Lynn, B., and H. Shacham,
              "Aggregate and verifiably encrypted signatures from
              bilinear maps", May 2003, <https://link.springer.com/
              chapter/10.1007%2F3-540-39200-9_26>.

   [BLS01]    Boneh, D., Lynn, B., and H. Shacham, "Short signatures
              from the Weil pairing", December 2001,
              <https://www.iacr.org/archive/asiacrypt2001/22480516.pdf>.

   [BNN07]    Bellare, M., Namprempre, C., and G. Neven, "Unrestricted
              aggregate signatures", July 2007,
              <https://link.springer.com/
              chapter/10.1007%2F978-3-540-73420-8_37>.

   [Bol03]    Boldyreva, A., "Threshold Signatures, Multisignatures and
              Blind Signatures Based on the Gap-Diffie-Hellman-Group
              Signature Scheme", January 2003,
              <https://link.springer.com/
              chapter/10.1007%2F3-540-36288-6_3>.





Boneh, et al.           Expires February 9, 2020               [Page 24]


Internet-Draft                BLS-signature                  August 2019


   [Bowe19]   Bowe, S., "Faster subgroup checks for BLS12-381", July
              2019, <https://eprint.iacr.org/2019/814>.

   [FIPS180-4]
              National Institute of Standards and Technology (NIST),
              "FIPS Publication 180-4: Secure Hash Standard", August
              2015, <https://nvlpubs.nist.gov/nistpubs/FIPS/
              NIST.FIPS.180-4.pdf>.

   [HDWH12]   Heninger, N., Durumeric, Z., Wustrow, E., and J.
              Halderman, "Mining your Ps and Qs: Detection of widespread
              weak keys in network devices", August 2012,
              <https://www.usenix.org/system/files/conference/
              usenixsecurity12/sec12-final228.pdf>.

   [I-D.irtf-cfrg-hash-to-curve]
              Faz-Hernandez, A., Scott, S., Sullivan, N., Wahby, R., and
              C. Wood, "Hashing to Elliptic Curves", draft-irtf-cfrg-
              hash-to-curve-04 (work in progress), July 2019.

   [I-D.yonezawa-pairing-friendly-curves]
              Yonezawa, S., Kobayashi, T., and T. Saito, "Pairing-
              Friendly Curves", draft-yonezawa-pairing-friendly-
              curves-02 (work in progress), July 2019.

   [LOSSW06]  Lu, S., Ostrovsky, R., Sahai, A., Shacham, H., and B.
              Waters, "Sequential Aggregate Signatures and
              Multisignatures Without Random Oracles", May 2006,
              <https://link.springer.com/chapter/10.1007/11761679_28>.

   [RFC5869]  Krawczyk, H. and P. Eronen, "HMAC-based Extract-and-Expand
              Key Derivation Function (HKDF)", RFC 5869,
              DOI 10.17487/RFC5869, May 2010,
              <https://www.rfc-editor.org/info/rfc5869>.

   [RFC8017]  Moriarty, K., Ed., Kaliski, B., Jonsson, J., and A. Rusch,
              "PKCS #1: RSA Cryptography Specifications Version 2.2",
              RFC 8017, DOI 10.17487/RFC8017, November 2016,
              <https://www.rfc-editor.org/info/rfc8017>.

   [RY07]     Ristenpart, T. and S. Yilek, "The Power of Proofs-of-
              Possession: Securing Multiparty Signatures against Rogue-
              Key Attacks", May 2007, <https://link.springer.com/
              chapter/10.1007%2F978-3-540-72540-4_13>.







Boneh, et al.           Expires February 9, 2020               [Page 25]


Internet-Draft                BLS-signature                  August 2019


9.3.  URIs

   [1] https://github.com/kwantam/bls_sigs_ref

   [2] https://github.com/Chia-Network/bls-signatures/blob/master/
       SPEC.md

   [3] https://github.com/Chia-Network/bls-signatures

   [4] https://github.com/dfinity/go-dfinity-crypto

   [5] https://github.com/dfinity/bls

   [6] https://github.com/ethereum/eth2.0-specs/blob/master/specs/
       bls_signature.md

   [7] https://tools.ietf.org/html/draft-yonezawa-pairing-friendly-
       curves-00

   [8] https://ieeexplore.ieee.org/document/6662370

   [9] https://tools.ietf.org/html/rfc5091

   [10] https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-02

   [11] https://tools.ietf.org/html/rfc8032

Appendix A.  BLS12-381

   The ciphersuites in Section 4 are based upon the BLS12-381 pairing-
   friendly elliptic curve.  The following defines the correspondence
   between the primitives in Section 1.3 and the parameters given in
   Section 4.2.2 of [I-D.yonezawa-pairing-friendly-curves].

   o  E1, G1: the curve E and its order-r subgroup.

   o  E2, G2: the curve E' and its order-r subgroup.

   o  GT: the subgroup G_T.

   o  P1: the point BP.

   o  P2: the point BP'.

   o  e: the optimal Ate pairing defined in Appendix A of
      [I-D.yonezawa-pairing-friendly-curves].





Boneh, et al.           Expires February 9, 2020               [Page 26]


Internet-Draft                BLS-signature                  August 2019


   o  point_to_octets and octets_to_point use the compressed
      serialization formats for E1 and E2 defined by [ZCash].

   o  subgroup_check MAY use either the naive check described in
      Section 1.3 or the optimized check given by [Bowe19].

Appendix B.  Test Vectors

   TBA: (i) test vectors for both variants of the signature scheme
   (signatures in G2 instead of G1) , (ii) test vectors ensuring
   membership checks, (iii) intermediate computations ctr, hm.

Appendix C.  Security analyses

   The security properties of the BLS signature scheme are proved in
   [BLS01].

   [BGLS03] prove the security of aggregate signatures over distinct
   messages, as in the basic scheme of Section 3.1.

   [BNN07] prove security of the message augmentation scheme of
   Section 3.2.

   [Bol03][LOSSW06][RY07] prove security of constructions related to the
   proof of possession scheme of Section 3.3.

   [BDN18] prove the security of another rogue key defense; this defense
   is not standardized in this document.

Authors' Addresses

   Dan Boneh
   Stanford University
   USA

   Email: dabo@cs.stanford.edu


   Riad S. Wahby
   Stanford University
   USA

   Email: rsw@cs.stanford.edu








Boneh, et al.           Expires February 9, 2020               [Page 27]


Internet-Draft                BLS-signature                  August 2019


   Sergey Gorbunov
   Algorand and University of Waterloo
   Boston, MA
   USA

   Email: sergey@algorand.com


   Hoeteck Wee
   Algorand and ENS, Paris
   Boston, MA
   USA

   Email: wee@di.ens.fr


   Zhenfei Zhang
   Algorand
   Boston, MA
   USA

   Email: zhenfei@algorand.com





























Boneh, et al.           Expires February 9, 2020               [Page 28]