By Mark Pecen, Chief Operating Officer, ISARA Corporation (Canada)
Chairman, ETSI TC Cyber Working Group for Quantum Safe Cryptography (QSC) (France)
Board member, Institute for Quantum Computing, (Canada)
What is a cryptographic certificate?
Cryptographic certificates are used to prove a person’s, system’s, company’s or other entity’s identity. Today, cryptographic certificates are based on public key cryptography, and are also known as a “digital certificate” or “identify certificate”, which is an electronic document whose contents can prove the ownership of a piece of information called the “public key”. A certificate functions somewhat like a passport or identity card, in that the counterparty can be reasonably assured of the person holding the certificate’s true identity. This assurance is achieved through the use of a cryptographic function, which is a mathematical operation, the results of which validate the identity of the certificate holder.
How are cryptographic certificates used?
Certificates are often used to prove the identity of a server component. For example, when a user signs onto an eCommerce site such as Amazon, that user wants to be absolutely sure that they are shopping with the “real Amazon” and not an imposter site who uses their credit card or other financial information for criminal purposes. Certificates are also used to secure email, so that the recipient knows the true identity of the sender. There is also the concept of non-repudiation, which means that the sender has no means of denying the fact that a properly signed email was written by that sender. Cryptographic certificates can also be used to validate signatures on programs, such as operating system and other software updates, to ensure that the update is coming from a reliable source and was not tampered with during delivery.
How is the development of quantum computers threatening the use of certificates?
As quantum computers become more capable, the security of existing cryptographic certificates declines over time. The real issue as quantum computers gain capabilities, is that certificates rely on public-key cryptographic functions, and today’s public-key cryptography relies on mathematical problems that are vulnerable to attack by quantum computers [1, 2]. Fortunately, there are classes of problems that make for excellent security against quantum computer attack. Now, there is ongoing work in the Information and Communication Technology (ICT) industry to use these new approaches to security to take certificates to the next level: quantum-safe and dual mode certificates.
Members of standards bodies such as the European Telecommunication Standards Institute (ETSI), International Telecommunication Union (ITU), National Institute of Technology and Standards (NIST), Internet Engineering Task Force (IETF) and American National Standards Institute (ANSI X9) are collaboratively evaluating the various quantum safe alternatives to existing public-key cryptographic primitives. These include cryptographic problems which are known as hash-based signatures, discrete multivariate based functions, cryptography based on error-detection and correction codes, lattice problems and isogenies which are a new kind of elliptic curve problem .
What is being done to ensure that certificates are quantum-safe?
Some work is being done by industry members to create both quantum-safe and hybrid certificates. A hybrid certificate is a type of certificate that supports both legacy and future quantum-safe certificates, so that migration to a quantum-safe alternative will be fairly simple and cost-effective.
Work is being done in the ITU by ISARA Corporation to add an optional feature to the widely-used ITU Rec. X.509 certificate so that certificates may operate as dual-mode – legacy and quantum-safe. This means that the existing certificates may be used as long as necessary, but new certificates can be introduced into a network at any time without risk to the operation of existing networks and systems. The new X.509 certificate feature is expected to be ready-to-use sometime in the second half of 2018.
Figure 1: Hybrid certificate operation – both legacy and quantum-safe certificates work in the same environment
Figure 2: Hybrid certificate operation – legacy and quantum-safe certificates are understood by legacy and updated components alike
 “A fast quantum mechanical algorithm for database search”, (Lov K. Grover, STOC 1996, pp 212-219), ACM 1996
 Peter W. Shor: “Polynomial-time algorithms for prime factorization and discrete logarithms on a
quantum computer”, SIAM Journal on Computing, 26(5):1484-1509, 1997
 Quantum Safe Cryptography and Security: an introduction, benefits, enablers and challenges, (Pecen, et al.; European Telecommunication Standards Institute (ETSI), ISBN No. 979-10-92620-03-0), June 2015