“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.’”
Communications of the ACM, April 2019, Vol. 62 No. 4, Page 132
Research Highlights : “Technical Perspective: Was Edgar Allan Poe Wrong After All?”
By Gilles Brassard
(Yes, this article is related to “Fully Device Independent Quantum Key Distribution.” Keep reading…)
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.
…
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.
About the Author:
Gilles Brassard is a professor at Université de Montréal Quebec, Canada, and Canada Research Chair in Quantum Information Science.
Communications of the ACM, April 2019, Vol. 62 No. 4, Page 133
Research Highlights : “Fully Device Independent Quantum Key Distribution”
By Umesh Vazirani, Thomas Vidick
Quantum cryptography promises levels of security that are impossible to attain in a classical world. Can this security be guaranteed to classical users of a quantum protocol, who may not even trust the quantum devices used to implement the protocol?
This central question dates back to the early 1990s when the challenge of achieving Device-Independent Quantum Key Distribution (DIQKD) was first formulated. We answer the challenge by rigorously proving the device-independent security of an entanglement-based protocol building on Ekert’s original proposal for quantum key distribution. The proof of security builds on techniques from the classical theory of pseudo-randomness to achieve a new quantitative understanding of the non-local nature of quantum correlations.
1. Introduction
The gold standard in classical cryptography is semantic security—given an encoded message (ciphertext), any polynomial time adversary should have a negligible chance of obtaining any information whatsoever about the plaintext (the message that was encoded). Classical cryptographers have developed encryption schemes that are able to provide this guarantee by relying on un-proven assumptions about the computational difficulty of number-theoretic problems, such as factoring large numbers, or other more general complexity-theoretic assumptions. Such cryptographic assumptions are stronger than P ≠ NP, and considered unlikely to be proven in the foreseeable future, so one may ask whether any cryptosystems can have security guarantees that do not rely on unproven computational assumptions.
Bennett and Brassard’s seminal discovery of a Quantum Protocol for Key Distribution (QKD) in 1984 opened up the possibility for a different kind of security—”unconditional security,” or security based solely on the validity of universally accepted physical laws. QKD is a protocol that allows two distant parties to collaboratively and privately generate a perfectly random string, called the users’ key. Once the users have generated a private shared key they can use it to communicate with perfect security as follows. To send a message securely, the sender uses the shared key as one time pad: the encoded message is simply the bit-wise XOR (parity) of the key with the message. The semantic security of this scheme is easy to verify, provided the one-time pad (the key) is completely random and unpredictable to any adversary.
The first rigorous proofs of security of QKD, established over two decades ago, appeared to guarantee this ultimate notion of security could be achieved. However, the promise was short-lived. QKD researchers soon realized that practical implementations fell prey to types of attacks that were not accounted for by the security proofs, including side-channel attacks and photon receptor blinding attacks. More generally, these attacks pointed to a fundamental issue: given the remarkable features of quantum mechanics, such as superpositions, entanglement, and the uncertainty principle—some of which made QKD possible in the first place—how can one trust that there are not novel ways of attacking the quantum devices implementing a QKD protocol, unbeknownst to the honest, but classical, users of the protocol? The basic assumption that the user has perfect control over and trust in her quantum devices in a cryptographic protocol, on which all security proofs crucially relied, now appeared wholly unrealistic.
Read the Full Article (Paywall) »
About the Authors:
Umesh Vazirani, Department of Computer Science, UC Berkeley, Berkeley, California, USA.
Thomas Vidick, Department of Computing and Mathematical Sciences, California Institute of Technology, Pasadena, California, USA.
