Post-Quantum Security: Origin, Fundamentals, and Adoption
arXiv:2405.11885 · doi:10.17352/tcsit.000089
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.
arXiv commentVersion 2: Reflecting progression of NIST standardization as well as governmental actions
References in corpus (8)
- Quantum Computing in the NISQ era and beyond
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Variational Quantum Algorithms
- How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
- The Bitter Truth About Quantum Algorithms in the NISQ Era
- Factoring integers with sublinear resources on a superconducting quantum processor
- A quantum circuit design of AES
- A Variational Quantum Attack for AES-like Symmetric Cryptography