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.

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

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

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:

1.3. Terminology and definitions

The following terminology is used through this document:

The following notation and primitives are used:

1.4. API

The BLS signature scheme defines the following API:

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.
    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:

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

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.

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

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

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).

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.

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.

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)

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):

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:

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.

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].

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:

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.

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.

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

The above ciphersuites share the following common parameters:

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.

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

The above ciphersuites share the following common parameters:

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.

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

The above ciphersuites share the following common parameters:

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].

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.

7. Related Standards

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.
[ZCash] Electric Coin Company, "BLS12-381", July 2017.

9.2. Informative References

[BDN18] Boneh, D., Drijvers, M. and G. Neven, "Compact multi-signatures for shorter blockchains", December 2018.
[BGLS03] Boneh, D., Gentry, C., Lynn, B. and H. Shacham, "Aggregate and verifiably encrypted signatures from bilinear maps", May 2003.
[BLS01] Boneh, D., Lynn, B. and H. Shacham, "Short signatures from the Weil pairing", December 2001.
[BNN07] Bellare, M., Namprempre, C. and G. Neven, "Unrestricted aggregate signatures", July 2007.
[Bol03] Boldyreva, A., "Threshold Signatures, Multisignatures and Blind Signatures Based on the Gap-Diffie-Hellman-Group Signature Scheme", January 2003.
[Bowe19] Bowe, S., "Faster subgroup checks for BLS12-381", July 2019.
[FIPS180-4] National Institute of Standards and Technology (NIST), "FIPS Publication 180-4: Secure Hash Standard", August 2015.
[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.
[I-D.irtf-cfrg-hash-to-curve] Faz-Hernandez, A., Scott, S., Sullivan, N., Wahby, R. and C. Wood, "Hashing to Elliptic Curves", Internet-Draft draft-irtf-cfrg-hash-to-curve-04, July 2019.
[I-D.yonezawa-pairing-friendly-curves] Yonezawa, S., Kobayashi, T. and T. Saito, "Pairing-Friendly Curves", Internet-Draft draft-yonezawa-pairing-friendly-curves-02, July 2019.
[LOSSW06] Lu, S., Ostrovsky, R., Sahai, A., Shacham, H. and B. Waters, "Sequential Aggregate Signatures and Multisignatures Without Random Oracles", May 2006.
[RFC5869] Krawczyk, H. and P. Eronen, "HMAC-based Extract-and-Expand Key Derivation Function (HKDF)", RFC 5869, DOI 10.17487/RFC5869, May 2010.
[RFC8017] Moriarty, K., Kaliski, B., Jonsson, J. and A. Rusch, "PKCS #1: RSA Cryptography Specifications Version 2.2", RFC 8017, DOI 10.17487/RFC8017, November 2016.
[RY07] Ristenpart, T. and S. Yilek, "The Power of Proofs-of-Possession: Securing Multiparty Signatures against Rogue-Key Attacks", May 2007.

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].

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
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