Unlike conventional computers, quantum computers use quantum mechanical effects for computation. Such a computer uses “qubits” that can exist in what is known as a superposition. Instead of being either 0 or 1 as is the case with conventional devices, they can be in both states simultaneously. Consequently, certain calculations can be performed simultaneously and far faster than ever before. Quantum computers are solving problems, which would require computing power that cannot be achieved with today’s systems.
For example, a quantum computer is not suited to multiply long integers – a multiplication of large numbers is best done on a classical computer. However, with respect to the “prime factorization of long integers” the basis for cryptanalysis – quantum computers are ultra-fast compared to a “classical” computer.
In addition, the computing power they deliver is rising rapidly – year over year. These rapid developments are mainly driven by a multitude of tech companies (including IBM, Google, Microsoft and Amazon) investing in quantum computing.
With operations that are thousands of times faster, quantum computers offer new possibilities, for instance, in searching through large databases, simulation of chemical and physical reactions, and in material design. Although quantum computers will not completely replace classical computers, they can exponentially speed up certain arithmetic calculations.
Quantum computers affect conventional cryptography
Due to their computing power, quantum computers have the disruptive potential to break various encryption algorithms currently used. It is assumed, that quantum computer attacks on today’s cryptography are expected to become reality within the next 10 to 20 years.
The availability of such a “universal quantum computer” will certainly have a game changing effect on the cryptographic security of identity documents like eID cards, especially as they often have a regular lifetime of 10 years and more.
The established and widely used encryption algorithms such as RSA (Rivest Shamir Adelman), ECC (Elliptic Curve Cryptography) deployed in those electronic ID documents and smart cards will be heavily affected by the cryptanalysis performed on such a future universal quantum computer. Equally, quantum computers have the potential to disruptively threaten algorithms like ECDSA (Elliptic Curve Digital Signature Algorithm) and protocols like ECDH (Elliptic Curve Diffie-Hellman).
Evidently not only electronic ID documents, but information and communication technology in general is affected. Various Internet standards like Transport Layer Security (TLS), S/MIME and PGP use cryptography based on RSA and ECC to protect data communications between smart cards, computers, servers, and industrial control systems. Online banking on “https” sites and “instant messaging” encryption on mobile phones are well-known examples.
While the development of quantum computers is on the rise, there are still a couple of questions that remain unanswered such as ‘when will a universal quantum computer powerful enough to break the cryptography?’ and ’ What actual size will this quantum computer have? Will it be a small rack? Has it the size of a large building?’
Today’s quantum computers do not provide sufficient calculation power yet, but there are rapid developments and improvements ongoing. Even if the size of a large building is needed – computing time on a quantum computer can be simply rented remotely.
Post-quantum cryptography
Post-quantum cryptography (PQC) aims to repel the cryptanalysis performed on both a quantum computer and a classical computer. Post-quantum cryptography refers to the new cryptographic algorithms (usually public-key algorithms) that have the potential to offer efficient protection against attacks using a quantum or conventional computer. PQC schemes are executed on conventional computers and security controllers and do not need a quantum computer to work1 [1]
From the user’s point of view, they behave in a similar way to currently available ciphers (e.g. RSA or ECC). This makes PQC an ideal drop-in replacement offering added robustness against quantum attacks. To afford protection against attacks that currently threaten RSA and ECC, PQC schemes rely on new and fundamentally different mathematical foundations. This leads to new challenges when implementing PQC on small chips with limited storage space.
In 2017, the US National Institute of Standards and Technology (NIST) started its post-quantum crypto project and asked for submissions of post-quantum key exchange, public-key encryption, and signature schemes to a competition-like standardization effort. It is expected that NIST will standardize PQC algorithms in 2024 and that several algorithms will be introduced.
Standardization and adoption is needed
The selection and standardization of the first post quantum algorithms will be just the starting point. Besides NIST, other standardization bodies like, for example, the European Telecommunications Standards Institute (ETSI) and the International Organization for Standardization (ISO) are also focusing on PQC and are now running study groups. In addition, the standardization work needs to continue finally integrating PQC into all relevant Government ID standards.
Ultimately, the adoption of infrastructure is required. Communication protocols need to be adapted and standardized. Documents, infrastructure including the background systems need to be upgraded.
Long transition periods are expected, moving from using conventional cryptographic protocols to the use of “hybrid” protocols combining conventional cryptography and PQC to an ultimate migration to “PQC-only” protocols.
Approaches towards post-quantum cryptography
There are several approaches towards a quantum computer world. The most obvious option – at least in the short-term – might be ignoring or to start using PQC only once the universal quantum computer is available. However, at a certain point of time in the future, already issued documents might be compromised – as they might be in the field for an additional ten years. Worst case, these issued documents need to be withdrawn and exchanged – a procedure generating significant challenges and costs.
So simply ignoring the quantum computer threat is probably not a valid option.
Of course, the validity period reduction of electronic ID-documents might be a suitable way to go. It is therefore often discussed to mitigate the potential threat by quantum computers. The shorter the document lifetime, the better the risk position and the less likely a document exchange will be needed at a later stage. For certain use cases, the documents are valid for only a manageable period, i.e. classical payment cards, which are mostly valid for three years only. However, dealing with the extended identity document lifetime of ten years or even more, things become disproportionately complex.
Moreover, reducing the validity period of a governmental document is difficult to be implemented. For some use cases (i.e. signature cards / tokens), it might be easy. For other governmental documents it´s probably not a realistic option.
In the preparation for a migration towards post-quantum cryptography, mitigation needs to be done with a variety of smaller actions – and early preparation is key, as the final implementation will take several years.
Migration strategies towards post-quantum cryptography
Neither the standardization of the PQC-algorithms nor the standardization of the additional required ID protocols is finished yet, and the finalization will still take some time.
Currently, a possible migration strategy towards PQC is crypto agility. The transition from today’s conventional algorithms to PQC will be gradual. The speed of migration depends not only on the availability of quantum computers, but also on the extent to which security is critical for the applications in question, the lifetime of devices in the field, and many other factors. Additionally, the set of PQC algorithms will change over time, reflecting the latest research insights. How can device vendors navigate all of these uncertainties?
The path to success lies in crypto agility; in other words, enable that devices can evolve to support different crypto algorithms. Looking ahead, adaptability in this dynamic space hinges on the ability to add and exchange crypto algorithms and the corresponding protocols.
However, crypto agility needs to be backed by high-performing hardware. Post-quantum cryptography requires significantly more computational power in a security controller. The prevailing majority of today’s security controllers is not able to run PQC-algorithms in a “sufficiently fast” transaction speed. While using an ID card for border crossing, a citizen will not tolerate an additional time penalty of 30 or even 60 seconds just because PQC is executed. Prior relying on crypto-agility and field upgrade mechanisms, the underlying solution (chip hardware, Operating system, applets…) needs to be well chosen. Appropriate hardware resources help to maintain adequate transaction performance.
There is also a second challenge: post-quantum cryptography does not only need to be quantum-secured and resistant against attacks with classical computers, but the implementation itself needs to be secured against the classical manipulating, observing and semi-invasive attacks. It is expected, that both secured implementations and certification of PQC-implementations will require learning cycles. Appropriate Hardware resources can support secured implementations.
A good way to start learning is working on demonstrators and preparing to timely start with first – although limited – field trials. First pilot projects for national eID cards are expected to start soon after 2025. A wide scale rollout of quantum-safe documents is expected to start before the end of this decade.
Recommendation: Early preparation is key
Although the first standardized algorithms are expected in 2024, continued by and more standardization afterwards – the rapid development of quantum computing signals the inevitability of this trend and the importance of early preparation. Knowledge and expertise will be essential to put appropriate and commercially feasible solutions in place in timely manner. Any future migration to new products and technologies, whether it´s cryptography or new products, or whatever, is always need considerable time and effort.
Government should begin by
- Learning and collecting the information,
- Making an inventory of which physical equipment and software will need to be upgraded,
- Preparing for the migration in (governmental) projects and start making strategic game plans (How to migrate infrastructure, how to upgrade documents)
- Making plans for first pilot projects (when to start, etc),
- Making infrastructure upgrade plans,
- Analysing the conditions in a project (which PKI is used, how the personalization is done, which cryptographic protocols are used and how, etc).
Moving to post-quantum cryptography affects the whole lifecycle of a document – industrialization, personalization, issuance, operational usage and field updates.
Summary
There are rapid developments in the field of quantum computers. The conventional cryptography deployed in current electronic ID documents and smart cards will be affected by the cryptanalysis performed on a future universal quantum computer. Post-quantum cryptography is intended to repel this cryptanalysis, but standardization and market introduction will take many years. Documents, infrastructure including background systems need to be upgraded, but long transition periods expected. Start the preparation right now!
[1] “post-quantum cryptography” should not be mixed up with “quantum cryptography” – a new kind of cryptography intended to be processed on a quantum computer.[1]
Leave a Reply