Quantum Computers for Code Breaking

by Dave D' Rave

A quantum computer is a device which uses quantum effects to perform numeric and symbolic processing.

Quantum computer technologies are expected to produce a dramatic speed improvement for applications such as code-breaking, compared with conventional computers.  This extreme speed increase is accomplished by using quantum superposition to implement a massively parallel architecture.

Current Technology

The field of quantum computers is currently in a technology race.

Research devices have been built using superconducting loops, quantum dots, ion traps, non-linear optics, and crystal defect centers.  All of these technologies suffer from noise problems, and it is not clear which method will prove to be suitable for mass production.  While there has been a lot of money spent on research, informed opinion is that we are several years away from commercial production of a quantum computer which is clearly useful.  When compared with conventional computers, quantum computers are in the year 1930.

Limitations of Quantum Computers

Despite the very high performance of a quantum processor, the input and output operations are going to be pretty much the same speed as any other computer.  This means that quantum processors are extremely I/O bound.  As a result, practical algorithms will tend to involve either very focused processing of a moderately sized data set (such as a Fourier transform, a convolution, function minimum search, etc.), or will involve set operations such that the object description is relatively compact (for example, "The set of all prime numbers less than one billion," or "The set of all strings which have the same statistics as the English language").

The output is also constrained, which means that practical algorithms are going to produce results which are relatively small compared to the problem space.  For example, we could provide an input set of 256-bit strings, and ask the question "Are any of these strings equal to all zeros?", or "Given this model of the Earth's climate, will it rain in Chicago today?".

There are also technology limitations.

Because of noise, many devices use aggressive error correction, and you frequently see systems in which three or more identical circuits perform the same operation, and voting is used to determine which answer gets sent to the next stage of the algorithm.  This sort of thing works better if algorithms are combinatorial, and do not use recursion.

Quantum Set Algorithms

In general, the particular hardware to implement a quantum computer does not matter, because most quantum computing algorithms will run on any suitable machine.  (This is similar to conventional computers, where a program will run on a vacuum tube machine, a transistor machine, or a virtual machine, producing the same results.)

One class of quantum algorithms which is relevant to the problem of code breaking are the "set theory" algorithms.  In these, a multi-qubit register is the basic unit of operation.  For code breaking, the registers are commonly 64-qubit, 128-qubits, or 256-qubits in length.

Some typical operations are:

• Load the qubit register with a fixed (often classical) value.
• Add a member to the qubit register's current set.
• Count the number of valid elements in a given set.
• Find the union of the sets in two quantum registers.
• Find the intersection of the sets in two registers.
• Find the inverse (individual not) of the contents of a qubit register.  (Single-operand function)
• Rotate the qubits in a given register.  (Single-operand function)
• Find the controlled-NOT (exclusive OR) of the contents of two qubit registers.  (Dual-operand function)

These medium-level set functions are built out of individual qubit functions, which include the usual sort of quantum computer operations described in the literature:

• NOT gate.
• Hadamard gate.  (Phase transform)
• Swap gate.
• Controlled-NOT gate.  (exclusive OR)
• Controlled-swap gate.

In practical systems, you would need to be able to create custom functions, by stacking these on top of each other.

For example, the DES algorithm contains functions called a "P-box," which can be constructed out of swap operations, and a function called the "S-box," which can be constructed out of controlled-NOT operations.

Code Breaking

The algorithms used for cryptanalysis tend to be a good fit for the strengths and weaknesses of quantum computers.  Electronic coding systems tend to be vulnerable to "set theory" quantum algorithms.  All of the mainstream crypto systems are vulnerable, including DES, AES, and IDEA.

One interesting algorithm for DES-type block cyphers is called "20 Questions," and it works like this:

1. Instantiate a quantum register which contains 56-qubits, called the key.
2. Instantiate a classical register which contains 64-bits, called the plaintext.
3. Instantiate a classical register which contains 64-bits, called the cyphertext.
4. Build a quantum function called decrypt, which accepts a key and a cyphertext, such that it returns a 64-bit quantum word containing the decryption.  (This decrypts the cyphertext using the key, according to the DES algorithm.)
5. Build a quantum function called match, which accepts one quantum register input called qdata and one classical register input called cdata, which returns a single quantum bit.  (This outputs a "1" bit if the two input words are identical, and outputs a "0" if they are not identical.)
6. Build a quantum function called completely_zero, which accepts a single qubit and returns a classical bit value of "1" if and only if the input was a pure |0> state.  Return "0" otherwise.
7. Iteration 0: Load the key register with a superposition of all possible keys, such that bit 0 (the least-significant bit) of the key is equal to "1".  (This will be a superposition of 2⁵⁵ keys.)
8. Send key and cyphertext into the decrypt function.  The output will be a superposition of 2⁵⁵ different decryptions of the cyphertext.
9. Send cyphertext and the output of the decrypt function into the match function.  (The output will be mostly zero, since most of the trial keys are not valid.)
10. Send the output of the match function into the completely_zero function.
11. If the output of completely_zero is 1, then bit 0 (the least-significant bit) of the result is equal to "0".
12. Iteration 1: Load the key register with a superposition of all possible keys, such that bit 1 of the key is equal to "1".  (This will be a superposition of 2⁵⁵ keys).
13. Send key and cyphertext into the decrypt function.  The output will be a superposition of 2⁵⁵ different decryptions of the cyphertext.
14. Send cyphertext and the output of the decrypt function into the match function.  (The output will be mostly zero, since most of the trial keys are not valid.)
15. Send the output of the match function into the completely_zero function.
16. If the output of completely_zero is 1, then bit 1 of the result is equal to "0".
17. Iteration 2-55: Repeat the above steps until Iteration 55.
18. Complete.  You now have all 56-bits of the cipher-key.

Proposed technologies such as quantum dot qubits and polarized photon qubits have a characteristic gate delay time of less than one microsecond.  In the above algorithm, the decrypt function and the match function are a few dozen gates thick, which is to say a fraction of a millisecond.  If we guess that each iteration will take one millisecond, then the total time for a known plaintext attack on DES is going to be 56 milliseconds.

Cipher systems like AES-256 can also be broken is less than a second.

More sophisticated attacks would require more elaborate functions, but the central fact is that quantum computers will probably provide speedups on the order of 2⁵⁰ for problems which are relevant to real-world situations.

Trends in Quantum Computer Hardware Technology

Today, the technology does not allow quantum computers with more than a few dozen qubits to work reliably.

This is mostly due to thermal noise.  The current approach to the noise problem is to build heroic low-temperature systems, operating in the microkelvin or nanokelvin temperature range.

There are a variety of approaches to building the quantum computer hardware, and there are a variety of approaches to algorithm development.  All of the candidate hardware technologies have similar speed characteristics, and all of them involve expensive support technology, such as nanokelvin refrigeration equipment.  As a practical matter, either quantum computers will be developed which are many orders of magnitude faster than current technology (for certain problems), or the hardware will not be developed at all.

So, why should you care about this?

The NSA is building a huge warehouse in Utah whose apparent purpose is to store encrypted messages which they cannot break at this time.  NSA believes that future technology will allow them to eventually break current encryption, and they believe that some of those messages will still be useful 20 or 30 years from now.

Quantum computers are part of that future.