A Quick Introduction to Post Quantum Cryptography (PQC)
by Stephen Purser, former Head of Operations, ENISA
This short paper is meant to serve as a (very simple) primer to the area of post quantum cryptography (PQC) for security practitioners. From the start, I stress that I am not a cryptographer, although I do have many years’ experience in implementing and operating cryptographic systems. That having been said, I believe the technical information presented to be correct and up to date. This is an informal opinion paper and, as such, I have not provided any references beyond those which I believe can be used immediately by the target audience. Furthermore, I have limited technical details to a minimum and kept explanations as simple as possible so as to appeal to a wider audience.
The primary goal of this paper is to get practitioners thinking about PQC and how it affects their operational environments. My hope is that this will encourage many of the readers to carry out a quick first analysis of their own operations, to estimate the level of risk and to have a first look at mitigating strategies and planning considerations.
To this end, I have made a number of generic recommendations at the end of the paper on how to move forward.
What is a quantum computer?
A quantum computer is a computing device that harnesses the quantum mechanical properties of small particles to carry out certain types of calculations exponentially faster than a modern, traditional computer. It is important to note that quantum computers can only do this for certain classes of problems and are not therefore better than traditional computers in all domains. In addition, it takes quite some skill to design useful quantum algorithms due to the fact that although such a computer can process a vast amount of information simultaneously, it will only yield a single result at the end.
In summary, quantum computers can carry out selective calculations for certain types of problem, which a well-constructed algorithm can exploit to deliver a useful result in the real world. Examples of areas where quantum computers are known to be faster than traditional computers include problems that involve a Fourier Transformation (this has important consequences for cryptography), searching large datasets and simulation of quantum systems.
Quantum computers function by manipulating Qubits (or quantum bits). Physical examples of how Qubits are implemented include superconducting quantum computers (where the Qubit is realised by the state of superconducting circuits) and ion trap computers (where the Qubit is realised by the internal state of trapped ions). When it is measured, a Qubit must ‘collapse’ into either a <0> or a <1> and in this sense it behaves just like a classical bit. However, during the calculation phase, this same Qubit can exist in a large number of ‘superposed states’, which are essentially linear combinations of these two limiting values. In other words, a cubit can be in any state that can be described by the expression a<0> + b<1>. This, together with the mysterious property of entanglement (which I will not even try to explain) are at the heart of why quantum computers are exponentially faster at solving some problems.
In some senses, a quantum computer can be thought of as a massive parallel processing device, for which a certain amount of ingenuity is required to get the answer you need at the end of the calculation.
An illustrative use case
In order to provide a practical example of why quantum computers pose a threat to current cryptographic implementations and why PQC potentially mitigates this threat, we will make reference to a common use case.
The use case is a two-step process; (a) agreement between two communicating parties on a symmetric session key using asymmetric cryptography and (b) use of this session key to encrypt traffic for the duration of the session. The details of these mechanisms do not concern us in this paper, but it is important that the use case relies on both asymmetric and symmetric cryptography.
Asymmetric cryptography (also known as public key cryptography) is well suited to the first task because key distribution is much easier (public keys are public!) and there is no need to have a pre-established secret to share the session key. It is however not suited to carry out bulk encryption because computer processors are not particularly good at handling integer arithmetic (they do ‘floating point’ arithmetic), which results in a significant performance overhead. By limiting the use of asymmetric algorithms to the key agreement exchange we optimise the use of the technique without suffering any significant performance downgrade.
Symmetric cryptography is well suited to the second task precisely because it makes use of mathematical techniques that are easily implemented on traditional computing platforms. This results in better computational efficiency and improved speed. By using symmetric algorithms to carry out the bulk encryption, we ensure that data transmission is fast and efficient.
Why quantum computers pose a security threat
Significant threats to the above mentioned scenario include:
Any technique that would allow the asymmetric scheme to be broken (which would lead to
identification of the symmetric session key and hence to the ability to decrypt the ciphertext transmitted in the session1).
More directly, the symmetric key might be compromised, again leading to decryption of the session ciphertext.
Unfortunately, both threats can be realised with a suitably powerful quantum computer, although the impact of the second threat turns out to be less severe than the first one.
The threat to the asymmetric component lies in an algorithm created in 1994 by Peter Shor (Shor’s Algorithm). The original algorithm was designed to find the prime factors of a given integer (the fact that this is a ‘hard problem’ for classical computers is the basis of RSA algorithm). Shor also proposed algorithms for solving the discrete logarithm problem (and other problems based on finding the ‘period’ of some cyclic series of numbers).
The threat to the symmetric component comes from an algorithm developed by Lov Grover in 1996 (Grover’s Algorithm). Grover’s algorithm is a quantum search algorithm that improves the time taken to search a large set of N elements from N to √N.
Shor’s algorithm, should it be implemented on a real quantum computer, would have catastrophic consequences for current day asymmetric cryptography and it is this that has essentially given birth to the discipline of post quantum cryptography. Grover’s algorithm on the other hand is manageable in the sense that we can increase the key size to counter the threat. For this reason, symmetric algorithms are considered secure in the post quantum world.
These threats are compounded by a third threat, known as ‘store now, decrypt later’. This involves an attacker storing encrypted text now (knowing that he/she cannot currently decrypt such ciphertext) with the intention of decrypting it once sufficient processing power is available. This is a serious threat for organizations that require their data to remain secret for long periods of time and is one of the main drivers for an early adoption of a PQC approach.
Post Quantum Cryptography (PQC)
PQC is the discipline covering the development of cryptographic algorithms that are secure against an attack by a quantum computer. The general idea underlying PQC is to base future algorithms on mathematical problems that quantum computers are not good at solving.
Currently, there are six classes of algorithms that are being extensively studied:
Lattice-based
Code-based
Mutivariate
Hash-based
Isogeny-based
Symmetric key
The theory behind each of these areas is well developed. Apart from proving the security of new algorithms in these areas, there are also challenges associated with implementation (key sizes, integration into protocol suites, performance, …). The differences between the approaches is mainly in the mathematical techniques that they deploy to achieve their goals. Note that the symmetric key algorithms are essentially those that we are currently using or improved variants thereof. The idea with symmetric algorithms is to define the key size appropriately.
In 2016, NIST launched its Post-Quantum Cryptography Standardization program and competition with the goal of including PQC in their standards2. In 2022, they chose the first four winners of the competition. The selected algorithms are:
CRYSTALS-Kyber for public-key encryption and key establishment.
CRYSTALS-Dilithium, Falcon and SPHINCS+ for digital signatures.
These algorithms will become part of NIST’s post-quantum cryptographic standard once it is released. At present, standardisation is still in progress and this is expected to be followed by implementation guidelines.
Some technical considerations
This is not a technical paper by any means and this section can be skipped without any loss of continuity. I take the opportunity however to address a couple of technical issues, which are important for a full understanding of quantum computers and PQC.
First, where quantum computers are concerned, it is customary to make the difference between physical and logical Qubits. A physical Qubit is an instantiation in a physical environment (such as a trapped ion), whereas a logical Qubit is a logical construction bringing together several physical Qubits so as to minimize errors. This is achieved by using error correcting codes, which allow errors in individual physical Qubits to be detected and corrected without disturbing the information stored in the logical Qubit. Here, it is important to note that it is the logical Qubit that is the functional entity and the number of logical Qubits defines the computing power of the machine.
Turning to PQC, there are some technical issues that need to be resolved before we can deploy these algorithms in commercial settings. These issues are mainly connected to key sizes and signature sizes (which are in general quite large). This is problematic when attempting to integrate these algorithms in established protocol suites, such as TLS. This is also important when the target environment is resource-constrained (such as mobile phones and IoT devices).
Timescales and business implications
The current situation is therefore probably best summed up as follows:
Although quantum computers already exist, they are in general expensive and difficult to deploy. In addition, these computers offer a limited number of (logical) Qubits due to the difficulty in providing stable environments in which Qubits can be used.
PQC is a mature field of study which is providing algorithms capable of mitigating the quantum threat. However, here also there are several hurdles to be surmounted before we will be able to achieve widespread deployment based on a competitive global offering.
The ‘store now, decrypt later’ threat makes it important for organisations to understand their data now and to take steps to protect it accordingly.
The term ‘Q-Day’ refers the day when quantum computers can break common cryptographic protocols using quantum algorithms. It is a matter of some debate when Q-Day will occur, but there seems to be some consensus that it will be in the 10 to 15 years range. Interestingly, the NSA has set 2035 as the target date by which all national security systems should be quantumresistant3.
We can use the estimate of Q-Day in an inequality derived by Mosca to assess when a particular organisation should start to transition to PQC. According to Mosca4:
D + T > Qc
Where ‘D’ is the time we need our data to be secure for, ‘T’ is the time necessary to make the transition to post quantum cryptography and ‘QC ‘ is our estimate of Q-Day. The inequality states that the threat becomes real when D+T is greater than QC. For most organisations, Mosca’s inequality is likely to lead to the conclusion that they need to start preparing the migration to PQC now.
Migration Strategies
It might seem strange to recommend starting the migration to PQC at a time when neither the threat nor the mitigation tools are at maturity level, but this ignores the fact that a lot of work can be done to prepare for a later migration.
Both ANSSI5 and the BSI6 are recommending hybrid approaches to migration. This is a reflection of the fact that the current state of PQC is not sufficiently mature on its own to achieve the desired level of security. The idea behind a hybrid migration strategy is to combine post quantum algorithms with classical algorithms. To simplify considerably, the idea is that in combining pre- and post- quantum algorithms an attacker would have to break both in order to succeed. The ANSSI publication provides a deeper discussion on this topic and also provides additional references for those interested. A deeper discussion is beyond the scope of this paper, but the interested reader is invited to dig deeper.
Recommendations
Security practitioners should:
Educate themselves on the rationale for PQC and develop a basic understanding of the core techniques and state of the art.
Perform an initial risk analysis on their own environment(s), taking into account the ‘store now, decrypt later paradigm).
Develop a first idea of the threat timeline as it applies to their data.
Develop a first idea on planning for transition to PQC.
Begin transition activities if warranted by the above.
Stephen Purser, former Head of Operations, ENISA
______________
1 Assuming that Perfect Forward Secrecy techniques are not being used. In order not to introduce unnecessary complexity, consider generation of a session key and transmission by encrypting with the public RSA key of the communications partner.
2 https://csrc.nist.gov/projects/post-quantum-cryptography
3 https://media.defense.gov/2022/Sep/07/2003071836/-1/-1/0/CSI_CNSA_2.0_FAQ_.PDF
4 https://analyticsindiamag.com/moscas-inequality-and-its-effect-on-quantum-cryptography/
5 https://cyber.gouv.fr/en/publications/follow-position-paper-post-quantum-cryptography