Internet-Draft K-threshold Sigs November 2022
Pala & Klaussner Expires 19 May 2023 [Page]
Intended Status:
Standards Track
M. Pala
J. Klaussner
D-Trust GmbH

K-threshold Composite Signatures for the Internet PKI


With the need to evolve the cryptography used in today applications, devices, and networks, there might be many scenarios where the use of a single-key certificate is not sufficient. For example, there might be the need for migrating between two existing algorithms (e.g., from classic to post-quantum) or there might be the need to test the capabilities of devices via test drivers and/or non-standard algorithms.

Differently from the situation where algorithms are not yet (or no more) trusted to be used by themselves, this document addresses the use of multiple keys and signatures that can be individually trusted to implement a generic 1-threshold and K-threshold signature validation procedures.

This document provides the definition of a new type of multi-algorithm public key and relies on the definition of CompositePrivateKey, and CompositeSignature which are sequences of the respective structure for each component algorithm as defined in [I-D.ounsworth-pq-composite-sigs] and [I-D.ounsworth-pq-composite-sigs].

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

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 19 May 2023.

1. Terminology

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here. These words may also appear in this document in lower case as plain English words, absent their normative meanings.

This document is consistent with the terminology defined in [I-D.driscoll-pqt-hybrid-terminology]. In addition, the following terminology is used throughout this document:


Basic Encoding Rules (BER) as defined in [X.690].


Any software that is making use of a cryptographic key. This includes a signer, verifier, encrypter, decrypter.


Distinguished Encoding Rules as defined in [X.690].


Public Key Infrastructure, as defined in [RFC5280].


The public and private portion of an asymmetric cryptographic key, making no assumptions about which algorithm.


One component of the Composite Key. For example, an RSA, a Dilithium3 or a Falcon512 key.

2. Introduction

When the trust in the cryptographic algorithms is not static (e.g., not enough crypto-analysis has happened yet or a new threat is envisioned to be deployable in the next future), there might be the need to combine multiple algorithms together to address the crypto-uncertainty of the envisioned period.

An example of such a situation can be found in the planning for the transition to post-quantum cryptography (PQ or PQC). While classic algorithms will still be trusted for some time (but we do not know how much), there is uncertainty as to the strength of the new cryptographic algorithms. Unlike previous cryptographic algorithm migrations, the choice of when to migrate and which algorithms to migrate to, is not so clear.

Even after the migration period, it may be advantageous for an entity cryptographic identity to be composed of multiple public-key algorithms by using a Post-Quantum/Traditional (PQ/T) or Post-Quantum/Post-Quantum (PQ/PQ) Hybrid scheme.

For further considerations on the challenges related to crypto-agility, please refer to [I-D.ounsworth-pq-composite-keys].

2.1. Alternative Algorithms Support

Although Composite cryptography and Hybrid solutions can be used in many common use-cases to protect against algorithmic failures over time, there are other use-cases that mandate for supporting crypto-interoperability to continue to be able to operate old devices (e.g., not upgradable) when deploying newer devices and crypto algorithms.

This is particularly true in environments where deployed devices might be distributed in the field such as infrastructure's network elements (e.g., network routers, amplifiers, monitoring devices, cable modems, public access points, etc.). The use of multi-algorithms provides a mechanism for enabling forward compatibility with newer devices even when they cannot be upgraded.

At a practical level this means that we need a mechanism to still be able to validate Composite signatures even when not all algorithms are supported by all devices.

This work introduces the concept of alternative signatures which joins the family of hybrid options such as Composite Crypto.

3. The MultiKey Approach Overview

The MultiKey approach focus is to provide the possibility to validate Composite signatures even when not all algorithms that were used in the generation of the Composite signature are supported. From this point of view, the MultiKey approach differs from the Composite crypto one in that it allows relying parties to perform the validation of a subset of signatures instead of requiring the successful validation of all signatures.

We define n the number of component key in the MultiKey key, and k the minimum number of component signature successful validations required for the Composite signature to be considered valid.

3.1. 1-threshold and K-threshold signature validation

