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
DOI: 10.1145/3310976
To view the accompanying paper,
visit doi.acm.org/10.1145/3310974