Quantum Cryptography: An Uncertain Future for Information Security

Jacob Marks
By Jacob Marks January 18, 2015 19:13

Quantum Cryptography: An Uncertain Future for Information Security

On September 10, news broke that roughly five million Gmail accounts had been hacked, their passwords stolen. This followed on the heels of a cyber attack against Community Health System, Inc., in which personal data of more than four million patients was compromised. It also came soon after a credit card theft that affected Home Depot locations all over the world, making the home improvement store the largest retailer yet to succumb to computerized security theft.

Every day, it seems, governments and corporations fall victim to data leaks caused by anonymous online crusaders or foreign terrorist organizations — leaks which call into question the efficacy of modern computer security measures. Quantum cryptography, the use of quantum mechanical principles to make and break codes, could alter the way cybercrimes are committed, as well as the way in which we defend against them. Quantum computing threatens to exacerbate our current information security problems by compromising current encryption techniques, and if this comes to pass, then quantum key distribution could level out the cybercrime landscape by restoring security.

The Scytale is a type of transposition cipher used in ancient Greece, which involved wrapping cloth around a stick. Image Courtesy of Wikipedia.

The Scytale is a type of transposition cipher used in ancient Greece, which involved wrapping cloth around a stick. Image Courtesy of Wikipedia.

Deriving from the Greek words kryptos, for ‘hidden’, and graphein, for ‘writing’, cryptography is defined as the science of writing secret codes. For thousands of years, the practice has been used to protect state secrets and to transmit war strategies. The ancient Greeks wrote messages along cloth wound around sticks of a specific diameter, and the Romans developed the first substitution cipher, called the Caesar Shift, in which each letter in a message was shifted forward a certain number of places. Later ciphers, such as those produced by the Enigma machines used by German forces in World War II, involved multiple arrangements of the alphabet to encrypt messages.

But the advent of the computer in the latter half of the twentieth century spurred a cryptographic revolution. By allowing for the electronic transmission of large quantities of data, the computer introduced the need to securely transmit information at a distance. In the past, sender and receiver shared special knowledge about how a message was

The Caesar Shift Cipher, invented by the Romans, was the first substitution cipher. Each letter in the alphabet was shifted forward a pre-set number of places, with z looping back to a. Image Courtesy of Wikimedia.

The Caesar Shift Cipher, invented by the Romans, was the first substitution cipher. Each letter in the alphabet was shifted forward a pre-set number of places, with z looping back to a. Image Courtesy of Wikimedia.

encrypted, such as the diameter of the stick. But computers necessitated a cryptosystem that could securely transmit information between people who did not share a previously agreed upon key.

The solution, public-key cryptography, makes use of a one-way problem – something that is easy to solve in one direction, but hard to solve in the other. RSA, one of the most widely-used public key cryptosystems, is rooted in the assumption that it is easy for a computer to multiply two large prime numbers, but much harder for it to factor the result into the two initial primes.

However, public key systems like this rely on the limited computing power of cryptanalysts, or code-breakers. Although hard to solve, the problem of factorization is certainly possible, and as computing power has increased, the key length needed to ensure information security has increased as well. In 2009, a 768 bit RSA key (an integer represented by a string of 768 0s and 1s), was successfully factored by Thorsten Kleinjung and colleagues. Some people believe that the 1024 bit RSA keys now in use will be breakable in the near future using only classical computers.

D-wave: D-Wave Two, pictured above, is the world's most complex quantum computer. Created in 2013, D-Wave Two is comprised of 512 qubits, and performs an optimization algorithm orders of magnitude faster than classical computers. Image Courtesy of Wikipedia.

D-wave: D-Wave Two, pictured above, is the world’s most complex quantum computer. Created in 2013, D-Wave Two is comprised of 512 qubits, and performs an optimization algorithm orders of magnitude faster than classical computers. Image Courtesy of Wikipedia.

Furthermore, quantum computing, a subset of quantum cryptography, threatens to dissolve public-key cryptography entirely. Quantum computers use qubits, the quantum analog of classical bits, to perform operations on data. Whereas bits can take the value of either 0 or 1, qubits exhibit the quantum property of superposition. This means they can simultaneously be 0 and 1, or any combination of the two. As a result, quantum computers can theoretically use Shor’s algorithm, an algorithm developed by Peter Shor in 1994 for the efficient factorization of prime numbers. In short, quantum computers may be able to solve the one-way problem that is the very foundation of public-key encryption.

Because of this, perceptions of quantum cryptography are often skewed. “Most people think that quantum cryptography will limit information privacy,” Yale Professor of Applied Physics Steven Girvin said. “But the truth is that it will actually enhance privacy.” Although quantum computing may one day be used to break public key cryptosystems, quantum key distribution could replace these flawed alternatives and restore secure communication over public channels.

Quantum key distribution, or QKD, is a subset of quantum cryptography that allows two parties to produce a shared random key, which they can then use to encrypt and decrypt private messages. It is split into two main branches: superposition which is also used in quantum computing, and quantum entanglement, or the concept that particles are produced whose states cannot be described independently. The most successful implementation of QKD, BB84, falls into the first category. Named after Bennett and Brassard, BB84 uses photon polarization states to transmit information from sender to source. The sender selects two complementary states, each described by two bases.  By the Heisenberg uncertainty principle, which states that it is impossible to measure two interdependent physical quantities simultaneously, only one of the two states can be known.

For each photon, the sender chooses a random bit (0 or 1), and one of the two bases that describe the state, and prepares the state of the photon based on both of these random choices. The recipient must also randomly choose a basis in which to measure the photon, and when the sender and recipient use the same basis, they will observe the same state. The resulting string of shared choices becomes their key, and the rest of the photons are discarded.

One of the benefits of this system is that it is impervious to eavesdroppers. Due to the no cloning theorem, the act of observing a system changes its state, so if an eavesdropper intercepts transmitted photons, the sender and receiver will know they are being spied on. “There are no quantum Xerox machines; you can’t copy quantum information,” Girvin said.

In the past few years, BB84 and protocols involving quantum entanglement have been used to successfully distribute keys through air and via optical fibers, reaching distances of up to 148 kilometers. QKD was used to secure the results of a 2007 Swiss election, and the Chinese government uses QKD to protect state secrets.

Although companies such as ID Quantique offer quantum key distribution services, the system has not been universally adopted due to its lack of robustness, range, and reasonable price. But this is bound to change. Battelle is working on building a 650 kilometer optical fiber for QKD, and the Chinese government plans to complete construction on a 2,000 kilometer link between Beijing and Shanghai by 2016. If researchers succeed in their goal of expanding quantum key distribution to satellites, we will soon have a secure communication network connecting disparate parts of the globe.

If quantum key distribution matures into a feasible cryptosystem, and is adopted as the standard, it will free us from the limitations of existing public-key systems, and render the code-breaking capabilities of quantum computers worthless. It is important to realize, however, that cryptography is only one aspect of information security.

In fact, even with its mathematical dependence, classical cryptography often isn’t the weakest link in a security system. “The biggest security problem today is people,” said Yale Professor of Computer Science Michael Fischer, who teaches a course at Yale called Cryptography and Computer Security, said. “The easiest way to break in is to trick or bribe someone into giving you the access to the data. Even the most sophisticated technological measures can’t prevent this.”

Professor Girvin added that, “in theory a successful attack against quantum cryptography would violate the laws of physics. There could, however, be attacks based on the physical objects used to transmit the data, such as the detector used for observing the photons”. Unless we are wrong about the laws of physics, quantum key distribution has the potential to be both secure, and feasible. Where humans are involved, cryptosystems can always be broken. Nonetheless, quantum cryptography has the potential to reconfigure the relationship between code-makers and code-breakers.

Jacob Marks
By Jacob Marks January 18, 2015 19:13