Post-Quantum Security: Origin, Fundamentals, and Adoption

• URL: http://arxiv.org/abs/2405.11885v2
• Date: Mon, 28 Oct 2024 09:30:12 GMT
• Title: Post-Quantum Security: Origin, Fundamentals, and Adoption
• Authors: Johanna Barzen, Frank Leymann,
• Abstract summary: We first describe the relation between discrete logarithms and two well-known asymmetric security schemes, RSA and Elliptic Curve Cryptography. Next, we present the foundations of lattice-based cryptography which is the bases of schemes that are considered to be safe against attacks by quantum algorithms. Finally, we describe two such quantum-safe algorithms (Kyber and Dilithium) in more detail.
• Score: 0.29465623430708915
• License:
• Abstract: Nowadays, predominant asymmetric cryptographic schemes are considered to be secure because discrete logarithms are believed to be hard to be computed. The algorithm of Shor can effectively compute discrete logarithms, i.e. it can brake such asymmetric schemes. But the algorithm of Shor is a quantum algorithm and at the time this algorithm has been invented, quantum computers that may successfully execute this algorithm seemed to be far out in the future. The latter has changed: quantum computers that are powerful enough are likely to be available in a couple of years. In this article, we first describe the relation between discrete logarithms and two well-known asymmetric security schemes, RSA and Elliptic Curve Cryptography. Next, we present the foundations of lattice-based cryptography which is the bases of schemes that are considered to be safe against attacks by quantum algorithms (as well as by classical algorithms). Then we describe two such quantum-safe algorithms (Kyber and Dilithium) in more detail. Finally, we give a very brief and selective overview of a few actions currently taken by governments and industry as well as standardization in this area. The article especially strives towards being self-contained: the required mathematical foundations to understand post-quantum cryptography are provided and examples are given.

Related papers

• Revocable Encryption, Programs, and More: The Case of Multi-Copy Security [48.53070281993869]
  We show the feasibility of revocable primitives, such as revocable encryption and revocable programs. This suggests that the stronger notion of multi-copy security is within reach in unclonable cryptography.
  arXiv  Detail & Related papers  (2024-10-17T02:37:40Z)
• Quantum Truncated Differential and Boomerang Attack [10.853582091917236]
  In this article, we concentrate on truncated differential and boomerang cryptanalysis. We first present a quantum algorithm which is designed for finding truncated differentials of symmetric ciphers. We prove that, with a overwhelming probability, the truncated differentials output by our algorithm must have high differential probability for the vast majority of keys in key space.
  arXiv  Detail & Related papers  (2024-07-21T11:34:29Z)
• The Algorithm for Solving Quantum Linear Systems of Equations With Coherent Superposition and Its Extended Applications [8.8400072344375]
  We propose two quantum algorithms for solving quantum linear systems of equations with coherent superposition. The two quantum algorithms can both compute the rank and general solution by one measurement. Our analysis indicates that the proposed algorithms are mainly suitable for conducting attacks against lightweight symmetric ciphers.
  arXiv  Detail & Related papers  (2024-05-11T03:03:14Z)
• Lightweight Public Key Encryption in Post-Quantum Computing Era [0.0]
  Confidentiality in our digital world is based on the security of cryptographic algorithms. In the course of technological progress with quantum computers, the protective function of common encryption algorithms is threatened. Our concept describes the transformation of a classical asymmetric encryption method to a modern complexity class.
  arXiv  Detail & Related papers  (2023-11-24T21:06:42Z)
• Generalized quantum Arimoto-Blahut algorithm and its application to quantum information bottleneck [55.22418739014892]
  We generalize the quantum Arimoto-Blahut algorithm by Ramakrishnan et al. We apply our algorithm to the quantum information bottleneck with three quantum systems. Our numerical analysis shows that our algorithm is better than their algorithm.
  arXiv  Detail & Related papers  (2023-11-19T00:06:11Z)
• Homomorphic Encryption of the k=2 Bernstein-Vazirani Algorithm [0.4511923587827301]
  We find an application of this scheme to quantum homomorphic encryption (QHE) which is an important cryptographic technology useful for delegated quantum computation. We develop QHE schemes with perfect security, $mathcalF$-homomorphism, no interaction between server and client, and quasi-compactness bounded by $O(M)$ where M is the number of gates $T$ in the circuit.
  arXiv  Detail & Related papers  (2023-03-30T14:49:15Z)
• Revocable Cryptography from Learning with Errors [61.470151825577034]
  We build on the no-cloning principle of quantum mechanics and design cryptographic schemes with key-revocation capabilities. We consider schemes where secret keys are represented as quantum states with the guarantee that, once the secret key is successfully revoked from a user, they no longer have the ability to perform the same functionality as before.
  arXiv  Detail & Related papers  (2023-02-28T18:58:11Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Benchmarking Small-Scale Quantum Devices on Computing Graph Edit Distance [52.77024349608834]
  Graph Edit Distance (GED) measures the degree of (dis)similarity between two graphs in terms of the operations needed to make them identical. In this paper we present a comparative study of two quantum approaches to computing GED.
  arXiv  Detail & Related papers  (2021-11-19T12:35:26Z)
• Synthesis of Quantum Circuits with an Island Genetic Algorithm [44.99833362998488]
  Given a unitary matrix that performs certain operation, obtaining the equivalent quantum circuit is a non-trivial task. Three problems are explored: the coin for the quantum walker, the Toffoli gate and the Fredkin gate. The algorithm proposed proved to be efficient in decomposition of quantum circuits, and as a generic approach, it is limited only by the available computational power.
  arXiv  Detail & Related papers  (2021-06-06T13:15:25Z)
• Lattice sieving via quantum random walks [0.0]
  lattice-based cryptography is one of the leading proposals for post-quantum cryptography. Shortest Vector Problem (SVP) is arguably the most important problem for the cryptanalysis of lattice-based cryptography. We present an algorithm that has a (heuristic) running time of $20.2570 d + o(d)$ where $d$ is the lattice dimension.
  arXiv  Detail & Related papers  (2021-05-12T11:59:30Z)

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.