Prepare for the Quantum Breakthrough with Post-Quantum Cryptography

The prospect of quantum computers triggers a fundamental shift in computing and security principles. NXP security engineers and cryptographers are contributing to the NIST PQC standardization effort for the post-quantum cryptography transition as well as helping ensure that upcoming PQC standards take into account core requirements of embedded security.

The Quantum Threat, Qubit by Qubit

A quantum computer has little in common with everyday smart phones and laptops. It is a “computer” in the sense that, upon a given input, it delivers an output. However, the similarities stop there. As opposed to classical computers built as digital circuits, quantum computers make use of quantum-mechanical properties such as superposition and entanglement to manipulate quantum bits (so-called “qubits”) by quantum gates. A general-purpose quantum computer is able to perform complex calculations infeasible with today’s classical computers. A quantum computer can lead to breakthroughs by solving what’s unsolvable today. And the potential applications are far-reaching across highly complex GPS, metrology, pharmaceutical research, artificial intelligence, and many other applications.

Qubit by qubit, there has been a slow but steady progress — from the first experimental demonstration of a quantum algorithm working on 2 qubits  in 1998, through 12 qubits  in 2006, to Google’s 72-qubit  quantum chip in 2018, leading to IBM’s 127-qubit   quantum processor in 2021 — gaining computational power at an exponential rate.

One important milestone in quantum computing is so-called quantum supremacy: solving a problem that no classical computer can feasibly solve. Google claimed  to have achieved this in October 2019 by performing a series of operations in 200 seconds that would take a supercomputer about 10,000 years to complete on an array of 54 qubits. This claim was not without controversy; IBM suggested  that the computation on a classical computer could be done in 2.5 days instead. Nevertheless, current estimates  indicate that we will see quantum computations capable of solving real-world cryptographic problems in 10 to 15 years from now.

One cannot overestimate the threat potential of quantum computing to society at large to secure the Internet, devices and legal infrastructure based on the currently used cryptographic systems. As far back as 1994, Peter Shor published  a quantum algorithm that would undermine the security of the majority of public-key cryptographic systems used today (i.e., RSA  and elliptic-curve cryptography ), while a quantum algorithm  by Lov Grover in 1996 has significant effect on the security symmetric ciphers and hash functions (e.g., AES256   and SHA-3  ).

Systems and solutions that could reasonably be regarded as secure today may be weakened or fully broken by the rise of large powerful quantum computers. This means that the currently used cryptographic keys or data encrypted today might be compromised whenever quantum computers become reality. Even if the threat of a quantum might still seem far away, it is important to start acting now to guarantee security in the future.

Post-Quantum Cryptography: Algorithms and Standards

Cryptography provides the building blocks to security. With the increase of quantum computing capabilities, one should expect a quantum leap in progress to break current public-key cryptography within the coming decades. This prospect has led to widespread initiatives to develop new cryptographic algorithms, standards and migration paths to secure against the emerging threat quantum computing presents. These initiatives are often executed as collaborations between industry, academia and government entities such as the USA’s National Institute of Standards and Technology  (NIST) and the German Federal Office for Information Security (BSI).

There are essentially two flavors of cryptographic mitigation approaches under investigation. The term “quantum cryptography” is often used to refer to the implementation of cryptographic protocols based on quantum-mechanical principles, and it is not necessarily referencing the use of a quantum computer. The best-known example is a technique called quantum key distribution (QKD), in which a provably secure link between two parties is established by an exchange of polarized quantum particles such as photons over a fiber optic link. This method has been used in applications since as early as 2007, when it was used to establish secure links carrying voting results in the Swiss national election.

The second mitigation option is the collection of new cryptographic algorithms, standards and migration paths that can be used for classical computing hardware — collectively referred to as “post-quantum cryptography” (PQC) or quantum-safe cryptography — to secure against the emerging threat quantum computing presents. As opposed to QKD, it does not rely on quantum-mechanical principles and can be deployed on devices we already use today. Many of the commonly used symmetric-key primitives (e.g., AES256   and SHA-3 ) are considered post-quantum secure after appropriate increase of the key or digest size, while popular public-key algorithms (e.g., RSA and ECC) will need to be replaced altogether. The search for replacement public-key post-quantum cryptographic standards was started in a competition format by NIST in 2016  with its first winners being announced in late March 2022.

Migration to post-quantum public-key cryptographic primitives will be a practical challenge. NXP is addressing issues around the larger key sizes, key serialization re-using existing hardware, improving performance  and finding better security defenses. Keep in mind that all past cryptographic transitions took significant amounts of time and effort — even for much simpler replacements. Preparing this transition now, as part of a larger crypto agility effort, will smooth the transition when the new PQC standard is announced.

At NXP, We Believe the Best Way to Predict the Future Is to Create It

NXP security engineers and cryptographers are contributing to the NIST PQC standardization effort for the PQC transition and help ensure that upcoming PQC standards take into account core requirements of embedded security such as physical secure implementations and resource limitations. NXP strives to ensure its products offer the long-term security protection. We are following premise that the best way to predict the future is to create it. A more detailed view of NXP on the emergence of post-quantum cryptography is published in our whitepaper and webinar. Follow NXP in the next weeks and months ahead for regular updates on the recent and ongoing work done by the PQC team at NXP.

Authors

Joppe W. Bos

Joppe W. Bos is a senior principal cryptographer at the Competence Center Crypto & Security (CCC&S) in the CTO organization at NXP Semiconductors. Based in Belgium, he is the technical lead of the Post-Quantum Cryptography team, and has authored over 20 patents and 50 academic papers. He also serves as the Secretary of the International Association for Cryptologic Research (IACR) and the co-editor of the IACR Cryptology ePrint Archive.

Christine Cloostermans

Christine Cloostermans is a senior cryptographer at Competence Center for Cryptography and Security (CCC&S) in the CTO organization at NXP Semiconductors. She acquired her doctorate from TU Eindhoven on topics related to lattice-based cryptography. Christine is a co-author on 10+ scientific publications, and has given many public presentations in the area of post-quantum cryptography. Beyond PQC, she is active in multiple standardization efforts, including IEC 62443 for the Industrial domain, ISO 18013 for the mobile driver’s license, and the Access Control Working Group of the Connectivity Standards Alliance.

Joost Renes

Joost Renes is a Senior Cryptographer at the Competence Center for Cryptography and Security (CCC&S) in the CTO organization at NXP Semiconductors. He holds a PhD in Cryptography from Radboud University in the Netherlands and is a developer of the NIST standardization proposal SIKE. He works towards solving the many challenges related to securely implementing post-quantum cryptography on resource-constrained systems, and integrating them into security-critical protocols.

Tobias Schneider

Tobias Schneider is a senior cryptographer at the NXP Competence Center for Cryptography and Security (CCC&S) in the CTO organization at NXP Semiconductors. He is also a member of the Post-Quantum Cryptography team. He received his PhD in cryptography from Ruhr-Universität Bochum in 2017 and authored over 25 international publications. His research topics include the physical security of cryptographic implementations, in particular of post-quantum cryptography, and cyber resilience.