Friday, February 09, 2007

Quantum redux

A company called D-Wave promises to demonstrate a 16-qubit quantum computer. This is scary.

Using a quantum computer and Shor's Algorithm, we can crack an RSA key of the same size as the number of qbits. Thus, a 2048 bit RSA key can be cracked by a 2048-qubit computer. (It's a little bit more complicated than that, but that's the gist).

There is a probably a "Moore's Law" equivelent for quantum computers. The number of qubits we can hold together is doubling at a rate. We just need to figure out what rate that is. In 2001, IBM demonstrated a 7-qubit computer. This gives a doubling rate of around 4-years, which means we'll start being able to crack the smallest RSA keys in about 20 years, and large 2048 RSA keys in 30 years.

Each new advancement in quantum computer gives us another data point to figure out the "Moore's Coefficient" for the industry, which narrows down how long it will take before today's crypto becomes absolete. If it turns out to be 2 years, then in 15 years today's crypto becomes obsolete. If it turns out to be 1 year, then in 7 years it's obsolete. I just keeping your packet sniffer captures of VPN and SSL traffic on DVDs until then -- there is a good chance you'll be able to decrypt them in a few years.

No comments: