Quantum Computing Continues to Evolve

Although still in its infancy, quantum computing is making some impressive strides forward. [1] We aren’t computer engineering students but it is important to understand, as security conscious individuals, the implications to computer security posed by quantum computers. Namely, cryptanalysis. Cryptanalysis is basically trying to find a way to read an encrypted message without having the key. Messages are encrypted using a cipher. An example of a cipher is the RSA cipher. The strength of the cipher lies in the mathematical algorithm (trapdoor function) used to create the keys, the key size, and the limited computational power available to potential attackers. The cipher creates the key with 2 VERY large prime numbers (the larger the better). If the attacker wants to read the message, he has to factor the product of those 2 prime numbers. Prime factorization is the biggest threat to a cipher like RSA or the Rabin cryptosystem. Using computers available today, it could take years upon years to crack such a message. However, with the computing power of quantum computers, such a calculation will be trivial.

From Wikipedia:

“Consider a problem that has these four properties:

  1. The only way to solve it is to guess answers repeatedly and check them,
  2. The number of possible answers to check is the same as the number of inputs,
  3. Every possible answer takes the same amount of time to check, and
  4. There are no clues about which answers might be better: generating possibilities randomly is just as good as checking them in some special order.

An example of this is a password cracker that attempts to guess the password for an encrypted file (assuming that the password has a maximum possible length).

For problems with all four properties, the time for a quantum computer to solve this will be proportional to the square root of the number of inputs. That can be a very large speedup, reducing some problems from years to seconds.” [2]

So who knows? In a decade, the cryptosystems considered strong today like AES may be totally useless (much like what happened to WEP).


[1] http://www.sciencedaily.com/releases/2011/08/110831115808.htm

[2] http://en.wikipedia.org/wiki/Quantum_computer#Potential