Is the Recent Quantum Hype by Google Willow’s Chip a Threat to RSA Algorithm?  

Recently, Google made headlines with the announcement of its new quantum chip, Willow, marking another step forward in the fascinating world of quantum computing. The technology promises to solve problems that are currently intractable for classical computers, fueling excitement—and a fair bit of concern—about its implications for cryptography, particularly the widely used RSA encryption. Cato Networks is following developments within quantum computing closely and has been informing security leaders as follows. 

Why Quantum Computers Won’t Break RSA Anytime Soon 

Quantum computers leverage principles like superposition and entanglement to perform computations that classical computers find exceedingly difficult. Shor’s algorithm, in particular, allows a quantum computer to efficiently factorize large integers, which could theoretically compromise RSA-2048 encryption. However, current quantum computers are far from capable of running Shor’s algorithm at a scale necessary to break modern RSA keys. Here’s why: 

1. Hardware Limitations:
   1. Breaking RSA-2048 would require a quantum computer with millions of error-corrected qubits. The Willow chip, like other state-of-the-art quantum devices, is still in the range of hundreds of physical qubits—and these qubits are not error-corrected.
   2. Quantum computations are incredibly sensitive to noise and decoherence, requiring significant advances in error correction before large-scale cryptographic attacks become feasible.

2. Scaling Challenges:
   1. Quantum computers need exponentially more qubits as problems scale. While progress is steady, we are likely decades away from quantum hardware capable of tackling RSA-level problems.

How Quantum Computing Challenges RSA Encryption 

Modern encryption protocols like TLS or IPsec rely on two main types of encryption/ Symmetric Encryption protects the data being transmitted using the same key for encryption and decryption. Algorithms like AES (Advanced Encryption Standard) are used for this purpose. Symmetric encryption is considered quantum-resistant because quantum algorithms like Grover’s algorithm can only halve the effective key strength. For example, AES-128 becomes equivalent to AES-64, and AES-256 remains highly secure against quantum attacks. 

Public Key Encryption secures the key exchange process, ensuring both parties share a secret key. Algorithms like RSA and ECDH (Elliptic Curve Diffie-Hellman) are widely used here. Public key encryption relies on the difficulty of certain mathematical problems, like factoring large numbers (RSA) or solving discrete logarithms (ECDH), which are computationally infeasible for classical computers. 

Shor’s algorithm, developed by Peter Shor in 1994, represents a groundbreaking advancement in quantum computing. It is specifically designed to efficiently solve two mathematical problems foundational to many cryptographic systems: 

1. Integer Factorization: Finding the prime factors of a large integer, which underpins RSA encryption. 

2. Discrete Logarithm Problem: Solving equations fundamental to cryptographic algorithms like Diffie-Hellman and ECC (Elliptic Curve Cryptography). 

The algorithm leverages quantum principles such as superposition and entanglement to reduce complex problems like factorization into a period-finding task. This task is then efficiently solved using the quantum Fourier transform. Shor’s algorithm has significant implications for public key encryption as if implemented at scale, it could theoretically break RSA and ECDH. 

However, implementing Shor’s algorithm to break RSA-2048 poses enormous challenges. Current quantum computers lack the required number of stable, error-corrected qubits—estimates suggest millions would be necessary. Furthermore, scaling quantum systems and addressing quantum error correction remain formidable obstacles, as highlighted by Google research. Experts widely agree that achieving this capability will take decades, making an immediate quantum threat to RSA highly unlikely. 

Quantum-Safe Mechanisms Are Already Here 

Even though quantum computers won’t break RSA tomorrow, the cryptographic community isn’t standing still. NIST has already developed post-quantum cryptography (PQC) standards. These algorithms are resistant to quantum attacks and can replace or supplement classical encryption mechanisms when needed. 

Here’s why transitioning to quantum-safe encryption will be relatively straightforward, especially in the context of TLS: 

1. Symmetric Encryption Remains Safe: 
   1. TLS already uses symmetric encryption (e.g., AES) for securing transmitted data after the key exchange. Symmetric algorithms like AES-256 are inherently resistant to quantum attacks because Grover’s algorithm only halves their effective key strength. This means that a 256-bit key, which has possible combinations, would require quantum operations to brute-force, a number still astronomically large and infeasible for quantum computers even in the foreseeable future. Grover’s algorithm works by searching the key space quadratically faster than classical brute force, which means that AES-256 would be reduced to the strength of AES-128—still considered highly secure. No changes are needed for this part of TLS. 

2. Updating the Key Exchange: 
   1. The key exchange in TLS can be modified to use post-quantum algorithms like CRYSTALS-Kyber instead of traditional RSA or ECDH. This change ensures the shared secret key remains secure even against quantum threats. 

3. Minimal Disruption: 
   1. Modern libraries like OpenSSL already support hybrid encryption modes, combining classical algorithms with quantum-safe algorithms. This means existing systems can incorporate these changes through software updates without requiring a complete overhaul. 

4. Proven Standards: 
   1. NIST-approved algorithms, such as CRYSTALS-Kyber (key exchange), are designed to seamlessly integrate into existing cryptographic protocols, including TLS and IPSec. 

Performance Implications 

Replacing just the key exchange mechanism and leveraging hybrid approaches during the transition makes TLS quantum-safe a manageable and incremental process. However, there are performance implications to consider. Implementing hybrid key exchanges, which combine classical algorithms like RSA or ECDH with quantum-safe algorithms such as CRYSTALS-Kyber, may introduce additional computational overhead and latency during the handshake process. While this could lead to noticeable delays in resource-constrained environments such as IoT devices, on most modern devices, the overhead is negligible, and the encryption remains both feasible and efficient. 

Summary 

TL;DR Hype. 

Google’s Willow chip and similar advancements are milestones worth celebrating as they push the boundaries of what quantum computers can achieve. However, the leap from solving niche problems to breaking RSA encryption is enormous and fraught with practical challenges.