LAMPS M. Ounsworth
Internet-Draft Entrust Datacard
Intended status: Informational September 17, 2019
Expires: March 20, 2020

Post-quantum Multi-Key Mechanisms for PKIX-like protocols; Problem Statement and Overview of Solution Space


With the widespread adoption of post-quantum (PQ) cryptography will come uncertainty about the strength of cryptographic primitives. For example; when will RSA and ECC fall? Are Lattice schemes as strong as we believe? The cryptographic community is calling for hybrid schemes that combine classic and post-quantum crypto in ways that remain strong so long as at least one of the algorithms used remains strong.

This document defines the problem statement for digital signatures in PKIX-like protocols, and gives an overview of the general families of solutions.

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 March 20, 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 ( 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. Problem Statement

In general terms, "hybrid" or "layered" signatures means that the document signer performs multiple, parallel, signatures over the document and provides them all to the verifier. The verifier's job is to check that all signatures are valid.

The general concept is straight-forward, but the devil is in the details.

1.1. Formal Security Requirements

A solution to the PQ multi-signature problem MUST meet the following "security" properties:

A solution to the PQ multi-signature problem MAY meet the following "desirable" properties, depending on context of the protocol in which the signature is being performed. And yes, some of these conflict with each other:

2. Solution Space

At the time of writing, there have been proposed three broad families of solutions being considered: concatenating multiple public keys and signatures together into a large single public key / signature object, multiple independent traditional certificate chains, and placing PQ data into v3 extensions. Since this discussion came out of LAMPS, the solutions that have drafts are X.509-focused, but we note that the first solution ("composite") is more general.

Each solution space is described below. I am trying to keep these abstract and not solution-specific.

2.1. "Composite" concatenated keys and signatures

Concatenate public keys, algorithmIDs, and signatureValues into "composite" versions of those structures.




This family of solutions has been instantiated in [draft-ounsworth-pq-composite-sigs-01].

2.2. Application: X.509

2.2.1. Multiple Certificate Chains

If you want multiple public keys on multiple cryptographic algorithms, then get multiple certificates from multiple PKIs. The protocol has control of negotiating which algorithms get used, how to encapsulate the large PQ data, etc. In many ways, this is the most obvious solution.



At time of writing, I am not aware of any internet drafts or other implementations of this family of solutions.

2.2.2. "Hybrid" v3 extensions

Place the PQ data into X.509v3 extensions. This has two general forms; the "PQ extension" contains a complete second certificate, or the "PQ extensions" contain an alternative public key, signature algorithm, and signature value.




This family of solutions has been instantiated in [draft-truskovsky-lamps-pq-hybrid-x509-01], and has a related standard currently before the ITU.

3. Conclusion

None of these solution families are a panacea. Multi-cert looks preferable for online negotiated protocols, hybrid looks preferable for environments with strong backwards compatibility requirements for legacy clients, and composite looks preferable for controlled environments where you know the clients will support the composite message format.

4. Intellectual Property Considerations

Hybrid certificates, specifically [draft-truskovsky-lamps-pq-hybrid-x509-01] has IPR held by ISARA which has an IPR statement available at

Composite certificates, specifically [draft-ounsworth-pq-composite-sigs-01] has IPR held by Max Pala and CableLabs, but with open license terms, available at

5. Contributors and Acknowledgements

This document incorporates contributions and comments from a large group of experts, including the authors list of [draft-ounsworth-pq-composite-sigs-01] and hallway chats at IETF105 and other crypto conferences.

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

6. Informative References

[I-D.ounsworth-pq-composite-sigs] Ounsworth, M. and M. Pala, "Composite Keys and Signatures For Use In Internet PKI", Internet-Draft draft-ounsworth-pq-composite-sigs-01, July 2019.
[I-D.truskovsky-lamps-pq-hybrid-x509] Truskovsky, A., Geest, D., Fluhrer, S., Kampanakis, P., Ounsworth, M. and S. Mister, "Multiple Public-Key Algorithm X.509 Certificates", Internet-Draft draft-truskovsky-lamps-pq-hybrid-x509-01, August 2018.
[RFC8411] Schaad, J. and R. Andrews, "IANA Registration for the Cryptographic Algorithm Object Identifier Range", RFC 8411, DOI 10.17487/RFC8411, August 2018.

Author's Address

Mike Ounsworth Entrust Datacard Limited 1000 Innovation Drive Ottawa, Ontario, K2K 1E3 Canada EMail: