Communications of the ACM
Home/Magazine Archive/April 2019 (Vol. 62, No. 4)/Technical Perspective: Was Edgar Allan Poe Wrong After.../Full Text
Research highlights
Technical Perspective: Was Edgar Allan Poe Wrong After All?
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 complex ciphers were designed. Somehow related to the P ≠NP conjecture, it appeared the emergence of increasingly powerful computers was to the advantage of codemakers. The invention 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 discovered in 1994 that a quantum computer could efficiently break not only RSA but also the earlier Diffie-Hellman key establishment scheme (even based on elliptic curves), essentially bringing to its knees the entire cryptographic infrastructure on which the presumed security of the Internet currently rests. Not to worry: quantum 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 Bennett 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." Furthermore, the implementation of QKD seemed so much easier than the construction of a full-scale quantum computer necessary to run Shor's algorithm. In 1996, the unconditional security of QKD was proved by Dominic Mayers (even against quantum computers) and increasingly sophisticated 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 unconditional only if the apparatus could be built exactly as defined in the theoretical papers, a seemingly impossible task. In 2009, they demonstrated a full-field implementation of a complete attack on a running 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.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2019 ACM, Inc.
No entries found