A Quantum Threat

A New Era of Computing

Quantum computing is right around the corner and threatens the safety of modern cryptographic algorithms. What would previously require a millenia to decode now may only take minutes. However, there are efforts being made to develop and implement quantum resistant cryptography.

The Traditional Computer

Current computer architecture, known universally as Von Neumann architecture, processes information using binary bits, 1s and 0s. The computations are sequentially processed using a bus system and central processing unit (CPU). This architecture is bound to the clock rate of the CPU and the bandwidth of the bus. Basically solving problems step by step in an orderly fashion as fast as their physical components allow.

Von Neumann Architecture Diagram — Von Neumann Diagram. Source: wikibooks.org

The Quantum Computer

Whereas quantum architecture operates using qubits, which can exist as 1s, 0s, or a superposition of both. A famous example of superposition is Schrödinger’s cat experiment, where a cat is sealed in a box with a poisonous substance. The substance has a 50/50 chance of killing the cat. However, until the box is opened, the cat is considered to be both alive and dead simultaneously. This same idea represents superposition in a quantum computer which processes many possible outcomes rather than a single deterministic answer. The quantum computer may run multiple times on the same problem set and reveal the most likely solution. Since quantum architecture can test many outcomes at once, large numbers can be factored exponentially faster than traditional Von Neumann computers.

The Problem

It is computationally easy to multiply two large prime numbers but is extremely difficult and time-consuming to find the original prime factors. This asymmetry is the backbone of many famous cryptographic algorithms like RSA. Von Neumann machines would take thousands of years to crack such large factored numbers. In contrast, Quantum architecture can calculate large factored numbers in hours or minutes. Such a reality would necessitate a different approach to cryptography that does not rely on the complexity of factored numbers.

The Solution?

As such, some new quantum resistant algorithms coined Kyber, Dilithium, and Falcon were developed that do not use large factored numbers. Instead, they rely on “combining sets of vectors to form new vectors” and “the new vectors you can form by these combinations are called a lattice”. The more dimensions of the lattice, the more difficult the computation. However, as quantum computing becomes more efficient, even these new quantum resistant encryption methods may become obsolete.