Complexity of Post-Quantum Cryptography in Embedded Systems and Its Optimization Strategies

Omar Alnaseri 1 , Yassine Himeur 5 , Shadi Atalla 5 and Wathiq Mansoor 5 · 2025

Read Complexity of Post-Quantum Cryptography in Embedded Systems and Its Optimization Strategies by Omar Alnaseri 1 , Yassine Himeur 5 , Shadi Atalla 5 and Wathiq Mansoor 5 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-13537.txt.

Introduction

Omar Alnaseri, Yassine Himeur, Shadi Atalla, and Wathiq Mansoor weigh the hardware cost of quantum-proof codes on small devices, in a paper from two thousand twenty-five. Quantum growth puts classic codes at risk, and standards work has finalists in hand. Code families split by their math roots.

Each family shows its own compute, memory, and energy stamp. Speed tricks like pipelining, parallel runs, and high-level build tools are weighed. Two finalists get a step-by-step cost race for key making, locking, and unlocking. Readers picking codes for tight chips get a cost map, not just a safety badge.

Catalog record

CREATOROmar Alnaseri 1 , Yassine Himeur 5 , Shadi Atalla 5 and Wathiq Mansoor 5
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE26 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-13537

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Complexity of Post-Quantum Cryptography in Embedded Systems and Its Optimization Strategies Omar Alnaseri 1 , Yassine Himeur 5 , Shadi Atalla 5 and Wathiq Mansoor 5 Abstract With the rapid advancements in quantum computing, traditional cryptographic schemes like Rivest-Shamir-Adleman (RSA) and elliptic curve cryptography (ECC) are becoming vulnerable, necessitating the development of quantum-resistant algorithms. The National Institute of Standards and Technology (NIST) has initiated a standardization process for PQC algorithms, and several candidates, including CRYSTALS-Kyber and McEliece, have reached the final stages. This paper first provides a comprehensive analysis of the hardware complexity of post-quantum cryptography (PQC) in embedded systems, categorizing PQC algorithms into families based on their underlying mathematical problems: lattice-based, code-based, hash-based and multivariate / isogeny-based schemes. Each family presents distinct computational, memory, and energy profiles, making them suitable for different use cases. To address these challenges, this paper discusses optimization strategies such as pipelining, parallelization, and high-level synthesis (HLS), which can improve the performance and energy efficiency of PQC implementations. Finally, a detailed complexity analysis of CRYSTALS-Kyber and McEliece, comparing their key generation, encryption, and decryption processes in terms of computational complexity, has been conducted. I Introduction Post-quantum cryptography (PQC) aims to develop cryptographic algorithms that are secure against attacks from quantum computers. With rapid advancements in quantum computing, traditional cryptographic schemes such as Rivest-Shamir-Adleman (RSA) and elliptic curve cryptography (ECC) are becoming vulnerable. PQC algorithms are broadly categorized into families based on their underlying mathematical problems, each posing distinct challenges for implementation in embedded systems. These families include lattice-based, code-based, hash-based, and multivariate/isogeny-based schemes, each with unique computational, memory, and energy profiles. TABLE I : Comparison of Cryptographic Families Family Computational Complexity Memory Footprint Energy Efficiency Implementation Flexibility Lattice-Based Medium-High (NTT) Medium (1–3 kB RAM) Medium High (scalable parameters) Code-Based Low Very High ( > 1 MB) Low Low (fixed key sizes) Hash-Based Low Low ( < 2 kB RAM) Very High Medium (state management) Multivariate Very High High ( 100 kB) Very Low Low Isogeny-Based Very High Medium ( 10 kB) Very Low Low Lattice-based algorithms derive security from hard problems like the shortest vector problem (SVP) or learning with errors (LWE). Schemes such as Kyber (key encapsulation) and CRYSTALS-Dilithium (digital signatures) rely on polynomial arithmetic and the number theoretic transform (NTT) for efficient polynomial multiplication. While NTT speeds up computations, it introduces hardware overhead due to modular arithmetic and parallel operations. Ducas et al. [ 1 ] showed NTT optimizations reduce latency by up to 40% on embedded platforms. However, lattice-based algorithms still require moderate memory (1-3 kB RAM for keys) and scalable parameters, making them demanding for limited devices. Kannwischer et al. [ 2 ] demonstrated Kyber on ARM Cortex M4, using less than 10 kB RAM, although it is less energy efficient than hash-based schemes. Code-based algorithms, such as McEliece and BIKE, rely on decoding random linear codes. They are computationally lightweight, using matrix multiplications and sparse linear algebra, but suffer from large key sizes (often over 1 MB). Chou et al. [ 3 ] reduced McEliece keys by 50% on STM32 microcontrollers, but compressed keys still overload flash storage, limiting their use in memory-constrained devices. Hash-based algorithms, such as SPHINCS+ and XMSS [ 4 ] , use cryptographic hash functions (e.g. SHA-3 or SHAKE-256). They are computationally simple, relying on iterative hashing, and are lightweight and parallelizable. Bernstein et al. [ 5 ] showed SPHINCS+ runs on 8-bit AVR microcontrollers with just 2 kB RAM, making it suitable for energy-constrained IoT devices. However, stateless schemes like SPHINCS+ produce large signatures (up to 41 KB), while stateful schemes (e.g., XMSS) require nonvolatile memory (NVM) for state tracking. Bernstein et al. [ 6 ] noted that parallelizing hash chains improves throughput but increases area overhead, limiting cost-sensitive applications. Multivariate and isogeny-based algorithms are niche categories with limited embedded adoption. Multivariate schemes like Rainbow involve solving nonlinear polynomial equations, leading to computationally intensive operations and large keys (often over 100 kB). Isogeny-based schemes, such as SIKE [ 7 ] , use complex elliptic curve isogeny computations that are sequential and hard to accelerate. Koziel et al. [ 8 ] showed that SIDH FPGA implementations require significant area and power, even with optimizations. Table I compares cryptographic families in computational complexity, memory footprint, energy efficiency, and flexibility. The National Institute of Standards and Technology (NIST) has narrowed the candidates to a few finalists,including CRYSTALS-Kyber and McEliece [ 9 ] . Nonetheless, embedded systems, characterized by their limited computational power and memory, present unique challenges for PQC implementation. Achieving successful deployment of these candidates on embedded systems necessitates a comprehensive analysis of the hardware complexity associated with these PQC algorithms. Thus, this paper conducts an exhaustive examination of the hardware complexity involved in deploying PQC within such systems, with a particular emphasis on CRYSTALS-Kyber and McEliece. This paper makes several key contributions to the field of PQC in embedded systems: • Comprehensive analysis: The paper provides a detailed analysis of the hardware complexity of PQC algorithms, categorizing them into families based on their underlying mathematical problems, and discussing their computational, memory, and energy profiles. • Optimization strategies: The paper explores optimization strategies such as pipelining, parallelization, and high-level synthesis (HLS) to improve the performance and energy efficiency of PQC implementations in embedded systems. • Complexity comparison: It offers a detailed complexity analysis of two leading PQC candidates, CRYSTALS-Kyber and McEliece, comparing their key generation, encryption, and decryption processes in terms of computational complexity, memory footprint, and energy efficiency. II Optimization Strategies In this section, we propose optimization strategies that improve the performance of PQC algorithms in embedded systems by focusing on techniques that improve computational efficiency and resource management. We will explore methods such as pipelining, parallelization, and efficient use of hardware resources to maximize algorithmic throughput and reduce execution time. II-A Pipelining and Parallelization Pipelining involves breaking down a complex task into a series of smaller tasks, each performed at a different stage of a pipeline [ 10 ] . This allows for parallel processing, where multiple tasks can be executed simultaneously, reducing the overall processing time. Pipelining can be applied to various stages of the cryptographic process, such as key generation, signature generation, and signature verification [ 11 ] . For example, the CRYSTALS-Dilithium scheme uses a pipelined processing method to reduce both storage requirements and processing time [ 10 ] . Similarly, the Picnic digital signature scheme uses a pipelined approach to optimize its hardware implementation, resulting in a significant reduction in clock cycle count and energy consumption [ 11 ] . Parallelization, on the other hand, involves dividing a task into smaller subtasks that can be executed concurrently by multiple processing units [ 12 ] . This can be achieved using parallel architectures, such as multi-core processors or specialized accelerators. For instance, the RISQ-V architecture [ 12 ] integrates tightly coupled accelerators directly into the processing pipeline to speed up lattice-based cryptography. The accelerators include an arithmetic unit for vectorized modular arithmetic and NTT operations, a vectorized modular multiply accumulate unit, a Keccak accelerator for the pseudo-random bit generation, and a binomial sampling unit for the generation of binomially distributed samples. Pipelining and parallelization can be combined to further improve performance. For

Read the complete text