Shor’S Algorithm And The Viability Of Common Public-Key Cryptosystems
Overview of Shor’s Quantum Factoring Algorithm
Shor’s algorithm for quantum computing provides an exponential speedup for integer factorization compared to the best known classical algorithms. Developed by mathematician Peter Shor in 1994, this quantum algorithm leverages the unique capabilities of quantum physics to quickly find the prime factors of large integers. The integer factorization problem, determining the prime factors p and q of an integer N=pq, underlies the security of widely used public key cryptosystems like RSA.
Shor’s insight was that the problem of finding periods in a quantum superposition of numbers could be connected to factoring. By querying a quantum system in superposition across many numbers, the period can sometimes be found in just one query. This exponentially speeds up certain number theoretic problems. Once the period is found, some classical post-processing can efficiently recover the factors p and q. The exponential speedup comes from using quantum parallelism across the superposition instead of checking numbers sequentially.
Implications for RSA and Common Public-Key Systems
The RSA cryptosystem relies on the difficulty of factoring large numbers that are the product of two large primes. If quantum computers can efficiently find the prime factors, they can break RSA encryption. Though RSA could still be used for shorter term security, many public key systems would become highly insecure if large-scale fault-tolerant quantum computers are ever developed.
Other public key cryptosystems like the Diffie-Hellman key exchange and elliptic curve cryptography (ECC) could also be weakened by Shor’s algorithm. Discrete log cryptosystems rely on similar mathematical assumptions to RSA, though progress on quantum attacks against ECC is currently less advanced compared to Shor’s algorithm for RSA.
While the threat is currently theoretical since the required quantum computing hardware does not yet exist, many experts believe Shor’s algorithm poses substantial risk to most widely deployed public key systems. Cryptographers have been working on “post-quantum” algorithms that could remain secure, though global infrastructure changes would be required to avoid mass vulnerabilities.
Mathematical Basis Behind Shor’s Algorithm
At a high level, Shor’s quantum factoring algorithm works by using the quantum Fourier transform to take advantage of quantum parallelism. It connects finding periods in the modular exponential function to the order of the multiplicative group modulo N. This allows efficient determination of factors like p and q. Mathematically, it relies on relationships between:
- The period finding problem for modular exponential function f(x)=ax (mod N)
- Order finding for group ZN*
- Factors of N
More specifically, given a composite integer N to be factored:
- Randomly select an integer a < N
- Use quantum Fourier sampling to find period r of function f(x)=ax (mod N)
- Apply continued fractions algorithm to find factors p and q from period
The quantum Fourier transform allows testing multiple x values simultaneously in superposition. This lets Shor’s algorithm exploit quantum parallelism for an exponential speedup compared to testing values sequentially. It demonstrates the potential for quantum algorithms to fundamentally break existing cryptographic assumptions.
Code Example Implementing Shor’s Algorithm in Q#
As a demonstration, here is code for a simplified implementation of Shor’s algorithm in Q#, Microsoft’s quantum programming language:
operation ShorFactor (N : Int) : Int[] {
using (register = Qubit[50]) {
// Put register in uniform superposition
ApplyToEach(H, register);
// Modular exponentiate by x on each basis state
for (idxElement in IndexRange(register.Length)) {
ModularExponentiate(a, idxElement, N, register);
}
// Apply QFT to extract period
let period = ApplyQuantumFourierTransform(register);
// Apply continued fractions algorithm
let factors = ClassicallyFactor(N, period);
ResetAll(register);
return factors;
}
}
While simplified, this demonstrates key steps like initializing a superposition, querying the modular exponential function across values of x, applying the quantum Fourier transform, and finally using classical post-processing to find factors p and q given the period r.
Recommendations for Post-Quantum Cryptographic Alternatives
Since Shor’s algorithm can efficiently break popular public key systems like RSA and ECC, researchers have been developing alternative “post-quantum” algorithms designed to be secure against both quantum and classical attacks.
Leading post-quantum candidates include:
- Lattice-based cryptography
- Hash-based signatures
- Multivariate polynomial cryptography
- Code-based cryptography
Each approach has tradeoffs and some have shorter keys sizes than RSA or traditional Discrete Log systems for equivalent classical security levels. Migration to post-quantum systems will require significant updates across security infrastructure from TLS certificates to identity systems and VPNs if fault-tolerant quantum computing becomes viable.
When Will Quantum Computers Become Practical?
There is vigorous disagreement about the timeline for quantum computers reaching the scale and error thresholds required to break meaningful cryptographic parameters.
On the optimistic side, some teams believe practical cryptographic breaking machines could exist within 10 years. More conservative estimates place broad cryptographic risks closer to 2030-2040 due to the difficulty in building reliable million+ qubit machines.
The field faces stiff engineering challenges including error correction, interconnect bottlenecks, calibration, and decoherence management for large qubit arrays. However, there have been rapid gains reported, even from advanced classical computing teams like IBM now competing alongside Google, IonQ, Rigetti, Oxford Quantum Circuits and others.
It remains deeply unclear when quantum computing will transition from narrow demonstrations to practical number theoretic applications like running Shor’s algorithm. This poses risks for estimating security lifetimes and upgrade cycles as the field is changing rapidly.
The Outlook for RSA and ECC Given Quantum Progress
The viability of standards like RSA and ECC in a post-quantum world remains connected to the pace of progress in quantum computing engineering.
If slow but steady advancement continues, we may be facing a 2030-2040 timeline before extensive cryptographic risk materializes allowing years still for migration. However if unreliable but rapidly advancing early fault-tolerant systems appear, risks could emerge faster than expected.
These questions remain tied to challenging engineering problems separate from the mathematical guarantees of quantum algorithms like Shor’s. The impressive theory must still be implemented in reliable hardware, which offers some natural protection for existing systems. However, the risks are substantial enough to begin planning encryption and infrastructure upgrades. With so much still unknown about the engineering development path, cryptographers are faced with deep timeline uncertainties.
