Communications of the ACM

QKD connection. The specific weakness thus uncovered by Makarov was quickly patched, but another emerged just as quickly. Poe’s statement could be paraphrased as “It may be roundly asserted that engineers ingenuity cannot implement a QKD apparatus without leaving a loophole which engineers ingenuity can exploit.” Thus, the game of cat-and-mouse would continue forever, albeit lifted from the realm of mathematics to that of engineering.

This is where the following paper by Umesh Vazirani and Thomas Vidick enters the stage. Artur Ekert realized as early as 1991 that a different kind of quantum cryptography was possible by harnessing entanglement, which is arguably the most nonclassical manifestation of quantum theory. Even though Ekert’s original protocol did not offer any security above and beyond my earlier invention with Bennett, he had planted the seed for a revolution. It was realized by several researchers in the mid-2000s that entanglement-based protocols could lead to unconditional security even if they are imperfectly implemented—even if the QKD apparatus is built by the eavesdropper, some argued. For a decade, these purely theoretical ideas remained elusive and seemed to require unreasonable hardware, such as an apparatus the size of the galaxy! Vazirani and Vidick’s paper provides an unexpectedly simple and elegant solution, indeed one that is almost within reach of current technology. Once it becomes reality, codemakers will have won the definitive battle, Poe’s prophecy notwithstanding.

Gilles Brassard is a professor at Université de Montréal, Quebec, Canada, and Canada Research Chair in Quantum Information Science.

Copyright held by author.

FOR THOUSANDS OF years, the battle has been raging between codemakers and codebreakers. There have been dramatic reversals of fortune throughout history, sometimes with spectacular consequences that have changed the course of civilization. For instance, the world today would be a very different place had the Allies not cracked the German’s Enigma cipher during the Second World War. Numerous popular books have been written about the war of codes, such as Simon Singh’s bestseller, The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography. Today, our entire economy, and the very existence of cyberspace, depends crucially on our ability to communicate confidentially. But can we really?

The billion-dollar question is: Will it be codemakers or codebreakers that emerge in the end as undisputed victors? Or perhaps the game of cat-and-mouse will go on forever, with codemakers inventing evermore clever encryption schemes, only to be defeated by even cleverer codebreakers. In 1841, poet and novelist Edgar Allan Poe famously wrote in the improbably named Graham’s Lady’s and Gentleman’s Magazine that “It may be roundly asserted that human ingenuity cannot concoct a cipher which human ingenuity cannot resolve.” This was quite a bold statement because Blaise de Vigenère had published in 1585 a scheme then known as le chiffre indéchiffrable, which nobody had yet been able to break. How could Poe ave foreseen that it would be broken by Charles Babbage just a few years later? So, perhaps he was right after all.

Then computers came into the
game and considerably more com-
plex ciphers were designed. Some-
how related to the P ≠ NP conjecture,
it appeared the emergence of increas-
ingly powerful computers was to the
advantage of codemakers. The in-
vention of public-key cryptography
in the 1970s seemed to turn the tide
resolutely in favor of codemakers. In
particular, the publication of the RSA
cryptosystem in these pages (CACM
Feb. 1978) was a turning point. Poe, it
would seem, was wrong.
That was until Peter Shor discov-
ered in 1994 that a quantum com-
puter could efficiently break not only
RSA but also the earlier Diffie-Hell-
man key establishment scheme (even
based on elliptic curves), essentially
bringing to its knees the entire cryp-
tographic infrastructure on which
the presumed security of the Internet
currently rests. Not to worry: quan-
tum computers seemed to be a threat
for the far future in 1994 … but not
anymore. Poe, it would seem, would
have the last laugh.
But already in 1983, Charles Ben-
nett and I had invented quantum key
distribution (QKD), thus harnessing
the power of the quantum for the
benefit of codemakers one decade
before Shor harnessed it to serve the
opposite side. As Asher Peres once
said, “The quantum taketh away and
the quantum giveth back.” Further-
more, the implementation of QKD
seemed so much easier than the
construction of a full-scale quantum
computer necessary to run Shor’s al-
gorithm. In 1996, the unconditional
security of QKD was proved by Domi-
nic Mayers (even against quantum
computers) and increasingly sophis-
ticated prototypes were being built.
Hence the issue was finally settled:
Poe was wrong.
That was until Quantum Hackers
emerged, many of whom under the
leadership of Vadim Makarov. They
realized the security of QKD was un-
conditional only if the apparatus
could be built exactly as defined in
the theoretical papers, a seemingly
impossible task. In 2009, they dem-
onstrated a full-field implementation
of a complete attack on a running
Technical Perspective
Was Edgar Allan Poe
Wrong After All?
By Gilles Brassard
research highlights