The MultiKey approach defined in this document leverages the same procedures and data structures defined for pk-Composite [I-D.ounsworth-pq-composite-keys] with the addition of an optional public key parameter. This optional parameter carries the K value that represents the total number of skipped or erroneous signature validations.

In practice, the MultiKey approach can support different validation policies based on the value of the optional key parameter. For example, by setting the value to one (1) it is possible to require that at least one (1) component signature is correctly validated, thus providing support for true alternative signatures. When using values greater than one (1), MultiKey keys can support K of N models where at least K successful validations MUST take place before the Composite signature is considered valid.

In the rest of the section we focus on the description of private and public key structures, while in the next section we focus on the changes in the validation process when compared to signatures generated via Composite Keys.

3.2. MultiKey Private Keys

This section provides an encoding for MultiKey private keys intended for PKIX protocols and other applications that require an interoperable format for transmitting private keys, such as PKCS #8 [RFC5958], PKCS #12 [RFC7292], CMP [RFC4210], or CRMF [RFC4211].

The format for the individual component key in a MultiKey key is defined by the algorithm OID that identifies the component key. The format of the MultiKey described in this section is meant to provide an interoperable format that can be adopted and implemented across implementations.

This document does not cover the use-case where individual components may be stored in multiple cryptographic modules.

The MultiKey private key data use the same structure as in CompositePrivateKey where each component key is a OneAsymmetricKey [RFC5958] object:

MultiKeyPrivateKey ::= CompositePrivateKey

A MultiKeyPrivateKey MUST contain at least two component private keys, and they MUST be in the same order as in the corresponding MultiKeyPublicKey.

3.3. MultiKey Public Keys

MultiKey Public Keys are identified by a unique OID and the associated definition of the related data structure for a multi-algorithm public key, namely a MultiKey key.

The OID that identifies a generic MultiKey key is defined as follows:

    id-multikey-key OBJECT IDENTIFIER ::= {
      iso(1) identified-organization(3) dod(6)
      internet(1) private(4) enterprise(1) OpenCA(18227)
      Algorithms(2) PublicKey(1) Experimental(999)
      MultiKey(2) }

The associated definition of MultiKey's public key (pk-MultiKey) and MultiKey's public key parameters (MultiKey-params) structures are as follows:

MultiKey-params ::= INTEGER (1..MAX)

