Security Laboratory

Security Laboratory: Cryptography in Business Series

We are grouping papers in this series to focus on the many facets of data encryption.

Quantum Cryptography

Jan 4th, 2008
By Stephen Northcutt

In their present state, (2008), Quantum computers are still experimental and the largest, so far, is a 16 qubit system built by D-Wave in Canada.[1] "Called Orion, it is a superconducting adiabatic quantum computer. The main computing engine is held in a big red tank, supercooled to a frosty 4mK (0.004 degrees Celsius above absolute zero, colder than interstellar space!) with liquid helium. The core computational unit is a single chip, with 16 qubits arranged in a four by four grid. Each qubit is coupled directly to its immediate neighbors (North, South, East, and West) and those on the diagonal, which provides considerably less efficiency than the theoretical maximum of every qubit entangled to every other qubit."[2]

A previous system by IBM was a '7 qubit computer' that consisted of a molecule constructed of 5 atoms of fluorine and 2 atoms of carbon. Physically, it is a vial containing 1018 molecules. You will recall from basic chemistry that a 'gram molecular weight' of a substance contains 6.022x1023 molecules, so the operative word here to describe its size is 'small'.

However, the IBM computer was used to factor the integer '15' using Shor's Quantum Factoring Algorithm. This is significant in that it means that the computer was able to be programmed and produce an answer. This advance, when coupled with the possibility of the use of 'Grove's Quantum Search' algorithm, does not bode well for the future viability of the current public key systems, if (or when) quantum computers finally appear on the scene. This risk to public key systems is theoretical at present since the NMR method is thought to be limited to 10-15 qubits and it is theorized that a 40 qubit computer would be required to pose a serious hazard to public key systems.

Another recent advance in quantum computing occurred June 19, 2006 when they reached the 12 qubit quantum computer benchmark. Researchers at Waterloo and Massachusetts have benchmarked quantum control methods on a 12-Qubit system. This is the largest quantum information processor to date. Despite decoherence, the researchers reached a 12-coherence state and decoded it using liquid state nuclear magnetic resonance quantum information processors. [3]

Computer Security Management Application
In 2007, from a hardware perspective, one of the more surprising cryptoanalysis developments was a Play Station used to brute force decrypt passwords.[4] In the not too distant future, Quantum Computers may possibly spell the end of Public Key Cryptography as we know it, but Quantum Cryptography may also be the solution for that problem. Oddly enough, the name 'Quantum Cryptography' originally refered to Quantum Key Distribution, (QKD), and not to the use of Quantum Computers for Encryption.

Quantum Key Distribution
QKD permits the secure delivery of encryption keys between two parties as an adversary, (a.k.a. Eve), cannot eavesdrop without being detected.

The ability to detect the presence of an adversary is rooted in quantum mechanics and cannot be circumvented.

Key Transmission with Adversary Detection:
Quantum Key Distribution permits the transmission of a cryptographic key with adversary detection, (i.e., if Eve is listening Alice and Bob will know it). This is a rapidly evolving field, but at present there are two general methods of quantum based secure key transmission under development. Both rely on quantum principles involving the photon. One method is based on the phenomenon of 'Quantum Entanglement'; the other is based on 'Photon Polarization' Detection. Both of these methods, Entanglement and Polarization Detection, can detect the presence of the eavesdropper, Eve, by monitoring the error rate of the transmission of the key.

Photon Polarization Detection:
While some organizations are working on systems over air with the ultimate aim being to do QKD over satellite, current methods are still of limited range (10km) in air. However, photon polarization over fiber has progressed to the point where practical systems are commercially available. A 'Photon Polarization Detection' system depends on the phenomenon that when a polarized photon is passed through a filter with its polarization axis orientated 45 degrees to the polarization of the photon, the filter will have a 50% probability of rotating the polarization of the photon passing through it. (I.e., when a vertically polarized photon is passed through a horizontally polarized filter it will be blocked. However, when it is passed through a 45 or 135 degree diagonally polarized filter it will emerge diagonally polarized 50% of the time.)

