acm-header
Sign In

Communications of the ACM

News

Future-Proof Encryption


Norbert Ltkenhaus of the University of Waterloo

Norbert Ltkenhaus, associate professor in the physics department at the University of Waterloo and a member of the Institute for Quantum Computing (IQC), is involved in research on the theory of practical quantum key distribution systems.

Credit: The Institute for Quantum Computing

This summer, the controversial former National Security Agency (NSA) analyst Edward Snowden answered a series of security-related questions in an online forum hosted by the Guardian newspaper. One worried reader asked if there was any way to hide email from the inquisitive eyes of the NSA. Snowden replied, in brief: "Encryption works. Properly implemented strong crypto systems are one of the few things you can rely on."

When these systems fail, the cause is typically human errorsomeone installing malware on their machine, for exampleand not the result of a fundamental flaw. Yet researchers say this will not remain true if quantum computers, machines with exponentially more processing power than today's technology, become a reality. "It is reasonably clear that the classical encryption methods we are using today are going to become insecure in the long term," says physicist Vadim Makarov of the Institute for Quantum Computing at the University of Waterloo. "Once the technology to crack classical encryption becomes available in the future, all the secrets become compromised retroactively. This is just not acceptable for many kinds of secrets, like medical, political, military secrets, which have very long-term value."

As a result, scientists have been developing systems that rely on quantum cryptography, a potentially unhackable form of communication. A group at Los Alamos National Laboratory has been operating a small but secure quantum-cryptography-based network for more than two years. The Swiss firm ID Quantique already has used quantum cryptography to secure point-to-point transactions within financial institutions.

There are a number of limitations to the nascent technology, but the potential benefits are tremendous. "It is ultra-secure," says physicist Duncan Earl, chief technology officer of Gridcom, a startup developing a quantum cryptography system for the electrical grid. "It is a security guarantee against future computer improvements. It is a future-proof technology."

Back to Top

A New Trust Model

The critical pieces of both quantum and standard cryptography are the keys used to encrypt and/or unscramble messages. The RSA algorithm for public-key cryptography, one of the more popular systems today, relies in part on a publicly available key that is the product of two large prime numbers. This public key is combined with a message to create a gibberish-like cipher text. Once the message is encrypted and sent, the only way to decipher it is to apply a second, private key.

It is almost impossible to derive the private key from the public one, but depending on the difficulty of that calculation could be a flaw in the long run. "It is only secure if factoring is a hard problem," explains physicist Daniel Gottesman of the Perimeter Institute. "That turns out to be very hard on a classical computer, whereas a quantum computer could run new kinds of algorithms that can efficiently factor large numbers. So if you had big quantum computers, RSA would not be secure."

Quantum cryptography takes a different approach. If two people, dubbed Alice and Bob in the crypto world, want to communicate securely, they first generate and exchange a shared, secret key. This key, which is as long as the message itself, as opposed to the relatively short 128-bit or 256-bit keys used in today's systems, is known as a one-time pad, and is only used once. Alice encrypts her message with the one-time pad, then sends it to Bob, who applies the same key to unscramble the text.

The quantum aspect of the process lies in how they generate and exchange that key. In the most common method, known as prepare and measure, Alice sends photons of light to Bob. A photon can assume a number of possible statesdifferent spins and polarizationsthat can be used to represent different bits. So, a photon with a vertical orientation might stand in for the bit 1, while a photon that is horizontally oriented could correspond to 0. Alice prepares each photon, collapsing it into a particular state, then sends it to Bob, who attempts to measure the result. They each translate what they see into key bits and compare their results.

If someone tries to spy on the process and intercept the photons en route, then Alice and Bob will notice too many discrepancies and conclude the line of communication is insecure. But if the measurements match often enough, they are left with a matching string of random bits they can use as a shared, secret key to encrypt and then decipher a message.

The security of the key stems from the fact it relies on photons, not factoring. "The laws of physics say that if I am sending light, any attempt by an eavesdropper to make a measurement on that must create a disturbance," says quantum communications expert Jeffrey Shapiro of the Massachusetts Institute of Technology. "What Alice and Bob rely on to get their security is that law of physics. That is a different trust model than saying we know this is a computationally difficult problem and therefore we can rely on the fact that no one has a computer powerful enough to break this system."

Back to Top

Theory and Practice

In quantum cryptography today, the devices used to transmit and receive photons between two parties can only communicate over relatively short distances, on the scale of tens of kilometers; any farther, and the photon signals fade. Furthermore, the devices that send these pulses do not always behave precisely, sometimes generating two or more photons when the system only asks for one. "We have a gap between theory and practice," says physicist Renato Renner of the Institute for Theoretical Physics in Zurich. "The devices that are used in practice just don't do what they're supposed to do."

Hackers such as the University of Waterloo's Makarov have exploited these flaws. In 2010, Makarov and his colleagues announced they had effectively hacked a quantum cryptography system by blinding it with a bright light. Yet Makarov does not see his work as an indictment of quantum cryptography; he merely found a weakness in a particular implementation. In fact, he informed the manufacturers long before he published the work, so they were able to fix the flaws before any damage could be done.

The Swiss firm ID Quantique, which has worked with Makarov and other hackers on occasion, has been steadily improving its technology since launching its first product in 2004. ID Quantique is exploring systems that would allow quantum cryptography to work over larger distances, but the company's primary focus today is on relatively local, point-to-point communications. "Our current customers are in the financial sector and government," says ID Quantique CEO Gregoire Ribordy. "We are offering long-term confidentiality of data over a link, such as one data center to another or, in a campus network, high-security transactions between buildings."

Gridcom plans to use quantum cryptography to secure machine-to-machine communications within the electrical grid. The company, which is scheduled to roll out its first commercial system in 2015, will rely on entanglement, a phenomenon in which two photons become inextricably linked in such a way that measuring one will produce an immediate change in its twin. Gridcom will use these entangled photons to generate a stream of secure, random bits, and if anyone tampers with one of the pair, the system will immediately recognize the interference. In Gridcom's model, companies will pay a subscription per machine for access to those securely generated bits. "They get these tamper-proof keys which they use in their encryption," Earl says.

Back to Top

A More Secure Future

The recent advances in the field have sparked some speculation about the larger potential of quantum cryptography. When the Los Alamos group led by physicists Richard Hughes and Jane Nordholt announced they had been successfully running a small, hub-and-spoke network secured by quantum cryptography, several popular news sites called their creation a "secret quantum Internet." Hughes quickly deflated the notion, and some experts say quantum cryptography might not be ideally suited for protecting mass communications. Gottesman and other experts note there are other public key cryptography systems that may be able to do the job more efficiently and economically on their own. No one has yet proven otherwise.

Instead, quantum cryptography will more likely be used in specific cases involving small networks or point-to-point communications, when long-term secrecy is essential. Even Makarov, who has exposed glitches in today's systems, believes the future is bright. To him, the successful hacks are not a proof that quantum cryptography itself is flawed. "This is a natural step in the process to make the technology secure," he says. "Once the implementation loopholes are found and closed, then we have a really, really secure technology. Quantum cryptography is going through this process right now."

Back to Top

Further Reading

Lydersen, L., Wiechers, C., Wittmann, C., Elser, D., Skaar, J., Makarov, V.
"Hacking commercial quantum cryptography systems by tailored bright illumination," Nature Photonics, 2010.

Gisin, N., Ribordy, G. Tittel, W. and Zbinden, H.
"Quantum Cryptography" in Reviews of Modern Physics, Volume 74, 2002.

Hughes, R.J., Nordholt, J.E., et. al.
"Network-Centric Quantum Communications with Application to Critical Infrastructure Protection." http://arxiv.org/abs/1305.0305

"A Multidisciplinary Introduction to Information Security." Chapman and Hall, 2011. See Chapter 5: Quantum Cryptography.

"Quantum Cryptography" An introductory video lecture by physicist Daniel Gottesman. http://www.youtube.com/watch?v=NejFo5hKcOg

Back to Top

Author

Gregory Mone is a Boston, MA-based writer and the author of the novel Dangerous Waters.

Back to Top

Figures

UF1Figure. Norbert Lütkenhaus, associate professor in the physics department at the University of Waterloo and a member of the Institute for Quantum Computing (IQC), is involved in research on the theory of practical quantum key distribution systems.

UF2Figure. This photon receiver nicknamed "Bob" is part of a quantum key distribution system housed at Waterloo's Perimeter Institute for Theoretical Physics. Bob communicates with photon receiver "Alice," which resides at the Institute for Quantum Computing at the University of Waterloo.

Back to top


©2013 ACM  0001-0782/13/11

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and full citation on the first page. Copyright for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or fee. Request permission to publish from permissions@acm.org or fax (212) 869-0481.

The Digital Library is published by the Association for Computing Machinery. Copyright © 2013 ACM, Inc.


Comments


K.R. Chowdhary

The article very clearly indicates that present Internet security, which is based on factoring of large numbers, is not sustainable as processors are becoming more and more powerful. As we note the trend, the DES (digital encryption standard) -- a 54 bit symmetric cryptography, orginally developed by IBM -- is no more secure. The RSA security, which is based on large prime numbers, where for breaking it one need to first generate the other prime number, by the processes of factoring. And, for factoring there is no efficient algorithm exists yet, and this is the strength of RSA. However, the RSA can be easily broken at least for not too large prime number based keys; either by running a powerful system for a long time, or by connecting many PCs in parallel, and sharing the work of generating prime numbers and attempting to crack the RSA key.

RSA has one fundamental weakness; if encrypted information while in transmission is copied in an intermediate station through eavesdropping, the packets are not able to sense that they have been copied. This copied information can be attempted to dug up later, to find out the contents.

However, in case of quantum cryptography, which is based on photons, you cannot copy the photons, at the middle station; in fact you can only steal some photons, which will result to tempering in the message (photons, and their counts, spins, etc.), and this will be detected at the destination easily.

Another important point about this article is that it talks about the information while in transmission, which can be in the form of photons, for quantum cryptography. But, it appears that a vast amount of information, which remains stored in media, if required to be secured, the conventional cryptography will continue to prevail. Because, photons cannot be stored. Hence, it requires to strengthen the existing RSA cryptography, as well as, and to investigate new methods to encrypt the stored information.


Displaying 1 comment