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

• URL: http://arxiv.org/abs/2504.13537v1
• Date: Fri, 18 Apr 2025 08:02:13 GMT
• Title: Complexity of Post-Quantum Cryptography in Embedded Systems and Its Optimization Strategies
• Authors: Omar Alnaseri, Yassine Himeur, Shadi Atalla, Wathiq Mansoor,
• Abstract summary: The National Institute of Standards and Technology (NIST) has initiated a standardization process for post-quantum cryptography (PQC) algorithms.<n>This paper first provides a comprehensive analysis of the hardware complexity of post-quantum cryptography (PQC) in embedded systems.<n>To address these challenges, this paper discusses optimization strategies such as pipelining, parallelization, and high-level synthesis.
• Score: 2.821324092673655
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Performance Analysis and Industry Deployment of Post-Quantum Cryptography Algorithms [0.8602553195689513]
  The National Institute of Standards and Technology (NIST) has selected CRYSTALS-Kyber and CRYSTALS-Dilithium as standardized PQC algorithms for secure key exchange and digital signatures.<n>This study conducts a comprehensive performance analysis of these algorithms by benchmarking execution times across cryptographic operations.<n>Our findings demonstrate that Kyber and Dilithium achieve efficient execution times, outperforming classical cryptographic schemes such as RSA and ECDSA at equivalent security levels.
  arXiv  Detail & Related papers  (2025-03-17T09:06:03Z)
• End-to-end compilable implementation of quantum elliptic curve logarithm in Qrisp [0.0]
  Elliptic curve cryptography (ECC) is recognized for its effectiveness and reliability across a broad range of applications.<n>We leverage the Qrisp programming language to realize one of the first fully compilable implementations of EC arithmetic.
  arXiv  Detail & Related papers  (2025-01-17T14:45:38Z)
• Performance Benchmarking of Quantum Algorithms for Hard Combinatorial Optimization Problems: A Comparative Study of non-FTQC Approaches [0.0]
  This study systematically benchmarks several non-fault-tolerant quantum computing algorithms across four distinct optimization problems. Our benchmark includes noisy intermediate-scale quantum (NISQ) algorithms, such as the variational quantum eigensolver. Our findings reveal that no single non-FTQC algorithm performs optimally across all problem types, underscoring the need for tailored algorithmic strategies.
  arXiv  Detail & Related papers  (2024-10-30T08:41:29Z)
• Solving the Independent Domination Problem by Quantum Approximate Optimization Algorithm [0.5919433278490629]
  Independent Domination Problem (IDP) has practical implications in various real-world scenarios.<n>Existing classical algorithms for IDP are plagued by high computational complexity.<n>This paper introduces a Quantum Approximate Optimization (QAOA)-based approach to address the IDP.
  arXiv  Detail & Related papers  (2024-10-22T17:49:00Z)
• Dependable Classical-Quantum Computer Systems Engineering [37.16076237842031]
  This paper aims to identify integration challenges, anticipate failures, and foster a diverse co-design for HPC-QC systems. The focus of this emerging inter-disciplinary effort is to develop engineering principles that ensure the dependability of hybrid systems.
  arXiv  Detail & Related papers  (2024-08-20T01:57:17Z)
• Post-Quantum Cryptography: Securing Digital Communication in the Quantum Era [0.0]
  Post-quantum cryptography (PQC) is a critical field aimed at developing resilient cryptographic algorithms to quantum attacks. This paper delineates the vulnerabilities of classical cryptographic systems to quantum attacks, elucidates impervious principles of quantum computing, and introduces various PQC algorithms.
  arXiv  Detail & Related papers  (2024-03-18T12:51:56Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem. The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
  arXiv  Detail & Related papers  (2023-04-18T11:57:15Z)
• Decomposition of Matrix Product States into Shallow Quantum Circuits [62.5210028594015]
  tensor network (TN) algorithms can be mapped to parametrized quantum circuits (PQCs) We propose a new protocol for approximating TN states using realistic quantum circuits. Our results reveal one particular protocol, involving sequential growth and optimization of the quantum circuit, to outperform all other methods.
  arXiv  Detail & Related papers  (2022-09-01T17:08:41Z)
• Optimizing Tensor Network Contraction Using Reinforcement Learning [86.05566365115729]
  We propose a Reinforcement Learning (RL) approach combined with Graph Neural Networks (GNN) to address the contraction ordering problem. The problem is extremely challenging due to the huge search space, the heavy-tailed reward distribution, and the challenging credit assignment. We show how a carefully implemented RL-agent that uses a GNN as the basic policy construct can address these challenges.
  arXiv  Detail & Related papers  (2022-04-18T21:45:13Z)
• Polynomial unconstrained binary optimisation inspired by optical simulation [52.11703556419582]
  We propose an algorithm inspired by optical coherent Ising machines to solve the problem of unconstrained binary optimization. We benchmark the proposed algorithm against existing PUBO algorithms, and observe its superior performance. The application of our algorithm to protein folding and quantum chemistry problems sheds light on the shortcomings of approxing the electronic structure problem by a PUBO problem.
  arXiv  Detail & Related papers  (2021-06-24T16:39:31Z)
• Detailed Account of Complexity for Implementation of Some Gate-Based Quantum Algorithms [55.41644538483948]
  In particular, some steps of the implementation, as state preparation and readout processes, can surpass the complexity aspects of the algorithm itself. We present the complexity involved in the full implementation of quantum algorithms for solving linear systems of equations and linear system of differential equations.
  arXiv  Detail & Related papers  (2021-06-23T16:33:33Z)
• A Dynamical Systems Approach for Convergence of the Bayesian EM Algorithm [59.99439951055238]
  We show how (discrete-time) Lyapunov stability theory can serve as a powerful tool to aid, or even lead, in the analysis (and potential design) of optimization algorithms that are not necessarily gradient-based. The particular ML problem that this paper focuses on is that of parameter estimation in an incomplete-data Bayesian framework via the popular optimization algorithm known as maximum a posteriori expectation-maximization (MAP-EM) We show that fast convergence (linear or quadratic) is achieved, which could have been difficult to unveil without our adopted S&C approach.
  arXiv  Detail & Related papers  (2020-06-23T01:34:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.