Quantum computing and the future of cryptography: Understanding the imminent threat

By Bobby O. Corpus Jr., President, OneQuantum PH/Quantum Computing Society of the Philippines

Encryption is the backbone of most sensitive transactions on the web, ensuring our data remains secure. If you’re not in the field of cybersecurity, it’s likely something you rarely consider, which speaks to the trust we place in these cryptosystems. One prominent example is RSA cryptography, which relies on the difficulty of factoring a large number into two prime numbers. For instance, with 2048-bit encryption, even the fastest supercomputer would take longer than the age of the universe to crack it via brute force — a practically impossible feat. 

However, a new challenge looms over this trust: the advent of quantum computers. Recognizing this, the US Office of Management and Budget set a deadline for agencies to submit inventories of their cryptographic systems by May 4, 2023, signaling the gravity of the quantum threat. But what exactly is this threat, and why should we be concerned?

Quantum computing represents a paradigm shift from classical computing. While we are accustomed to tasks like running spreadsheets on laptops or simulating weather patterns on supercomputers, quantum computing leverages quantum properties such as superposition, entanglement, and interference — phenomena that occur on very small scales and are not part of our everyday experience. A quantum computer can exploit these properties to solve specialized problems that would take classical computers an astronomical amount of time. Among these problems is the ability to crack widely used cryptosystems in e-commerce, like RSA, elliptic curve cryptography, and Diffie-Hellman, rendering them obsolete.

In the quantum era, two algorithms are particularly crucial in the context of cryptography: Grover’s Algorithm and Shor’s Algorithm.

Grover’s Algorithm is a quantum brute-force method that can search through possible solutions much more efficiently than classical algorithms. While it doesn’t pose a severe threat to current cryptosystems, it does necessitate increasing key sizes to maintain security.

The real threat lies with Shor’s Algorithm, which can solve the “hidden subgroup problem.” RSA, elliptic curve cryptography, and Diffie-Hellman are instances of this problem. Shor’s Algorithm can efficiently find a number known as the “period,” which can then be used to compute private keys, effectively decrypting the message. It does this by leveraging a quantum phenomenon called superposition to compute all possible values of a mathematical function called “modular exponentiation” in parallel (also known as quantum parallelism) and interference to extract the “period.” Though the result is probabilistic and requires verification, once the correct period is identified, the encryption can be broken.

Currently, we don’t have a quantum computer powerful enough to break 2048-bit encryption, as there are significant engineering challenges to overcome. However, researchers worldwide are racing to build the first fault-tolerant quantum computer capable of this feat. Given this potential, it’s not hard to imagine that entities interested in decrypting sensitive communications might already be harvesting encrypted data, storing it for future decryption once the necessary quantum technology is available.

Given this, we must assume that our encrypted communications could be at risk in the future. So, what can we do to protect our sensitive information from the threat of quantum computing? Thankfully, there are cryptosystems — known as post-quantum cryptography algorithms — that are currently resistant to known quantum attacks. The only way to crack them, at least for now, is through brute force, which would require an astronomical amount of computational time.

The US National Institute of Standards and Technology (NIST) has already begun standardizing post-quantum cryptography algorithms. To protect our sensitive information, we should transition to using these post-quantum cryptographic methods as soon as possible.

Follow OneQuantum Philippines on LinkedIn, Facebook, and Instagram.