pk-MultiKey PUBLIC-KEY ::= {
  id id-multikey-key
  KeyValue MultiKeyPublicKey
  Params TYPE MultiKey-params ARE optional
  PrivateKey MultiKeyPrivateKey

Where the MultiKey-params is used to specify the number of minimum successful validations required for the signature to be considered valid.

The value of the MultiKey-params must be greater or equal to one (1) and shall not exceed the number of component keys present in the MultiKey public key.

The use of MultiKey algorithm in a component key is not allowed in a MultiKey key.

3.4. Composite Signature Extended definition

The sa-CompositeSignature structure is extended as follows:

sa-CompositeSignatureEx SIGNATURE-ALGORITHM ::= {
       IDENTIFIER id-alg-composite
       VALUE CompositeSignatureValue
       PUBLIC-KEYS { pk-Composite | pk-MultiKey }
       SMIME-CAPS { IDENTIFIED BY id-alg-composite } }

The difference with the original sa-CompositeSignature definition is the introduction of the pk-MultiKey in the PUBLIC-KEYS definition.

4. MultiKey Signature Processes

This section specifies the processes for generating and verifying composite signatures generated via MultiKey keys.

4.1. Generating Composite Signatures

When using MultiKey to generate signatures, the process is the same as in the Composite case. Please refer to section 5.1 of [I-D.ounsworth-pq-composite-sigs].

4.2. Validating Composite Signatures

When validating composite signatures generated via MultiKey keys, the validation procedures are modified to allow for a well-defined number of component signatures validation failures to occur before failing the validation of the composite signature as a whole. The possibility to be able to still consider a composite signature valid in the presence of unsupported protocols is a useful feature for guaranteeing the interoperability of newer devices with older ones that might not be able to correctly process all the algorithms (but they can still validate a subset of them).

In fact, when validating signatures generated via MultiKey keys, the total number of successful component signature validations shall be equal or greater than the public key parameter K (when present). After that, additional component signatures' validations may be skipped (or fail) without impacting the validity of the whole composite signature.

When the public key parameter K is absent or its value is set to the number of components in the signing key (i.e., K = n), the validation process for MultiKey and Composite are the same.

When the public key parameter K is set to one (1), the validation process for MultiKey provides support for fully alternative signatures where a single successful component signature's validation validates the whole composite signature.

When compared to the composite signatures' validation process, we modify the for..loop cycle where the invalid signature output is not emitted after the first validation failure, but only if the number of remaining successful validations is larger than the number of remaining validations.

The second optimization allowed by MultiKey keys is to be able to consider a composite signature successful right after at least K successful component signatures' validations, without the need for even attempting at performing the remaining ones.

The Input and Output definitions are the same as defined in composite:

     P1, P2, .., Pn    Public verification keys.

     M                 Message

     S1, S2, .., Sn    Component signature values.

     A1, A2, ... An    Component signature algorithms.


    Validity (bool)    "Valid signature" (true) if the composite
                        signature is valid, "Invalid signature"
                        (false) otherwise.

The following process is used to perform composite signatures verification with a MultiKey key:

1. Check keys, signatures, and algorithms for consistency.

   If Error during desequencing, or the three sequences
   have different numbers of elements, or any of the public
   keys P1, P2, .., Pn or algorithm identifiers A1, A2, ..,
   An are multikey with the OID id-alg-composite or an
   explicit composite OID then output "Invalid signature"
   and stop.

2. Check each component signature individually, according to
   its algorithm specification. Parameter K holds the number of successful
   validations yet required and is reduced as soon as a component signature is verified.
   If K reaches 0, the entire signature validation
   succeeds. If all component signatures are processed and K is not 0, The Validation as whole fails.

   IF MultiKey-params
     K := MultiKey-params
     K := n

   FOR i := 1 TO n:
     IF verify( Pi, M, Si, Ai ):
     IF (K == 0):
       Output "Valid signature"
     IF (n - i < K):
       Output "Invalid Signature"

5. Algorithm Identifiers

In this work, we define a set of OIDs that allow for assigning explicit algorithm combination to specific MultiKey keys configuration.

Please refer to Appendix Section 5 for more details about explicit MultiKey identifiers.

5.1. Signature Algorithm Identifiers

This document does not define a separate sets of algorithms and leverages the extends the definitions of composite signatures defined in [I-D.ounsworth-pq-composite-sigs] with the addition of the pk-multikey-key in the PUBLIC-KEYS set.

5.2. Public Key Algorithm Identifiers

Section Section 3.3 provides the definition for the generic MultiKey key identifier. The generic construct for a MultiKey key allows for both standard and non-standard (i.e., private, test, etc.) public key algorithms to be used to produce composite signatures.

Similarly to the composite case, the use of explicit combinations of algorithms can simplify the management of identities by allowing for inspecting a single OID (the outmost one) instead of requiring the inspection of the individual components of the MultiKey key.

6. Deprecating Algorithms and Impact over signature validations

Traditionally, a public key, certificate, or signature contains a single cryptographic algorithm and to revoke a certificate due to algorithm depecation we still need to use serial-number-based revocations.

However, in a multi-algorithms environment (e.g., supported via Composite, MultiKey, or other Hybrid approaches), it might be possible to deprecate an entire algorithm and still be able to securely continue performing authentications and validations instead of revoking (or simply distrust) the entire infrastructure (and without adding every single certificate that relies on the deprecated algorithm on the revocation list).

By integrating the concept of deprecated algorithms, in the MultiKey case it is possible to dynamically switch among which algorithms are going to be used for signature validations by informing the validating entity about the OIDs of the individual algorithms that are considered "failures".

In fact, the validating entity can automatically "fail" the validation of component signatures that match any value present in the list of revoked algorithms, exactly in the same fashion as when the algorithm is not supported in the first place.

6.1. Distributing the list of deprecated algorithms

As we just mentioned, in MultiKey environments, there are situations where the validation of a component signature that carries a deprecated algorithm identifier might still be allowed, e.g. when at least another K validate correctly.

On top of that, there are also typical use-cases where the deprecation of an algorithm is paramount to make sure that authentications do not rely only on deprecated algorithms. This is the case, for example, when older devices that can only successfully validate one algorithm from a composite signature (e.g., it can validate RSA signatures but no other) are still part of the network. When the only algorithm that they can use is deprecated, validation of composite signature MUST fail.

Differently from the pure composite case, if the device can still successfully validate K component signatures, the device does not need to be re-provisioned (or replaced) and can continue to operate by relying on the non-deprecated algorithm.

The list of deprecated algorithms that are to be considered automatic validation "failures" can be directly configured as a parameter in the validating entity's process, or by accessing a trusted source of information.

In an ecosystem such as the Internet PKI or IoT PKIs, since algorithm deprecation can be seen as another form of (mass) revocation, a convenient mechanism to distribute the list of deprecated algorithms by adding a specific extension to Certificate Revocation Lists [RFC5280] or Online Certificate Status Protocol [RFC6960] responses.

We define a new deprecated-algorithms extension together with the associated id-ext-deprecated-algorithms identifier. The data structure of the extension is defined as a SEQUENCE of DeprecatedAlgorithm. Each DeprecatedAlgorithm is defined as an OBJECT IDENTIFIER.

We define the following identifier:

id-ce-deprecatedAlgsList OBJECT IDENTIFIER ::= {
      iso(1) identified-organization(3) dod(6)
      internet(1) private(4) enterprise(1) OpenCA(18227)
      Extensions(3) deprecated-algs (2) }

7. IANA Considerations

This document registers the following in the SMI "Security for PKIX Algorithms (" registry:

id-composite-key OBJECT IDENTIFIER ::= {
    iso(1) identified-organization(3) dod(6) internet(1) security(5)
    mechanisms(5) pkix(7) algorithms(6) id-multikey-key(??) }

This document registers the following in the SMI " " registry:

id-ce-deprecatedAlgsList OBJECT IDENTIFIER ::= { id-ce deprecatedAlgsList(??) }

9. References

9.1. Normative References

Ounsworth, M., Pala, M., and J. Klaußner, "Composite Public and Private Keys For Use In Internet PKI", Work in Progress, Internet-Draft, draft-ounsworth-pq-composite-keys-03, , <>.
Ounsworth, M. and M. Pala, "Composite Signatures For Use In Internet PKI", Work in Progress, Internet-Draft, draft-ounsworth-pq-composite-sigs-07, , <>.
Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, , <>.
Adams, C., Farrell, S., Kause, T., Mononen, T., and RFC Publisher, "Internet X.509 Public Key Infrastructure Certificate Management Protocol (CMP)", RFC 4210, DOI 10.17487/RFC4210, , <>.
Schaad, J. and RFC Publisher, "Internet X.509 Public Key Infrastructure Certificate Request Message Format (CRMF)", RFC 4211, DOI 10.17487/RFC4211, , <>.
Cooper, D., Santesson, S., Farrell, S., Boeyen, S., Housley, R., and W. Polk, "Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile", RFC 5280, DOI 10.17487/RFC5280, , <>.
Turner, S. and RFC Publisher, "Asymmetric Key Packages", RFC 5958, DOI 10.17487/RFC5958, , <>.
Santesson, S., Myers, M., Ankney, R., Malpani, A., Galperin, S., Adams, C., and RFC Publisher, "X.509 Internet Public Key Infrastructure Online Certificate Status Protocol - OCSP", RFC 6960, DOI 10.17487/RFC6960, , <>.
Moriarty, K., Ed., Nystrom, M., Parkinson, S., Rusch, A., Scott, M., and RFC Publisher, "PKCS #12: Personal Information Exchange Syntax v1.1", RFC 7292, DOI 10.17487/RFC7292, , <>.
Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, , <>.
Schaad, J., Andrews, R., and RFC Publisher, "IANA Registration for the Cryptographic Algorithm Object Identifier Range", RFC 8411, DOI 10.17487/RFC8411, , <>.
ITU-T, "Information technology - ASN.1 encoding Rules: Specification of Basic Encoding Rules (BER), Canonical Encoding Rules (CER) and Distinguished Encoding Rules (DER)", ISO/IEC 8825-1:2015, .

9.2. Informative References

D, F., "Terminology for Post-Quantum Traditional Hybrid Schemes", Work in Progress, Internet-Draft, draft-driscoll-pqt-hybrid-terminology-01, , <>.

Appendix A. Explicit Algorithm Identifiers

This variant provides a rigid way of specifying supported combinations of algorithms.

Although this variant limits the possibility for combining non-standard algorithms (or algorithms not considered by the authors of this document), the use of identifiers that identify pairs of standard algorithms might be easier in certain situations such as referencing and/or enforcing specific combinations of algorithms without the need for developing additional validation procedures external to the signature validation one.

Explicit algorithms must define a new signature algorithm which consists of:

  • A new algorithm identifier OID for the explicit algorithm.
  • The algorithm identifier OID and PUBLIC-KEY type of each component algorithm.
  • Signature parameters either declared ABSENT, or defined with a type and encoding.

The definition of the explicit algorithm identifiers follows the same definitions provided in Section 4.2 of [I-D.ounsworth-pq-composite-keys] with the exception of the parameters that are not ABSENT but OPTIONAL and their TYPE is MultiKey-params as defined in Section 3.3.

Appendix B. ASN.1 Module





  PUBLIC-KEY, SIGNATURE-ALGORITHM, ParamOptions, AlgorithmIdentifier{}
    FROM AlgorithmInformation-2009  -- RFC 5912 [X509ASN1]
      { iso(1) identified-organization(3) dod(6) internet(1)
        security(5) mechanisms(5) pkix(7) id-mod(0)
        id-mod-algorithmInformation-02(58) }

    FROM PKIX1Explicit-2009
      { iso(1) identified-organization(3) dod(6) internet(1)
        security(5) mechanisms(5) pkix(7) id-mod(0)
        id-mod-pkix1-explicit-02(51) }

    FROM AsymmetricKeyPackageModuleV1
      { iso(1) member-body(2) us(840) rsadsi(113549) pkcs(1)
        pkcs-9(9) smime(16) modules(0)
        id-mod-asymmetricKeyPkgV1(50) } ;

  COMPOSITE-KEY-ALGORITHM, pk-Composite, CompositePublicKey,
    CompositePrivateKey, pk-explicitComposite, id-composite-key
    FROM Composite-Keys-2022 -- {{I-D.draft-ounsworth-pq-sigs}}
      { ... }
-- Object Identifiers

-- Public Key



Appendix C. Intellectual Property Considerations

The following IPR Disclosure relates to this draft:

Appendix D. Contributors and Acknowledgements

This document incorporates contributions and comments from a large group of experts. The Editors would especially like to acknowledge the expertise and tireless dedication of the following people, who attended many long meetings and generated millions of bytes of electronic mail and VOIP traffic over the past year in pursuit of this document:

John Gray (Entrust), Serge Mister (Entrust), Scott Fluhrer (Cisco Systems), Panos Kampanakis (Cisco Systems), Daniel Van Geest (ISARA), Tim Hollebeek (Digicert), Klaus-Dieter Wirth (D-Trust), and Francois Rousseau.

We are grateful to all, including any contributors who may have been inadvertently omitted from this list.

This document borrows text from similar documents, including those referenced below. Thanks go to the authors of those documents. "Copying always makes things easier and less error prone" - [RFC8411].

D.1. Making contributions

Additional contributions to this draft are welcome. Please see the working copy of this draft at, as well as open issues at:

Authors' Addresses

Massimiliano Pala
CableLabs Inc.
858 Coal Creek Cir
Louisville, Colorado, 80027
United States of America
Jan Klaussner
D-Trust GmbH
Kommandantenstr. 15
10969 Berlin