NIST Standardisation of Post-Quantum Cryptography
The National Institute of Standards and Technology (NIST) is an American governmental agency; dedicated to the promotion of innovation and industrial competitiveness.
Notably, this includes the publication of standards in the field of cyber-security and cryptography. For example, the hash function SHA-3 and the symmetric cipher AES both emerged during competitions supervised by NIST.
At the end of 2016, NIST published a call for proposals for post-quantum public-key (PQ-PK) cryptographic algorithms. Briefly, PQ-PK cryptographic algorithms are asymmetric cryptographic solutions, which are secure against attacks by quantum computers. The call was motivated by two key factors:
- If quantum computers became practical, they will destroy the security of our currently deployed public-key cryptographic solutions (such as RSA or ECDSA). The majority of our telecommunications channels make use of these encryption schemes to provide confidentiality, authentication and integrity. The realisation of a quantum computer would impact on almost every aspect of our communications. For example, economic markets would be severely impaired, as economic transactions are often encrypted using non-quantum-safe methods.
- Significant progress has been made in recent years that brings a practical quantum computer closer to reality. The point at which a quantum computer is able to outperform a classic super computer is known as the point of ‘quantum supremacy’. This is universally recognised as a quantum computer with 50 long-term, stable qubits. At present, managing a long-term qubit is complex, so the development community is looking to leverage more qubits with a shorter lifespan.
For instance, in January 2018 Intel unveiled a 49 short-term-qubit quantum computer, and three months later, Google presented a 72 short-term-qubit quantum chip called Bristlecone. Microsoft is also working on a quantum computer with a similar of medium-term qubits. It is believed by many that the realisation of large-scale quantum computers is more an engineering challenge than a theoretical one.
In November 2017, NIST closed its called for PQ-PK crypto algorithms, having receive 70 submissions. It’s interesting to note that the majority of submissions were not exclusively academic or commercial in nature, but the result of close collaboration between both sides of the cryptographic community.
As the competition progresses, each submission will be subject to intense scrutiny around practical implementation (both software and hardware), security proofs and intellectual property analysis.
Submissions are categorised as either encryption algorithms (aimed at providing confidentiality) or signature algorithms (providing authentication, non-repudiation, and integrity). They can roughly be divided into five categories:
- Code-based algorithms – mainly encryption: the first such algorithm was proposed in 1978 and has not been broken since. Usually quite fast but suffer from large keys sizes.
- Lattice-based algorithms – signature and encryption: they may offer the best theoretical security, but this is not fully understood yet. Usually efficient, fast, and simple.
- Hash-based algorithms – signature: at present, their resistance to quantum attacks is best known. They are fast but have two major drawbacks. The signer must keep track of the number of signatures issued, and this number is limited. NB: the limit on the number of signatures can be raised, but at the expense of signature size.
- Multivariate-polynomial algorithms – mainly signature: they provide the shortest signature size among the PQ-PK algorithms, but their keys sizes are large. Also, they do not rely on formal security proofs, but on practical security estimates based on the complexity of known attacks.
- Other algorithms – signature and encryption: some algorithms do not fit in the previous categories; including isogeny-based schemes, aimed at adapting elliptic-curve cryptography to the post-quantum era.
It is likely that NIST will select several algorithms at the end of the process, as each of the technologies has its own strengths and weaknesses. In any case, NIST plans to standardise encryption and signature algorithms separately; excluding the de facto selection of a single solution. This process is likely to involve two steps:
- First, immediately standardise a solution based on mature technologies (for which the level of confidence regarding security is high) such as hash-based, code-based, or lattice-based algorithms.
- Second, take some time to investigate solutions based on emerging technologies (such as isogeny-based algorithms) before developing standards.
ID Quantique is not directly involved in the development of the PQ-PK algorithms submitted to NIST, but we maintain strong links with some of the main protagonists, such as the Ecole Polytechnique Fédérale de Lausanne (EPFL).
As a leading developer of quantum-safe random number generation and quantum key distribution systems, we will be closely following the results of the competition as future solutions will almost certainly encompass the developing PQ-PK primitives.