Last summer I wrote a pair of blog entries about the use of quantum phenomena in cryptography. First, defensive use to protect your confidentiality, using QKD or Quantum Key Distribution to securely communicate the long binary key stream needed for a One-Time Pad or OTP, the only perfectly secure system (if you are extremely careful). And a year before that I explained how quantum effects can give us that truly random key stream.
The second item last summer looked at the opposite side, the possibility of breaking asymmetric ciphers with quantum computers.
All this is beyond the scope of Learning Tree’s System and Network Security Introduction course, but that course provides a good background for this area. Let’s look ahead.
What’s new on both sides of quantum physics in cryptography?
On the defensive side, a new paper just appeared in Nature, “Practical quantum key distribution protocol without monitoring signal disturbance” (22 May 2014, pages 475-478). QKD is becoming more practical.
Moving to the offensive side, breaking ciphers by solving what currently are impractically difficult math problems, work continues incrementally.
The state of the art in quantum discovery of the prime factors of numbers, what would be needed to defeat RSA, seems to still stand at 143. Not a 143-digit number, or an attack using 143 qubits, but finding the factors of the 3-digit number 143. (Spoiler alert: The answer is 11×13)
Perhaps more significantly, there is still debate over the technology involved in solving that relatively trivial problem — is it truly quantum computing, or is it a simulation of quantum computing?
Adiabatic computing is also used by D-Wave’s system, and a controversy continues there as to whether it is really computing in a quantum fashion. Scott Aaronson, a quantum physicist at MIT, strongly questions whether either of these systems are really quantum computers.
Right now we have known quantum algorithms including Shor’s Algorithm and Grover’s Algorithm, but we don’t have a quantum computer of any meaningful size that can run them. And we have multiple systems claiming to be quantum computers but they use annealing or adiabatic methods for which there’s no agreement on their true quantum nature.
Even when someone builds a system that is recognized as a quantum computer, it is not of useful size. To attack currently used asymmetric ciphers, researchers at the University of Waterloo have shown that it would take about 4096 qubits to break 2048-bit RSA, and 1300 to 1600 qubits to break equivalently strong 224-bit ECC. Compare this to the handful of qubits in current implementations.
Researchers at the University of Bristol are working on 6-qubit and 8-qubit systems, and looking ahead to when they have a quantum computer and need someone to program it.
They have placed a simulator on line, allowing anyone to experiment with quantum programming. If you become competent on that simulation, you can apply to run your program on their real (but limited) quantum system.
The most recent development is Google’s Quantum Computing Playground. It is a browser-based WebGL Chrome Experiment which can “simulate quantum registers of up to 22 qubits, run Grover’s and Shor’s algorithms, and has a variety of quantum gates built into the scripting language itself.” An experiment applying Shor’s algorithm is described here.
So, small steps continue. I’m keeping an eye on this, but I’m not worried about a breakthrough changing all of cybersecurity tomorrow.