As technology progresses, the rise of quantum computing brings both exciting opportunities and serious challenges, particularly in the field of cybersecurity. Quantum computers have the potential to break widely used encryption methods, threatening the security of the digital systems that keep our world connected. In response, Post-Quantum Cryptography (PQC) is emerging as the solution to future-proof data security, specifically designed to resist attacks from both classical and quantum computers.
However, integrating PQC into embedded systems presents unique challenges due to their limited resources. In this post, we’ll explore why PQC is essential, the current standards, the general hurdles of adopting these technologies, and the specific challenges developers face when working with embedded devices.
Before we delve into the topic of post-quantum cryptography, it is helpful to understand the fundamentals of (classical) cryptography. First, crypthography is a process for encrypting and decrypting data and follows the four main principles:
Confidentiality: sensitive data should not be passed on to unintended recipients
Authenticity: the source of the data should be verified
Data integrity: data should not have been altered by an untrustworthy party
Non-repudiation: it should be prevented that the sender and recipient can deny their involvement in certain messages
In cryptography, individual building blocks are referred to as cryptographic primitives (low-level algorithms) that can be combined to form more complex cryptographic protocols. Examples of primitives are RSA and AES, while examples of protocols are TLS (Transport Layer Security) and SSH (Secure Shell).
Cryptographic algorithms have formed the backbone of secure communication for decades and were developed for two main functions:
General encryption, which protects data such as passwords that are transmitted over public networks
Digital signatures, which are used to verify identity
The most well-known cryptographic functions are encryption schemes. They protect the confidentiality of data and prevent it from being intercepted by unauthorized persons. To encrypt data, an encryption key is used that can only be decrypted with the correct key.
Another widely used cryptographic function is the signature method, which aims to ensure the authenticity and integrity of data. The data is signed with a key, which in turn can be verified with a verification key.
To function securely, cryptographic functions need secure keys, which are generated either symmetrically or asymmetrically.
In symmetric cryptography, encryption and decryption or signing and verification are done with the same key, which the parties must agree on in advance. This leads to a problem known as the key distribution problem, which describes that the key could be stolen or copied while in transit.
In asymmetric cryptography, two different keys are used, a public and a private one. One party generates a key pair and publicly announces the public key so that anyone can encrypt data or verify signatures. However, only the owner of the private key can decrypt or create signatures.
Symmetric key functions are usually more efficient than asymmetric key functions, so the less efficient asymmetric primitives are usually used to create a symmetric key. This solves the key distribution problem.
The asymmetric primitives used to create a shared symmetric key between two parties are called Key Exchange (KE) algorithms or Key Encapsulation Mechanisms (KEMs). To protect the communication channel, more efficient symmetric primitives such as AES can be used.
In addition, hash functions convert a message into a hash value, so it is easy to check whether a particular hash value matches a particular message. Reversing the hash value to its origin or finding two different messages with the same hash value is difficult. Hash functions do not necessarily require a cryptographic key, but if they do, they use a symmetric key. Therefore, they are often grouped with symmetric key primitives.
Finally, message authentication codes (MACs) ensure authenticity and integrity by marking a message so that the recipient can verify that it was sent by the intended party and has not been altered during transmission. MACs are usually constructed from hash functions or block ciphers.
Classical cryptographic systems work by choosing two large prime numbers - numbers that are only divisible by 1 and themselves - and multiplying them together to obtain an even larger number. While multiplying these primes is quick and easy, the real difficulty lies in reversing the process to find the original primes. A conventional computer would have to perform this task in order to decode the information. The two prime numbers involved in this process are called “prime factors”. For sufficiently large numbers, conventional computers would take an impractically long time - possibly billions of years - to figure out these prime factors. With powerful quantum computers, however, this challenge could be completely circumvented. They could examine all potential prime factors in parallel, speeding up the process dramatically. Such a powerful quantum computer is often referred to as a “cryptographically relevant” quantum computer. Instead of taking billions of years, it could crack encryption in a matter of days or even hours, putting sensitive information such as government secrets and personal financial data at risk.
This poses a significant risk, not only to data currently encrypted but also to data that has been encrypted today and stored for future use - a concept known as the "store now, decrypt later" threat. This quantum vulnerability is particularly concerning because the data encrypted today could still be in storage years from now, and the advent of a practical quantum computer could render that data accessible to malicious actors. The problem is not just theoretical: several advancements in quantum computing show that we are nearing the point where these systems will be capable of breaking modern encryption. This is where Post-Quantum Cryptography (PQC) becomes critical. Post-Quantum Cryptography is designed to offer security against both classical and quantum computing threats. These algorithms are based on mathematical structures that are significantly more difficult for quantum computers to break. By adopting PQC, industries and organizations can future-proof their security systems against the looming quantum threat.
To prepare for the quantum future, the National Institute of Standards and Technology (NIST) launched a multi-phase initiative to standardize Post-Quantum Cryptography algorithms. In 2022, after rigorous evaluation, NIST officially selected a set of PQC algorithms that offer the best security and performance characteristics for a variety of applications.
Published NIST-Standards
Among these selected algorithms, two major categories stand out:
Module-Lattice-Based Key-Encapsulation Mechanism (ML-KEM), formerly known as Chrystals-Kyber: An algorithm that allows two parties, under certain conditions, to securely establish a shared secret key over a public channel. Once the shared secret key has been securely generated by a KEM, it can be used with symmetric cryptography to perform essential tasks in secure communication, such as encryption and authentication. ML-KEM is considered secure, even against attackers with access to a quantum computer.
Module-Lattice-Based Digital Signature Algorithm (ML-DSA) formerly known as Crystals-Dilithium: Also a lattice-based algorithm, it is designed to protect digital signatures. ML-DSA is an algorithm for generating and verifying digital signatures. It is considered secure, even against attackers with access to advanced quantum computers.
These algorithms were selected after years of testing and research, which involved hundreds of proposals and extensive analysis to ensure that they could withstand potential quantum computing threats. With NIST’s official adoption of these standards, industries can now begin to integrate quantum-resistant cryptography into their systems. In addition to these standards, other algorithms, such as the hash-based signature schemes and hybrid models, continue to undergo evaluation for broader adoption. As quantum-safe cryptography continues to evolve, more solutions will be available to meet the needs of diverse industries.
Embedded systems face unique challenges as the devices are often constrained by hardware, power, and memory limitations. These systems play a crucial role in secure communications and data protection. However, integrating PQC into these resource-limited environments presents substantial hurdles. The need to migrate to PQC is urgent, but embedded systems developers must carefully address the specific challenges posed by hardware and memory constraints, and the lack of hardware acceleration for PQC algorithms.
Embedded systems are designed with specific constraints that differentiate them from traditional computing environments. They are optimized for low power consumption, compact size, and cost-effectiveness, but these very attributes make them less suited to handle the computational demands of modern cryptography, especially post-quantum cryptography. One of the key challenges of migrating embedded systems to support PQC is the significant increase in hardware requirements needed to support quantum-resistant algorithms.
Embedded microcontrollers in the lower performance class present particular challenges. Devices with 32-bit ARM or RISC-V processors or even more limited devices such as 16-bit processors or even 8-bit microcontrollers are still popular and used. Such devices present the following challenges:
available clock speed
available RAM & ROM/flash memory
These devices usually operate in the low megahertz range. There are models with speeds as low as 8-24 MHz, while some models can reach up to 100-300 MHz. Devices in the lower performance class often work with lower clock frequencies in the low double-digit range.
This means that KEM calculations, for example, must be optimized to fit within the limited clock speed, while these devices often lack crypto accelerators, the hardware needed for faster calculations, resulting in lower performance.
A bigger challenge for embedded devices, however, is that post-quantum cryptography in some cases requires more memory by comparison. Unlike standard computers, which can typically allocate more memory as needed, constrained devices have a fixed and limited memory capacity. Typically, devices only have 64 to 128 KB of RAM.
These limitations highlight the challenges of integrating post-quantum cryptography (PQC) into embedded devices. To solve these problems, developers need to focus on optimizing algorithms for low memory and low power environments, explore hybrid cryptography solutions and consider future hardware accelerators for PQC.
Hybrid solutions would allow embedded systems to continue using traditional RSA or ECC for operations like digital signatures while introducing PQC for improving key exchange and data protection. This way, systems can gradually transition to quantum-safe cryptography without overwhelming the hardware. However, using hybrid cryptography adds additional complexity, as devices must be able to manage and process both traditional and quantum-safe cryptographic algorithms simultaneously.
Hardware acceleration is a fundamental feature in many modern cryptographic systems, enabling faster processing and more efficient execution of cryptographic algorithms. Traditional cryptographic algorithms like RSA and ECC have long benefited from hardware acceleration, as these algorithms are highly parallelizable and can be optimized to run on specialized hardware. For example, many embedded systems use hardware accelerators to speed up RSA key generation, ECC point multiplication, and symmetric encryption tasks.
However, PQC algorithms, especially those based on lattice-based cryptography, present unique challenges for hardware acceleration. These algorithms involve complex mathematical operations, such as polynomial multiplications and error correction techniques. While some components (e.g., polynomial multiplication via Number Theoretic Transforms) can be parallelized efficiently, traditional cryptographic hardware accelerators designed for RSA or ECC are not directly applicable to PQC without significant modifications.
Lattice-based cryptography, which underpins many PQC algorithms like Kyber and NTRU, relies on structured polynomial and modular arithmetic involving multi-dimensional vectors and matrices. These operations differ significantly from the scalar arithmetic typically used in traditional cryptography. As a result, embedded systems with existing cryptographic hardware accelerators designed for RSA or ECC do not natively support PQC and require significant modifications to achieve efficient acceleration.
The lack of hardware acceleration for PQC in embedded systems results in longer processing times and higher power consumption for cryptographic operations. For embedded devices that must operate under stringent power constraints, such as battery-powered IoT devices or remote sensors, this increase in power consumption can lead to reduced battery life and overall system inefficiency. Furthermore, without hardware acceleration, the computational load of PQC algorithms could result in increased latencies, making the system unfit for fast operations.
Cryptographic hardware that accelerates hash computations such as SHA-3 can be re-used for schemes like ML-DSA, ML-KEM and SLH-DSA. ML-DSA and ML-KEM benefit from additional, dedicated acceleration. However, the ideal situation is to deploy dedicated PQC hardware co-processors whenever feasible.
The migration to Post-Quantum Cryptography (PQC) for embedded systems presents unique and substantial challenges. Memory limitations and processing power constraints are major obstacles, as PQC algorithms are significantly more demanding than traditional cryptographic algorithms. Furthermore, the lack of hardware acceleration for PQC operations makes it more difficult to implement these algorithms efficiently in embedded environments, where real-time performance and low power consumption are critical.
Despite these challenges, the transition to PQC is necessary to ensure the long-term security of embedded systems against quantum threats. Developers can address these challenges by optimizing PQC algorithms for low-resource environments, using hybrid cryptographic solutions, and exploring new hardware accelerators designed specifically for PQC. As the field of PQC evolves, embedded systems will become increasingly capable of supporting quantum-safe cryptography without compromising performance or security.
By taking a proactive approach to PQC migration, embedded system developers can ensure that their systems remain secure and resilient in the face of emerging quantum computing threats, helping to future-proof the devices that are critical to our digital infrastructure.