This is an effect of the Heisenberg Uncertainty Principle which requires that a photon which is polarized in one of two possible non-orthogonal polarization systems (e.g., rectilinear, 0 & 90 degree; or diagonal, 45 & 135 degree) cannot be detected by both polarization systems simultaneously with 100% probability. The same principle also applies to circularly polarized photons, but we will stay with orthogonal systems for the remainder of this discussion.

Key bits are transmitted as a single photon per bit from one end of the link to the other using a bit weighting in one of the two polarization systems, where the polarization system is chosen randomly on a photon by photon basis. The bits are received at the end of the link using randomly chosen polarization system detection. After transmission of all the key bits, Alice and Bob communicate over an authenticated but unencrypted link and discard all bits which were not sent and received with the same polarization systems. Of these remaining candidate key bits, a random check subset is compared by Alice and Bob. If the check subset agrees bit for bit, the check subset is discarded and the remaining candidate key bits are used as the cipher key.

It is Quantum Mechanically impossible for Eve to monitor the photon transmission without altering it, and since, statistically, it is extremely unlikely that Eve could monitor the transmission without altering some of the random bits selected for the random check subset; her presence will be detected by errors in the check subset.

In a real system there are other sources of errors, but all errors are considered to be due to Eve. However, a certain low error rate can be acceptable; in which case, any errors in the remaining candidate key bits can be corrected by applying error correcting procedures to those remaining bits.

Commercial Key Systems:
Currently, two vendors (idquantique with Cerberis[5] & magiqtech with MagiQ QPN) have commercialy available shipping systems on the market which operate over fiber. The maximum theoretical range is determined by the present levels of laser photon emission efficiency, photon detector efficiency, and fiber photon absorption rates. While current commercial systems are listed at the 100 - 120km maximum range over standard fiber, and a data rate of 1kbps is adequate to update 2 AES keys per second; practical systems have only been demonstrated to a range of 67km due to the aforementioned equipment & fiber limitations. These systems are adequate for use in a Municipal Local Area network, e.g., for key transmission between a bank's home office and its local branches.

In 2004, BBN Communications and Harvard University activated a joint network secured by quantum encryption. (Security in Computing, Fourth Edition, 2007, Pfleeger & Pfleeger).

Quantum Networks:
All of the currently available commercial systems are point-to-point systems. These systems do not scale well to large enterprises and also are vulnerable to simple denial of service attacks, (e.g. sever the fiber link, or install 'Eve' as a 'spoiler' to increase error rates to unacceptable levels.). Obviously a switched network would to a large extent mitigate these weaknesses.

BBN Technologies, Harvard University and Boston University, working under a DARPA contract, have developed and tested such a network. The network architecture uses passive optical switches and active relays to implement a multipath architecture using both fiber and free space quantum links. While passive optical switches do not interfere with the photon quantum polarization characteristics, they do reduce the range of the system versus a point-to-point system, due to optical losses through the switches. The active relays permit extension of the range of the network over that of a point-to-point system, but they have the drawback of having to expose the keys at each relay point, as it is not possible to actively interfere with the photon stream without destroying its quantum polarization characteristics, and, therefore, each relay has to 'read' and 'rebuild' the photon stream at each relay node.

Should you deploy a QKD system today?
Not unless you are NSA or have information with very high value, this has a long way to go before it makes commercial sense. If you are running a system with very high value traffic, susceptible to recording by Eve, and where the protected information is sensitive for long periods of time, then further investigation of QKD systems in their current state is probably warranted. Remember, if your traffic can be recorded by Eve and a breakthrough in factoring is discovered or a 40 qubit quantum computer is invented, Eve will be able to read all of her recorded traffic as well as your current traffic. As Magiqtech puts it, "Quantum key distribution is based on a completely different paradigm from all current schemes. As a result, no matter what advances occur in digital computing, the encryption will never be able to be deciphered. It's as if the data has been written with an alphabet that doesn't use letters."[6]

1. http://www.dwavesys.com/
2. http://arstechnica.com/articles/paedia/hardware/quantum.ars/1
3. http://advancednano.blogspot.com/2006/06/12-cubit-quantum-computer-benchmark.html
4. http://d4rkn3ss.wordpress.com/2007/12/01/the-playstation-3-is-a-machine-cracking-passwords/
5. http://www.idquantique.com/products/cerberis.htm
6. http://www.magiqtech.com/products/index.php