Quantum Computers And Why Your Cat Meme Album Is At Risk

The Current Landscape

                Right now, everything you do over any type of network is based on three types of cryptography, made popular in the 70s. You have RSA, Diffie-Hellman key exchange, and Elliptic Curve technology. These are all based on mathematical problems that are easy to solve, but hard to reverse. For example, a computer can easily multiply two large numbers together, and get a solution. But start with the solution, and it is incredibly hard (takes an impractically long time) to factorize a large integer in to its component primes.  This is what RSA is based on. The primes serve as a person’s “private key”, which is kept private by the person, and then “public key” is the product of the primes. It is extremely hard to get the “private key” from the “public key”, due to prime factorization. An example of this, was RSA-768, a 768 bit number (232 decimal digits) that was factored on December 12, 2009. Researchers used a collection of computers, that amounted to the equivalent of 2000 years of processing power. Quite a long time.

Enter Quantum Computing

Currently a computer works quite simply. It is a collection of bits, and that bit can be a 0 or a 1. These collections of bits’ form algorithms and functions that make a computer tick. A Quantum Computer works a bit different… and bear with me because it’s kind of over my head as well. A quantum computer doesn’t use bits; it uses something called qubits. These qubits exist a state called superposition, and they can do something crazy things. They can be a 1 or 0 at the same time, they can be moving up and down at the same time, they can be spinning clockwise and counterclockwise at the same time. So you can take one qubit, and turn it in too much more information than just a 0 or 1. And when you add more qubits, they can interact with each other, and in turn the amount of information able to be stored adds up exponentially with each new qubit.

Shor’s Algorithm

                Now all this new processing power is all fine and dandy, but what do we do with it? In 1994, an AT&T researcher named Peter Shor revealed the theoretical algorithm to harness the power of a quantum computer. His algorithm was shown to be able to, in a timely fashion, compute both prime factors and discrete logarithms, effectively breaking both RSA encryption and Diffie-Hellman key exchange. And we’ve been in a race ever since.

Your Data, How Much Is It Really At Risk?

                The NSA has announced it is publicly moving away from any cryptographic algorithm susceptible to quantum computing cryptanalysts. They have also publicly announced that at this point in time, nothing has been shown to be a proven, standard replacement. There are some proposed methods, such as lattices, but nothing concrete. Most current estimates show that readily available quantum computers capable of such cryptanalysts are a way out. Lower end of that estimate says about five years, and the higher end says about 30. Now, I don’t think anybody is going to be hacking your imgur account any time soon. But industries relying on privacy are going to have to worry about this sooner rather than later. Banks need to protect your information, and Governments need to protect their secrets. It’s a constant cat and mouse game between academic cryptographers, and cryptanalysts.