At some point in the not-too-distant future, it’s expected that quantum computing will pose a security risk to all currently used encryption techniques. Most current encryption methods are based on the challenges associated with factoring large numbers into their prime factors. They provide good levels of security when classical computers are being used, but quantum computers operate much faster and will be able to factor those numbers quickly using Shor’s algorithm to break encryption schemes like RSA (Rivest–Shamir–Adleman) public-key encryption and elliptic curve cryptography (ECC) that are currently secure.

As a result of this anticipated threat, the National Institute of Standards and Technology (NIST) initiated a process to gather, evaluate, and standardize quantum-resistant public-key cryptographic algorithms. That effort is referred to generically as post-quantum cryptography (PQC). NIST’s PQC program began in 2016 with a call for submissions of possible PQC algorithms. The agency had received 69 eligible algorithms by the November 2017 deadline.

The 69 algorithms were released for experts to analyze and, if possible, to break. Another goal was the development of discovery tools that can be used to detect and report current uses of quantum vulnerable cryptography with enough detail to enable risk analysis and remediation. Discovery was a multi-part process with the end goal of developing a prioritization list for further efforts (Figure 1).

Other aspects of the initial effort included:

• Identifying performance and interoperability challenges that may need to be overcome when implementing the first PQC algorithms that NIST will standardize.
• Comparing algorithms based on performance testing to estimate the initial costs of deploying the PQC algorithms compared with baseline classical crypto implementations.

The next activity was to prioritize development efforts using risk management methodologies, including Mosca’s Theorem, (X+Y)>Z, which states that if the amount of time that data must remain secure (X) plus the time it takes to upgrade cryptographic systems (Y) is greater than when quantum computers come online with enough power to break cryptography (Z), you have already run out of time. According to NIST, it has historically taken about 20 years to develop and deploy new security protocols, hence the sense of urgency to develop and deploy PQC algorithms.

The project also focuses on developing standardized and systematic methodologies for migrating to PQC algorithms on a range of platforms and technologies.

Quantum crypto for the IoT
NIST is leading the largest and most organized effort to develop PQC algorithms, but it’s not the only effort. Independent researchers are active worldwide, working on the challenges associated with PQC algorithms. Several groups are working on the challenges of securing IoT devices that can require lightweight and energy efficient PQC implementations. PQC algorithms fall into four categories (Figure 2):

• Hash-based functions are one-way functions that map bit strings of an arbitrary length to short, fixed-length strings called hash values. The hash-based signature scheme starts with a one-time signature scheme (OTS) and is suited for IoT devices since they don’t require computationally expensive mathematical operations like big integer arithmetic.
• Multivariate cryptography is the generic term for asymmetric cryptographic primitives based on solving nonlinear multivariate polynomials. All multivariate public-key cryptosystems (MPKC) use the same basic architecture.
• Code-based cryptography is a new approach intended to diversify existing public-key cryptosystems. Code-based cryptography, unlike public-key algorithms, is based on the problem of decoding unknown error-correcting codes.
• Lattice-based public-key encryption algorithms must find the shortest vector or the nearest vector in a high-dimensional lattice. Lattice PQC algorithms tend to be quantum-resistant and computationally efficient.

Summary
PQC algorithms are needed to ensure robust security when quantum computing comes online. NIST’s program to develop PQC algorithms is a race against time since the agency estimates that the development and deployment of PQC algorithms could take 20 years.

References
Migration to Post-Quantum Cryptography, NIST
Post-Quantum Cryptography: Anticipating Threats and Preparing the Future, European Union Agency for Cybersecurity (ENISA)
Post-Quantum Cryptosystems for Internet-of-Things, MDPI IoT