The cryptography world is going through a revolution. As new computation paradigms emerge and rapidly advance, like quantum computing (QC), the broadband industry needs to start planning how it will address the new security threats that are on the horizon.
Most of the public key cryptosystems like RSA [Rsa16] or ECDSA [Ec05] will not be considered secure when (and if) a large quantum supercomputer is ever built. For the broadband industry this means that, because of the dependency on X.509 [X509] certificates and the RSA algorithm, to provide devices with secure and verifiable identities, the protocols that are used today, e.g. DOCSIS® protocols [Doc31;Doc40], will need to support new algorithms and identities. In fact, network elements like cable modems or Remote PHY (R-PHY) nodes [RPhy18] use, today, their RSA private key and associated certificates chain to prove they are a legitimate and registered entity on the network. To continue to benefit from the security and usability advantages of public-key cryptography (PKC), the broadband industry must provide a mechanism for transitioning to quantum-resistant solutions in a cost-effective manner.
Although our previous results on Composite Crypto (or Hybrid certificates) provided a promising path forward for the deployment of multiple keys associated with a single identity, our work still left some important questions. For example, an area that was still left to be explored was how to handle complex crypto policies for algorithm validation and deprecation. Because of these limitations, encryption was also left out of scope.
This paper describes our new results in multi-key environments that address the open issues from our previous work and update its technical details [Pala04]. Specifically, in this work we extend the initial proposal and introduce the explicit separation of “AND” and “OR” logic operations across the multi-key signature components. Additionally, our work enables encryption for multi-key certificates (e.g., for S/MIME or document multi-signing purposes) that was, up to now, still an open problem. Together with these important results, this paper also describes our proposal for algorithm revocation and how we leverage the details of X.509 certificates’ public key structures together with extensions in CRLs and/or OCSP responses to provide a dynamic, centrally managed, and easy to deploy algorithm revocation mechanism.
The rest of the paper is organized as follows: Section 2 provides an overview of the current landscape of Post-Quantum (PQ) cryptography and how it addresses the quantum threat. Section 3 describes the composite crypto solution and highlights current limitations of multi-key certificates when it comes to validations or encryption; Section 4 describes the new results that stem from the introduction of Combined Crypto alongside Composite Crypto; Section 5 provides the details on our algorithm revocation mechanism. Section 6 addresses the multi-key encryption conundrum and, finally, Section 7provides our conclusions and envisioned future work.