The threat of a large-scale quantum computer to modern encryption is not just theoretical, it is a fundamental challenge to the cryptographic primitives we rely on today, such as RSA. In my research paper, “An Undergraduate Introduction to Post-Quantum Cryptography,” I explore the mechanics of this threat and the potential solutions emerging in the scientific community.
Breaking RSA with Shor’s Algorithm
The core of the “Quantum Threat” lies in Shor’s Algorithm. While classical computers struggle with integer factorization, Shor’s algorithm reduces this to the problem of Order Finding. At its heart is the Quantum Fourier Transform (QFT), which allows a quantum computer to find the period of a function exponentially faster than any known classical method. By leveraging the Phase Estimation Algorithm, we can extract the mathematical ‘r’ needed to factor large numbers, effectively dismantling the security of RSA.
Securing the Future: QKD and BB84
The paper also delves into Quantum Key Distribution (QKD), specifically the BB84 protocol proposed by Bennet and Brassard. Unlike classical encryption, BB84 uses the laws of physics—the no-cloning theorem and the collapse of the wavefunction—to ensure that any eavesdropper (Eve) who attempts to intercept a key will inevitably introduce errors that Alice and Bob can detect.
Classical Resistance: Lattice-Based Cryptography
Finally, I examine the classical side of the solution: Post-Quantum Cryptography (PQC). Even without quantum hardware, we are developing classical algorithms that are resistant to quantum attack. Lattice-based cryptography stands out as a leading candidate, providing complex mathematical structures that remain computationally “hard” even for a quantum adversary.
The attached paper provides a more rigorous walk-through of the circuits, gates (like Hadamard and controlled-Rk), and the mathematical foundations of these protocols.