A Comprehensive Review of Post-Quantum Cryptography Algorithms

Abstract

The development of quantum computing has been rapid, and an existential threat to computational hardness assumptions that underlie today's public-key cryptography has been encountered. This manuscript is a complete and thoroughly organized review of Post-Quantum Cryptography (PQC), discussing the mathematical concepts, complexity, and mechanisms of the algorithms that underpin quantum-safe security infrastructures. Rather than the principles of quantum mechanics, the analysis mathematically defines the basic principles of qubits, superposition, and entanglement, and clarifies common misunderstandings of the theory of parallelism in quantum mechanics. The research places cryptographic problems into the Bounded-Error Quantum Polynomial-Time (BQP) complexity class, thus highlighting the exact defects of classical algorithms. The quantum gate complexity of Shor's algorithm is compared to classical bounds as in Pollard's rho algorithm for the Elliptic Curve Discrete Logarithm Problem (ECDLP), for a detailed comparative cryptanalysis. The comparison highlights a very important “quantum security inversion” in that Elliptic Curve Cryptography (ECC) is much more susceptible to the early-stage fault-tolerant quantum computer as compared to the approach used today in RSA. It unfolds the architectural dependency of quantum algorithms, one by one, from the Quantum Fourier Transform (QFT) to Quantum Phase Estimation (QPE) and Shor's algorithm to Grover's algorithm. Last but not least, the manuscript examines emerging attack primitives such as lattice-based, code-based, and hash-based cryptography, their security models, side channel vulnerabilities, and the recently finalised Federal Information Processing Standards (FIPS 205, 203, and 204) that have been published by the National Institute of Standards and Technology (NIST).