Saturday, December 15, 2007

Quantum Computing

ZDNET Australia reported yesterday that

"Researchers from the University of Queensland have taken a significant step in the quest to build a quantum computer, creating a light-based quantum circuit capable of basic calculations and moving quantum computing closer to a becoming a reality."

link to original article)

This big stuff. A "quantum computer" can factor numbers linearly. What does this mean? Consider the following Slashdot post, written by "swilver":

"What a lot of people fail to realise is that encryption can be made unbreakable even by brute force by simply choosing a large enough encryption key. What people also fail to realise is that 256 bit encryption doesn't take twice as long to crack as 128 bit encryption. It in fact takes 2^128 times as long to crack.

Let's for a second assume that 128 bit encryption is crackable by your own personal home computer in a period of 1 hour.

136 bit encryption would take 2^8 times as long (250 times as long)... so we use 250 computers, and crack it in 1 hour still.

144 bit encryption takes again 250 times as long, so instead we use 250 superpowerful server computers and crack it in 1 hour.

156 bit encryption takes another 250 times longer, so we use a top-secret government super computer the size of the Pentagon and still crack it in 1 hour.

164 bit encryption takes.. you guess it, 250 times longer to crack. All the governments in the world pool their top-secret super computers and crack your content in.. 1 hour.

172 bit encryption takes 250 times longer to crack. We use all the computers on the entire planet and manage to crack it in 1 hour.

180 bit encryption takes 250 times longer to crack. We use all those computers, but let them run 250 hours (10 days) instead.

188 bit encryption takes 250 times longer to crack. We let those computers run 6 years to crack your password.

192 bit encryption takes 250 times longer to crack... never mind, we're not THAT interested in your personal photo album.

( Link to original post)

Very well said. The linear addition of bits to a cipher causes an exponential increase in processing time - if your processing power is running on a traditional bit of computer hardware. If you're using a quantum- based computer, however, a linear increase in bits only results in a linear increase in processing time.

So if it takes you 1 hour to crack a 128 bit cipher with your quantum home PC, a doubling of the nuimber of bits would only double the time it takes to crack.

Big stuff, indeed.